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