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