Test commit
[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   for (symbol_iterator SI = Obj.begin_symbols(), SE = Obj.end_symbols();
41        SI != SE; ++SI) {
42     StringRef Name;
43     SI->getName(Name);
44     if (Name == "main" || Name == "_main") {
45       uint64_t Entrypoint;
46       SI->getAddress(Entrypoint);
47       return getEffectiveLoadAddr(Entrypoint);
48     }
49   }
50   return 0;
51 }
52
53 ArrayRef<uint64_t> MCObjectDisassembler::getStaticInitFunctions() {
54   return ArrayRef<uint64_t>();
55 }
56
57 ArrayRef<uint64_t> MCObjectDisassembler::getStaticExitFunctions() {
58   return ArrayRef<uint64_t>();
59 }
60
61 MemoryObject *MCObjectDisassembler::getRegionFor(uint64_t Addr) {
62   // FIXME: Keep track of object sections.
63   return FallbackRegion.get();
64 }
65
66 uint64_t MCObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) {
67   return Addr;
68 }
69
70 uint64_t MCObjectDisassembler::getOriginalLoadAddr(uint64_t Addr) {
71   return Addr;
72 }
73
74 MCModule *MCObjectDisassembler::buildEmptyModule() {
75   MCModule *Module = new MCModule;
76   Module->Entrypoint = getEntrypoint();
77   return Module;
78 }
79
80 MCModule *MCObjectDisassembler::buildModule(bool withCFG) {
81   MCModule *Module = buildEmptyModule();
82
83   buildSectionAtoms(Module);
84   if (withCFG)
85     buildCFG(Module);
86   return Module;
87 }
88
89 void MCObjectDisassembler::buildSectionAtoms(MCModule *Module) {
90   for (section_iterator SI = Obj.begin_sections(), SE = Obj.end_sections();
91        SI != SE; ++SI) {
92     bool isText; SI->isText(isText);
93     bool isData; SI->isData(isData);
94     if (!isData && !isText)
95       continue;
96
97     uint64_t StartAddr; SI->getAddress(StartAddr);
98     uint64_t SecSize; SI->getSize(SecSize);
99     if (StartAddr == UnknownAddressOrSize || SecSize == UnknownAddressOrSize)
100       continue;
101     StartAddr = getEffectiveLoadAddr(StartAddr);
102
103     StringRef Contents; SI->getContents(Contents);
104     StringRefMemoryObject memoryObject(Contents, StartAddr);
105
106     // We don't care about things like non-file-backed sections yet.
107     if (Contents.size() != SecSize || !SecSize)
108       continue;
109     uint64_t EndAddr = StartAddr + SecSize - 1;
110
111     StringRef SecName; SI->getName(SecName);
112
113     if (isText) {
114       MCTextAtom *Text = 0;
115       MCDataAtom *InvalidData = 0;
116
117       uint64_t InstSize;
118       for (uint64_t Index = 0; Index < SecSize; Index += InstSize) {
119         const uint64_t CurAddr = StartAddr + Index;
120         MCInst Inst;
121         if (Dis.getInstruction(Inst, InstSize, memoryObject, CurAddr, nulls(),
122                                nulls())) {
123           if (!Text) {
124             Text = Module->createTextAtom(CurAddr, CurAddr);
125             Text->setName(SecName);
126           }
127           Text->addInst(Inst, InstSize);
128           InvalidData = 0;
129         } else {
130           assert(InstSize && "getInstruction() consumed no bytes");
131           if (!InvalidData) {
132             Text = 0;
133             InvalidData = Module->createDataAtom(CurAddr, CurAddr+InstSize - 1);
134           }
135           for (uint64_t I = 0; I < InstSize; ++I)
136             InvalidData->addData(Contents[Index+I]);
137         }
138       }
139     } else {
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]);
144     }
145   }
146 }
147
148 namespace {
149   struct BBInfo;
150   typedef SmallPtrSet<BBInfo*, 2> BBInfoSetTy;
151
152   struct BBInfo {
153     MCTextAtom *Atom;
154     MCBasicBlock *BB;
155     BBInfoSetTy Succs;
156     BBInfoSetTy Preds;
157     MCObjectDisassembler::AddressSetTy SuccAddrs;
158
159     BBInfo() : Atom(0), BB(0) {}
160
161     void addSucc(BBInfo &Succ) {
162       Succs.insert(&Succ);
163       Succ.Preds.insert(this);
164     }
165   };
166 }
167
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());
171 }
172
173 void MCObjectDisassembler::buildCFG(MCModule *Module) {
174   typedef std::map<uint64_t, BBInfo> BBInfoByAddrTy;
175   BBInfoByAddrTy BBInfos;
176   AddressSetTy Splits;
177   AddressSetTy Calls;
178
179   for (symbol_iterator SI = Obj.begin_symbols(), SE = Obj.end_symbols();
180        SI != SE; ++SI) {
181     SymbolRef::Type SymType;
182     SI->getType(SymType);
183     if (SymType == SymbolRef::ST_Function) {
184       uint64_t SymAddr;
185       SI->getAddress(SymAddr);
186       SymAddr = getEffectiveLoadAddr(SymAddr);
187       Calls.push_back(SymAddr);
188       Splits.push_back(SymAddr);
189     }
190   }
191
192   assert(Module->func_begin() == Module->func_end()
193          && "Module already has a CFG!");
194
195   // First, determine the basic block boundaries and call targets.
196   for (MCModule::atom_iterator AI = Module->atom_begin(),
197                                AE = Module->atom_end();
198        AI != AE; ++AI) {
199     MCTextAtom *TA = dyn_cast<MCTextAtom>(*AI);
200     if (!TA) continue;
201     Calls.push_back(TA->getBeginAddr());
202     BBInfos[TA->getBeginAddr()].Atom = TA;
203     for (MCTextAtom::const_iterator II = TA->begin(), IE = TA->end();
204          II != IE; ++II) {
205       if (MIA.isTerminator(II->Inst))
206         Splits.push_back(II->Address + II->Size);
207       uint64_t Target;
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);
212       }
213     }
214   }
215
216   RemoveDupsFromAddressVector(Splits);
217   RemoveDupsFromAddressVector(Calls);
218
219   // Split text atoms into basic block atoms.
220   for (AddressSetTy::const_iterator SI = Splits.begin(), SE = Splits.end();
221        SI != SE; ++SI) {
222     MCAtom *A = Module->findAtomContaining(*SI);
223     if (!A) continue;
224     MCTextAtom *TA = cast<MCTextAtom>(A);
225     if (TA->getBeginAddr() == *SI)
226       continue;
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());
232   }
233
234   // Compute succs/preds.
235   for (MCModule::atom_iterator AI = Module->atom_begin(),
236                                AE = Module->atom_end();
237                                AI != AE; ++AI) {
238     MCTextAtom *TA = dyn_cast<MCTextAtom>(*AI);
239     if (!TA) continue;
240     BBInfo &CurBB = BBInfos[TA->getBeginAddr()];
241     const MCDecodedInst &LI = TA->back();
242     if (MIA.isBranch(LI.Inst)) {
243       uint64_t Target;
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]);
250   }
251
252
253   // Create functions and basic blocks.
254   for (AddressSetTy::const_iterator CI = Calls.begin(), CE = Calls.end();
255        CI != CE; ++CI) {
256     BBInfo &BBI = BBInfos[*CI];
257     if (!BBI.Atom) continue;
258
259     MCFunction &MCFN = *Module->createFunction(BBI.Atom->getName());
260
261     // Create MCBBs.
262     SmallSetVector<BBInfo*, 16> Worklist;
263     Worklist.insert(&BBI);
264     for (size_t wi = 0; wi < Worklist.size(); ++wi) {
265       BBInfo *BBI = Worklist[wi];
266       if (!BBI->Atom)
267         continue;
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();
271                                  SI != SE; ++SI)
272         Worklist.insert(*SI);
273       for (BBInfoSetTy::iterator PI = BBI->Preds.begin(), PE = BBI->Preds.end();
274                                  PI != PE; ++PI)
275         Worklist.insert(*PI);
276     }
277
278     // Set preds/succs.
279     for (size_t wi = 0; wi < Worklist.size(); ++wi) {
280       BBInfo *BBI = Worklist[wi];
281       MCBasicBlock *MCBB = BBI->BB;
282       if (!MCBB)
283         continue;
284       for (BBInfoSetTy::iterator SI = BBI->Succs.begin(), SE = BBI->Succs.end();
285            SI != SE; ++SI)
286         if ((*SI)->BB)
287           MCBB->addSuccessor((*SI)->BB);
288       for (BBInfoSetTy::iterator PI = BBI->Preds.begin(), PE = BBI->Preds.end();
289            PI != PE; ++PI)
290         if ((*PI)->BB)
291           MCBB->addPredecessor((*PI)->BB);
292     }
293   }
294 }
295
296 // Basic idea of the disassembly + discovery:
297 //
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..
310 //
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;
319
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];
324
325     MCTextAtom *&TA = BBI->Atom;
326     assert(!TA && "Discovered basic block already has an associated atom!");
327
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);
332
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);
337
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);
344         }
345         TA = NewTA;
346       }
347       BBI->Atom = TA;
348     } else {
349       // If we didn't find an atom, then we have to disassemble to create one!
350
351       MemoryObject *Region = getRegionFor(BeginAddr);
352       if (!Region)
353         llvm_unreachable(("Couldn't find suitable region for disassembly at " +
354                           utostr(BeginAddr)).c_str());
355
356       uint64_t InstSize;
357       uint64_t EndAddr = Region->getBase() + Region->getExtent();
358
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());
363
364       for (uint64_t Addr = BeginAddr; Addr < EndAddr; Addr += InstSize) {
365         MCInst Inst;
366         if (Dis.getInstruction(Inst, InstSize, *Region, Addr, nulls(),
367                                nulls())) {
368           if (!TA)
369             TA = Module->createTextAtom(Addr, Addr);
370           TA->addInst(Inst, InstSize);
371         } else {
372           // We don't care about splitting mixed atoms either.
373           llvm_unreachable("Couldn't disassemble instruction in atom.");
374         }
375
376         uint64_t BranchTarget;
377         if (MIA.evaluateBranch(Inst, Addr, InstSize, BranchTarget)) {
378           if (MIA.isCall(Inst))
379             CallTargets.push_back(BranchTarget);
380         }
381
382         if (MIA.isTerminator(Inst))
383           break;
384       }
385       BBI->Atom = TA;
386     }
387
388     assert(TA && "Couldn't disassemble atom, none was created!");
389     assert(TA->begin() != TA->end() && "Empty atom!");
390
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();
394
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);
402     }
403
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)) {
409         StringRef ExtFnName;
410         if (MOS)
411           ExtFnName =
412               MOS->findExternalFunctionAt(getOriginalLoadAddr(BranchTarget));
413         if (!ExtFnName.empty()) {
414           TailCallTargets.push_back(BranchTarget);
415           CallTargets.push_back(BranchTarget);
416         } else {
417           BBI->SuccAddrs.push_back(BranchTarget);
418           Worklist.insert(BranchTarget);
419         }
420       }
421     }
422   }
423
424   for (size_t wi = 0, we = Worklist.size(); wi != we; ++wi) {
425     const uint64_t BeginAddr = Worklist[wi];
426     BBInfo *BBI = &BBInfos[BeginAddr];
427
428     assert(BBI->Atom && "Found a basic block without an associated atom!");
429
430     // Look for a basic block at BeginAddr.
431     BBI->BB = MCFN->find(BeginAddr);
432     if (BBI->BB) {
433       // FIXME: check that the succs/preds are the same
434       continue;
435     }
436     // If there was none, we have to create one from the atom.
437     BBI->BB = &MCFN->createBlock(*BBI->Atom);
438   }
439
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;
444
445     RemoveDupsFromAddressVector(BBI->SuccAddrs);
446     for (AddressSetTy::const_iterator SI = BBI->SuccAddrs.begin(),
447          SE = BBI->SuccAddrs.end();
448          SE != SE; ++SI) {
449       MCBasicBlock *Succ = BBInfos[*SI].BB;
450       BB->addSuccessor(Succ);
451       Succ->addPredecessor(BB);
452     }
453   }
454
455   assert(BBInfos[Worklist[0]].BB &&
456          "No basic block created at requested address?");
457
458   return BBInfos[Worklist[0]].BB;
459 }
460
461 MCFunction *
462 MCObjectDisassembler::createFunction(MCModule *Module, uint64_t BeginAddr,
463                                      AddressSetTy &CallTargets,
464                                      AddressSetTy &TailCallTargets) {
465   // First, check if this is an external function.
466   StringRef ExtFnName;
467   if (MOS)
468     ExtFnName = MOS->findExternalFunctionAt(getOriginalLoadAddr(BeginAddr));
469   if (!ExtFnName.empty())
470     return Module->createFunction(ExtFnName);
471
472   // If it's not, look for an existing function.
473   for (MCModule::func_iterator FI = Module->func_begin(),
474                                FE = Module->func_end();
475        FI != FE; ++FI) {
476     if ((*FI)->empty())
477       continue;
478     // FIXME: MCModule should provide a findFunctionByAddr()
479     if ((*FI)->getEntryBlock()->getInsts()->getBeginAddr() == BeginAddr)
480       return *FI;
481   }
482
483   // Finally, just create a new one.
484   MCFunction *MCFN = Module->createFunction("");
485   getBBAt(Module, MCFN, BeginAddr, CallTargets, TailCallTargets);
486   return MCFN;
487 }
488
489 // MachO MCObjectDisassembler implementation.
490
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) {
497
498   for (section_iterator SI = MOOF.begin_sections(), SE = MOOF.end_sections();
499        SI != SE; ++SI) {
500     StringRef Name;
501     SI->getName(Name);
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);
509     }
510   }
511 }
512
513 // FIXME: Only do the translations for addresses actually inside the object.
514 uint64_t MCMachOObjectDisassembler::getEffectiveLoadAddr(uint64_t Addr) {
515   return Addr + VMAddrSlide;
516 }
517
518 uint64_t
519 MCMachOObjectDisassembler::getOriginalLoadAddr(uint64_t EffectiveAddr) {
520   return EffectiveAddr - VMAddrSlide;
521 }
522
523 uint64_t MCMachOObjectDisassembler::getEntrypoint() {
524   uint64_t EntryFileOffset = 0;
525
526   // Look for LC_MAIN.
527   {
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) {
532         EntryFileOffset =
533             ((const MachO::entry_point_command *)Load.Ptr)->entryoff;
534         break;
535       }
536
537       if (I == LoadCommandCount - 1)
538         break;
539       else
540         Load = MOOF.getNextLoadCommandInfo(Load);
541     }
542   }
543
544   // If we didn't find anything, default to the common implementation.
545   // FIXME: Maybe we could also look at LC_UNIXTHREAD and friends?
546   if (EntryFileOffset)
547     return MCObjectDisassembler::getEntrypoint();
548
549   return EntryFileOffset + HeaderLoadAddress;
550 }
551
552 ArrayRef<uint64_t> MCMachOObjectDisassembler::getStaticInitFunctions() {
553   // FIXME: We only handle 64bit mach-o
554   assert(MOOF.is64Bit());
555
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);
560 }
561
562 ArrayRef<uint64_t> MCMachOObjectDisassembler::getStaticExitFunctions() {
563   // FIXME: We only handle 64bit mach-o
564   assert(MOOF.is64Bit());
565
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);
570 }