MachineFunction.cpp revision 0e0da734bbdfa1d3f55cd04db31d83b97e4556f7
1//===-- MachineFunction.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// Collect native machine code information for a function. This allows 11// target-specific information about the generated code to be stored with each 12// function. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/DerivedTypes.h" 17#include "llvm/CodeGen/MachineConstantPool.h" 18#include "llvm/CodeGen/MachineFunctionPass.h" 19#include "llvm/CodeGen/MachineFrameInfo.h" 20#include "llvm/CodeGen/MachineInstr.h" 21#include "llvm/CodeGen/MachineJumpTableInfo.h" 22#include "llvm/CodeGen/MachineRegisterInfo.h" 23#include "llvm/CodeGen/Passes.h" 24#include "llvm/Target/TargetData.h" 25#include "llvm/Target/TargetMachine.h" 26#include "llvm/Target/TargetFrameInfo.h" 27#include "llvm/Function.h" 28#include "llvm/Instructions.h" 29#include "llvm/Support/Compiler.h" 30#include "llvm/Support/GraphWriter.h" 31#include "llvm/Support/raw_ostream.h" 32#include "llvm/ADT/STLExtras.h" 33#include "llvm/Config/config.h" 34#include <fstream> 35#include <sstream> 36using namespace llvm; 37 38static AnnotationID MF_AID( 39 AnnotationManager::getID("CodeGen::MachineCodeForFunction")); 40 41bool MachineFunctionPass::runOnFunction(Function &F) { 42 // Do not codegen any 'available_externally' functions at all, they have 43 // definitions outside the translation unit. 44 if (F.hasAvailableExternallyLinkage()) 45 return false; 46 47 return runOnMachineFunction(MachineFunction::get(&F)); 48} 49 50namespace { 51 struct VISIBILITY_HIDDEN Printer : public MachineFunctionPass { 52 static char ID; 53 54 std::ostream *OS; 55 const std::string Banner; 56 57 Printer (std::ostream *os, const std::string &banner) 58 : MachineFunctionPass(&ID), OS(os), Banner(banner) {} 59 60 const char *getPassName() const { return "MachineFunction Printer"; } 61 62 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 63 AU.setPreservesAll(); 64 } 65 66 bool runOnMachineFunction(MachineFunction &MF) { 67 (*OS) << Banner; 68 MF.print (*OS); 69 return false; 70 } 71 }; 72 char Printer::ID = 0; 73} 74 75/// Returns a newly-created MachineFunction Printer pass. The default output 76/// stream is std::cerr; the default banner is empty. 77/// 78FunctionPass *llvm::createMachineFunctionPrinterPass(std::ostream *OS, 79 const std::string &Banner){ 80 return new Printer(OS, Banner); 81} 82 83namespace { 84 struct VISIBILITY_HIDDEN Deleter : public MachineFunctionPass { 85 static char ID; 86 Deleter() : MachineFunctionPass(&ID) {} 87 88 const char *getPassName() const { return "Machine Code Deleter"; } 89 90 bool runOnMachineFunction(MachineFunction &MF) { 91 // Delete the annotation from the function now. 92 MachineFunction::destruct(MF.getFunction()); 93 return true; 94 } 95 }; 96 char Deleter::ID = 0; 97} 98 99/// MachineCodeDeletion Pass - This pass deletes all of the machine code for 100/// the current function, which should happen after the function has been 101/// emitted to a .s file or to memory. 102FunctionPass *llvm::createMachineCodeDeleter() { 103 return new Deleter(); 104} 105 106 107 108//===---------------------------------------------------------------------===// 109// MachineFunction implementation 110//===---------------------------------------------------------------------===// 111 112void ilist_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) { 113 MBB->getParent()->DeleteMachineBasicBlock(MBB); 114} 115 116MachineFunction::MachineFunction(const Function *F, 117 const TargetMachine &TM) 118 : Annotation(MF_AID), Fn(F), Target(TM) { 119 if (TM.getRegisterInfo()) 120 RegInfo = new (Allocator.Allocate<MachineRegisterInfo>()) 121 MachineRegisterInfo(*TM.getRegisterInfo()); 122 else 123 RegInfo = 0; 124 HasBuiltinSetjmp = false; 125 MFInfo = 0; 126 FrameInfo = new (Allocator.Allocate<MachineFrameInfo>()) 127 MachineFrameInfo(*TM.getFrameInfo()); 128 ConstantPool = new (Allocator.Allocate<MachineConstantPool>()) 129 MachineConstantPool(TM.getTargetData()); 130 131 // Set up jump table. 132 const TargetData &TD = *TM.getTargetData(); 133 bool IsPic = TM.getRelocationModel() == Reloc::PIC_; 134 unsigned EntrySize = IsPic ? 4 : TD.getPointerSize(); 135 unsigned Alignment = IsPic ? TD.getABITypeAlignment(Type::Int32Ty) 136 : TD.getPointerABIAlignment(); 137 JumpTableInfo = new (Allocator.Allocate<MachineJumpTableInfo>()) 138 MachineJumpTableInfo(EntrySize, Alignment); 139} 140 141MachineFunction::~MachineFunction() { 142 BasicBlocks.clear(); 143 InstructionRecycler.clear(Allocator); 144 BasicBlockRecycler.clear(Allocator); 145 if (RegInfo) 146 RegInfo->~MachineRegisterInfo(); Allocator.Deallocate(RegInfo); 147 if (MFInfo) { 148 MFInfo->~MachineFunctionInfo(); Allocator.Deallocate(MFInfo); 149 } 150 FrameInfo->~MachineFrameInfo(); Allocator.Deallocate(FrameInfo); 151 ConstantPool->~MachineConstantPool(); Allocator.Deallocate(ConstantPool); 152 JumpTableInfo->~MachineJumpTableInfo(); Allocator.Deallocate(JumpTableInfo); 153} 154 155 156/// RenumberBlocks - This discards all of the MachineBasicBlock numbers and 157/// recomputes them. This guarantees that the MBB numbers are sequential, 158/// dense, and match the ordering of the blocks within the function. If a 159/// specific MachineBasicBlock is specified, only that block and those after 160/// it are renumbered. 161void MachineFunction::RenumberBlocks(MachineBasicBlock *MBB) { 162 if (empty()) { MBBNumbering.clear(); return; } 163 MachineFunction::iterator MBBI, E = end(); 164 if (MBB == 0) 165 MBBI = begin(); 166 else 167 MBBI = MBB; 168 169 // Figure out the block number this should have. 170 unsigned BlockNo = 0; 171 if (MBBI != begin()) 172 BlockNo = prior(MBBI)->getNumber()+1; 173 174 for (; MBBI != E; ++MBBI, ++BlockNo) { 175 if (MBBI->getNumber() != (int)BlockNo) { 176 // Remove use of the old number. 177 if (MBBI->getNumber() != -1) { 178 assert(MBBNumbering[MBBI->getNumber()] == &*MBBI && 179 "MBB number mismatch!"); 180 MBBNumbering[MBBI->getNumber()] = 0; 181 } 182 183 // If BlockNo is already taken, set that block's number to -1. 184 if (MBBNumbering[BlockNo]) 185 MBBNumbering[BlockNo]->setNumber(-1); 186 187 MBBNumbering[BlockNo] = MBBI; 188 MBBI->setNumber(BlockNo); 189 } 190 } 191 192 // Okay, all the blocks are renumbered. If we have compactified the block 193 // numbering, shrink MBBNumbering now. 194 assert(BlockNo <= MBBNumbering.size() && "Mismatch!"); 195 MBBNumbering.resize(BlockNo); 196} 197 198/// CreateMachineInstr - Allocate a new MachineInstr. Use this instead 199/// of `new MachineInstr'. 200/// 201MachineInstr * 202MachineFunction::CreateMachineInstr(const TargetInstrDesc &TID, 203 DebugLoc DL, bool NoImp) { 204 return new (InstructionRecycler.Allocate<MachineInstr>(Allocator)) 205 MachineInstr(TID, DL, NoImp); 206} 207 208/// CloneMachineInstr - Create a new MachineInstr which is a copy of the 209/// 'Orig' instruction, identical in all ways except the the instruction 210/// has no parent, prev, or next. 211/// 212MachineInstr * 213MachineFunction::CloneMachineInstr(const MachineInstr *Orig) { 214 return new (InstructionRecycler.Allocate<MachineInstr>(Allocator)) 215 MachineInstr(*this, *Orig); 216} 217 218/// DeleteMachineInstr - Delete the given MachineInstr. 219/// 220void 221MachineFunction::DeleteMachineInstr(MachineInstr *MI) { 222 // Clear the instructions memoperands. This must be done manually because 223 // the instruction's parent pointer is now null, so it can't properly 224 // deallocate them on its own. 225 MI->clearMemOperands(*this); 226 227 MI->~MachineInstr(); 228 InstructionRecycler.Deallocate(Allocator, MI); 229} 230 231/// CreateMachineBasicBlock - Allocate a new MachineBasicBlock. Use this 232/// instead of `new MachineBasicBlock'. 233/// 234MachineBasicBlock * 235MachineFunction::CreateMachineBasicBlock(const BasicBlock *bb) { 236 return new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator)) 237 MachineBasicBlock(*this, bb); 238} 239 240/// DeleteMachineBasicBlock - Delete the given MachineBasicBlock. 241/// 242void 243MachineFunction::DeleteMachineBasicBlock(MachineBasicBlock *MBB) { 244 assert(MBB->getParent() == this && "MBB parent mismatch!"); 245 MBB->~MachineBasicBlock(); 246 BasicBlockRecycler.Deallocate(Allocator, MBB); 247} 248 249void MachineFunction::dump() const { 250 print(*cerr.stream()); 251} 252 253void MachineFunction::print(std::ostream &OS) const { 254 OS << "# Machine code for " << Fn->getName () << "():\n"; 255 256 // Print Frame Information 257 FrameInfo->print(*this, OS); 258 259 // Print JumpTable Information 260 JumpTableInfo->print(OS); 261 262 // Print Constant Pool 263 { 264 raw_os_ostream OSS(OS); 265 ConstantPool->print(OSS); 266 } 267 268 const TargetRegisterInfo *TRI = getTarget().getRegisterInfo(); 269 270 if (RegInfo && !RegInfo->livein_empty()) { 271 OS << "Live Ins:"; 272 for (MachineRegisterInfo::livein_iterator 273 I = RegInfo->livein_begin(), E = RegInfo->livein_end(); I != E; ++I) { 274 if (TRI) 275 OS << " " << TRI->getName(I->first); 276 else 277 OS << " Reg #" << I->first; 278 279 if (I->second) 280 OS << " in VR#" << I->second << " "; 281 } 282 OS << "\n"; 283 } 284 if (RegInfo && !RegInfo->liveout_empty()) { 285 OS << "Live Outs:"; 286 for (MachineRegisterInfo::liveout_iterator 287 I = RegInfo->liveout_begin(), E = RegInfo->liveout_end(); I != E; ++I) 288 if (TRI) 289 OS << " " << TRI->getName(*I); 290 else 291 OS << " Reg #" << *I; 292 OS << "\n"; 293 } 294 295 for (const_iterator BB = begin(); BB != end(); ++BB) 296 BB->print(OS); 297 298 OS << "\n# End machine code for " << Fn->getName () << "().\n\n"; 299} 300 301/// CFGOnly flag - This is used to control whether or not the CFG graph printer 302/// prints out the contents of basic blocks or not. This is acceptable because 303/// this code is only really used for debugging purposes. 304/// 305static bool CFGOnly = false; 306 307namespace llvm { 308 template<> 309 struct DOTGraphTraits<const MachineFunction*> : public DefaultDOTGraphTraits { 310 static std::string getGraphName(const MachineFunction *F) { 311 return "CFG for '" + F->getFunction()->getName() + "' function"; 312 } 313 314 static std::string getNodeLabel(const MachineBasicBlock *Node, 315 const MachineFunction *Graph) { 316 if (CFGOnly && Node->getBasicBlock() && 317 !Node->getBasicBlock()->getName().empty()) 318 return Node->getBasicBlock()->getName() + ":"; 319 320 std::ostringstream Out; 321 if (CFGOnly) { 322 Out << Node->getNumber() << ':'; 323 return Out.str(); 324 } 325 326 Node->print(Out); 327 328 std::string OutStr = Out.str(); 329 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 330 331 // Process string output to make it nicer... 332 for (unsigned i = 0; i != OutStr.length(); ++i) 333 if (OutStr[i] == '\n') { // Left justify 334 OutStr[i] = '\\'; 335 OutStr.insert(OutStr.begin()+i+1, 'l'); 336 } 337 return OutStr; 338 } 339 }; 340} 341 342void MachineFunction::viewCFG() const 343{ 344#ifndef NDEBUG 345 ViewGraph(this, "mf" + getFunction()->getName()); 346#else 347 cerr << "SelectionDAG::viewGraph is only available in debug builds on " 348 << "systems with Graphviz or gv!\n"; 349#endif // NDEBUG 350} 351 352void MachineFunction::viewCFGOnly() const 353{ 354 CFGOnly = true; 355 viewCFG(); 356 CFGOnly = false; 357} 358 359// The next two methods are used to construct and to retrieve 360// the MachineCodeForFunction object for the given function. 361// construct() -- Allocates and initializes for a given function and target 362// get() -- Returns a handle to the object. 363// This should not be called before "construct()" 364// for a given Function. 365// 366MachineFunction& 367MachineFunction::construct(const Function *Fn, const TargetMachine &Tar) 368{ 369 assert(Fn->getAnnotation(MF_AID) == 0 && 370 "Object already exists for this function!"); 371 MachineFunction* mcInfo = new MachineFunction(Fn, Tar); 372 Fn->addAnnotation(mcInfo); 373 return *mcInfo; 374} 375 376void MachineFunction::destruct(const Function *Fn) { 377 bool Deleted = Fn->deleteAnnotation(MF_AID); 378 assert(Deleted && "Machine code did not exist for function!"); 379 Deleted = Deleted; // silence warning when no assertions. 380} 381 382MachineFunction& MachineFunction::get(const Function *F) 383{ 384 MachineFunction *mc = (MachineFunction*)F->getAnnotation(MF_AID); 385 assert(mc && "Call construct() method first to allocate the object"); 386 return *mc; 387} 388 389/// addLiveIn - Add the specified physical register as a live-in value and 390/// create a corresponding virtual register for it. 391unsigned MachineFunction::addLiveIn(unsigned PReg, 392 const TargetRegisterClass *RC) { 393 assert(RC->contains(PReg) && "Not the correct regclass!"); 394 unsigned VReg = getRegInfo().createVirtualRegister(RC); 395 getRegInfo().addLiveIn(PReg, VReg); 396 return VReg; 397} 398 399/// getOrCreateDebugLocID - Look up the DebugLocTuple index with the given 400/// source file, line, and column. If none currently exists, create a new 401/// DebugLocTuple, and insert it into the DebugIdMap. 402unsigned MachineFunction::getOrCreateDebugLocID(GlobalVariable *CompileUnit, 403 unsigned Line, unsigned Col) { 404 DebugLocTuple Tuple(CompileUnit, Line, Col); 405 DenseMap<DebugLocTuple, unsigned>::iterator II 406 = DebugLocInfo.DebugIdMap.find(Tuple); 407 if (II != DebugLocInfo.DebugIdMap.end()) 408 return II->second; 409 // Add a new tuple. 410 unsigned Id = DebugLocInfo.DebugLocations.size(); 411 DebugLocInfo.DebugLocations.push_back(Tuple); 412 DebugLocInfo.DebugIdMap[Tuple] = Id; 413 return Id; 414} 415 416/// getDebugLocTuple - Get the DebugLocTuple for a given DebugLoc object. 417DebugLocTuple MachineFunction::getDebugLocTuple(DebugLoc DL) const { 418 unsigned Idx = DL.getIndex(); 419 assert(Idx < DebugLocInfo.DebugLocations.size() && 420 "Invalid index into debug locations!"); 421 return DebugLocInfo.DebugLocations[Idx]; 422} 423 424//===----------------------------------------------------------------------===// 425// MachineFrameInfo implementation 426//===----------------------------------------------------------------------===// 427 428/// CreateFixedObject - Create a new object at a fixed location on the stack. 429/// All fixed objects should be created before other objects are created for 430/// efficiency. By default, fixed objects are immutable. This returns an 431/// index with a negative value. 432/// 433int MachineFrameInfo::CreateFixedObject(uint64_t Size, int64_t SPOffset, 434 bool Immutable) { 435 assert(Size != 0 && "Cannot allocate zero size fixed stack objects!"); 436 Objects.insert(Objects.begin(), StackObject(Size, 1, SPOffset, Immutable)); 437 return -++NumFixedObjects; 438} 439 440 441void MachineFrameInfo::print(const MachineFunction &MF, std::ostream &OS) const{ 442 const TargetFrameInfo *FI = MF.getTarget().getFrameInfo(); 443 int ValOffset = (FI ? FI->getOffsetOfLocalArea() : 0); 444 445 for (unsigned i = 0, e = Objects.size(); i != e; ++i) { 446 const StackObject &SO = Objects[i]; 447 OS << " <fi#" << (int)(i-NumFixedObjects) << ">: "; 448 if (SO.Size == ~0ULL) { 449 OS << "dead\n"; 450 continue; 451 } 452 if (SO.Size == 0) 453 OS << "variable sized"; 454 else 455 OS << "size is " << SO.Size << " byte" << (SO.Size != 1 ? "s," : ","); 456 OS << " alignment is " << SO.Alignment << " byte" 457 << (SO.Alignment != 1 ? "s," : ","); 458 459 if (i < NumFixedObjects) 460 OS << " fixed"; 461 if (i < NumFixedObjects || SO.SPOffset != -1) { 462 int64_t Off = SO.SPOffset - ValOffset; 463 OS << " at location [SP"; 464 if (Off > 0) 465 OS << "+" << Off; 466 else if (Off < 0) 467 OS << Off; 468 OS << "]"; 469 } 470 OS << "\n"; 471 } 472 473 if (HasVarSizedObjects) 474 OS << " Stack frame contains variable sized objects\n"; 475} 476 477void MachineFrameInfo::dump(const MachineFunction &MF) const { 478 print(MF, *cerr.stream()); 479} 480 481 482//===----------------------------------------------------------------------===// 483// MachineJumpTableInfo implementation 484//===----------------------------------------------------------------------===// 485 486/// getJumpTableIndex - Create a new jump table entry in the jump table info 487/// or return an existing one. 488/// 489unsigned MachineJumpTableInfo::getJumpTableIndex( 490 const std::vector<MachineBasicBlock*> &DestBBs) { 491 assert(!DestBBs.empty() && "Cannot create an empty jump table!"); 492 for (unsigned i = 0, e = JumpTables.size(); i != e; ++i) 493 if (JumpTables[i].MBBs == DestBBs) 494 return i; 495 496 JumpTables.push_back(MachineJumpTableEntry(DestBBs)); 497 return JumpTables.size()-1; 498} 499 500/// ReplaceMBBInJumpTables - If Old is the target of any jump tables, update 501/// the jump tables to branch to New instead. 502bool 503MachineJumpTableInfo::ReplaceMBBInJumpTables(MachineBasicBlock *Old, 504 MachineBasicBlock *New) { 505 assert(Old != New && "Not making a change?"); 506 bool MadeChange = false; 507 for (size_t i = 0, e = JumpTables.size(); i != e; ++i) { 508 MachineJumpTableEntry &JTE = JumpTables[i]; 509 for (size_t j = 0, e = JTE.MBBs.size(); j != e; ++j) 510 if (JTE.MBBs[j] == Old) { 511 JTE.MBBs[j] = New; 512 MadeChange = true; 513 } 514 } 515 return MadeChange; 516} 517 518void MachineJumpTableInfo::print(std::ostream &OS) const { 519 // FIXME: this is lame, maybe we could print out the MBB numbers or something 520 // like {1, 2, 4, 5, 3, 0} 521 for (unsigned i = 0, e = JumpTables.size(); i != e; ++i) { 522 OS << " <jt#" << i << "> has " << JumpTables[i].MBBs.size() 523 << " entries\n"; 524 } 525} 526 527void MachineJumpTableInfo::dump() const { print(*cerr.stream()); } 528 529 530//===----------------------------------------------------------------------===// 531// MachineConstantPool implementation 532//===----------------------------------------------------------------------===// 533 534const Type *MachineConstantPoolEntry::getType() const { 535 if (isMachineConstantPoolEntry()) 536 return Val.MachineCPVal->getType(); 537 return Val.ConstVal->getType(); 538} 539 540MachineConstantPool::~MachineConstantPool() { 541 for (unsigned i = 0, e = Constants.size(); i != e; ++i) 542 if (Constants[i].isMachineConstantPoolEntry()) 543 delete Constants[i].Val.MachineCPVal; 544} 545 546/// getConstantPoolIndex - Create a new entry in the constant pool or return 547/// an existing one. User must specify the log2 of the minimum required 548/// alignment for the object. 549/// 550unsigned MachineConstantPool::getConstantPoolIndex(Constant *C, 551 unsigned Alignment) { 552 assert(Alignment && "Alignment must be specified!"); 553 if (Alignment > PoolAlignment) PoolAlignment = Alignment; 554 555 // Check to see if we already have this constant. 556 // 557 // FIXME, this could be made much more efficient for large constant pools. 558 for (unsigned i = 0, e = Constants.size(); i != e; ++i) 559 if (Constants[i].Val.ConstVal == C && 560 (Constants[i].getAlignment() & (Alignment - 1)) == 0) 561 return i; 562 563 Constants.push_back(MachineConstantPoolEntry(C, Alignment)); 564 return Constants.size()-1; 565} 566 567unsigned MachineConstantPool::getConstantPoolIndex(MachineConstantPoolValue *V, 568 unsigned Alignment) { 569 assert(Alignment && "Alignment must be specified!"); 570 if (Alignment > PoolAlignment) PoolAlignment = Alignment; 571 572 // Check to see if we already have this constant. 573 // 574 // FIXME, this could be made much more efficient for large constant pools. 575 int Idx = V->getExistingMachineCPValue(this, Alignment); 576 if (Idx != -1) 577 return (unsigned)Idx; 578 579 Constants.push_back(MachineConstantPoolEntry(V, Alignment)); 580 return Constants.size()-1; 581} 582 583void MachineConstantPool::print(raw_ostream &OS) const { 584 for (unsigned i = 0, e = Constants.size(); i != e; ++i) { 585 OS << " <cp#" << i << "> is"; 586 if (Constants[i].isMachineConstantPoolEntry()) 587 Constants[i].Val.MachineCPVal->print(OS); 588 else 589 OS << *(Value*)Constants[i].Val.ConstVal; 590 OS << " , alignment=" << Constants[i].getAlignment(); 591 OS << "\n"; 592 } 593} 594 595void MachineConstantPool::dump() const { print(errs()); } 596