diff options
Diffstat (limited to 'lib/CodeGen')
| -rw-r--r-- | lib/CodeGen/AsmPrinter/DwarfDebug.cpp | 7 | ||||
| -rw-r--r-- | lib/CodeGen/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/CodeGen/ELF.h | 129 | ||||
| -rw-r--r-- | lib/CodeGen/ELFCodeEmitter.cpp | 33 | ||||
| -rw-r--r-- | lib/CodeGen/ELFWriter.cpp | 446 | ||||
| -rw-r--r-- | lib/CodeGen/ELFWriter.h | 61 | ||||
| -rw-r--r-- | lib/CodeGen/LLVMTargetMachine.cpp | 2 | ||||
| -rw-r--r-- | lib/CodeGen/LazyLiveness.cpp | 158 | ||||
| -rw-r--r-- | lib/CodeGen/RegisterScavenging.cpp | 17 |
9 files changed, 576 insertions, 278 deletions
diff --git a/lib/CodeGen/AsmPrinter/DwarfDebug.cpp b/lib/CodeGen/AsmPrinter/DwarfDebug.cpp index 5a66f4b..c773378 100644 --- a/lib/CodeGen/AsmPrinter/DwarfDebug.cpp +++ b/lib/CodeGen/AsmPrinter/DwarfDebug.cpp @@ -1581,6 +1581,7 @@ void DwarfDebug::EndFunction(MachineFunction *MF) { FunctionDbgScope = NULL; LexicalScopeStack.clear(); AbstractInstanceRootList.clear(); + AbstractInstanceRootMap.clear(); } Lines.clear(); @@ -1669,7 +1670,11 @@ unsigned DwarfDebug::RecordRegionEnd(GlobalVariable *V) { DbgScope *Scope = getOrCreateScope(V); unsigned ID = MMI->NextLabelID(); Scope->setEndLabelID(ID); - if (LexicalScopeStack.size() != 0) + // FIXME : region.end() may not be in the last basic block. + // For now, do not pop last lexical scope because next basic + // block may start new inlined function's body. + unsigned LSSize = LexicalScopeStack.size(); + if (LSSize != 0 && LSSize != 1) LexicalScopeStack.pop_back(); if (TimePassesIsEnabled) diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index ff917a7..5ba8b3c 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -12,6 +12,7 @@ add_llvm_library(LLVMCodeGen IntrinsicLowering.cpp LLVMTargetMachine.cpp LatencyPriorityQueue.cpp + LazyLiveness.cpp LiveInterval.cpp LiveIntervalAnalysis.cpp LiveStackAnalysis.cpp diff --git a/lib/CodeGen/ELF.h b/lib/CodeGen/ELF.h index c22f6ed..796bc2c 100644 --- a/lib/CodeGen/ELF.h +++ b/lib/CodeGen/ELF.h @@ -10,23 +10,24 @@ // This header contains common, non-processor-specific data structures and // constants for the ELF file format. // -// The details of the ELF32 bits in this file are largely based on -// the Tool Interface Standard (TIS) Executable and Linking Format -// (ELF) Specification Version 1.2, May 1995. The ELF64 stuff is not -// standardized, as far as I can tell. It was largely based on information -// I found in OpenBSD header files. +// The details of the ELF32 bits in this file are largely based on the Tool +// Interface Standard (TIS) Executable and Linking Format (ELF) Specification +// Version 1.2, May 1995. The ELF64 is based on HP/Intel definition of the +// ELF-64 object file format document, Version 1.5 Draft 2 May 27, 1998 // //===----------------------------------------------------------------------===// #ifndef CODEGEN_ELF_H #define CODEGEN_ELF_H +#include "llvm/GlobalVariable.h" +#include "llvm/CodeGen/BinaryObject.h" #include "llvm/CodeGen/MachineRelocation.h" #include "llvm/Support/DataTypes.h" #include <cstring> namespace llvm { - class GlobalVariable; + class BinaryObject; // Identification Indexes enum { @@ -47,71 +48,28 @@ namespace llvm { ET_HIPROC = 0xffff // Processor-specific }; - // Object file classes. - enum { - ELFCLASS32 = 1, // 32-bit object file - ELFCLASS64 = 2 // 64-bit object file - }; - - // Object file byte orderings. - enum { - ELFDATA2LSB = 1, // Little-endian object file - ELFDATA2MSB = 2 // Big-endian object file - }; - // Versioning enum { EV_NONE = 0, EV_CURRENT = 1 }; - struct ELFHeader { - // e_machine - This field is the target specific value to emit as the - // e_machine member of the ELF header. - unsigned short e_machine; - - // e_flags - The machine flags for the target. This defaults to zero. - unsigned e_flags; - - // e_size - Holds the ELF header's size in bytes - unsigned e_ehsize; - - // Endianess and ELF Class (64 or 32 bits) - unsigned ByteOrder; - unsigned ElfClass; - - unsigned getByteOrder() const { return ByteOrder; } - unsigned getElfClass() const { return ElfClass; } - unsigned getSize() const { return e_ehsize; } - unsigned getMachine() const { return e_machine; } - unsigned getFlags() const { return e_flags; } - - ELFHeader(unsigned short machine, unsigned flags, - bool is64Bit, bool isLittleEndian) - : e_machine(machine), e_flags(flags) { - ElfClass = is64Bit ? ELFCLASS64 : ELFCLASS32; - ByteOrder = isLittleEndian ? ELFDATA2LSB : ELFDATA2MSB; - e_ehsize = is64Bit ? 64 : 52; - } - }; - /// ELFSection - This struct contains information about each section that is /// emitted to the file. This is eventually turned into the section header /// table at the end of the file. - struct ELFSection { - + class ELFSection : public BinaryObject { + public: // ELF specific fields - std::string Name; // Name of the section. - unsigned NameIdx; // Index in .shstrtab of name, once emitted. - unsigned Type; - unsigned Flags; - uint64_t Addr; - unsigned Offset; - unsigned Size; - unsigned Link; - unsigned Info; - unsigned Align; - unsigned EntSize; + unsigned NameIdx; // sh_name - .shstrtab idx of name, once emitted. + unsigned Type; // sh_type - Section contents & semantics + unsigned Flags; // sh_flags - Section flags. + uint64_t Addr; // sh_addr - The mem addr this section is in. + unsigned Offset; // sh_offset - Offset from the file start + unsigned Size; // sh_size - The section size. + unsigned Link; // sh_link - Section header table index link. + unsigned Info; // sh_info - Auxillary information. + unsigned Align; // sh_addralign - Alignment of section. + unsigned EntSize; // sh_entsize - Size of entries in the section e // Section Header Flags enum { @@ -141,8 +99,8 @@ namespace llvm { SHT_REL = 9, // Relocation entries; no explicit addends. SHT_SHLIB = 10, // Reserved. SHT_DYNSYM = 11, // Symbol table. - SHT_LOPROC = 0x70000000, // Lowest processor architecture-specific type. - SHT_HIPROC = 0x7fffffff, // Highest processor architecture-specific type. + SHT_LOPROC = 0x70000000, // Lowest processor arch-specific type. + SHT_HIPROC = 0x7fffffff, // Highest processor arch-specific type. SHT_LOUSER = 0x80000000, // Lowest type reserved for applications. SHT_HIUSER = 0xffffffff // Highest type reserved for applications. }; @@ -161,22 +119,9 @@ namespace llvm { /// SectionIdx - The number of the section in the Section Table. unsigned short SectionIdx; - /// SectionData - The actual data for this section which we are building - /// up for emission to the file. - std::vector<unsigned char> SectionData; - - /// Relocations - The relocations that we have encountered so far in this - /// section that we will need to convert to Elf relocation entries when - /// the file is written. - std::vector<MachineRelocation> Relocations; - - /// Section Header Size - static unsigned getSectionHdrSize(bool is64Bit) - { return is64Bit ? 64 : 40; } - - ELFSection(const std::string &name) - : Name(name), Type(0), Flags(0), Addr(0), Offset(0), Size(0), - Link(0), Info(0), Align(0), EntSize(0) {} + ELFSection(const std::string &name, bool isLittleEndian, bool is64Bit) + : BinaryObject(name, isLittleEndian, is64Bit), Type(0), Flags(0), Addr(0), + Offset(0), Size(0), Link(0), Info(0), Align(0), EntSize(0) {} }; /// ELFSym - This struct contains information about each symbol that is @@ -207,9 +152,33 @@ namespace llvm { STT_FILE = 4 }; + enum { + STV_DEFAULT = 0, // Visibility is specified by binding type + STV_INTERNAL = 1, // Defined by processor supplements + STV_HIDDEN = 2, // Not visible to other components + STV_PROTECTED = 3 // Visible in other components but not preemptable + }; + ELFSym(const GlobalValue *gv) : GV(gv), NameIdx(0), Value(0), Size(0), Info(0), Other(0), - SectionIdx(ELFSection::SHN_UNDEF) {} + SectionIdx(ELFSection::SHN_UNDEF) { + if (!GV) + return; + + switch (GV->getVisibility()) { + default: + assert(0 && "unknown visibility type"); + case GlobalValue::DefaultVisibility: + Other = STV_DEFAULT; + break; + case GlobalValue::HiddenVisibility: + Other = STV_HIDDEN; + break; + case GlobalValue::ProtectedVisibility: + Other = STV_PROTECTED; + break; + } + } void SetBind(unsigned X) { assert(X == (X & 0xF) && "Bind value out of range!"); diff --git a/lib/CodeGen/ELFCodeEmitter.cpp b/lib/CodeGen/ELFCodeEmitter.cpp index c7bd873..ca68396 100644 --- a/lib/CodeGen/ELFCodeEmitter.cpp +++ b/lib/CodeGen/ELFCodeEmitter.cpp @@ -13,9 +13,9 @@ #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/Function.h" +#include "llvm/CodeGen/BinaryObject.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineJumpTableInfo.h" -#include "llvm/Target/TargetData.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Support/Debug.h" @@ -28,27 +28,22 @@ namespace llvm { /// startFunction - This callback is invoked when a new machine function is /// about to be emitted. void ELFCodeEmitter::startFunction(MachineFunction &MF) { - const TargetData *TD = TM.getTargetData(); - const Function *F = MF.getFunction(); - - // Align the output buffer to the appropriate alignment, power of 2. - unsigned FnAlign = F->getAlignment(); - unsigned TDAlign = TD->getPrefTypeAlignment(F->getType()); - unsigned Align = std::max(FnAlign, TDAlign); - assert(!(Align & (Align-1)) && "Alignment is not a power of two!"); - // Get the ELF Section that this function belongs in. ES = &EW.getTextSection(); - // FIXME: better memory management, this will be replaced by BinaryObjects - ES->SectionData.reserve(4096); - BufferBegin = &ES->SectionData[0]; - BufferEnd = BufferBegin + ES->SectionData.capacity(); + DOUT << "processing function: " << MF.getFunction()->getName() << "\n"; - // Upgrade the section alignment if required. + // FIXME: better memory management, this will be replaced by BinaryObjects + BinaryData &BD = ES->getData(); + BD.reserve(4096); + BufferBegin = &BD[0]; + BufferEnd = BufferBegin + BD.capacity(); + + // Align the output buffer with function alignment, and + // upgrade the section alignment if required + unsigned Align = + TM.getELFWriterInfo()->getFunctionAlignment(MF.getFunction()); if (ES->Align < Align) ES->Align = Align; - - // Round the size up to the correct alignment for starting the new function. ES->Size = (ES->Size + (Align-1)) & (-Align); // Snaity check on allocated space for text section @@ -107,7 +102,7 @@ bool ELFCodeEmitter::finishFunction(MachineFunction &MF) { FnSym.Value = FnStartPtr-BufferBegin; // Finally, add it to the symtab. - EW.SymbolTable.push_back(FnSym); + EW.SymbolList.push_back(FnSym); // Relocations // ----------- @@ -128,7 +123,7 @@ bool ELFCodeEmitter::finishFunction(MachineFunction &MF) { } else { assert(0 && "Unhandled relocation type"); } - ES->Relocations.push_back(MR); + ES->addRelocation(MR); } Relocations.clear(); diff --git a/lib/CodeGen/ELFWriter.cpp b/lib/CodeGen/ELFWriter.cpp index 3859ea3..aeccefb 100644 --- a/lib/CodeGen/ELFWriter.cpp +++ b/lib/CodeGen/ELFWriter.cpp @@ -26,9 +26,6 @@ // ... // #N. ".shstrtab" entry - String table for the section names. // -// NOTE: This code should eventually be extended to support 64-bit ELF (this -// won't be hard), but we haven't done so yet! -// //===----------------------------------------------------------------------===// #define DEBUG_TYPE "elfwriter" @@ -36,18 +33,18 @@ #include "ELFWriter.h" #include "ELFCodeEmitter.h" #include "ELF.h" +#include "llvm/Constants.h" #include "llvm/Module.h" #include "llvm/PassManager.h" #include "llvm/DerivedTypes.h" +#include "llvm/CodeGen/BinaryObject.h" #include "llvm/CodeGen/FileWriters.h" #include "llvm/CodeGen/MachineCodeEmitter.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Target/TargetData.h" -#include "llvm/Target/TargetELFWriterInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Support/Mangler.h" -#include "llvm/Support/OutputBuffer.h" #include "llvm/Support/Streams.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/Debug.h" @@ -70,21 +67,23 @@ MachineCodeEmitter *llvm::AddELFWriter(PassManagerBase &PM, //===----------------------------------------------------------------------===// ELFWriter::ELFWriter(raw_ostream &o, TargetMachine &tm) - : MachineFunctionPass(&ID), O(o), TM(tm), ElfHdr() { - is64Bit = TM.getTargetData()->getPointerSizeInBits() == 64; - isLittleEndian = TM.getTargetData()->isLittleEndian(); + : MachineFunctionPass(&ID), O(o), TM(tm), + is64Bit(TM.getTargetData()->getPointerSizeInBits() == 64), + isLittleEndian(TM.getTargetData()->isLittleEndian()), + ElfHdr(isLittleEndian, is64Bit) { - ElfHdr = new ELFHeader(TM.getELFWriterInfo()->getEMachine(), 0, - is64Bit, isLittleEndian); + TAI = TM.getTargetAsmInfo(); + TEW = TM.getELFWriterInfo(); // Create the machine code emitter object for this target. MCE = new ELFCodeEmitter(*this); + + // Inital number of sections NumSections = 0; } ELFWriter::~ELFWriter() { delete MCE; - delete ElfHdr; } // doInitialization - Emit the file header and all of the global variables for @@ -92,10 +91,6 @@ ELFWriter::~ELFWriter() { bool ELFWriter::doInitialization(Module &M) { Mang = new Mangler(M); - // Local alias to shortenify coming code. - std::vector<unsigned char> &FH = FileHeader; - OutputBuffer FHOut(FH, is64Bit, isLittleEndian); - // ELF Header // ---------- // Fields e_shnum e_shstrndx are only known after all section have @@ -104,54 +99,58 @@ bool ELFWriter::doInitialization(Module &M) { // // Note // ---- - // FHOut.outaddr method behaves differently for ELF32 and ELF64 writing + // emitWord method behaves differently for ELF32 and ELF64, writing // 4 bytes in the former and 8 in the last for *_off and *_addr elf types - FHOut.outbyte(0x7f); // e_ident[EI_MAG0] - FHOut.outbyte('E'); // e_ident[EI_MAG1] - FHOut.outbyte('L'); // e_ident[EI_MAG2] - FHOut.outbyte('F'); // e_ident[EI_MAG3] - - FHOut.outbyte(ElfHdr->getElfClass()); // e_ident[EI_CLASS] - FHOut.outbyte(ElfHdr->getByteOrder()); // e_ident[EI_DATA] - FHOut.outbyte(EV_CURRENT); // e_ident[EI_VERSION] - - FH.resize(16); // e_ident[EI_NIDENT-EI_PAD] - - FHOut.outhalf(ET_REL); // e_type - FHOut.outhalf(ElfHdr->getMachine()); // e_machine = target - FHOut.outword(EV_CURRENT); // e_version - FHOut.outaddr(0); // e_entry = 0, no entry point in .o file - FHOut.outaddr(0); // e_phoff = 0, no program header for .o - ELFHdr_e_shoff_Offset = FH.size(); - FHOut.outaddr(0); // e_shoff = sec hdr table off in bytes - FHOut.outword(ElfHdr->getFlags()); // e_flags = whatever the target wants - FHOut.outhalf(ElfHdr->getSize()); // e_ehsize = ELF header size - FHOut.outhalf(0); // e_phentsize = prog header entry size - FHOut.outhalf(0); // e_phnum = # prog header entries = 0 + ElfHdr.emitByte(0x7f); // e_ident[EI_MAG0] + ElfHdr.emitByte('E'); // e_ident[EI_MAG1] + ElfHdr.emitByte('L'); // e_ident[EI_MAG2] + ElfHdr.emitByte('F'); // e_ident[EI_MAG3] + + ElfHdr.emitByte(TEW->getEIClass()); // e_ident[EI_CLASS] + ElfHdr.emitByte(TEW->getEIData()); // e_ident[EI_DATA] + ElfHdr.emitByte(EV_CURRENT); // e_ident[EI_VERSION] + ElfHdr.emitAlignment(16); // e_ident[EI_NIDENT-EI_PAD] + + ElfHdr.emitWord16(ET_REL); // e_type + ElfHdr.emitWord16(TEW->getEMachine()); // e_machine = target + ElfHdr.emitWord32(EV_CURRENT); // e_version + ElfHdr.emitWord(0); // e_entry, no entry point in .o file + ElfHdr.emitWord(0); // e_phoff, no program header for .o + ELFHdr_e_shoff_Offset = ElfHdr.size(); + ElfHdr.emitWord(0); // e_shoff = sec hdr table off in bytes + ElfHdr.emitWord32(TEW->getEFlags()); // e_flags = whatever the target wants + ElfHdr.emitWord16(TEW->getHdrSize()); // e_ehsize = ELF header size + ElfHdr.emitWord16(0); // e_phentsize = prog header entry size + ElfHdr.emitWord16(0); // e_phnum = # prog header entries = 0 // e_shentsize = Section header entry size - FHOut.outhalf(ELFSection::getSectionHdrSize(is64Bit)); + ElfHdr.emitWord16(TEW->getSHdrSize()); // e_shnum = # of section header ents - ELFHdr_e_shnum_Offset = FH.size(); - FHOut.outhalf(0); + ELFHdr_e_shnum_Offset = ElfHdr.size(); + ElfHdr.emitWord16(0); // Placeholder // e_shstrndx = Section # of '.shstrtab' - ELFHdr_e_shstrndx_Offset = FH.size(); - FHOut.outhalf(0); + ELFHdr_e_shstrndx_Offset = ElfHdr.size(); + ElfHdr.emitWord16(0); // Placeholder // Add the null section, which is required to be first in the file. getSection("", ELFSection::SHT_NULL, 0); - // Start up the symbol table. The first entry in the symtab is the null + // Start up the symbol table. The first entry in the symtab is the null // entry. - SymbolTable.push_back(ELFSym(0)); + SymbolList.push_back(ELFSym(0)); return false; } void ELFWriter::EmitGlobal(GlobalVariable *GV) { + + // XXX: put local symbols *before* global ones! + const Section *S = TAI->SectionForGlobal(GV); + DOUT << "Section " << S->getName() << " for global " << GV->getName() << "\n"; + // If this is an external global, emit it now. TODO: Note that it would be // better to ignore the symbol here and only add it to the symbol table if // referenced. @@ -160,17 +159,17 @@ void ELFWriter::EmitGlobal(GlobalVariable *GV) { ExternalSym.SetBind(ELFSym::STB_GLOBAL); ExternalSym.SetType(ELFSym::STT_NOTYPE); ExternalSym.SectionIdx = ELFSection::SHN_UNDEF; - SymbolTable.push_back(ExternalSym); + SymbolList.push_back(ExternalSym); return; } - unsigned Align = TM.getTargetData()->getPreferredAlignment(GV); - unsigned Size = - TM.getTargetData()->getTypeAllocSize(GV->getType()->getElementType()); + const TargetData *TD = TM.getTargetData(); + unsigned Align = TD->getPreferredAlignment(GV); + Constant *CV = GV->getInitializer(); + unsigned Size = TD->getTypeAllocSize(CV->getType()); - // If this global has a zero initializer, it is part of the .bss or common - // section. - if (GV->getInitializer()->isNullValue()) { + // If this global has a zero initializer, go to .bss or common section. + if (CV->isNullValue() || isa<UndefValue>(CV)) { // If this global is part of the common block, add it now. Variables are // part of the common block if they are zero initialized and allowed to be // merged with other symbols. @@ -182,14 +181,14 @@ void ELFWriter::EmitGlobal(GlobalVariable *GV) { CommonSym.Size = Size; CommonSym.SetBind(ELFSym::STB_GLOBAL); CommonSym.SetType(ELFSym::STT_OBJECT); - // TODO SOMEDAY: add ELF visibility. CommonSym.SectionIdx = ELFSection::SHN_COMMON; - SymbolTable.push_back(CommonSym); + SymbolList.push_back(CommonSym); + getSection(S->getName(), ELFSection::SHT_NOBITS, + ELFSection::SHF_WRITE | ELFSection::SHF_ALLOC, 1); return; } // Otherwise, this symbol is part of the .bss section. Emit it now. - // Handle alignment. Ensure section is aligned at least as much as required // by this symbol. ELFSection &BSSSection = getBSSSection(); @@ -220,18 +219,128 @@ void ELFWriter::EmitGlobal(GlobalVariable *GV) { // Set the idx of the .bss section BSSSym.SectionIdx = BSSSection.SectionIdx; if (!GV->hasPrivateLinkage()) - SymbolTable.push_back(BSSSym); + SymbolList.push_back(BSSSym); // Reserve space in the .bss section for this symbol. BSSSection.Size += Size; return; } - // FIXME: handle .rodata - //assert(!GV->isConstant() && "unimp"); + /// Emit the Global symbol to the right ELF section + ELFSym GblSym(GV); + GblSym.Size = Size; + GblSym.SetType(ELFSym::STT_OBJECT); + GblSym.SetBind(ELFSym::STB_GLOBAL); + unsigned Flags = S->getFlags(); + unsigned SectType = ELFSection::SHT_PROGBITS; + unsigned SHdrFlags = ELFSection::SHF_ALLOC; + + if (Flags & SectionFlags::Code) + SHdrFlags |= ELFSection::SHF_EXECINSTR; + if (Flags & SectionFlags::Writeable) + SHdrFlags |= ELFSection::SHF_WRITE; + if (Flags & SectionFlags::Mergeable) + SHdrFlags |= ELFSection::SHF_MERGE; + if (Flags & SectionFlags::TLS) + SHdrFlags |= ELFSection::SHF_TLS; + if (Flags & SectionFlags::Strings) + SHdrFlags |= ELFSection::SHF_STRINGS; + + // Remove tab from section name prefix + std::string SectionName(S->getName()); + size_t Pos = SectionName.find("\t"); + if (Pos != std::string::npos) + SectionName.erase(Pos, 1); + + // The section alignment should be bound to the element with + // the largest alignment + ELFSection &ElfS = getSection(SectionName, SectType, SHdrFlags); + GblSym.SectionIdx = ElfS.SectionIdx; + if (Align > ElfS.Align) + ElfS.Align = Align; + + // S.Value should contain the symbol index inside the section, + // and all symbols should start on their required alignment boundary + GblSym.Value = (ElfS.size() + (Align-1)) & (-Align); + ElfS.emitAlignment(Align); + + // Emit the constant symbol to its section + EmitGlobalConstant(CV, ElfS); + SymbolList.push_back(GblSym); +} - // FIXME: handle .data - //assert(0 && "unimp"); +void ELFWriter::EmitGlobalConstantStruct(const ConstantStruct *CVS, + ELFSection &GblS) { + + // Print the fields in successive locations. Pad to align if needed! + const TargetData *TD = TM.getTargetData(); + unsigned Size = TD->getTypeAllocSize(CVS->getType()); + const StructLayout *cvsLayout = TD->getStructLayout(CVS->getType()); + uint64_t sizeSoFar = 0; + for (unsigned i = 0, e = CVS->getNumOperands(); i != e; ++i) { + const Constant* field = CVS->getOperand(i); + + // Check if padding is needed and insert one or more 0s. + uint64_t fieldSize = TD->getTypeAllocSize(field->getType()); + uint64_t padSize = ((i == e-1 ? Size : cvsLayout->getElementOffset(i+1)) + - cvsLayout->getElementOffset(i)) - fieldSize; + sizeSoFar += fieldSize + padSize; + + // Now print the actual field value. + EmitGlobalConstant(field, GblS); + + // Insert padding - this may include padding to increase the size of the + // current field up to the ABI size (if the struct is not packed) as well + // as padding to ensure that the next field starts at the right offset. + for (unsigned p=0; p < padSize; p++) + GblS.emitByte(0); + } + assert(sizeSoFar == cvsLayout->getSizeInBytes() && + "Layout of constant struct may be incorrect!"); +} + +void ELFWriter::EmitGlobalConstant(const Constant *CV, ELFSection &GblS) { + const TargetData *TD = TM.getTargetData(); + unsigned Size = TD->getTypeAllocSize(CV->getType()); + + if (const ConstantArray *CVA = dyn_cast<ConstantArray>(CV)) { + if (CVA->isString()) { + std::string GblStr = CVA->getAsString(); + GblS.emitString(GblStr); + } else { // Not a string. Print the values in successive locations + for (unsigned i = 0, e = CVA->getNumOperands(); i != e; ++i) + EmitGlobalConstant(CVA->getOperand(i), GblS); + } + return; + } else if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV)) { + EmitGlobalConstantStruct(CVS, GblS); + return; + } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(CV)) { + uint64_t Val = CFP->getValueAPF().bitcastToAPInt().getZExtValue(); + if (CFP->getType() == Type::DoubleTy) + GblS.emitWord64(Val); + else if (CFP->getType() == Type::FloatTy) + GblS.emitWord32(Val); + else if (CFP->getType() == Type::X86_FP80Ty) { + assert(0 && "X86_FP80Ty global emission not implemented"); + } else if (CFP->getType() == Type::PPC_FP128Ty) + assert(0 && "PPC_FP128Ty global emission not implemented"); + return; + } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) { + if (Size == 4) + GblS.emitWord32(CI->getZExtValue()); + else if (Size == 8) + GblS.emitWord64(CI->getZExtValue()); + else + assert(0 && "LargeInt global emission not implemented"); + return; + } else if (const ConstantVector *CP = dyn_cast<ConstantVector>(CV)) { + const VectorType *PTy = CP->getType(); + for (unsigned I = 0, E = PTy->getNumElements(); I < E; ++I) + EmitGlobalConstant(CP->getOperand(I), GblS); + return; + } + assert(0 && "unknown global constant"); } @@ -243,22 +352,41 @@ bool ELFWriter::runOnMachineFunction(MachineFunction &MF) { /// doFinalization - Now that the module has been completely processed, emit /// the ELF file to 'O'. bool ELFWriter::doFinalization(Module &M) { - // Okay, the ELF header and .text sections have been completed, build the - // .data, .bss, and "common" sections next. + /// FIXME: This should be removed when moving to ObjectCodeEmiter. Since the + /// current ELFCodeEmiter uses CurrBuff, ... it doesn't update S.Data + /// vector size for .text sections, so this is a quick dirty fix + ELFSection &TS = getTextSection(); + if (TS.Size) { + BinaryData &BD = TS.getData(); + for (unsigned e=0; e<TS.Size; ++e) + BD.push_back(BD[e]); + } + + // Emit .data section placeholder + getDataSection(); + + // Emit .bss section placeholder + getBSSSection(); + + // Build and emit data, bss and "common" sections. for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) EmitGlobal(I); + // Emit non-executable stack note + if (TAI->getNonexecutableStackDirective()) + getNonExecStackSection(); + // Emit the symbol table now, if non-empty. EmitSymbolTable(); // Emit the relocation sections. EmitRelocations(); - // Emit the string table for the sections in the ELF file. + // Emit the sections string table. EmitSectionTableStringTable(); - // Emit the sections to the .o file, and emit the section table for the file. + // Dump the sections and section table to the .o file. OutputSectionsAndSectionTable(); // We are done with the abstract symbols. @@ -274,78 +402,97 @@ bool ELFWriter::doFinalization(Module &M) { void ELFWriter::EmitRelocations() { } +/// EmitSymbol - Write symbol 'Sym' to the symbol table 'SymbolTable' +void ELFWriter::EmitSymbol(BinaryObject &SymbolTable, ELFSym &Sym) { + if (is64Bit) { + SymbolTable.emitWord32(Sym.NameIdx); + SymbolTable.emitByte(Sym.Info); + SymbolTable.emitByte(Sym.Other); + SymbolTable.emitWord16(Sym.SectionIdx); + SymbolTable.emitWord64(Sym.Value); + SymbolTable.emitWord64(Sym.Size); + } else { + SymbolTable.emitWord32(Sym.NameIdx); + SymbolTable.emitWord32(Sym.Value); + SymbolTable.emitWord32(Sym.Size); + SymbolTable.emitByte(Sym.Info); + SymbolTable.emitByte(Sym.Other); + SymbolTable.emitWord16(Sym.SectionIdx); + } +} + +/// EmitSectionHeader - Write section 'Section' header in 'SHdrTab' +/// Section Header Table +void ELFWriter::EmitSectionHeader(BinaryObject &SHdrTab, + const ELFSection &SHdr) { + SHdrTab.emitWord32(SHdr.NameIdx); + SHdrTab.emitWord32(SHdr.Type); + if (is64Bit) { + SHdrTab.emitWord64(SHdr.Flags); + SHdrTab.emitWord(SHdr.Addr); + SHdrTab.emitWord(SHdr.Offset); + SHdrTab.emitWord64(SHdr.Size); + SHdrTab.emitWord32(SHdr.Link); + SHdrTab.emitWord32(SHdr.Info); + SHdrTab.emitWord64(SHdr.Align); + SHdrTab.emitWord64(SHdr.EntSize); + } else { + SHdrTab.emitWord32(SHdr.Flags); + SHdrTab.emitWord(SHdr.Addr); + SHdrTab.emitWord(SHdr.Offset); + SHdrTab.emitWord32(SHdr.Size); + SHdrTab.emitWord32(SHdr.Link); + SHdrTab.emitWord32(SHdr.Info); + SHdrTab.emitWord32(SHdr.Align); + SHdrTab.emitWord32(SHdr.EntSize); + } +} + /// EmitSymbolTable - If the current symbol table is non-empty, emit the string /// table for it and then the symbol table itself. void ELFWriter::EmitSymbolTable() { - if (SymbolTable.size() == 1) return; // Only the null entry. + if (SymbolList.size() == 1) return; // Only the null entry. // FIXME: compact all local symbols to the start of the symtab. unsigned FirstNonLocalSymbol = 1; - ELFSection &StrTab = getSection(".strtab", ELFSection::SHT_STRTAB, 0); - StrTab.Align = 1; - - DataBuffer &StrTabBuf = StrTab.SectionData; - OutputBuffer StrTabOut(StrTabBuf, is64Bit, isLittleEndian); + ELFSection &StrTab = getStringTableSection(); // Set the zero'th symbol to a null byte, as required. - StrTabOut.outbyte(0); + StrTab.emitByte(0); + unsigned Index = 1; - for (unsigned i = 1, e = SymbolTable.size(); i != e; ++i) { + for (unsigned i = 1, e = SymbolList.size(); i != e; ++i) { // Use the name mangler to uniquify the LLVM symbol. - std::string Name = Mang->getValueName(SymbolTable[i].GV); + std::string Name = Mang->getValueName(SymbolList[i].GV); if (Name.empty()) { - SymbolTable[i].NameIdx = 0; + SymbolList[i].NameIdx = 0; } else { - SymbolTable[i].NameIdx = Index; - - // Add the name to the output buffer, including the null terminator. - StrTabBuf.insert(StrTabBuf.end(), Name.begin(), Name.end()); - - // Add a null terminator. - StrTabBuf.push_back(0); + SymbolList[i].NameIdx = Index; + StrTab.emitString(Name); // Keep track of the number of bytes emitted to this section. Index += Name.size()+1; } } - assert(Index == StrTabBuf.size()); + assert(Index == StrTab.size()); StrTab.Size = Index; // Now that we have emitted the string table and know the offset into the // string table of each symbol, emit the symbol table itself. - ELFSection &SymTab = getSection(".symtab", ELFSection::SHT_SYMTAB, 0); - SymTab.Align = is64Bit ? 8 : 4; - SymTab.Link = StrTab.SectionIdx; // Section Index of .strtab. - SymTab.Info = FirstNonLocalSymbol; // First non-STB_LOCAL symbol. - SymTab.EntSize = is64Bit ? 24 : 16; // Size of each symtab entry. - DataBuffer &SymTabBuf = SymTab.SectionData; - OutputBuffer SymTabOut(SymTabBuf, is64Bit, isLittleEndian); - - if (!is64Bit) { // 32-bit and 64-bit formats are shuffled a bit. - for (unsigned i = 0, e = SymbolTable.size(); i != e; ++i) { - ELFSym &Sym = SymbolTable[i]; - SymTabOut.outword(Sym.NameIdx); - SymTabOut.outaddr32(Sym.Value); - SymTabOut.outword(Sym.Size); - SymTabOut.outbyte(Sym.Info); - SymTabOut.outbyte(Sym.Other); - SymTabOut.outhalf(Sym.SectionIdx); - } - } else { - for (unsigned i = 0, e = SymbolTable.size(); i != e; ++i) { - ELFSym &Sym = SymbolTable[i]; - SymTabOut.outword(Sym.NameIdx); - SymTabOut.outbyte(Sym.Info); - SymTabOut.outbyte(Sym.Other); - SymTabOut.outhalf(Sym.SectionIdx); - SymTabOut.outaddr64(Sym.Value); - SymTabOut.outxword(Sym.Size); - } - } + ELFSection &SymTab = getSymbolTableSection(); + SymTab.Align = TEW->getSymTabAlignment(); + SymTab.Link = StrTab.SectionIdx; // Section Index of .strtab. + SymTab.Info = FirstNonLocalSymbol; // First non-STB_LOCAL symbol. + + // Size of each symtab entry. + SymTab.EntSize = TEW->getSymTabEntrySize(); + + for (unsigned i = 0, e = SymbolList.size(); i != e; ++i) + EmitSymbol(SymTab, SymbolList[i]); - SymTab.Size = SymTabBuf.size(); + SymTab.Size = SymTab.size(); } /// EmitSectionTableStringTable - This method adds and emits a section for the @@ -357,32 +504,25 @@ void ELFWriter::EmitSectionTableStringTable() { // Now that we know which section number is the .shstrtab section, update the // e_shstrndx entry in the ELF header. - OutputBuffer FHOut(FileHeader, is64Bit, isLittleEndian); - FHOut.fixhalf(SHStrTab.SectionIdx, ELFHdr_e_shstrndx_Offset); + ElfHdr.fixWord16(SHStrTab.SectionIdx, ELFHdr_e_shstrndx_Offset); // Set the NameIdx of each section in the string table and emit the bytes for // the string table. unsigned Index = 0; - DataBuffer &Buf = SHStrTab.SectionData; for (std::list<ELFSection>::iterator I = SectionList.begin(), E = SectionList.end(); I != E; ++I) { // Set the index into the table. Note if we have lots of entries with // common suffixes, we could memoize them here if we cared. I->NameIdx = Index; - - // Add the name to the output buffer, including the null terminator. - Buf.insert(Buf.end(), I->Name.begin(), I->Name.end()); - - // Add a null terminator. - Buf.push_back(0); + SHStrTab.emitString(I->getName()); // Keep track of the number of bytes emitted to this section. - Index += I->Name.size()+1; + Index += I->getName().size()+1; } // Set the size of .shstrtab now that we know what it is. - assert(Index == Buf.size()); + assert(Index == SHStrTab.size()); SHStrTab.Size = Index; } @@ -391,9 +531,9 @@ void ELFWriter::EmitSectionTableStringTable() { /// SectionTable. void ELFWriter::OutputSectionsAndSectionTable() { // Pass #1: Compute the file offset for each section. - size_t FileOff = FileHeader.size(); // File header first. + size_t FileOff = ElfHdr.size(); // File header first. - // Emit all of the section data in order. + // Adjust alignment of all section if needed. for (std::list<ELFSection>::iterator I = SectionList.begin(), E = SectionList.end(); I != E; ++I) { @@ -401,9 +541,14 @@ void ELFWriter::OutputSectionsAndSectionTable() { if (!I->SectionIdx) continue; + if (!I->size()) { + I->Offset = FileOff; + continue; + } + // Update Section size if (!I->Size) - I->Size = I->SectionData.size(); + I->Size = I->size(); // Align FileOff to whatever the alignment restrictions of the section are. if (I->Align) @@ -419,49 +564,40 @@ void ELFWriter::OutputSectionsAndSectionTable() { // Now that we know where all of the sections will be emitted, set the e_shnum // entry in the ELF header. - OutputBuffer FHOut(FileHeader, is64Bit, isLittleEndian); - FHOut.fixhalf(NumSections, ELFHdr_e_shnum_Offset); + ElfHdr.fixWord16(NumSections, ELFHdr_e_shnum_Offset); // Now that we know the offset in the file of the section table, update the // e_shoff address in the ELF header. - FHOut.fixaddr(FileOff, ELFHdr_e_shoff_Offset); + ElfHdr.fixWord(FileOff, ELFHdr_e_shoff_Offset); // Now that we know all of the data in the file header, emit it and all of the // sections! - O.write((char*)&FileHeader[0], FileHeader.size()); - FileOff = FileHeader.size(); - DataBuffer().swap(FileHeader); + O.write((char *)&ElfHdr.getData()[0], ElfHdr.size()); + FileOff = ElfHdr.size(); - DataBuffer Table; - OutputBuffer TableOut(Table, is64Bit, isLittleEndian); + // Section Header Table blob + BinaryObject SHdrTable(isLittleEndian, is64Bit); - // Emit all of the section data and build the section table itself. + // Emit all of sections to the file and build the section header table. while (!SectionList.empty()) { - const ELFSection &S = *SectionList.begin(); + ELFSection &S = *SectionList.begin(); + DOUT << "SectionIdx: " << S.SectionIdx << ", Name: " << S.getName() + << ", Size: " << S.Size << ", Offset: " << S.Offset + << ", SectionData Size: " << S.size() << "\n"; // Align FileOff to whatever the alignment restrictions of the section are. - if (S.Align) + if (S.Align) { for (size_t NewFileOff = (FileOff+S.Align-1) & ~(S.Align-1); - FileOff != NewFileOff; ++FileOff) + FileOff != NewFileOff; ++FileOff) O << (char)0xAB; - O.write((char*)&S.SectionData[0], S.Size); - - DOUT << "SectionIdx: " << S.SectionIdx << ", Name: " << S.Name - << ", Size: " << S.Size << ", Offset: " << S.Offset << "\n"; - - FileOff += S.Size; + } - TableOut.outword(S.NameIdx); // sh_name - Symbol table name idx - TableOut.outword(S.Type); // sh_type - Section contents & semantics - TableOut.outaddr(S.Flags); // sh_flags - Section flags. - TableOut.outaddr(S.Addr); // sh_addr - The mem addr this section is in. - TableOut.outaddr(S.Offset); // sh_offset - Offset from the file start. - TableOut.outaddr(S.Size); // sh_size - The section size. - TableOut.outword(S.Link); // sh_link - Section header table index link. - TableOut.outword(S.Info); // sh_info - Auxillary information. - TableOut.outaddr(S.Align); // sh_addralign - Alignment of section. - TableOut.outaddr(S.EntSize); // sh_entsize - Size of entries in the section + if (S.size()) { + O.write((char *)&S.getData()[0], S.Size); + FileOff += S.Size; + } + EmitSectionHeader(SHdrTable, S); SectionList.pop_front(); } @@ -471,5 +607,5 @@ void ELFWriter::OutputSectionsAndSectionTable() { O << (char)0xAB; // Emit the section table itself. - O.write((char*)&Table[0], Table.size()); + O.write((char *)&SHdrTable.getData()[0], SHdrTable.size()); } diff --git a/lib/CodeGen/ELFWriter.h b/lib/CodeGen/ELFWriter.h index 14a44f0..8a380f0 100644 --- a/lib/CodeGen/ELFWriter.h +++ b/lib/CodeGen/ELFWriter.h @@ -16,15 +16,20 @@ #include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Support/OutputBuffer.h" +#include "llvm/Target/TargetAsmInfo.h" +#include "llvm/Target/TargetELFWriterInfo.h" #include "ELF.h" #include <list> #include <map> namespace llvm { + class BinaryObject; + class ConstantStruct; + class ELFCodeEmitter; class GlobalVariable; class Mangler; class MachineCodeEmitter; - class ELFCodeEmitter; class raw_ostream; /// ELFWriter - This class implements the common target-independent code for @@ -52,6 +57,9 @@ namespace llvm { /// Target machine description. TargetMachine &TM; + /// Target Elf Writer description. + const TargetELFWriterInfo *TEW; + /// Mang - The object used to perform name mangling for this module. Mangler *Mang; @@ -59,6 +67,10 @@ namespace llvm { /// code for functions to the .o file. ELFCodeEmitter *MCE; + /// TAI - Target Asm Info, provide information about section names for + /// globals and other target specific stuff. + const TargetAsmInfo *TAI; + //===------------------------------------------------------------------===// // Properties inferred automatically from the target machine. //===------------------------------------------------------------------===// @@ -77,13 +89,8 @@ namespace llvm { bool doFinalization(Module &M); private: - // The buffer we accumulate the file header into. Note that this should be - // changed into something much more efficient later (and the bitcode writer - // as well!). - DataBuffer FileHeader; - - /// ElfHdr - Hold information about the ELF Header - ELFHeader *ElfHdr; + // Blob containing the Elf header + BinaryObject ElfHdr; /// SectionList - This is the list of sections that we have emitted to the /// file. Once the file has been completely built, the section header table @@ -97,17 +104,18 @@ namespace llvm { /// getSection - Return the section with the specified name, creating a new /// section if one does not already exist. - ELFSection &getSection(const std::string &Name, - unsigned Type, unsigned Flags = 0) { + ELFSection &getSection(const std::string &Name, unsigned Type, + unsigned Flags = 0, unsigned Align = 0) { ELFSection *&SN = SectionLookup[Name]; if (SN) return *SN; - SectionList.push_back(Name); + SectionList.push_back(ELFSection(Name, isLittleEndian, is64Bit)); SN = &SectionList.back(); SN->SectionIdx = NumSections++; SN->Type = Type; SN->Flags = Flags; SN->Link = ELFSection::SHN_UNDEF; + SN->Align = Align; return *SN; } @@ -116,23 +124,36 @@ namespace llvm { ELFSection::SHF_EXECINSTR | ELFSection::SHF_ALLOC); } + ELFSection &getNonExecStackSection() { + return getSection(".note.GNU-stack", ELFSection::SHT_PROGBITS, 0, 1); + } + + ELFSection &getSymbolTableSection() { + return getSection(".symtab", ELFSection::SHT_SYMTAB, 0); + } + + ELFSection &getStringTableSection() { + return getSection(".strtab", ELFSection::SHT_STRTAB, 0, 1); + } + ELFSection &getDataSection() { return getSection(".data", ELFSection::SHT_PROGBITS, ELFSection::SHF_WRITE | ELFSection::SHF_ALLOC); } + ELFSection &getBSSSection() { return getSection(".bss", ELFSection::SHT_NOBITS, ELFSection::SHF_WRITE | ELFSection::SHF_ALLOC); } - /// SymbolTable - This is the list of symbols we have emitted to the file. + /// SymbolList - This is the list of symbols we have emitted to the file. /// This actually gets rearranged before emission to the file (to put the /// local symbols first in the list). - std::vector<ELFSym> SymbolTable; + std::vector<ELFSym> SymbolList; - /// PendingSyms - This is a list of externally defined symbols that we have - /// been asked to emit, but have not seen a reference to. When a reference - /// is seen, the symbol will move from this list to the SymbolTable. + /// PendingGlobals - List of externally defined symbols that we have been + /// asked to emit, but have not seen a reference to. When a reference + /// is seen, the symbol will move from this list to the SymbolList. SetVector<GlobalValue*> PendingGlobals; // As we complete the ELF file, we need to update fields in the ELF header @@ -142,11 +163,17 @@ namespace llvm { unsigned ELFHdr_e_shoff_Offset; // e_shoff in ELF header. unsigned ELFHdr_e_shstrndx_Offset; // e_shstrndx in ELF header. unsigned ELFHdr_e_shnum_Offset; // e_shnum in ELF header. + private: void EmitGlobal(GlobalVariable *GV); - void EmitSymbolTable(); + void EmitGlobalConstant(const Constant *C, ELFSection &GblS); + void EmitGlobalConstantStruct(const ConstantStruct *CVS, + ELFSection &GblS); void EmitRelocations(); + void EmitSectionHeader(BinaryObject &SHdrTab, const ELFSection &SHdr); void EmitSectionTableStringTable(); + void EmitSymbol(BinaryObject &SymbolTable, ELFSym &Sym); + void EmitSymbolTable(); void OutputSectionsAndSectionTable(); }; } diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp index b3c60e6..a163cac 100644 --- a/lib/CodeGen/LLVMTargetMachine.cpp +++ b/lib/CodeGen/LLVMTargetMachine.cpp @@ -240,7 +240,7 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, if (OptLevel != CodeGenOpt::None) { PM.add(createMachineLICMPass()); PM.add(createMachineSinkingPass()); - printAndVerify(PM, /* allowDoubleDefs= */ true); + printAndVerify(PM, /* allowDoubleDefs= */ false); } // Run pre-ra passes. diff --git a/lib/CodeGen/LazyLiveness.cpp b/lib/CodeGen/LazyLiveness.cpp new file mode 100644 index 0000000..6fb35d2 --- /dev/null +++ b/lib/CodeGen/LazyLiveness.cpp @@ -0,0 +1,158 @@ +//===- LazyLiveness.cpp - Lazy, CFG-invariant liveness information --------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass implements a lazy liveness analysis as per "Fast Liveness Checking +// for SSA-form Programs," by Boissinot, et al. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "lazyliveness" +#include "llvm/CodeGen/LazyLiveness.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" +using namespace llvm; + +char LazyLiveness::ID = 0; +static RegisterPass<LazyLiveness> X("lazy-liveness", "Lazy Liveness Analysis"); + +void LazyLiveness::computeBackedgeChain(MachineFunction& mf, + MachineBasicBlock* MBB) { + SparseBitVector<128> tmp = rv[MBB]; + tmp.set(preorder[MBB]); + tmp &= backedge_source; + calculated.set(preorder[MBB]); + + for (SparseBitVector<128>::iterator I = tmp.begin(); I != tmp.end(); ++I) { + MachineBasicBlock* SrcMBB = rev_preorder[*I]; + + for (MachineBasicBlock::succ_iterator SI = SrcMBB->succ_begin(); + SI != SrcMBB->succ_end(); ++SI) { + MachineBasicBlock* TgtMBB = *SI; + + if (backedges.count(std::make_pair(SrcMBB, TgtMBB)) && + !rv[MBB].test(preorder[TgtMBB])) { + if (!calculated.test(preorder[TgtMBB])) + computeBackedgeChain(mf, TgtMBB); + + tv[MBB].set(preorder[TgtMBB]); + tv[MBB] |= tv[TgtMBB]; + } + } + + tv[MBB].reset(preorder[MBB]); + } +} + +bool LazyLiveness::runOnMachineFunction(MachineFunction &mf) { + rv.clear(); + tv.clear(); + backedges.clear(); + backedge_source.clear(); + backedge_target.clear(); + calculated.clear(); + preorder.clear(); + + MRI = &mf.getRegInfo(); + MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); + + // Step 0: Compute preorder numbering for all MBBs. + unsigned num = 0; + for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT.getRootNode()), + DE = df_end(MDT.getRootNode()); DI != DE; ++DI) { + preorder[(*DI)->getBlock()] = num++; + rev_preorder.push_back((*DI)->getBlock()); + } + + // Step 1: Compute the transitive closure of the CFG, ignoring backedges. + for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), + POE = po_end(&*mf.begin()); POI != POE; ++POI) { + MachineBasicBlock* MBB = *POI; + SparseBitVector<128>& entry = rv[MBB]; + entry.set(preorder[MBB]); + + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) { + DenseMap<MachineBasicBlock*, SparseBitVector<128> >::iterator SII = + rv.find(*SI); + + // Because we're iterating in postorder, any successor that does not yet + // have an rv entry must be on a backedge. + if (SII != rv.end()) { + entry |= SII->second; + } else { + backedges.insert(std::make_pair(MBB, *SI)); + backedge_source.set(preorder[MBB]); + backedge_target.set(preorder[*SI]); + } + } + } + + for (SparseBitVector<128>::iterator I = backedge_source.begin(); + I != backedge_source.end(); ++I) + computeBackedgeChain(mf, rev_preorder[*I]); + + for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), + POE = po_end(&*mf.begin()); POI != POE; ++POI) + if (!backedge_target.test(preorder[*POI])) + for (MachineBasicBlock::succ_iterator SI = (*POI)->succ_begin(), + SE = (*POI)->succ_end(); SI != SE; ++SI) + if (!backedges.count(std::make_pair(*POI, *SI)) && tv.count(*SI)) { + SparseBitVector<128>& PBV = tv[*POI]; + PBV = tv[*SI]; + } + + for (po_iterator<MachineBasicBlock*> POI = po_begin(&*mf.begin()), + POE = po_end(&*mf.begin()); POI != POE; ++POI) + tv[*POI].set(preorder[*POI]); + + return false; +} + +bool LazyLiveness::vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB) { + MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); + + MachineBasicBlock* DefMBB = MRI->def_begin(vreg)->getParent(); + unsigned def = preorder[DefMBB]; + unsigned max_dom = 0; + for (df_iterator<MachineDomTreeNode*> DI = df_begin(MDT[DefMBB]), + DE = df_end(MDT[DefMBB]); DI != DE; ++DI) { + if (preorder[DI->getBlock()] > max_dom) { + max_dom = preorder[(*DI)->getBlock()]; + } + } + + if (preorder[MBB] <= def || max_dom < preorder[MBB]) + return false; + + SparseBitVector<128>::iterator I = tv[MBB].begin(); + while (I != tv[MBB].end() && *I <= def) ++I; + while (I != tv[MBB].end() && *I < max_dom) { + for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(vreg), + UE = MachineRegisterInfo::use_end(); UI != UE; ++UI) { + MachineBasicBlock* UseMBB = UI->getParent(); + if (rv[rev_preorder[*I]].test(preorder[UseMBB])) + return true; + + unsigned t_dom = 0; + for (df_iterator<MachineDomTreeNode*> DI = + df_begin(MDT[rev_preorder[*I]]), DE = df_end(MDT[rev_preorder[*I]]); + DI != DE; ++DI) + if (preorder[DI->getBlock()] > t_dom) { + max_dom = preorder[(*DI)->getBlock()]; + } + I = tv[MBB].begin(); + while (I != tv[MBB].end() && *I < t_dom) ++I; + } + } + + return false; +} diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp index 944468e..3feb92f 100644 --- a/lib/CodeGen/RegisterScavenging.cpp +++ b/lib/CodeGen/RegisterScavenging.cpp @@ -214,26 +214,33 @@ void RegScavenger::forward() { } // Process uses first. - BitVector UseRegs(NumPhysRegs); + BitVector KillRegs(NumPhysRegs); for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { const MachineOperand MO = *UseMOs[i].first; unsigned Reg = MO.getReg(); assert(isUsed(Reg) && "Using an undefined register!"); - if (MO.isKill() && !isReserved(Reg)) { - UseRegs.set(Reg); + // Kill of implicit_def defined registers are ignored. e.g. + // entry: 0x2029ab8, LLVM BB @0x1b06080, ID#0: + // Live Ins: %R0 + // %R0<def> = IMPLICIT_DEF + // %R0<def> = IMPLICIT_DEF + // STR %R0<kill>, %R0, %reg0, 0, 14, %reg0, Mem:ST(4,4) [0x1b06510 + 0] + // %R1<def> = LDR %R0, %reg0, 24, 14, %reg0, Mem:LD(4,4) [0x1b065bc + 0] + if (MO.isKill() && !isReserved(Reg) && !isImplicitlyDefined(Reg)) { + KillRegs.set(Reg); // Mark sub-registers as used. for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) - UseRegs.set(SubReg); + KillRegs.set(SubReg); } } // Change states of all registers after all the uses are processed to guard // against multiple uses. - setUnused(UseRegs); + setUnused(KillRegs); // Process early clobber defs then process defs. We can have a early clobber // that is dead, it should not conflict with a def that happens one "slot" |
