1 //===- lib/MC/MCObjectDisassembler.cpp ------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/MC/MCObjectDisassembler.h"
11 #include "llvm/ADT/SetVector.h"
12 #include "llvm/ADT/SmallPtrSet.h"
13 #include "llvm/ADT/StringExtras.h"
14 #include "llvm/ADT/StringRef.h"
15 #include "llvm/ADT/Twine.h"
16 #include "llvm/MC/MCAtom.h"
17 #include "llvm/MC/MCDisassembler.h"
18 #include "llvm/MC/MCFunction.h"
19 #include "llvm/MC/MCInstrAnalysis.h"
20 #include "llvm/MC/MCModule.h"
21 #include "llvm/MC/MCObjectSymbolizer.h"
22 #include "llvm/Object/MachO.h"
23 #include "llvm/Object/ObjectFile.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/MachO.h"
26 #include "llvm/Support/MemoryObject.h"
27 #include "llvm/Support/StringRefMemoryObject.h"
28 #include "llvm/Support/raw_ostream.h"
32 using namespace object;
34 MCObjectDisassembler::MCObjectDisassembler(const ObjectFile &Obj,
35 const MCDisassembler &Dis,
36 const MCInstrAnalysis &MIA)
37 : Obj(Obj), Dis(Dis), MIA(MIA), MOS(0) {}
39 uint64_t MCObjectDisassembler::getEntrypoint() {
40 for (symbol_iterator SI = Obj.symbol_begin(), SE = Obj.symbol_end();
44 if (Name == "main" || Name == "_main") {
46 SI->getAddress(Entrypoint);
47 return getEffectiveLoadAddr(Entrypoint);
53 ArrayRef<uint64_t> MCObjectDisassembler::getStaticInitFunctions() {
54 return ArrayRef<uint64_t>();
57 ArrayRef<uint64_t> MCObjectDisassembler::getStaticExitFunctions() {
58 return ArrayRef<uint64_t>();
61 MemoryObject *MCObjectDisassembler::getRegionFor(uint64_t Addr) {
62 // FIXME: Keep track of object sections.
63 return FallbackRegion.get();
66 uint64_t MCObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) {
70 uint64_t MCObjectDisassembler::getOriginalLoadAddr(uint64_t Addr) {
74 MCModule *MCObjectDisassembler::buildEmptyModule() {
75 MCModule *Module = new MCModule;
76 Module->Entrypoint = getEntrypoint();
80 MCModule *MCObjectDisassembler::buildModule(bool withCFG) {
81 MCModule *Module = buildEmptyModule();
83 buildSectionAtoms(Module);
89 void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) {
90 for (section_iterator SI = Obj.section_begin(), SE = Obj.section_end();
92 bool isText; SI->isText(isText);
93 bool isData; SI->isData(isData);
94 if (!isData && !isText)
97 uint64_t StartAddr; SI->getAddress(StartAddr);
98 uint64_t SecSize; SI->getSize(SecSize);
99 if (StartAddr == UnknownAddressOrSize || SecSize == UnknownAddressOrSize)
101 StartAddr = getEffectiveLoadAddr(StartAddr);
103 StringRef Contents; SI->getContents(Contents);
104 StringRefMemoryObject memoryObject(Contents, StartAddr);
106 // We don't care about things like non-file-backed sections yet.
107 if (Contents.size() != SecSize || !SecSize)
109 uint64_t EndAddr = StartAddr + SecSize - 1;
111 StringRef SecName; SI->getName(SecName);
114 MCTextAtom *Text = 0;
115 MCDataAtom *InvalidData = 0;
118 for (uint64_t Index = 0; Index < SecSize; Index += InstSize) {
119 const uint64_t CurAddr = StartAddr + Index;
121 if (Dis.getInstruction(Inst, InstSize, memoryObject, CurAddr, nulls(),
124 Text = Module->createTextAtom(CurAddr, CurAddr);
125 Text->setName(SecName);
127 Text->addInst(Inst, InstSize);
130 assert(InstSize && "getInstruction() consumed no bytes");
133 InvalidData = Module->createDataAtom(CurAddr, CurAddr+InstSize - 1);
135 for (uint64_t I = 0; I < InstSize; ++I)
136 InvalidData->addData(Contents[Index+I]);
140 MCDataAtom *Data = Module->createDataAtom(StartAddr, EndAddr);
141 Data->setName(SecName);
142 for (uint64_t Index = 0; Index < SecSize; ++Index)
143 Data->addData(Contents[Index]);
150 typedef SmallPtrSet<BBInfo*, 2> BBInfoSetTy;
157 MCObjectDisassembler::AddressSetTy SuccAddrs;
159 BBInfo() : Atom(0), BB(0) {}
161 void addSucc(BBInfo &Succ) {
163 Succ.Preds.insert(this);
168 static void RemoveDupsFromAddressVector(MCObjectDisassembler::AddressSetTy &V) {
169 std::sort(V.begin(), V.end());
170 V.erase(std::unique(V.begin(), V.end()), V.end());
173 void MCObjectDisassembler::buildCFG(MCModule *Module) {
174 typedef std::map<uint64_t, BBInfo> BBInfoByAddrTy;
175 BBInfoByAddrTy BBInfos;
179 for (symbol_iterator SI = Obj.symbol_begin(), SE = Obj.symbol_end();
181 SymbolRef::Type SymType;
182 SI->getType(SymType);
183 if (SymType == SymbolRef::ST_Function) {
185 SI->getAddress(SymAddr);
186 SymAddr = getEffectiveLoadAddr(SymAddr);
187 Calls.push_back(SymAddr);
188 Splits.push_back(SymAddr);
192 assert(Module->func_begin() == Module->func_end()
193 && "Module already has a CFG!");
195 // First, determine the basic block boundaries and call targets.
196 for (MCModule::atom_iterator AI = Module->atom_begin(),
197 AE = Module->atom_end();
199 MCTextAtom *TA = dyn_cast<MCTextAtom>(*AI);
201 Calls.push_back(TA->getBeginAddr());
202 BBInfos[TA->getBeginAddr()].Atom = TA;
203 for (MCTextAtom::const_iterator II = TA->begin(), IE = TA->end();
205 if (MIA.isTerminator(II->Inst))
206 Splits.push_back(II->Address + II->Size);
208 if (MIA.evaluateBranch(II->Inst, II->Address, II->Size, Target)) {
209 if (MIA.isCall(II->Inst))
210 Calls.push_back(Target);
211 Splits.push_back(Target);
216 RemoveDupsFromAddressVector(Splits);
217 RemoveDupsFromAddressVector(Calls);
219 // Split text atoms into basic block atoms.
220 for (AddressSetTy::const_iterator SI = Splits.begin(), SE = Splits.end();
222 MCAtom *A = Module->findAtomContaining(*SI);
224 MCTextAtom *TA = cast<MCTextAtom>(A);
225 if (TA->getBeginAddr() == *SI)
227 MCTextAtom *NewAtom = TA->split(*SI);
228 BBInfos[NewAtom->getBeginAddr()].Atom = NewAtom;
229 StringRef BBName = TA->getName();
230 BBName = BBName.substr(0, BBName.find_last_of(':'));
231 NewAtom->setName((BBName + ":" + utohexstr(*SI)).str());
234 // Compute succs/preds.
235 for (MCModule::atom_iterator AI = Module->atom_begin(),
236 AE = Module->atom_end();
238 MCTextAtom *TA = dyn_cast<MCTextAtom>(*AI);
240 BBInfo &CurBB = BBInfos[TA->getBeginAddr()];
241 const MCDecodedInst &LI = TA->back();
242 if (MIA.isBranch(LI.Inst)) {
244 if (MIA.evaluateBranch(LI.Inst, LI.Address, LI.Size, Target))
245 CurBB.addSucc(BBInfos[Target]);
246 if (MIA.isConditionalBranch(LI.Inst))
247 CurBB.addSucc(BBInfos[LI.Address + LI.Size]);
248 } else if (!MIA.isTerminator(LI.Inst))
249 CurBB.addSucc(BBInfos[LI.Address + LI.Size]);
253 // Create functions and basic blocks.
254 for (AddressSetTy::const_iterator CI = Calls.begin(), CE = Calls.end();
256 BBInfo &BBI = BBInfos[*CI];
257 if (!BBI.Atom) continue;
259 MCFunction &MCFN = *Module->createFunction(BBI.Atom->getName());
262 SmallSetVector<BBInfo*, 16> Worklist;
263 Worklist.insert(&BBI);
264 for (size_t wi = 0; wi < Worklist.size(); ++wi) {
265 BBInfo *BBI = Worklist[wi];
268 BBI->BB = &MCFN.createBlock(*BBI->Atom);
269 // Add all predecessors and successors to the worklist.
270 for (BBInfoSetTy::iterator SI = BBI->Succs.begin(), SE = BBI->Succs.end();
272 Worklist.insert(*SI);
273 for (BBInfoSetTy::iterator PI = BBI->Preds.begin(), PE = BBI->Preds.end();
275 Worklist.insert(*PI);
279 for (size_t wi = 0; wi < Worklist.size(); ++wi) {
280 BBInfo *BBI = Worklist[wi];
281 MCBasicBlock *MCBB = BBI->BB;
284 for (BBInfoSetTy::iterator SI = BBI->Succs.begin(), SE = BBI->Succs.end();
287 MCBB->addSuccessor((*SI)->BB);
288 for (BBInfoSetTy::iterator PI = BBI->Preds.begin(), PE = BBI->Preds.end();
291 MCBB->addPredecessor((*PI)->BB);
296 // Basic idea of the disassembly + discovery:
298 // start with the wanted address, insert it in the worklist
299 // while worklist not empty, take next address in the worklist:
300 // - check if atom exists there
301 // - if middle of atom:
302 // - split basic blocks referencing the atom
303 // - look for an already encountered BBInfo (using a map<atom, bbinfo>)
304 // - if there is, split it (new one, fallthrough, move succs, etc..)
305 // - if start of atom: nothing else to do
306 // - if no atom: create new atom and new bbinfo
307 // - look at the last instruction in the atom, add succs to worklist
308 // for all elements in the worklist:
309 // - create basic block, update preds/succs, etc..
311 MCBasicBlock *MCObjectDisassembler::getBBAt(MCModule *Module, MCFunction *MCFN,
312 uint64_t BBBeginAddr,
313 AddressSetTy &CallTargets,
314 AddressSetTy &TailCallTargets) {
315 typedef std::map<uint64_t, BBInfo> BBInfoByAddrTy;
316 typedef SmallSetVector<uint64_t, 16> AddrWorklistTy;
317 BBInfoByAddrTy BBInfos;
318 AddrWorklistTy Worklist;
320 Worklist.insert(BBBeginAddr);
321 for (size_t wi = 0; wi < Worklist.size(); ++wi) {
322 const uint64_t BeginAddr = Worklist[wi];
323 BBInfo *BBI = &BBInfos[BeginAddr];
325 MCTextAtom *&TA = BBI->Atom;
326 assert(!TA && "Discovered basic block already has an associated atom!");
328 // Look for an atom at BeginAddr.
329 if (MCAtom *A = Module->findAtomContaining(BeginAddr)) {
330 // FIXME: We don't care about mixed atoms, see above.
331 TA = cast<MCTextAtom>(A);
333 // The found atom doesn't begin at BeginAddr, we have to split it.
334 if (TA->getBeginAddr() != BeginAddr) {
335 // FIXME: Handle overlapping atoms: middle-starting instructions, etc..
336 MCTextAtom *NewTA = TA->split(BeginAddr);
338 // Look for an already encountered basic block that needs splitting
339 BBInfoByAddrTy::iterator It = BBInfos.find(TA->getBeginAddr());
340 if (It != BBInfos.end() && It->second.Atom) {
341 BBI->SuccAddrs = It->second.SuccAddrs;
342 It->second.SuccAddrs.clear();
343 It->second.SuccAddrs.push_back(BeginAddr);
349 // If we didn't find an atom, then we have to disassemble to create one!
351 MemoryObject *Region = getRegionFor(BeginAddr);
353 llvm_unreachable(("Couldn't find suitable region for disassembly at " +
354 utostr(BeginAddr)).c_str());
357 uint64_t EndAddr = Region->getBase() + Region->getExtent();
359 // We want to stop before the next atom and have a fallthrough to it.
360 if (MCTextAtom *NextAtom =
361 cast_or_null<MCTextAtom>(Module->findFirstAtomAfter(BeginAddr)))
362 EndAddr = std::min(EndAddr, NextAtom->getBeginAddr());
364 for (uint64_t Addr = BeginAddr; Addr < EndAddr; Addr += InstSize) {
366 if (Dis.getInstruction(Inst, InstSize, *Region, Addr, nulls(),
369 TA = Module->createTextAtom(Addr, Addr);
370 TA->addInst(Inst, InstSize);
372 // We don't care about splitting mixed atoms either.
373 llvm_unreachable("Couldn't disassemble instruction in atom.");
376 uint64_t BranchTarget;
377 if (MIA.evaluateBranch(Inst, Addr, InstSize, BranchTarget)) {
378 if (MIA.isCall(Inst))
379 CallTargets.push_back(BranchTarget);
382 if (MIA.isTerminator(Inst))
388 assert(TA && "Couldn't disassemble atom, none was created!");
389 assert(TA->begin() != TA->end() && "Empty atom!");
391 MemoryObject *Region = getRegionFor(TA->getBeginAddr());
392 assert(Region && "Couldn't find region for already disassembled code!");
393 uint64_t EndRegion = Region->getBase() + Region->getExtent();
395 // Now we have a basic block atom, add successors.
396 // Add the fallthrough block.
397 if ((MIA.isConditionalBranch(TA->back().Inst) ||
398 !MIA.isTerminator(TA->back().Inst)) &&
399 (TA->getEndAddr() + 1 < EndRegion)) {
400 BBI->SuccAddrs.push_back(TA->getEndAddr() + 1);
401 Worklist.insert(TA->getEndAddr() + 1);
404 // If the terminator is a branch, add the target block.
405 if (MIA.isBranch(TA->back().Inst)) {
406 uint64_t BranchTarget;
407 if (MIA.evaluateBranch(TA->back().Inst, TA->back().Address,
408 TA->back().Size, BranchTarget)) {
412 MOS->findExternalFunctionAt(getOriginalLoadAddr(BranchTarget));
413 if (!ExtFnName.empty()) {
414 TailCallTargets.push_back(BranchTarget);
415 CallTargets.push_back(BranchTarget);
417 BBI->SuccAddrs.push_back(BranchTarget);
418 Worklist.insert(BranchTarget);
424 for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) {
425 const uint64_t BeginAddr = Worklist[wi];
426 BBInfo *BBI = &BBInfos[BeginAddr];
428 assert(BBI->Atom && "Found a basic block without an associated atom!");
430 // Look for a basic block at BeginAddr.
431 BBI->BB = MCFN->find(BeginAddr);
433 // FIXME: check that the succs/preds are the same
436 // If there was none, we have to create one from the atom.
437 BBI->BB = &MCFN->createBlock(*BBI->Atom);
440 for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) {
441 const uint64_t BeginAddr = Worklist[wi];
442 BBInfo *BBI = &BBInfos[BeginAddr];
443 MCBasicBlock *BB = BBI->BB;
445 RemoveDupsFromAddressVector(BBI->SuccAddrs);
446 for (AddressSetTy::const_iterator SI = BBI->SuccAddrs.begin(),
447 SE = BBI->SuccAddrs.end();
449 MCBasicBlock *Succ = BBInfos[*SI].BB;
450 BB->addSuccessor(Succ);
451 Succ->addPredecessor(BB);
455 assert(BBInfos[Worklist[0]].BB &&
456 "No basic block created at requested address?");
458 return BBInfos[Worklist[0]].BB;
462 MCObjectDisassembler::createFunction(MCModule *Module, uint64_t BeginAddr,
463 AddressSetTy &CallTargets,
464 AddressSetTy &TailCallTargets) {
465 // First, check if this is an external function.
468 ExtFnName = MOS->findExternalFunctionAt(getOriginalLoadAddr(BeginAddr));
469 if (!ExtFnName.empty())
470 return Module->createFunction(ExtFnName);
472 // If it's not, look for an existing function.
473 for (MCModule::func_iterator FI = Module->func_begin(),
474 FE = Module->func_end();
478 // FIXME: MCModule should provide a findFunctionByAddr()
479 if ((*FI)->getEntryBlock()->getInsts()->getBeginAddr() == BeginAddr)
483 // Finally, just create a new one.
484 MCFunction *MCFN = Module->createFunction("");
485 getBBAt(Module, MCFN, BeginAddr, CallTargets, TailCallTargets);
489 // MachO MCObjectDisassembler implementation.
491 MCMachOObjectDisassembler::MCMachOObjectDisassembler(
492 const MachOObjectFile &MOOF, const MCDisassembler &Dis,
493 const MCInstrAnalysis &MIA, uint64_t VMAddrSlide,
494 uint64_t HeaderLoadAddress)
495 : MCObjectDisassembler(MOOF, Dis, MIA), MOOF(MOOF),
496 VMAddrSlide(VMAddrSlide), HeaderLoadAddress(HeaderLoadAddress) {
498 for (section_iterator SI = MOOF.section_begin(), SE = MOOF.section_end();
502 // FIXME: We should use the S_ section type instead of the name.
503 if (Name == "__mod_init_func") {
504 DEBUG(dbgs() << "Found __mod_init_func section!\n");
505 SI->getContents(ModInitContents);
506 } else if (Name == "__mod_exit_func") {
507 DEBUG(dbgs() << "Found __mod_exit_func section!\n");
508 SI->getContents(ModExitContents);
513 // FIXME: Only do the translations for addresses actually inside the object.
514 uint64_t MCMachOObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) {
515 return Addr + VMAddrSlide;
519 MCMachOObjectDisassembler::getOriginalLoadAddr(uint64_t EffectiveAddr) {
520 return EffectiveAddr - VMAddrSlide;
523 uint64_t MCMachOObjectDisassembler::getEntrypoint() {
524 uint64_t EntryFileOffset = 0;
528 uint32_t LoadCommandCount = MOOF.getHeader().ncmds;
529 MachOObjectFile::LoadCommandInfo Load = MOOF.getFirstLoadCommandInfo();
530 for (unsigned I = 0;; ++I) {
531 if (Load.C.cmd == MachO::LC_MAIN) {
533 ((const MachO::entry_point_command *)Load.Ptr)->entryoff;
537 if (I == LoadCommandCount - 1)
540 Load = MOOF.getNextLoadCommandInfo(Load);
544 // If we didn't find anything, default to the common implementation.
545 // FIXME: Maybe we could also look at LC_UNIXTHREAD and friends?
547 return MCObjectDisassembler::getEntrypoint();
549 return EntryFileOffset + HeaderLoadAddress;
552 ArrayRef<uint64_t> MCMachOObjectDisassembler::getStaticInitFunctions() {
553 // FIXME: We only handle 64bit mach-o
554 assert(MOOF.is64Bit());
556 size_t EntrySize = 8;
557 size_t EntryCount = ModInitContents.size() / EntrySize;
558 return ArrayRef<uint64_t>(
559 reinterpret_cast<const uint64_t *>(ModInitContents.data()), EntryCount);
562 ArrayRef<uint64_t> MCMachOObjectDisassembler::getStaticExitFunctions() {
563 // FIXME: We only handle 64bit mach-o
564 assert(MOOF.is64Bit());
566 size_t EntrySize = 8;
567 size_t EntryCount = ModExitContents.size() / EntrySize;
568 return ArrayRef<uint64_t>(
569 reinterpret_cast<const uint64_t *>(ModExitContents.data()), EntryCount);