LLVM API Documentation

MachineFunction.cpp

Go to the documentation of this file.
00001 //===-- MachineFunction.cpp -----------------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Collect native machine code information for a function.  This allows
00011 // target-specific information about the generated code to be stored with each
00012 // function.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/DerivedTypes.h"
00017 #include "llvm/Function.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/ADT/STLExtras.h"
00020 #include "llvm/Config/config.h"
00021 #include "llvm/CodeGen/MachineConstantPool.h"
00022 #include "llvm/CodeGen/MachineFunction.h"
00023 #include "llvm/CodeGen/MachineFunctionPass.h"
00024 #include "llvm/CodeGen/MachineFrameInfo.h"
00025 #include "llvm/CodeGen/MachineInstr.h"
00026 #include "llvm/CodeGen/MachineJumpTableInfo.h"
00027 #include "llvm/CodeGen/MachineRegisterInfo.h"
00028 #include "llvm/CodeGen/Passes.h"
00029 #include "llvm/Target/TargetData.h"
00030 #include "llvm/Target/TargetLowering.h"
00031 #include "llvm/Target/TargetMachine.h"
00032 #include "llvm/Target/TargetFrameInfo.h"
00033 #include "llvm/Support/Compiler.h"
00034 #include "llvm/Support/GraphWriter.h"
00035 #include "llvm/Support/raw_ostream.h"
00036 #include <fstream>
00037 #include <sstream>
00038 using namespace llvm;
00039 
00040 namespace {
00041   struct VISIBILITY_HIDDEN Printer : public MachineFunctionPass {
00042     static char ID;
00043 
00044     std::ostream *OS;
00045     const std::string Banner;
00046 
00047     Printer (std::ostream *os, const std::string &banner) 
00048       : MachineFunctionPass(&ID), OS(os), Banner(banner) {}
00049 
00050     const char *getPassName() const { return "MachineFunction Printer"; }
00051 
00052     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00053       AU.setPreservesAll();
00054       MachineFunctionPass::getAnalysisUsage(AU);
00055     }
00056 
00057     bool runOnMachineFunction(MachineFunction &MF) {
00058       (*OS) << Banner;
00059       MF.print (*OS);
00060       return false;
00061     }
00062   };
00063   char Printer::ID = 0;
00064 }
00065 
00066 /// Returns a newly-created MachineFunction Printer pass. The default banner is
00067 /// empty.
00068 ///
00069 FunctionPass *llvm::createMachineFunctionPrinterPass(std::ostream *OS,
00070                                                      const std::string &Banner){
00071   return new Printer(OS, Banner);
00072 }
00073 
00074 //===---------------------------------------------------------------------===//
00075 // MachineFunction implementation
00076 //===---------------------------------------------------------------------===//
00077 
00078 void ilist_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) {
00079   MBB->getParent()->DeleteMachineBasicBlock(MBB);
00080 }
00081 
00082 MachineFunction::MachineFunction(Function *F,
00083                                  const TargetMachine &TM)
00084   : Fn(F), Target(TM) {
00085   if (TM.getRegisterInfo())
00086     RegInfo = new (Allocator.Allocate<MachineRegisterInfo>())
00087                   MachineRegisterInfo(*TM.getRegisterInfo());
00088   else
00089     RegInfo = 0;
00090   MFInfo = 0;
00091   FrameInfo = new (Allocator.Allocate<MachineFrameInfo>())
00092                   MachineFrameInfo(*TM.getFrameInfo());
00093   ConstantPool = new (Allocator.Allocate<MachineConstantPool>())
00094                      MachineConstantPool(TM.getTargetData());
00095   Alignment = TM.getTargetLowering()->getFunctionAlignment(F);
00096 
00097   // Set up jump table.
00098   const TargetData &TD = *TM.getTargetData();
00099   bool IsPic = TM.getRelocationModel() == Reloc::PIC_;
00100   unsigned EntrySize = IsPic ? 4 : TD.getPointerSize();
00101   unsigned TyAlignment = IsPic ?
00102                        TD.getABITypeAlignment(Type::getInt32Ty(F->getContext()))
00103                                : TD.getPointerABIAlignment();
00104   JumpTableInfo = new (Allocator.Allocate<MachineJumpTableInfo>())
00105                       MachineJumpTableInfo(EntrySize, TyAlignment);
00106 }
00107 
00108 MachineFunction::~MachineFunction() {
00109   BasicBlocks.clear();
00110   InstructionRecycler.clear(Allocator);
00111   BasicBlockRecycler.clear(Allocator);
00112   if (RegInfo) {
00113     RegInfo->~MachineRegisterInfo();
00114     Allocator.Deallocate(RegInfo);
00115   }
00116   if (MFInfo) {
00117     MFInfo->~MachineFunctionInfo();
00118     Allocator.Deallocate(MFInfo);
00119   }
00120   FrameInfo->~MachineFrameInfo();         Allocator.Deallocate(FrameInfo);
00121   ConstantPool->~MachineConstantPool();   Allocator.Deallocate(ConstantPool);
00122   JumpTableInfo->~MachineJumpTableInfo(); Allocator.Deallocate(JumpTableInfo);
00123 }
00124 
00125 
00126 /// RenumberBlocks - This discards all of the MachineBasicBlock numbers and
00127 /// recomputes them.  This guarantees that the MBB numbers are sequential,
00128 /// dense, and match the ordering of the blocks within the function.  If a
00129 /// specific MachineBasicBlock is specified, only that block and those after
00130 /// it are renumbered.
00131 void MachineFunction::RenumberBlocks(MachineBasicBlock *MBB) {
00132   if (empty()) { MBBNumbering.clear(); return; }
00133   MachineFunction::iterator MBBI, E = end();
00134   if (MBB == 0)
00135     MBBI = begin();
00136   else
00137     MBBI = MBB;
00138   
00139   // Figure out the block number this should have.
00140   unsigned BlockNo = 0;
00141   if (MBBI != begin())
00142     BlockNo = prior(MBBI)->getNumber()+1;
00143   
00144   for (; MBBI != E; ++MBBI, ++BlockNo) {
00145     if (MBBI->getNumber() != (int)BlockNo) {
00146       // Remove use of the old number.
00147       if (MBBI->getNumber() != -1) {
00148         assert(MBBNumbering[MBBI->getNumber()] == &*MBBI &&
00149                "MBB number mismatch!");
00150         MBBNumbering[MBBI->getNumber()] = 0;
00151       }
00152       
00153       // If BlockNo is already taken, set that block's number to -1.
00154       if (MBBNumbering[BlockNo])
00155         MBBNumbering[BlockNo]->setNumber(-1);
00156 
00157       MBBNumbering[BlockNo] = MBBI;
00158       MBBI->setNumber(BlockNo);
00159     }
00160   }    
00161 
00162   // Okay, all the blocks are renumbered.  If we have compactified the block
00163   // numbering, shrink MBBNumbering now.
00164   assert(BlockNo <= MBBNumbering.size() && "Mismatch!");
00165   MBBNumbering.resize(BlockNo);
00166 }
00167 
00168 /// CreateMachineInstr - Allocate a new MachineInstr. Use this instead
00169 /// of `new MachineInstr'.
00170 ///
00171 MachineInstr *
00172 MachineFunction::CreateMachineInstr(const TargetInstrDesc &TID,
00173                                     DebugLoc DL, bool NoImp) {
00174   return new (InstructionRecycler.Allocate<MachineInstr>(Allocator))
00175     MachineInstr(TID, DL, NoImp);
00176 }
00177 
00178 /// CloneMachineInstr - Create a new MachineInstr which is a copy of the
00179 /// 'Orig' instruction, identical in all ways except the the instruction
00180 /// has no parent, prev, or next.
00181 ///
00182 MachineInstr *
00183 MachineFunction::CloneMachineInstr(const MachineInstr *Orig) {
00184   return new (InstructionRecycler.Allocate<MachineInstr>(Allocator))
00185              MachineInstr(*this, *Orig);
00186 }
00187 
00188 /// DeleteMachineInstr - Delete the given MachineInstr.
00189 ///
00190 void
00191 MachineFunction::DeleteMachineInstr(MachineInstr *MI) {
00192   // Clear the instructions memoperands. This must be done manually because
00193   // the instruction's parent pointer is now null, so it can't properly
00194   // deallocate them on its own.
00195   MI->clearMemOperands(*this);
00196 
00197   MI->~MachineInstr();
00198   InstructionRecycler.Deallocate(Allocator, MI);
00199 }
00200 
00201 /// CreateMachineBasicBlock - Allocate a new MachineBasicBlock. Use this
00202 /// instead of `new MachineBasicBlock'.
00203 ///
00204 MachineBasicBlock *
00205 MachineFunction::CreateMachineBasicBlock(const BasicBlock *bb) {
00206   return new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator))
00207              MachineBasicBlock(*this, bb);
00208 }
00209 
00210 /// DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
00211 ///
00212 void
00213 MachineFunction::DeleteMachineBasicBlock(MachineBasicBlock *MBB) {
00214   assert(MBB->getParent() == this && "MBB parent mismatch!");
00215   MBB->~MachineBasicBlock();
00216   BasicBlockRecycler.Deallocate(Allocator, MBB);
00217 }
00218 
00219 void MachineFunction::dump() const {
00220   print(*cerr.stream());
00221 }
00222 
00223 void MachineFunction::print(std::ostream &OS,
00224                             const PrefixPrinter &prefix) const {
00225   OS << "# Machine code for " << Fn->getNameStr () << "():\n";
00226 
00227   // Print Frame Information
00228   FrameInfo->print(*this, OS);
00229   
00230   // Print JumpTable Information
00231   JumpTableInfo->print(OS);
00232 
00233   // Print Constant Pool
00234   {
00235     raw_os_ostream OSS(OS);
00236     ConstantPool->print(OSS);
00237   }
00238   
00239   const TargetRegisterInfo *TRI = getTarget().getRegisterInfo();
00240   
00241   if (RegInfo && !RegInfo->livein_empty()) {
00242     OS << "Live Ins:";
00243     for (MachineRegisterInfo::livein_iterator
00244          I = RegInfo->livein_begin(), E = RegInfo->livein_end(); I != E; ++I) {
00245       if (TRI)
00246         OS << " " << TRI->getName(I->first);
00247       else
00248         OS << " Reg #" << I->first;
00249       
00250       if (I->second)
00251         OS << " in VR#" << I->second << " ";
00252     }
00253     OS << "\n";
00254   }
00255   if (RegInfo && !RegInfo->liveout_empty()) {
00256     OS << "Live Outs:";
00257     for (MachineRegisterInfo::liveout_iterator
00258          I = RegInfo->liveout_begin(), E = RegInfo->liveout_end(); I != E; ++I)
00259       if (TRI)
00260         OS << " " << TRI->getName(*I);
00261       else
00262         OS << " Reg #" << *I;
00263     OS << "\n";
00264   }
00265   
00266   for (const_iterator BB = begin(); BB != end(); ++BB) {
00267     prefix(OS, *BB);
00268     BB->print(OS, prefix);
00269   }
00270 
00271   OS << "\n# End machine code for " << Fn->getNameStr () << "().\n\n";
00272 }
00273 
00274 namespace llvm {
00275   template<>
00276   struct DOTGraphTraits<const MachineFunction*> : public DefaultDOTGraphTraits {
00277     static std::string getGraphName(const MachineFunction *F) {
00278       return "CFG for '" + F->getFunction()->getNameStr() + "' function";
00279     }
00280 
00281     static std::string getNodeLabel(const MachineBasicBlock *Node,
00282                                     const MachineFunction *Graph,
00283                                     bool ShortNames) {
00284       if (ShortNames && Node->getBasicBlock() &&
00285           !Node->getBasicBlock()->getName().empty())
00286         return Node->getBasicBlock()->getNameStr() + ":";
00287 
00288       std::ostringstream Out;
00289       if (ShortNames) {
00290         Out << Node->getNumber() << ':';
00291         return Out.str();
00292       }
00293 
00294       Node->print(Out);
00295 
00296       std::string OutStr = Out.str();
00297       if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
00298 
00299       // Process string output to make it nicer...
00300       for (unsigned i = 0; i != OutStr.length(); ++i)
00301         if (OutStr[i] == '\n') {                            // Left justify
00302           OutStr[i] = '\\';
00303           OutStr.insert(OutStr.begin()+i+1, 'l');
00304         }
00305       return OutStr;
00306     }
00307   };
00308 }
00309 
00310 void MachineFunction::viewCFG() const
00311 {
00312 #ifndef NDEBUG
00313   ViewGraph(this, "mf" + getFunction()->getNameStr());
00314 #else
00315   cerr << "SelectionDAG::viewGraph is only available in debug builds on "
00316        << "systems with Graphviz or gv!\n";
00317 #endif // NDEBUG
00318 }
00319 
00320 void MachineFunction::viewCFGOnly() const
00321 {
00322 #ifndef NDEBUG
00323   ViewGraph(this, "mf" + getFunction()->getNameStr(), true);
00324 #else
00325   cerr << "SelectionDAG::viewGraph is only available in debug builds on "
00326        << "systems with Graphviz or gv!\n";
00327 #endif // NDEBUG
00328 }
00329 
00330 /// addLiveIn - Add the specified physical register as a live-in value and
00331 /// create a corresponding virtual register for it.
00332 unsigned MachineFunction::addLiveIn(unsigned PReg,
00333                                     const TargetRegisterClass *RC) {
00334   assert(RC->contains(PReg) && "Not the correct regclass!");
00335   unsigned VReg = getRegInfo().createVirtualRegister(RC);
00336   getRegInfo().addLiveIn(PReg, VReg);
00337   return VReg;
00338 }
00339 
00340 /// getOrCreateDebugLocID - Look up the DebugLocTuple index with the given
00341 /// source file, line, and column. If none currently exists, create a new
00342 /// DebugLocTuple, and insert it into the DebugIdMap.
00343 unsigned MachineFunction::getOrCreateDebugLocID(GlobalVariable *CompileUnit,
00344                                                 unsigned Line, unsigned Col) {
00345   DebugLocTuple Tuple(CompileUnit, Line, Col);
00346   DenseMap<DebugLocTuple, unsigned>::iterator II
00347     = DebugLocInfo.DebugIdMap.find(Tuple);
00348   if (II != DebugLocInfo.DebugIdMap.end())
00349     return II->second;
00350   // Add a new tuple.
00351   unsigned Id = DebugLocInfo.DebugLocations.size();
00352   DebugLocInfo.DebugLocations.push_back(Tuple);
00353   DebugLocInfo.DebugIdMap[Tuple] = Id;
00354   return Id;
00355 }
00356 
00357 /// getDebugLocTuple - Get the DebugLocTuple for a given DebugLoc object.
00358 DebugLocTuple MachineFunction::getDebugLocTuple(DebugLoc DL) const {
00359   unsigned Idx = DL.getIndex();
00360   assert(Idx < DebugLocInfo.DebugLocations.size() &&
00361          "Invalid index into debug locations!");
00362   return DebugLocInfo.DebugLocations[Idx];
00363 }
00364 
00365 //===----------------------------------------------------------------------===//
00366 //  MachineFrameInfo implementation
00367 //===----------------------------------------------------------------------===//
00368 
00369 /// CreateFixedObject - Create a new object at a fixed location on the stack.
00370 /// All fixed objects should be created before other objects are created for
00371 /// efficiency. By default, fixed objects are immutable. This returns an
00372 /// index with a negative value.
00373 ///
00374 int MachineFrameInfo::CreateFixedObject(uint64_t Size, int64_t SPOffset,
00375                                         bool Immutable) {
00376   assert(Size != 0 && "Cannot allocate zero size fixed stack objects!");
00377   Objects.insert(Objects.begin(), StackObject(Size, 1, SPOffset, Immutable));
00378   return -++NumFixedObjects;
00379 }
00380 
00381 
00382 BitVector
00383 MachineFrameInfo::getPristineRegs(const MachineBasicBlock *MBB) const {
00384   assert(MBB && "MBB must be valid");
00385   const MachineFunction *MF = MBB->getParent();
00386   assert(MF && "MBB must be part of a MachineFunction");
00387   const TargetMachine &TM = MF->getTarget();
00388   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
00389   BitVector BV(TRI->getNumRegs());
00390 
00391   // Before CSI is calculated, no registers are considered pristine. They can be
00392   // freely used and PEI will make sure they are saved.
00393   if (!isCalleeSavedInfoValid())
00394     return BV;
00395 
00396   for (const unsigned *CSR = TRI->getCalleeSavedRegs(MF); CSR && *CSR; ++CSR)
00397     BV.set(*CSR);
00398 
00399   // The entry MBB always has all CSRs pristine.
00400   if (MBB == &MF->front())
00401     return BV;
00402 
00403   // On other MBBs the saved CSRs are not pristine.
00404   const std::vector<CalleeSavedInfo> &CSI = getCalleeSavedInfo();
00405   for (std::vector<CalleeSavedInfo>::const_iterator I = CSI.begin(),
00406          E = CSI.end(); I != E; ++I)
00407     BV.reset(I->getReg());
00408 
00409   return BV;
00410 }
00411 
00412 
00413 void MachineFrameInfo::print(const MachineFunction &MF, std::ostream &OS) const{
00414   const TargetFrameInfo *FI = MF.getTarget().getFrameInfo();
00415   int ValOffset = (FI ? FI->getOffsetOfLocalArea() : 0);
00416 
00417   for (unsigned i = 0, e = Objects.size(); i != e; ++i) {
00418     const StackObject &SO = Objects[i];
00419     OS << "  <fi#" << (int)(i-NumFixedObjects) << ">: ";
00420     if (SO.Size == ~0ULL) {
00421       OS << "dead\n";
00422       continue;
00423     }
00424     if (SO.Size == 0)
00425       OS << "variable sized";
00426     else
00427       OS << "size is " << SO.Size << " byte" << (SO.Size != 1 ? "s," : ",");
00428     OS << " alignment is " << SO.Alignment << " byte"
00429        << (SO.Alignment != 1 ? "s," : ",");
00430 
00431     if (i < NumFixedObjects)
00432       OS << " fixed";
00433     if (i < NumFixedObjects || SO.SPOffset != -1) {
00434       int64_t Off = SO.SPOffset - ValOffset;
00435       OS << " at location [SP";
00436       if (Off > 0)
00437         OS << "+" << Off;
00438       else if (Off < 0)
00439         OS << Off;
00440       OS << "]";
00441     }
00442     OS << "\n";
00443   }
00444 
00445   if (HasVarSizedObjects)
00446     OS << "  Stack frame contains variable sized objects\n";
00447 }
00448 
00449 void MachineFrameInfo::dump(const MachineFunction &MF) const {
00450   print(MF, *cerr.stream());
00451 }
00452 
00453 //===----------------------------------------------------------------------===//
00454 //  MachineJumpTableInfo implementation
00455 //===----------------------------------------------------------------------===//
00456 
00457 /// getJumpTableIndex - Create a new jump table entry in the jump table info
00458 /// or return an existing one.
00459 ///
00460 unsigned MachineJumpTableInfo::getJumpTableIndex(
00461                                const std::vector<MachineBasicBlock*> &DestBBs) {
00462   assert(!DestBBs.empty() && "Cannot create an empty jump table!");
00463   for (unsigned i = 0, e = JumpTables.size(); i != e; ++i)
00464     if (JumpTables[i].MBBs == DestBBs)
00465       return i;
00466   
00467   JumpTables.push_back(MachineJumpTableEntry(DestBBs));
00468   return JumpTables.size()-1;
00469 }
00470 
00471 /// ReplaceMBBInJumpTables - If Old is the target of any jump tables, update
00472 /// the jump tables to branch to New instead.
00473 bool
00474 MachineJumpTableInfo::ReplaceMBBInJumpTables(MachineBasicBlock *Old,
00475                                              MachineBasicBlock *New) {
00476   assert(Old != New && "Not making a change?");
00477   bool MadeChange = false;
00478   for (size_t i = 0, e = JumpTables.size(); i != e; ++i) {
00479     MachineJumpTableEntry &JTE = JumpTables[i];
00480     for (size_t j = 0, e = JTE.MBBs.size(); j != e; ++j)
00481       if (JTE.MBBs[j] == Old) {
00482         JTE.MBBs[j] = New;
00483         MadeChange = true;
00484       }
00485   }
00486   return MadeChange;
00487 }
00488 
00489 void MachineJumpTableInfo::print(std::ostream &OS) const {
00490   // FIXME: this is lame, maybe we could print out the MBB numbers or something
00491   // like {1, 2, 4, 5, 3, 0}
00492   for (unsigned i = 0, e = JumpTables.size(); i != e; ++i) {
00493     OS << "  <jt#" << i << "> has " << JumpTables[i].MBBs.size() 
00494        << " entries\n";
00495   }
00496 }
00497 
00498 void MachineJumpTableInfo::dump() const { print(*cerr.stream()); }
00499 
00500 
00501 //===----------------------------------------------------------------------===//
00502 //  MachineConstantPool implementation
00503 //===----------------------------------------------------------------------===//
00504 
00505 const Type *MachineConstantPoolEntry::getType() const {
00506   if (isMachineConstantPoolEntry())
00507     return Val.MachineCPVal->getType();
00508   return Val.ConstVal->getType();
00509 }
00510 
00511 
00512 unsigned MachineConstantPoolEntry::getRelocationInfo() const {
00513   if (isMachineConstantPoolEntry())
00514     return Val.MachineCPVal->getRelocationInfo();
00515   return Val.ConstVal->getRelocationInfo();
00516 }
00517 
00518 MachineConstantPool::~MachineConstantPool() {
00519   for (unsigned i = 0, e = Constants.size(); i != e; ++i)
00520     if (Constants[i].isMachineConstantPoolEntry())
00521       delete Constants[i].Val.MachineCPVal;
00522 }
00523 
00524 /// getConstantPoolIndex - Create a new entry in the constant pool or return
00525 /// an existing one.  User must specify the log2 of the minimum required
00526 /// alignment for the object.
00527 ///
00528 unsigned MachineConstantPool::getConstantPoolIndex(Constant *C, 
00529                                                    unsigned Alignment) {
00530   assert(Alignment && "Alignment must be specified!");
00531   if (Alignment > PoolAlignment) PoolAlignment = Alignment;
00532   
00533   // Check to see if we already have this constant.
00534   //
00535   // FIXME, this could be made much more efficient for large constant pools.
00536   for (unsigned i = 0, e = Constants.size(); i != e; ++i)
00537     if (Constants[i].Val.ConstVal == C &&
00538         (Constants[i].getAlignment() & (Alignment - 1)) == 0)
00539       return i;
00540   
00541   Constants.push_back(MachineConstantPoolEntry(C, Alignment));
00542   return Constants.size()-1;
00543 }
00544 
00545 unsigned MachineConstantPool::getConstantPoolIndex(MachineConstantPoolValue *V,
00546                                                    unsigned Alignment) {
00547   assert(Alignment && "Alignment must be specified!");
00548   if (Alignment > PoolAlignment) PoolAlignment = Alignment;
00549   
00550   // Check to see if we already have this constant.
00551   //
00552   // FIXME, this could be made much more efficient for large constant pools.
00553   int Idx = V->getExistingMachineCPValue(this, Alignment);
00554   if (Idx != -1)
00555     return (unsigned)Idx;
00556 
00557   Constants.push_back(MachineConstantPoolEntry(V, Alignment));
00558   return Constants.size()-1;
00559 }
00560 
00561 void MachineConstantPool::print(raw_ostream &OS) const {
00562   for (unsigned i = 0, e = Constants.size(); i != e; ++i) {
00563     OS << "  <cp#" << i << "> is";
00564     if (Constants[i].isMachineConstantPoolEntry())
00565       Constants[i].Val.MachineCPVal->print(OS);
00566     else
00567       OS << *(Value*)Constants[i].Val.ConstVal;
00568     OS << " , alignment=" << Constants[i].getAlignment();
00569     OS << "\n";
00570   }
00571 }
00572 
00573 void MachineConstantPool::dump() const { print(errs()); }