4d1c29638dd9aa7f7ad289c37602b069a2f2111d
[oota-llvm.git] / lib / MC / MCObjectDisassembler.cpp
1 //===- lib/MC/MCObjectDisassembler.cpp ------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
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"
29 #include <map>
30
31 using namespace llvm;
32 using namespace object;
33
34 MCObjectDisassembler::MCObjectDisassembler(const ObjectFile &Obj,
35                                            const MCDisassembler &Dis,
36                                            const MCInstrAnalysis &MIA)
37     : Obj(Obj), Dis(Dis), MIA(MIA), MOS(0) {}
38
39 uint64_t MCObjectDisassembler::getEntrypoint() {
40   error_code ec;
41   for (symbol_iterator SI = Obj.begin_symbols(), SE = Obj.end_symbols();
42        SI != SE; SI.increment(ec)) {
43     if (ec)
44       break;
45     StringRef Name;
46     SI->getName(Name);
47     if (Name == "main" || Name == "_main") {
48       uint64_t Entrypoint;
49       SI->getAddress(Entrypoint);
50       return getEffectiveLoadAddr(Entrypoint);
51     }
52   }
53   return 0;
54 }
55
56 ArrayRef<uint64_t> MCObjectDisassembler::getStaticInitFunctions() {
57   return ArrayRef<uint64_t>();
58 }
59
60 ArrayRef<uint64_t> MCObjectDisassembler::getStaticExitFunctions() {
61   return ArrayRef<uint64_t>();
62 }
63
64 MemoryObject *MCObjectDisassembler::getRegionFor(uint64_t Addr) {
65   // FIXME: Keep track of object sections.
66   return FallbackRegion.get();
67 }
68
69 uint64_t MCObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) {
70   return Addr;
71 }
72
73 uint64_t MCObjectDisassembler::getOriginalLoadAddr(uint64_t Addr) {
74   return Addr;
75 }
76
77 MCModule *MCObjectDisassembler::buildEmptyModule() {
78   MCModule *Module = new MCModule;
79   Module->Entrypoint = getEntrypoint();
80   return Module;
81 }
82
83 MCModule *MCObjectDisassembler::buildModule(bool withCFG) {
84   MCModule *Module = buildEmptyModule();
85
86   buildSectionAtoms(Module);
87   if (withCFG)
88     buildCFG(Module);
89   return Module;
90 }
91
92 void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) {
93   error_code ec;
94   for (section_iterator SI = Obj.begin_sections(),
95                         SE = Obj.end_sections();
96                         SI != SE;
97                         SI.increment(ec)) {
98     if (ec) break;
99
100     bool isText; SI->isText(isText);
101     bool isData; SI->isData(isData);
102     if (!isData && !isText)
103       continue;
104
105     uint64_t StartAddr; SI->getAddress(StartAddr);
106     uint64_t SecSize; SI->getSize(SecSize);
107     if (StartAddr == UnknownAddressOrSize || SecSize == UnknownAddressOrSize)
108       continue;
109     StartAddr = getEffectiveLoadAddr(StartAddr);
110
111     StringRef Contents; SI->getContents(Contents);
112     StringRefMemoryObject memoryObject(Contents, StartAddr);
113
114     // We don't care about things like non-file-backed sections yet.
115     if (Contents.size() != SecSize || !SecSize)
116       continue;
117     uint64_t EndAddr = StartAddr + SecSize - 1;
118
119     StringRef SecName; SI->getName(SecName);
120
121     if (isText) {
122       MCTextAtom *Text = 0;
123       MCDataAtom *InvalidData = 0;
124
125       uint64_t InstSize;
126       for (uint64_t Index = 0; Index < SecSize; Index += InstSize) {
127         const uint64_t CurAddr = StartAddr + Index;
128         MCInst Inst;
129         if (Dis.getInstruction(Inst, InstSize, memoryObject, CurAddr, nulls(),
130                                nulls())) {
131           if (!Text) {
132             Text = Module->createTextAtom(CurAddr, CurAddr);
133             Text->setName(SecName);
134           }
135           Text->addInst(Inst, InstSize);
136           InvalidData = 0;
137         } else {
138           if (!InvalidData) {
139             Text = 0;
140             InvalidData = Module->createDataAtom(CurAddr, EndAddr);
141           }
142           InvalidData->addData(Contents[Index]);
143         }
144       }
145     } else {
146       MCDataAtom *Data = Module->createDataAtom(StartAddr, EndAddr);
147       Data->setName(SecName);
148       for (uint64_t Index = 0; Index < SecSize; ++Index)
149         Data->addData(Contents[Index]);
150     }
151   }
152 }
153
154 namespace {
155   struct BBInfo;
156   typedef SmallPtrSet<BBInfo*, 2> BBInfoSetTy;
157
158   struct BBInfo {
159     MCTextAtom *Atom;
160     MCBasicBlock *BB;
161     BBInfoSetTy Succs;
162     BBInfoSetTy Preds;
163     MCObjectDisassembler::AddressSetTy SuccAddrs;
164
165     BBInfo() : Atom(0), BB(0) {}
166
167     void addSucc(BBInfo &Succ) {
168       Succs.insert(&Succ);
169       Succ.Preds.insert(this);
170     }
171   };
172 }
173
174 static void RemoveDupsFromAddressVector(MCObjectDisassembler::AddressSetTy &V) {
175   std::sort(V.begin(), V.end());
176   V.erase(std::unique(V.begin(), V.end()), V.end());
177 }
178
179 void MCObjectDisassembler::buildCFG(MCModule *Module) {
180   typedef std::map<uint64_t, BBInfo> BBInfoByAddrTy;
181   BBInfoByAddrTy BBInfos;
182   AddressSetTy Splits;
183   AddressSetTy Calls;
184
185   error_code ec;
186   for (symbol_iterator SI = Obj.begin_symbols(), SE = Obj.end_symbols();
187        SI != SE; SI.increment(ec)) {
188     if (ec)
189       break;
190     SymbolRef::Type SymType;
191     SI->getType(SymType);
192     if (SymType == SymbolRef::ST_Function) {
193       uint64_t SymAddr;
194       SI->getAddress(SymAddr);
195       SymAddr = getEffectiveLoadAddr(SymAddr);
196       Calls.push_back(SymAddr);
197       Splits.push_back(SymAddr);
198     }
199   }
200
201   assert(Module->func_begin() == Module->func_end()
202          && "Module already has a CFG!");
203
204   // First, determine the basic block boundaries and call targets.
205   for (MCModule::atom_iterator AI = Module->atom_begin(),
206                                AE = Module->atom_end();
207        AI != AE; ++AI) {
208     MCTextAtom *TA = dyn_cast<MCTextAtom>(*AI);
209     if (!TA) continue;
210     Calls.push_back(TA->getBeginAddr());
211     BBInfos[TA->getBeginAddr()].Atom = TA;
212     for (MCTextAtom::const_iterator II = TA->begin(), IE = TA->end();
213          II != IE; ++II) {
214       if (MIA.isTerminator(II->Inst))
215         Splits.push_back(II->Address + II->Size);
216       uint64_t Target;
217       if (MIA.evaluateBranch(II->Inst, II->Address, II->Size, Target)) {
218         if (MIA.isCall(II->Inst))
219           Calls.push_back(Target);
220         Splits.push_back(Target);
221       }
222     }
223   }
224
225   RemoveDupsFromAddressVector(Splits);
226   RemoveDupsFromAddressVector(Calls);
227
228   // Split text atoms into basic block atoms.
229   for (AddressSetTy::const_iterator SI = Splits.begin(), SE = Splits.end();
230        SI != SE; ++SI) {
231     MCAtom *A = Module->findAtomContaining(*SI);
232     if (!A) continue;
233     MCTextAtom *TA = cast<MCTextAtom>(A);
234     if (TA->getBeginAddr() == *SI)
235       continue;
236     MCTextAtom *NewAtom = TA->split(*SI);
237     BBInfos[NewAtom->getBeginAddr()].Atom = NewAtom;
238     StringRef BBName = TA->getName();
239     BBName = BBName.substr(0, BBName.find_last_of(':'));
240     NewAtom->setName((BBName + ":" + utohexstr(*SI)).str());
241   }
242
243   // Compute succs/preds.
244   for (MCModule::atom_iterator AI = Module->atom_begin(),
245                                AE = Module->atom_end();
246                                AI != AE; ++AI) {
247     MCTextAtom *TA = dyn_cast<MCTextAtom>(*AI);
248     if (!TA) continue;
249     BBInfo &CurBB = BBInfos[TA->getBeginAddr()];
250     const MCDecodedInst &LI = TA->back();
251     if (MIA.isBranch(LI.Inst)) {
252       uint64_t Target;
253       if (MIA.evaluateBranch(LI.Inst, LI.Address, LI.Size, Target))
254         CurBB.addSucc(BBInfos[Target]);
255       if (MIA.isConditionalBranch(LI.Inst))
256         CurBB.addSucc(BBInfos[LI.Address + LI.Size]);
257     } else if (!MIA.isTerminator(LI.Inst))
258       CurBB.addSucc(BBInfos[LI.Address + LI.Size]);
259   }
260
261
262   // Create functions and basic blocks.
263   for (AddressSetTy::const_iterator CI = Calls.begin(), CE = Calls.end();
264        CI != CE; ++CI) {
265     BBInfo &BBI = BBInfos[*CI];
266     if (!BBI.Atom) continue;
267
268     MCFunction &MCFN = *Module->createFunction(BBI.Atom->getName());
269
270     // Create MCBBs.
271     SmallSetVector<BBInfo*, 16> Worklist;
272     Worklist.insert(&BBI);
273     for (size_t wi = 0; wi < Worklist.size(); ++wi) {
274       BBInfo *BBI = Worklist[wi];
275       if (!BBI->Atom)
276         continue;
277       BBI->BB = &MCFN.createBlock(*BBI->Atom);
278       // Add all predecessors and successors to the worklist.
279       for (BBInfoSetTy::iterator SI = BBI->Succs.begin(), SE = BBI->Succs.end();
280                                  SI != SE; ++SI)
281         Worklist.insert(*SI);
282       for (BBInfoSetTy::iterator PI = BBI->Preds.begin(), PE = BBI->Preds.end();
283                                  PI != PE; ++PI)
284         Worklist.insert(*PI);
285     }
286
287     // Set preds/succs.
288     for (size_t wi = 0; wi < Worklist.size(); ++wi) {
289       BBInfo *BBI = Worklist[wi];
290       MCBasicBlock *MCBB = BBI->BB;
291       if (!MCBB)
292         continue;
293       for (BBInfoSetTy::iterator SI = BBI->Succs.begin(), SE = BBI->Succs.end();
294            SI != SE; ++SI)
295         if ((*SI)->BB)
296           MCBB->addSuccessor((*SI)->BB);
297       for (BBInfoSetTy::iterator PI = BBI->Preds.begin(), PE = BBI->Preds.end();
298            PI != PE; ++PI)
299         if ((*PI)->BB)
300           MCBB->addPredecessor((*PI)->BB);
301     }
302   }
303 }
304
305 // Basic idea of the disassembly + discovery:
306 //
307 // start with the wanted address, insert it in the worklist
308 // while worklist not empty, take next address in the worklist:
309 // - check if atom exists there
310 //   - if middle of atom:
311 //     - split basic blocks referencing the atom
312 //     - look for an already encountered BBInfo (using a map<atom, bbinfo>)
313 //       - if there is, split it (new one, fallthrough, move succs, etc..)
314 //   - if start of atom: nothing else to do
315 //   - if no atom: create new atom and new bbinfo
316 // - look at the last instruction in the atom, add succs to worklist
317 // for all elements in the worklist:
318 // - create basic block, update preds/succs, etc..
319 //
320 MCBasicBlock *MCObjectDisassembler::getBBAt(MCModule *Module, MCFunction *MCFN,
321                                             uint64_t BBBeginAddr,
322                                             AddressSetTy &CallTargets,
323                                             AddressSetTy &TailCallTargets) {
324   typedef std::map<uint64_t, BBInfo> BBInfoByAddrTy;
325   typedef SmallSetVector<uint64_t, 16> AddrWorklistTy;
326   BBInfoByAddrTy BBInfos;
327   AddrWorklistTy Worklist;
328
329   Worklist.insert(BBBeginAddr);
330   for (size_t wi = 0; wi < Worklist.size(); ++wi) {
331     const uint64_t BeginAddr = Worklist[wi];
332     BBInfo *BBI = &BBInfos[BeginAddr];
333
334     MCTextAtom *&TA = BBI->Atom;
335     assert(!TA && "Discovered basic block already has an associated atom!");
336
337     // Look for an atom at BeginAddr.
338     if (MCAtom *A = Module->findAtomContaining(BeginAddr)) {
339       // FIXME: We don't care about mixed atoms, see above.
340       TA = cast<MCTextAtom>(A);
341
342       // The found atom doesn't begin at BeginAddr, we have to split it.
343       if (TA->getBeginAddr() != BeginAddr) {
344         // FIXME: Handle overlapping atoms: middle-starting instructions, etc..
345         MCTextAtom *NewTA = TA->split(BeginAddr);
346
347         // Look for an already encountered basic block that needs splitting
348         BBInfoByAddrTy::iterator It = BBInfos.find(TA->getBeginAddr());
349         if (It != BBInfos.end() && It->second.Atom) {
350           BBI->SuccAddrs = It->second.SuccAddrs;
351           It->second.SuccAddrs.clear();
352           It->second.SuccAddrs.push_back(BeginAddr);
353         }
354         TA = NewTA;
355       }
356       BBI->Atom = TA;
357     } else {
358       // If we didn't find an atom, then we have to disassemble to create one!
359
360       MemoryObject *Region = getRegionFor(BeginAddr);
361       if (!Region)
362         llvm_unreachable(("Couldn't find suitable region for disassembly at " +
363                           utostr(BeginAddr)).c_str());
364
365       uint64_t InstSize;
366       uint64_t EndAddr = Region->getBase() + Region->getExtent();
367
368       // We want to stop before the next atom and have a fallthrough to it.
369       if (MCTextAtom *NextAtom =
370               cast_or_null<MCTextAtom>(Module->findFirstAtomAfter(BeginAddr)))
371         EndAddr = std::min(EndAddr, NextAtom->getBeginAddr());
372
373       for (uint64_t Addr = BeginAddr; Addr < EndAddr; Addr += InstSize) {
374         MCInst Inst;
375         if (Dis.getInstruction(Inst, InstSize, *Region, Addr, nulls(),
376                                nulls())) {
377           if (!TA)
378             TA = Module->createTextAtom(Addr, Addr);
379           TA->addInst(Inst, InstSize);
380         } else {
381           // We don't care about splitting mixed atoms either.
382           llvm_unreachable("Couldn't disassemble instruction in atom.");
383         }
384
385         uint64_t BranchTarget;
386         if (MIA.evaluateBranch(Inst, Addr, InstSize, BranchTarget)) {
387           if (MIA.isCall(Inst))
388             CallTargets.push_back(BranchTarget);
389         }
390
391         if (MIA.isTerminator(Inst))
392           break;
393       }
394       BBI->Atom = TA;
395     }
396
397     assert(TA && "Couldn't disassemble atom, none was created!");
398     assert(TA->begin() != TA->end() && "Empty atom!");
399
400     MemoryObject *Region = getRegionFor(TA->getBeginAddr());
401     assert(Region && "Couldn't find region for already disassembled code!");
402     uint64_t EndRegion = Region->getBase() + Region->getExtent();
403
404     // Now we have a basic block atom, add successors.
405     // Add the fallthrough block.
406     if ((MIA.isConditionalBranch(TA->back().Inst) ||
407          !MIA.isTerminator(TA->back().Inst)) &&
408         (TA->getEndAddr() + 1 < EndRegion)) {
409       BBI->SuccAddrs.push_back(TA->getEndAddr() + 1);
410       Worklist.insert(TA->getEndAddr() + 1);
411     }
412
413     // If the terminator is a branch, add the target block.
414     if (MIA.isBranch(TA->back().Inst)) {
415       uint64_t BranchTarget;
416       if (MIA.evaluateBranch(TA->back().Inst, TA->back().Address,
417                              TA->back().Size, BranchTarget)) {
418         StringRef ExtFnName;
419         if (MOS)
420           ExtFnName =
421               MOS->findExternalFunctionAt(getOriginalLoadAddr(BranchTarget));
422         if (!ExtFnName.empty()) {
423           TailCallTargets.push_back(BranchTarget);
424           CallTargets.push_back(BranchTarget);
425         } else {
426           BBI->SuccAddrs.push_back(BranchTarget);
427           Worklist.insert(BranchTarget);
428         }
429       }
430     }
431   }
432
433   for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) {
434     const uint64_t BeginAddr = Worklist[wi];
435     BBInfo *BBI = &BBInfos[BeginAddr];
436
437     assert(BBI->Atom && "Found a basic block without an associated atom!");
438
439     // Look for a basic block at BeginAddr.
440     BBI->BB = MCFN->find(BeginAddr);
441     if (BBI->BB) {
442       // FIXME: check that the succs/preds are the same
443       continue;
444     }
445     // If there was none, we have to create one from the atom.
446     BBI->BB = &MCFN->createBlock(*BBI->Atom);
447   }
448
449   for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) {
450     const uint64_t BeginAddr = Worklist[wi];
451     BBInfo *BBI = &BBInfos[BeginAddr];
452     MCBasicBlock *BB = BBI->BB;
453
454     RemoveDupsFromAddressVector(BBI->SuccAddrs);
455     for (AddressSetTy::const_iterator SI = BBI->SuccAddrs.begin(),
456          SE = BBI->SuccAddrs.end();
457          SE != SE; ++SI) {
458       MCBasicBlock *Succ = BBInfos[*SI].BB;
459       BB->addSuccessor(Succ);
460       Succ->addPredecessor(BB);
461     }
462   }
463
464   assert(BBInfos[Worklist[0]].BB &&
465          "No basic block created at requested address?");
466
467   return BBInfos[Worklist[0]].BB;
468 }
469
470 MCFunction *
471 MCObjectDisassembler::createFunction(MCModule *Module, uint64_t BeginAddr,
472                                      AddressSetTy &CallTargets,
473                                      AddressSetTy &TailCallTargets) {
474   // First, check if this is an external function.
475   StringRef ExtFnName;
476   if (MOS)
477     ExtFnName = MOS->findExternalFunctionAt(getOriginalLoadAddr(BeginAddr));
478   if (!ExtFnName.empty())
479     return Module->createFunction(ExtFnName);
480
481   // If it's not, look for an existing function.
482   for (MCModule::func_iterator FI = Module->func_begin(),
483                                FE = Module->func_end();
484        FI != FE; ++FI) {
485     if ((*FI)->empty())
486       continue;
487     // FIXME: MCModule should provide a findFunctionByAddr()
488     if ((*FI)->getEntryBlock()->getInsts()->getBeginAddr() == BeginAddr)
489       return *FI;
490   }
491
492   // Finally, just create a new one.
493   MCFunction *MCFN = Module->createFunction("");
494   getBBAt(Module, MCFN, BeginAddr, CallTargets, TailCallTargets);
495   return MCFN;
496 }
497
498 // MachO MCObjectDisassembler implementation.
499
500 MCMachOObjectDisassembler::MCMachOObjectDisassembler(
501     const MachOObjectFile &MOOF, const MCDisassembler &Dis,
502     const MCInstrAnalysis &MIA, uint64_t VMAddrSlide,
503     uint64_t HeaderLoadAddress)
504     : MCObjectDisassembler(MOOF, Dis, MIA), MOOF(MOOF),
505       VMAddrSlide(VMAddrSlide), HeaderLoadAddress(HeaderLoadAddress) {
506
507   error_code ec;
508   for (section_iterator SI = MOOF.begin_sections(), SE = MOOF.end_sections();
509        SI != SE; SI.increment(ec)) {
510     if (ec)
511       break;
512     StringRef Name;
513     SI->getName(Name);
514     // FIXME: We should use the S_ section type instead of the name.
515     if (Name == "__mod_init_func") {
516       DEBUG(dbgs() << "Found __mod_init_func section!\n");
517       SI->getContents(ModInitContents);
518     } else if (Name == "__mod_exit_func") {
519       DEBUG(dbgs() << "Found __mod_exit_func section!\n");
520       SI->getContents(ModExitContents);
521     }
522   }
523 }
524
525 // FIXME: Only do the translations for addresses actually inside the object.
526 uint64_t MCMachOObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) {
527   return Addr + VMAddrSlide;
528 }
529
530 uint64_t
531 MCMachOObjectDisassembler::getOriginalLoadAddr(uint64_t EffectiveAddr) {
532   return EffectiveAddr - VMAddrSlide;
533 }
534
535 uint64_t MCMachOObjectDisassembler::getEntrypoint() {
536   uint64_t EntryFileOffset = 0;
537
538   // Look for LC_MAIN.
539   {
540     uint32_t LoadCommandCount = MOOF.getHeader().NumLoadCommands;
541     MachOObjectFile::LoadCommandInfo Load = MOOF.getFirstLoadCommandInfo();
542     for (unsigned I = 0;; ++I) {
543       if (Load.C.Type == MachO::LoadCommandMain) {
544         EntryFileOffset =
545             ((const MachO::entry_point_command *)Load.Ptr)->entryoff;
546         break;
547       }
548
549       if (I == LoadCommandCount - 1)
550         break;
551       else
552         Load = MOOF.getNextLoadCommandInfo(Load);
553     }
554   }
555
556   // If we didn't find anything, default to the common implementation.
557   // FIXME: Maybe we could also look at LC_UNIXTHREAD and friends?
558   if (EntryFileOffset)
559     return MCObjectDisassembler::getEntrypoint();
560
561   return EntryFileOffset + HeaderLoadAddress;
562 }
563
564 ArrayRef<uint64_t> MCMachOObjectDisassembler::getStaticInitFunctions() {
565   // FIXME: We only handle 64bit mach-o
566   assert(MOOF.is64Bit());
567
568   size_t EntrySize = 8;
569   size_t EntryCount = ModInitContents.size() / EntrySize;
570   return ArrayRef<uint64_t>(
571       reinterpret_cast<const uint64_t *>(ModInitContents.data()), EntryCount);
572 }
573
574 ArrayRef<uint64_t> MCMachOObjectDisassembler::getStaticExitFunctions() {
575   // FIXME: We only handle 64bit mach-o
576   assert(MOOF.is64Bit());
577
578   size_t EntrySize = 8;
579   size_t EntryCount = ModExitContents.size() / EntrySize;
580   return ArrayRef<uint64_t>(
581       reinterpret_cast<const uint64_t *>(ModExitContents.data()), EntryCount);
582 }