Mercurial > hg > CbC > CbC_llvm

comparison lib/MC/MCObjectDisassembler.cpp @ 0:95c75e76d11b LLVM3.4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.4
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Thu, 12 Dec 2013 13:56:28 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:95c75e76d11b
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 }