X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FMC%2FMCObjectDisassembler.cpp;h=85de4111b7f8abd9f8a8a55d5ea659bd8b6ff390;hb=11b8b431964b870e3021a8eca8bf1d870a58f474;hp=6b3ad836429b91d0db3bbddd034f6b37734441dd;hpb=0f4a5ba24e680f5193792822c9dd066bfccdfc2d;p=oota-llvm.git diff --git a/lib/MC/MCObjectDisassembler.cpp b/lib/MC/MCObjectDisassembler.cpp index 6b3ad836429..85de4111b7f 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,7 +27,6 @@ #include "llvm/Support/StringRefMemoryObject.h" #include "llvm/Support/raw_ostream.h" #include -#include using namespace llvm; using namespace object; @@ -38,11 +37,8 @@ MCObjectDisassembler::MCObjectDisassembler(const ObjectFile &Obj, : Obj(Obj), Dis(Dis), MIA(MIA), MOS(0) {} 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; + SI != SE; ++SI) { StringRef Name; SI->getName(Name); if (Name == "main" || Name == "_main") { @@ -62,6 +58,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,13 +87,8 @@ 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; - + for (section_iterator SI = Obj.begin_sections(), SE = Obj.end_sections(); + SI != SE; ++SI) { bool isText; SI->isText(isText); bool isData; SI->isData(isData); if (!isData && !isText) @@ -131,11 +127,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 { @@ -149,13 +147,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) {} @@ -166,26 +165,27 @@ 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; + SI != SE; ++SI) { SymbolRef::Type SymType; SI->getType(SymType); if (SymType == SymbolRef::ST_Function) { uint64_t SymAddr; SI->getAddress(SymAddr); SymAddr = getEffectiveLoadAddr(SymAddr); - Calls.insert(SymAddr); - Splits.insert(SymAddr); + Calls.push_back(SymAddr); + Splits.push_back(SymAddr); } } @@ -198,21 +198,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 +293,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( @@ -299,11 +495,8 @@ 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; + SI != SE; ++SI) { StringRef Name; SI->getName(Name); // FIXME: We should use the S_ section type instead of the name. @@ -332,10 +525,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;