X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FMC%2FMCObjectDisassembler.cpp;h=8a258cb0909720a91a67333912cdedfe5d335361;hb=7fc69597b78d96a42fb96f406b1f96232fe848dc;hp=6b3ad836429b91d0db3bbddd034f6b37734441dd;hpb=0f4a5ba24e680f5193792822c9dd066bfccdfc2d;p=oota-llvm.git diff --git a/lib/MC/MCObjectDisassembler.cpp b/lib/MC/MCObjectDisassembler.cpp index 6b3ad836429..8a258cb0909 100644 --- a/lib/MC/MCObjectDisassembler.cpp +++ b/lib/MC/MCObjectDisassembler.cpp @@ -8,8 +8,8 @@ //===----------------------------------------------------------------------===// #include "llvm/MC/MCObjectDisassembler.h" -#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Twine.h" @@ -27,27 +27,24 @@ #include "llvm/Support/StringRefMemoryObject.h" #include "llvm/Support/raw_ostream.h" #include -#include using namespace llvm; using namespace object; +#define DEBUG_TYPE "mc" + MCObjectDisassembler::MCObjectDisassembler(const ObjectFile &Obj, const MCDisassembler &Dis, const MCInstrAnalysis &MIA) - : Obj(Obj), Dis(Dis), MIA(MIA), MOS(0) {} + : Obj(Obj), Dis(Dis), MIA(MIA), MOS(nullptr) {} uint64_t MCObjectDisassembler::getEntrypoint() { - error_code ec; - for (symbol_iterator SI = Obj.begin_symbols(), SE = Obj.end_symbols(); - SI != SE; SI.increment(ec)) { - if (ec) - break; + for (const SymbolRef &Symbol : Obj.symbols()) { StringRef Name; - SI->getName(Name); + Symbol.getName(Name); if (Name == "main" || Name == "_main") { uint64_t Entrypoint; - SI->getAddress(Entrypoint); + Symbol.getAddress(Entrypoint); return getEffectiveLoadAddr(Entrypoint); } } @@ -62,6 +59,11 @@ ArrayRef MCObjectDisassembler::getStaticExitFunctions() { return ArrayRef(); } +MemoryObject *MCObjectDisassembler::getRegionFor(uint64_t Addr) { + // FIXME: Keep track of object sections. + return FallbackRegion.get(); +} + uint64_t MCObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) { return Addr; } @@ -86,25 +88,24 @@ MCModule *MCObjectDisassembler::buildModule(bool withCFG) { } void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) { - error_code ec; - for (section_iterator SI = Obj.begin_sections(), - SE = Obj.end_sections(); - SI != SE; - SI.increment(ec)) { - if (ec) break; - - bool isText; SI->isText(isText); - bool isData; SI->isData(isData); + for (const SectionRef &Section : Obj.sections()) { + bool isText; + Section.isText(isText); + bool isData; + Section.isData(isData); if (!isData && !isText) continue; - uint64_t StartAddr; SI->getAddress(StartAddr); - uint64_t SecSize; SI->getSize(SecSize); + uint64_t StartAddr; + Section.getAddress(StartAddr); + uint64_t SecSize; + Section.getSize(SecSize); if (StartAddr == UnknownAddressOrSize || SecSize == UnknownAddressOrSize) continue; StartAddr = getEffectiveLoadAddr(StartAddr); - StringRef Contents; SI->getContents(Contents); + StringRef Contents; + Section.getContents(Contents); StringRefMemoryObject memoryObject(Contents, StartAddr); // We don't care about things like non-file-backed sections yet. @@ -112,11 +113,12 @@ void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) { continue; uint64_t EndAddr = StartAddr + SecSize - 1; - StringRef SecName; SI->getName(SecName); + StringRef SecName; + Section.getName(SecName); if (isText) { - MCTextAtom *Text = 0; - MCDataAtom *InvalidData = 0; + MCTextAtom *Text = nullptr; + MCDataAtom *InvalidData = nullptr; uint64_t InstSize; for (uint64_t Index = 0; Index < SecSize; Index += InstSize) { @@ -129,13 +131,15 @@ void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) { Text->setName(SecName); } Text->addInst(Inst, InstSize); - InvalidData = 0; + InvalidData = nullptr; } else { + assert(InstSize && "getInstruction() consumed no bytes"); if (!InvalidData) { - Text = 0; - InvalidData = Module->createDataAtom(CurAddr, EndAddr); + Text = nullptr; + InvalidData = Module->createDataAtom(CurAddr, CurAddr+InstSize - 1); } - InvalidData->addData(Contents[Index]); + for (uint64_t I = 0; I < InstSize; ++I) + InvalidData->addData(Contents[Index+I]); } } } else { @@ -149,15 +153,16 @@ void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) { namespace { struct BBInfo; - typedef std::set BBInfoSetTy; + typedef SmallPtrSet BBInfoSetTy; struct BBInfo { MCTextAtom *Atom; MCBasicBlock *BB; BBInfoSetTy Succs; BBInfoSetTy Preds; + MCObjectDisassembler::AddressSetTy SuccAddrs; - BBInfo() : Atom(0), BB(0) {} + BBInfo() : Atom(nullptr), BB(nullptr) {} void addSucc(BBInfo &Succ) { Succs.insert(&Succ); @@ -166,26 +171,26 @@ namespace { }; } +static void RemoveDupsFromAddressVector(MCObjectDisassembler::AddressSetTy &V) { + std::sort(V.begin(), V.end()); + V.erase(std::unique(V.begin(), V.end()), V.end()); +} + void MCObjectDisassembler::buildCFG(MCModule *Module) { typedef std::map BBInfoByAddrTy; BBInfoByAddrTy BBInfos; - typedef std::set AddressSetTy; AddressSetTy Splits; AddressSetTy Calls; - error_code ec; - for (symbol_iterator SI = Obj.begin_symbols(), SE = Obj.end_symbols(); - SI != SE; SI.increment(ec)) { - if (ec) - break; + for (const SymbolRef &Symbol : Obj.symbols()) { SymbolRef::Type SymType; - SI->getType(SymType); + Symbol.getType(SymType); if (SymType == SymbolRef::ST_Function) { uint64_t SymAddr; - SI->getAddress(SymAddr); + Symbol.getAddress(SymAddr); SymAddr = getEffectiveLoadAddr(SymAddr); - Calls.insert(SymAddr); - Splits.insert(SymAddr); + Calls.push_back(SymAddr); + Splits.push_back(SymAddr); } } @@ -198,21 +203,24 @@ void MCObjectDisassembler::buildCFG(MCModule *Module) { AI != AE; ++AI) { MCTextAtom *TA = dyn_cast(*AI); if (!TA) continue; - Calls.insert(TA->getBeginAddr()); + Calls.push_back(TA->getBeginAddr()); BBInfos[TA->getBeginAddr()].Atom = TA; for (MCTextAtom::const_iterator II = TA->begin(), IE = TA->end(); II != IE; ++II) { if (MIA.isTerminator(II->Inst)) - Splits.insert(II->Address + II->Size); + Splits.push_back(II->Address + II->Size); uint64_t Target; if (MIA.evaluateBranch(II->Inst, II->Address, II->Size, Target)) { if (MIA.isCall(II->Inst)) - Calls.insert(Target); - Splits.insert(Target); + Calls.push_back(Target); + Splits.push_back(Target); } } } + RemoveDupsFromAddressVector(Splits); + RemoveDupsFromAddressVector(Calls); + // Split text atoms into basic block atoms. for (AddressSetTy::const_iterator SI = Splits.begin(), SE = Splits.end(); SI != SE; ++SI) { @@ -290,6 +298,199 @@ void MCObjectDisassembler::buildCFG(MCModule *Module) { } } +// Basic idea of the disassembly + discovery: +// +// start with the wanted address, insert it in the worklist +// while worklist not empty, take next address in the worklist: +// - check if atom exists there +// - if middle of atom: +// - split basic blocks referencing the atom +// - look for an already encountered BBInfo (using a map) +// - if there is, split it (new one, fallthrough, move succs, etc..) +// - if start of atom: nothing else to do +// - if no atom: create new atom and new bbinfo +// - look at the last instruction in the atom, add succs to worklist +// for all elements in the worklist: +// - create basic block, update preds/succs, etc.. +// +MCBasicBlock *MCObjectDisassembler::getBBAt(MCModule *Module, MCFunction *MCFN, + uint64_t BBBeginAddr, + AddressSetTy &CallTargets, + AddressSetTy &TailCallTargets) { + typedef std::map BBInfoByAddrTy; + typedef SmallSetVector AddrWorklistTy; + BBInfoByAddrTy BBInfos; + AddrWorklistTy Worklist; + + Worklist.insert(BBBeginAddr); + for (size_t wi = 0; wi < Worklist.size(); ++wi) { + const uint64_t BeginAddr = Worklist[wi]; + BBInfo *BBI = &BBInfos[BeginAddr]; + + MCTextAtom *&TA = BBI->Atom; + assert(!TA && "Discovered basic block already has an associated atom!"); + + // Look for an atom at BeginAddr. + if (MCAtom *A = Module->findAtomContaining(BeginAddr)) { + // FIXME: We don't care about mixed atoms, see above. + TA = cast(A); + + // The found atom doesn't begin at BeginAddr, we have to split it. + if (TA->getBeginAddr() != BeginAddr) { + // FIXME: Handle overlapping atoms: middle-starting instructions, etc.. + MCTextAtom *NewTA = TA->split(BeginAddr); + + // Look for an already encountered basic block that needs splitting + BBInfoByAddrTy::iterator It = BBInfos.find(TA->getBeginAddr()); + if (It != BBInfos.end() && It->second.Atom) { + BBI->SuccAddrs = It->second.SuccAddrs; + It->second.SuccAddrs.clear(); + It->second.SuccAddrs.push_back(BeginAddr); + } + TA = NewTA; + } + BBI->Atom = TA; + } else { + // If we didn't find an atom, then we have to disassemble to create one! + + MemoryObject *Region = getRegionFor(BeginAddr); + if (!Region) + llvm_unreachable(("Couldn't find suitable region for disassembly at " + + utostr(BeginAddr)).c_str()); + + uint64_t InstSize; + uint64_t EndAddr = Region->getBase() + Region->getExtent(); + + // We want to stop before the next atom and have a fallthrough to it. + if (MCTextAtom *NextAtom = + cast_or_null(Module->findFirstAtomAfter(BeginAddr))) + EndAddr = std::min(EndAddr, NextAtom->getBeginAddr()); + + for (uint64_t Addr = BeginAddr; Addr < EndAddr; Addr += InstSize) { + MCInst Inst; + if (Dis.getInstruction(Inst, InstSize, *Region, Addr, nulls(), + nulls())) { + if (!TA) + TA = Module->createTextAtom(Addr, Addr); + TA->addInst(Inst, InstSize); + } else { + // We don't care about splitting mixed atoms either. + llvm_unreachable("Couldn't disassemble instruction in atom."); + } + + uint64_t BranchTarget; + if (MIA.evaluateBranch(Inst, Addr, InstSize, BranchTarget)) { + if (MIA.isCall(Inst)) + CallTargets.push_back(BranchTarget); + } + + if (MIA.isTerminator(Inst)) + break; + } + BBI->Atom = TA; + } + + assert(TA && "Couldn't disassemble atom, none was created!"); + assert(TA->begin() != TA->end() && "Empty atom!"); + + MemoryObject *Region = getRegionFor(TA->getBeginAddr()); + assert(Region && "Couldn't find region for already disassembled code!"); + uint64_t EndRegion = Region->getBase() + Region->getExtent(); + + // Now we have a basic block atom, add successors. + // Add the fallthrough block. + if ((MIA.isConditionalBranch(TA->back().Inst) || + !MIA.isTerminator(TA->back().Inst)) && + (TA->getEndAddr() + 1 < EndRegion)) { + BBI->SuccAddrs.push_back(TA->getEndAddr() + 1); + Worklist.insert(TA->getEndAddr() + 1); + } + + // If the terminator is a branch, add the target block. + if (MIA.isBranch(TA->back().Inst)) { + uint64_t BranchTarget; + if (MIA.evaluateBranch(TA->back().Inst, TA->back().Address, + TA->back().Size, BranchTarget)) { + StringRef ExtFnName; + if (MOS) + ExtFnName = + MOS->findExternalFunctionAt(getOriginalLoadAddr(BranchTarget)); + if (!ExtFnName.empty()) { + TailCallTargets.push_back(BranchTarget); + CallTargets.push_back(BranchTarget); + } else { + BBI->SuccAddrs.push_back(BranchTarget); + Worklist.insert(BranchTarget); + } + } + } + } + + for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) { + const uint64_t BeginAddr = Worklist[wi]; + BBInfo *BBI = &BBInfos[BeginAddr]; + + assert(BBI->Atom && "Found a basic block without an associated atom!"); + + // Look for a basic block at BeginAddr. + BBI->BB = MCFN->find(BeginAddr); + if (BBI->BB) { + // FIXME: check that the succs/preds are the same + continue; + } + // If there was none, we have to create one from the atom. + BBI->BB = &MCFN->createBlock(*BBI->Atom); + } + + for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) { + const uint64_t BeginAddr = Worklist[wi]; + BBInfo *BBI = &BBInfos[BeginAddr]; + MCBasicBlock *BB = BBI->BB; + + RemoveDupsFromAddressVector(BBI->SuccAddrs); + for (AddressSetTy::const_iterator SI = BBI->SuccAddrs.begin(), + SE = BBI->SuccAddrs.end(); + SE != SE; ++SI) { + MCBasicBlock *Succ = BBInfos[*SI].BB; + BB->addSuccessor(Succ); + Succ->addPredecessor(BB); + } + } + + assert(BBInfos[Worklist[0]].BB && + "No basic block created at requested address?"); + + return BBInfos[Worklist[0]].BB; +} + +MCFunction * +MCObjectDisassembler::createFunction(MCModule *Module, uint64_t BeginAddr, + AddressSetTy &CallTargets, + AddressSetTy &TailCallTargets) { + // First, check if this is an external function. + StringRef ExtFnName; + if (MOS) + ExtFnName = MOS->findExternalFunctionAt(getOriginalLoadAddr(BeginAddr)); + if (!ExtFnName.empty()) + return Module->createFunction(ExtFnName); + + // If it's not, look for an existing function. + for (MCModule::func_iterator FI = Module->func_begin(), + FE = Module->func_end(); + FI != FE; ++FI) { + if ((*FI)->empty()) + continue; + // FIXME: MCModule should provide a findFunctionByAddr() + if ((*FI)->getEntryBlock()->getInsts()->getBeginAddr() == BeginAddr) + return FI->get(); + } + + // Finally, just create a new one. + MCFunction *MCFN = Module->createFunction(""); + getBBAt(Module, MCFN, BeginAddr, CallTargets, TailCallTargets); + return MCFN; +} + // MachO MCObjectDisassembler implementation. MCMachOObjectDisassembler::MCMachOObjectDisassembler( @@ -299,20 +500,16 @@ MCMachOObjectDisassembler::MCMachOObjectDisassembler( : MCObjectDisassembler(MOOF, Dis, MIA), MOOF(MOOF), VMAddrSlide(VMAddrSlide), HeaderLoadAddress(HeaderLoadAddress) { - error_code ec; - for (section_iterator SI = MOOF.begin_sections(), SE = MOOF.end_sections(); - SI != SE; SI.increment(ec)) { - if (ec) - break; + for (const SectionRef &Section : MOOF.sections()) { StringRef Name; - SI->getName(Name); + Section.getName(Name); // FIXME: We should use the S_ section type instead of the name. if (Name == "__mod_init_func") { DEBUG(dbgs() << "Found __mod_init_func section!\n"); - SI->getContents(ModInitContents); + Section.getContents(ModInitContents); } else if (Name == "__mod_exit_func") { DEBUG(dbgs() << "Found __mod_exit_func section!\n"); - SI->getContents(ModExitContents); + Section.getContents(ModExitContents); } } } @@ -332,10 +529,10 @@ uint64_t MCMachOObjectDisassembler::getEntrypoint() { // Look for LC_MAIN. { - uint32_t LoadCommandCount = MOOF.getHeader().NumLoadCommands; + uint32_t LoadCommandCount = MOOF.getHeader().ncmds; MachOObjectFile::LoadCommandInfo Load = MOOF.getFirstLoadCommandInfo(); for (unsigned I = 0;; ++I) { - if (Load.C.Type == MachO::LoadCommandMain) { + if (Load.C.cmd == MachO::LC_MAIN) { EntryFileOffset = ((const MachO::entry_point_command *)Load.Ptr)->entryoff; break;