lib/CodeGen/MachineFunction.cpp

   1 //===-- MachineFunction.cpp -----------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/CodeGen/MachineFunctionPass.h"
  17 #include "llvm/CodeGen/MachineInstr.h"
  18 #include "llvm/CodeGen/SSARegMap.h"
  19 #include "llvm/CodeGen/MachineFrameInfo.h"
  20 #include "llvm/CodeGen/MachineConstantPool.h"
  21 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  22 #include "llvm/CodeGen/Passes.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetFrameInfo.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/Instructions.h"
  28 #include "llvm/Support/Compiler.h"
  29 #include "llvm/Support/GraphWriter.h"
  30 #include "llvm/Support/LeakDetector.h"
  31 #include "llvm/ADT/STLExtras.h"
  32 #include "llvm/Config/config.h"
  33 #include <fstream>
  34 #include <sstream>
  35 using namespace llvm;
  36
  37 static AnnotationID MF_AID(
  38   AnnotationManager::getID("CodeGen::MachineCodeForFunction"));
  39
  40 // Out of line virtual function to home classes.
  41 void MachineFunctionPass::virtfn() {}
  42
  43 namespace {
  44   struct VISIBILITY_HIDDEN Printer : public MachineFunctionPass {
  45     std::ostream *OS;
  46     const std::string Banner;
  47
  48     Printer (std::ostream *_OS, const std::string &_Banner) :
  49       OS (_OS), Banner (_Banner) { }
  50
  51     const char *getPassName() const { return "MachineFunction Printer"; }
  52
  53     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  54       AU.setPreservesAll();
  55     }
  56
  57     bool runOnMachineFunction(MachineFunction &MF) {
  58       (*OS) << Banner;
  59       MF.print (*OS);
  60       return false;
  61     }
  62   };
  63 }
  64
  65 /// Returns a newly-created MachineFunction Printer pass. The default output
  66 /// stream is std::cerr; the default banner is empty.
  67 ///
  68 FunctionPass *llvm::createMachineFunctionPrinterPass(std::ostream *OS,
  69                                                      const std::string &Banner){
  70   return new Printer(OS, Banner);
  71 }
  72
  73 namespace {
  74   struct VISIBILITY_HIDDEN Deleter : public MachineFunctionPass {
  75     const char *getPassName() const { return "Machine Code Deleter"; }
  76
  77     bool runOnMachineFunction(MachineFunction &MF) {
  78       // Delete the annotation from the function now.
  79       MachineFunction::destruct(MF.getFunction());
  80       return true;
  81     }
  82   };
  83 }
  84
  85 /// MachineCodeDeletion Pass - This pass deletes all of the machine code for
  86 /// the current function, which should happen after the function has been
  87 /// emitted to a .s file or to memory.
  88 FunctionPass *llvm::createMachineCodeDeleter() {
  89   return new Deleter();
  90 }
  91
  92
  93
  94 //===---------------------------------------------------------------------===//
  95 // MachineFunction implementation
  96 //===---------------------------------------------------------------------===//
  97
  98 MachineBasicBlock* ilist_traits<MachineBasicBlock>::createSentinel() {
  99   MachineBasicBlock* dummy = new MachineBasicBlock();
 100   LeakDetector::removeGarbageObject(dummy);
 101   return dummy;
 102 }
 103
 104 void ilist_traits<MachineBasicBlock>::transferNodesFromList(
 105   iplist<MachineBasicBlock, ilist_traits<MachineBasicBlock> >& toList,
 106   ilist_iterator<MachineBasicBlock> first,
 107   ilist_iterator<MachineBasicBlock> last) {
 108   if (Parent != toList.Parent)
 109     for (; first != last; ++first)
 110       first->Parent = toList.Parent;
 111 }
 112
 113 MachineFunction::MachineFunction(const Function *F,
 114                                  const TargetMachine &TM)
 115   : Annotation(MF_AID), Fn(F), Target(TM), UsedPhysRegs(0) {
 116   SSARegMapping = new SSARegMap();
 117   MFInfo = 0;
 118   FrameInfo = new MachineFrameInfo();
 119   ConstantPool = new MachineConstantPool(TM.getTargetData());
 120   JumpTableInfo = new MachineJumpTableInfo(TM.getTargetData());
 121   BasicBlocks.Parent = this;
 122 }
 123
 124 MachineFunction::~MachineFunction() {
 125   BasicBlocks.clear();
 126   delete SSARegMapping;
 127   delete MFInfo;
 128   delete FrameInfo;
 129   delete ConstantPool;
 130   delete JumpTableInfo;
 131   delete[] UsedPhysRegs;
 132 }
 133
 134
 135 /// RenumberBlocks - This discards all of the MachineBasicBlock numbers and
 136 /// recomputes them.  This guarantees that the MBB numbers are sequential,
 137 /// dense, and match the ordering of the blocks within the function.  If a
 138 /// specific MachineBasicBlock is specified, only that block and those after
 139 /// it are renumbered.
 140 void MachineFunction::RenumberBlocks(MachineBasicBlock *MBB) {
 141   if (empty()) { MBBNumbering.clear(); return; }
 142   MachineFunction::iterator MBBI, E = end();
 143   if (MBB == 0)
 144     MBBI = begin();
 145   else
 146     MBBI = MBB;
 147
 148   // Figure out the block number this should have.
 149   unsigned BlockNo = 0;
 150   if (MBBI != begin())
 151     BlockNo = prior(MBBI)->getNumber()+1;
 152
 153   for (; MBBI != E; ++MBBI, ++BlockNo) {
 154     if (MBBI->getNumber() != (int)BlockNo) {
 155       // Remove use of the old number.
 156       if (MBBI->getNumber() != -1) {
 157         assert(MBBNumbering[MBBI->getNumber()] == &*MBBI &&
 158                "MBB number mismatch!");
 159         MBBNumbering[MBBI->getNumber()] = 0;
 160       }
 161
 162       // If BlockNo is already taken, set that block's number to -1.
 163       if (MBBNumbering[BlockNo])
 164         MBBNumbering[BlockNo]->setNumber(-1);
 165
 166       MBBNumbering[BlockNo] = MBBI;
 167       MBBI->setNumber(BlockNo);
 168     }
 169   }
 170
 171   // Okay, all the blocks are renumbered.  If we have compactified the block
 172   // numbering, shrink MBBNumbering now.
 173   assert(BlockNo <= MBBNumbering.size() && "Mismatch!");
 174   MBBNumbering.resize(BlockNo);
 175 }
 176
 177
 178 void MachineFunction::dump() const { print(*cerr.stream()); }
 179
 180 void MachineFunction::print(std::ostream &OS) const {
 181   OS << "# Machine code for " << Fn->getName () << "():\n";
 182
 183   // Print Frame Information
 184   getFrameInfo()->print(*this, OS);
 185
 186   // Print JumpTable Information
 187   getJumpTableInfo()->print(OS);
 188
 189   // Print Constant Pool
 190   getConstantPool()->print(OS);
 191
 192   const MRegisterInfo *MRI = getTarget().getRegisterInfo();
 193
 194   if (livein_begin() != livein_end()) {
 195     OS << "Live Ins:";
 196     for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) {
 197       if (MRI)
 198         OS << " " << MRI->getName(I->first);
 199       else
 200         OS << " Reg #" << I->first;
 201
 202       if (I->second)
 203         OS << " in VR#" << I->second << " ";
 204     }
 205     OS << "\n";
 206   }
 207   if (liveout_begin() != liveout_end()) {
 208     OS << "Live Outs:";
 209     for (liveout_iterator I = liveout_begin(), E = liveout_end(); I != E; ++I)
 210       if (MRI)
 211         OS << " " << MRI->getName(*I);
 212       else
 213         OS << " Reg #" << *I;
 214     OS << "\n";
 215   }
 216
 217   for (const_iterator BB = begin(); BB != end(); ++BB)
 218     BB->print(OS);
 219
 220   OS << "\n# End machine code for " << Fn->getName () << "().\n\n";
 221 }
 222
 223 /// CFGOnly flag - This is used to control whether or not the CFG graph printer
 224 /// prints out the contents of basic blocks or not.  This is acceptable because
 225 /// this code is only really used for debugging purposes.
 226 ///
 227 static bool CFGOnly = false;
 228
 229 namespace llvm {
 230   template<>
 231   struct DOTGraphTraits<const MachineFunction*> : public DefaultDOTGraphTraits {
 232     static std::string getGraphName(const MachineFunction *F) {
 233       return "CFG for '" + F->getFunction()->getName() + "' function";
 234     }
 235
 236     static std::string getNodeLabel(const MachineBasicBlock *Node,
 237                                     const MachineFunction *Graph) {
 238       if (CFGOnly && Node->getBasicBlock() &&
 239           !Node->getBasicBlock()->getName().empty())
 240         return Node->getBasicBlock()->getName() + ":";
 241
 242       std::ostringstream Out;
 243       if (CFGOnly) {
 244         Out << Node->getNumber() << ':';
 245         return Out.str();
 246       }
 247
 248       Node->print(Out);
 249
 250       std::string OutStr = Out.str();
 251       if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
 252
 253       // Process string output to make it nicer...
 254       for (unsigned i = 0; i != OutStr.length(); ++i)
 255         if (OutStr[i] == '\n') {                            // Left justify
 256           OutStr[i] = '\\';
 257           OutStr.insert(OutStr.begin()+i+1, 'l');
 258         }
 259       return OutStr;
 260     }
 261   };
 262 }
 263
 264 void MachineFunction::viewCFG() const
 265 {
 266 #ifndef NDEBUG
 267   ViewGraph(this, "mf" + getFunction()->getName());
 268 #else
 269   cerr << "SelectionDAG::viewGraph is only available in debug builds on "
 270        << "systems with Graphviz or gv!\n";
 271 #endif // NDEBUG
 272 }
 273
 274 void MachineFunction::viewCFGOnly() const
 275 {
 276   CFGOnly = true;
 277   viewCFG();
 278   CFGOnly = false;
 279 }
 280
 281 // The next two methods are used to construct and to retrieve
 282 // the MachineCodeForFunction object for the given function.
 283 // construct() -- Allocates and initializes for a given function and target
 284 // get()       -- Returns a handle to the object.
 285 //                This should not be called before "construct()"
 286 //                for a given Function.
 287 //
 288 MachineFunction&
 289 MachineFunction::construct(const Function *Fn, const TargetMachine &Tar)
 290 {
 291   assert(Fn->getAnnotation(MF_AID) == 0 &&
 292          "Object already exists for this function!");
 293   MachineFunction* mcInfo = new MachineFunction(Fn, Tar);
 294   Fn->addAnnotation(mcInfo);
 295   return *mcInfo;
 296 }
 297
 298 void MachineFunction::destruct(const Function *Fn) {
 299   bool Deleted = Fn->deleteAnnotation(MF_AID);
 300   assert(Deleted && "Machine code did not exist for function!");
 301 }
 302
 303 MachineFunction& MachineFunction::get(const Function *F)
 304 {
 305   MachineFunction *mc = (MachineFunction*)F->getAnnotation(MF_AID);
 306   assert(mc && "Call construct() method first to allocate the object");
 307   return *mc;
 308 }
 309
 310 void MachineFunction::clearSSARegMap() {
 311   delete SSARegMapping;
 312   SSARegMapping = 0;
 313 }
 314
 315 //===----------------------------------------------------------------------===//
 316 //  MachineFrameInfo implementation
 317 //===----------------------------------------------------------------------===//
 318
 319 void MachineFrameInfo::print(const MachineFunction &MF, std::ostream &OS) const{
 320   int ValOffset = MF.getTarget().getFrameInfo()->getOffsetOfLocalArea();
 321
 322   for (unsigned i = 0, e = Objects.size(); i != e; ++i) {
 323     const StackObject &SO = Objects[i];
 324     OS << "  <fi #" << (int)(i-NumFixedObjects) << ">: ";
 325     if (SO.Size == 0)
 326       OS << "variable sized";
 327     else
 328       OS << "size is " << SO.Size << " byte" << (SO.Size != 1 ? "s," : ",");
 329     OS << " alignment is " << SO.Alignment << " byte"
 330        << (SO.Alignment != 1 ? "s," : ",");
 331
 332     if (i < NumFixedObjects)
 333       OS << " fixed";
 334     if (i < NumFixedObjects || SO.SPOffset != -1) {
 335       int Off = SO.SPOffset - ValOffset;
 336       OS << " at location [SP";
 337       if (Off > 0)
 338         OS << "+" << Off;
 339       else if (Off < 0)
 340         OS << Off;
 341       OS << "]";
 342     }
 343     OS << "\n";
 344   }
 345
 346   if (HasVarSizedObjects)
 347     OS << "  Stack frame contains variable sized objects\n";
 348 }
 349
 350 void MachineFrameInfo::dump(const MachineFunction &MF) const {
 351   print(MF, *cerr.stream());
 352 }
 353
 354
 355 //===----------------------------------------------------------------------===//
 356 //  MachineJumpTableInfo implementation
 357 //===----------------------------------------------------------------------===//
 358
 359 /// getJumpTableIndex - Create a new jump table entry in the jump table info
 360 /// or return an existing one.
 361 ///
 362 unsigned MachineJumpTableInfo::getJumpTableIndex(
 363                                const std::vector<MachineBasicBlock*> &DestBBs) {
 364   assert(!DestBBs.empty() && "Cannot create an empty jump table!");
 365   for (unsigned i = 0, e = JumpTables.size(); i != e; ++i)
 366     if (JumpTables[i].MBBs == DestBBs)
 367       return i;
 368
 369   JumpTables.push_back(MachineJumpTableEntry(DestBBs));
 370   return JumpTables.size()-1;
 371 }
 372
 373
 374 void MachineJumpTableInfo::print(std::ostream &OS) const {
 375   // FIXME: this is lame, maybe we could print out the MBB numbers or something
 376   // like {1, 2, 4, 5, 3, 0}
 377   for (unsigned i = 0, e = JumpTables.size(); i != e; ++i) {
 378     OS << "  <jt #" << i << "> has " << JumpTables[i].MBBs.size()
 379        << " entries\n";
 380   }
 381 }
 382
 383 unsigned MachineJumpTableInfo::getEntrySize() const {
 384   return TD->getPointerSize();
 385 }
 386
 387 unsigned MachineJumpTableInfo::getAlignment() const {
 388   return TD->getPointerAlignment();
 389 }
 390
 391 void MachineJumpTableInfo::dump() const { print(*cerr.stream()); }
 392
 393
 394 //===----------------------------------------------------------------------===//
 395 //  MachineConstantPool implementation
 396 //===----------------------------------------------------------------------===//
 397
 398 const Type *MachineConstantPoolEntry::getType() const {
 399   if (isMachineConstantPoolEntry())
 400       return Val.MachineCPVal->getType();
 401   return Val.ConstVal->getType();
 402 }
 403
 404 MachineConstantPool::~MachineConstantPool() {
 405   for (unsigned i = 0, e = Constants.size(); i != e; ++i)
 406     if (Constants[i].isMachineConstantPoolEntry())
 407       delete Constants[i].Val.MachineCPVal;
 408 }
 409
 410 /// getConstantPoolIndex - Create a new entry in the constant pool or return
 411 /// an existing one.  User must specify an alignment in bytes for the object.
 412 ///
 413 unsigned MachineConstantPool::getConstantPoolIndex(Constant *C,
 414                                                    unsigned Alignment) {
 415   assert(Alignment && "Alignment must be specified!");
 416   if (Alignment > PoolAlignment) PoolAlignment = Alignment;
 417
 418   // Check to see if we already have this constant.
 419   //
 420   // FIXME, this could be made much more efficient for large constant pools.
 421   unsigned AlignMask = (1 << Alignment)-1;
 422   for (unsigned i = 0, e = Constants.size(); i != e; ++i)
 423     if (Constants[i].Val.ConstVal == C && (Constants[i].Offset & AlignMask)== 0)
 424       return i;
 425
 426   unsigned Offset = 0;
 427   if (!Constants.empty()) {
 428     Offset = Constants.back().getOffset();
 429     Offset += TD->getTypeSize(Constants.back().getType());
 430     Offset = (Offset+AlignMask)&~AlignMask;
 431   }
 432
 433   Constants.push_back(MachineConstantPoolEntry(C, Offset));
 434   return Constants.size()-1;
 435 }
 436
 437 unsigned MachineConstantPool::getConstantPoolIndex(MachineConstantPoolValue *V,
 438                                                    unsigned Alignment) {
 439   assert(Alignment && "Alignment must be specified!");
 440   if (Alignment > PoolAlignment) PoolAlignment = Alignment;
 441
 442   // Check to see if we already have this constant.
 443   //
 444   // FIXME, this could be made much more efficient for large constant pools.
 445   unsigned AlignMask = (1 << Alignment)-1;
 446   int Idx = V->getExistingMachineCPValue(this, Alignment);
 447   if (Idx != -1)
 448     return (unsigned)Idx;
 449
 450   unsigned Offset = 0;
 451   if (!Constants.empty()) {
 452     Offset = Constants.back().getOffset();
 453     Offset += TD->getTypeSize(Constants.back().getType());
 454     Offset = (Offset+AlignMask)&~AlignMask;
 455   }
 456
 457   Constants.push_back(MachineConstantPoolEntry(V, Offset));
 458   return Constants.size()-1;
 459 }
 460
 461
 462 void MachineConstantPool::print(std::ostream &OS) const {
 463   for (unsigned i = 0, e = Constants.size(); i != e; ++i) {
 464     OS << "  <cp #" << i << "> is";
 465     if (Constants[i].isMachineConstantPoolEntry())
 466       Constants[i].Val.MachineCPVal->print(OS);
 467     else
 468       OS << *(Value*)Constants[i].Val.ConstVal;
 469     OS << " , offset=" << Constants[i].Offset;
 470     OS << "\n";
 471   }
 472 }
 473
 474 void MachineConstantPool::dump() const { print(*cerr.stream()); }