X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FMC%2FMCObjectDisassembler.cpp;h=16a110f09bf8559154a1d9974614d502c8c1a6af;hb=6e08a410aa0a375450dfbdd3c1114aafc5fb1fb9;hp=1969bcb473513bf71572a435a7917186c8a82c13;hpb=0e83b902834530da4670ad8416cf44afba9b4111;p=oota-llvm.git diff --git a/lib/MC/MCObjectDisassembler.cpp b/lib/MC/MCObjectDisassembler.cpp index 1969bcb4735..16a110f09bf 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" @@ -18,6 +18,7 @@ #include "llvm/MC/MCFunction.h" #include "llvm/MC/MCInstrAnalysis.h" #include "llvm/MC/MCModule.h" +#include "llvm/MC/MCObjectSymbolizer.h" #include "llvm/Object/MachO.h" #include "llvm/Object/ObjectFile.h" #include "llvm/Support/Debug.h" @@ -26,7 +27,6 @@ #include "llvm/Support/StringRefMemoryObject.h" #include "llvm/Support/raw_ostream.h" #include -#include using namespace llvm; using namespace object; @@ -34,7 +34,7 @@ using namespace object; MCObjectDisassembler::MCObjectDisassembler(const ObjectFile &Obj, const MCDisassembler &Dis, const MCInstrAnalysis &MIA) - : Obj(Obj), Dis(Dis), MIA(MIA) {} + : Obj(Obj), Dis(Dis), MIA(MIA), MOS(0) {} uint64_t MCObjectDisassembler::getEntrypoint() { error_code ec; @@ -61,6 +61,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; } @@ -130,11 +135,13 @@ void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) { Text->addInst(Inst, InstSize); InvalidData = 0; } else { + assert(InstSize && "getInstruction() consumed no bytes"); if (!InvalidData) { Text = 0; - InvalidData = Module->createDataAtom(CurAddr, EndAddr); + 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 { @@ -148,13 +155,14 @@ 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) {} @@ -165,10 +173,14 @@ 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; @@ -183,8 +195,8 @@ void MCObjectDisassembler::buildCFG(MCModule *Module) { uint64_t SymAddr; SI->getAddress(SymAddr); SymAddr = getEffectiveLoadAddr(SymAddr); - Calls.insert(SymAddr); - Splits.insert(SymAddr); + Calls.push_back(SymAddr); + Splits.push_back(SymAddr); } } @@ -197,21 +209,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) { @@ -289,6 +304,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; + } + + // Finally, just create a new one. + MCFunction *MCFN = Module->createFunction(""); + getBBAt(Module, MCFN, BeginAddr, CallTargets, TailCallTargets); + return MCFN; +} + // MachO MCObjectDisassembler implementation. MCMachOObjectDisassembler::MCMachOObjectDisassembler( @@ -331,10 +539,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;