lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

   1 //===- InstrSelection.cpp - Machine Independent Inst Selection Driver -----===//
   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 // Machine-independent driver file for instruction selection.  This file
  11 // constructs a forest of BURG instruction trees and then uses the
  12 // BURG-generated tree grammar (BURM) to find the optimal instruction sequences
  13 // for a given machine.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/CodeGen/InstrSelection.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/iPHINode.h"
  20 #include "llvm/iOther.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/CodeGen/InstrForest.h"
  23 #include "llvm/CodeGen/IntrinsicLowering.h"
  24 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "llvm/Support/CFG.h"
  28 #include "../SparcV9RegInfo.h"
  29 #include "Support/CommandLine.h"
  30 #include "Support/LeakDetector.h"
  31 #include <iostream>
  32
  33 namespace llvm {
  34   std::vector<MachineInstr*>
  35   FixConstantOperandsForInstr(Instruction *I, MachineInstr *MI,
  36                               TargetMachine &TM);
  37 }
  38
  39 namespace {
  40   //===--------------------------------------------------------------------===//
  41   // SelectDebugLevel - Allow command line control over debugging.
  42   //
  43   enum SelectDebugLevel_t {
  44     Select_NoDebugInfo,
  45     Select_PrintMachineCode,
  46     Select_DebugInstTrees,
  47     Select_DebugBurgTrees,
  48   };
  49
  50   // Enable Debug Options to be specified on the command line
  51   cl::opt<SelectDebugLevel_t>
  52   SelectDebugLevel("dselect", cl::Hidden,
  53                    cl::desc("enable instruction selection debug information"),
  54                    cl::values(
  55      clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
  56      clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
  57      clEnumValN(Select_DebugInstTrees,   "i",
  58                 "print debugging info for instruction selection"),
  59      clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"),
  60                               clEnumValEnd));
  61
  62
  63   //===--------------------------------------------------------------------===//
  64   //  InstructionSelection Pass
  65   //
  66   // This is the actual pass object that drives the instruction selection
  67   // process.
  68   //
  69   class InstructionSelection : public FunctionPass {
  70     TargetMachine &Target;
  71     void InsertCodeForPhis(Function &F);
  72     void InsertPhiElimInstructions(BasicBlock *BB,
  73                                    const std::vector<MachineInstr*>& CpVec);
  74     void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
  75     void PostprocessMachineCodeForTree(InstructionNode* instrNode,
  76                                        int ruleForNode, short* nts);
  77   public:
  78     InstructionSelection(TargetMachine &TM) : Target(TM) {}
  79
  80     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  81       AU.setPreservesCFG();
  82     }
  83
  84     bool runOnFunction(Function &F);
  85     virtual const char *getPassName() const { return "Instruction Selection"; }
  86   };
  87 }
  88
  89 TmpInstruction::TmpInstruction(Value *s1, Value *s2, const std::string &name)
  90   : Instruction(s1->getType(), Instruction::UserOp1, name)
  91 {
  92   Operands.push_back(Use(s1, this));  // s1 must be non-null
  93   if (s2)
  94     Operands.push_back(Use(s2, this));
  95
  96   // TmpInstructions should not be garbage checked.
  97   LeakDetector::removeGarbageObject(this);
  98 }
  99
 100 TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
 101                                Value *s1, Value *s2, const std::string &name)
 102   : Instruction(s1->getType(), Instruction::UserOp1, name)
 103 {
 104   mcfi.addTemp(this);
 105
 106   Operands.push_back(Use(s1, this));  // s1 must be non-null
 107   if (s2)
 108     Operands.push_back(Use(s2, this));
 109
 110   // TmpInstructions should not be garbage checked.
 111   LeakDetector::removeGarbageObject(this);
 112 }
 113
 114 // Constructor that requires the type of the temporary to be specified.
 115 // Both S1 and S2 may be NULL.
 116 TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
 117                                const Type *Ty, Value *s1, Value* s2,
 118                                const std::string &name)
 119   : Instruction(Ty, Instruction::UserOp1, name)
 120 {
 121   mcfi.addTemp(this);
 122
 123   if (s1)
 124     Operands.push_back(Use(s1, this));
 125   if (s2)
 126     Operands.push_back(Use(s2, this));
 127
 128   // TmpInstructions should not be garbage checked.
 129   LeakDetector::removeGarbageObject(this);
 130 }
 131
 132 bool InstructionSelection::runOnFunction(Function &F) {
 133   // First pass - Walk the function, lowering any calls to intrinsic functions
 134   // which the instruction selector cannot handle.
 135   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 136     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
 137       if (CallInst *CI = dyn_cast<CallInst>(I++))
 138         if (Function *F = CI->getCalledFunction())
 139           switch (F->getIntrinsicID()) {
 140           case Intrinsic::not_intrinsic:
 141           case Intrinsic::vastart:
 142           case Intrinsic::vacopy:
 143           case Intrinsic::vaend:
 144             // We directly implement these intrinsics.  Note that this knowledge
 145             // is incestuously entangled with the code in
 146             // SparcInstrSelection.cpp and must be updated when it is updated.
 147             // Since ALL of the code in this library is incestuously intertwined
 148             // with it already and sparc specific, we will live with this.
 149             break;
 150           default:
 151             // All other intrinsic calls we must lower.
 152             Instruction *Before = CI->getPrev();
 153             Target.getIntrinsicLowering().LowerIntrinsicCall(CI);
 154             if (Before) {        // Move iterator to instruction after call
 155               I = Before;  ++I;
 156             } else {
 157               I = BB->begin();
 158             }
 159           }
 160
 161   // Build the instruction trees to be given as inputs to BURG.
 162   InstrForest instrForest(&F);
 163   if (SelectDebugLevel >= Select_DebugInstTrees) {
 164     std::cerr << "\n\n*** Input to instruction selection for function "
 165               << F.getName() << "\n\n" << F
 166               << "\n\n*** Instruction trees for function "
 167               << F.getName() << "\n\n";
 168     instrForest.dump();
 169   }
 170
 171   // Invoke BURG instruction selection for each tree
 172   for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
 173        RI != instrForest.roots_end(); ++RI) {
 174     InstructionNode* basicNode = *RI;
 175     assert(basicNode->parent() == NULL && "A `root' node has a parent?");
 176
 177     // Invoke BURM to label each tree node with a state
 178     burm_label(basicNode);
 179     if (SelectDebugLevel >= Select_DebugBurgTrees) {
 180       printcover(basicNode, 1, 0);
 181       std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
 182       printMatches(basicNode);
 183     }
 184
 185     // Then recursively walk the tree to select instructions
 186     SelectInstructionsForTree(basicNode, /*goalnt*/1);
 187   }
 188
 189   // Create the MachineBasicBlocks and add all of the MachineInstrs
 190   // defined in the MachineCodeForInstruction objects to the MachineBasicBlocks.
 191   MachineFunction &MF = MachineFunction::get(&F);
 192   std::map<const BasicBlock *, MachineBasicBlock *> MBBMap;
 193   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
 194     MachineBasicBlock *MBB = new MachineBasicBlock(BI);
 195     MF.getBasicBlockList().push_back(MBB);
 196     MBBMap[BI] = MBB;
 197
 198     for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
 199       MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
 200       MBB->insert(MBB->end(), mvec.begin(), mvec.end());
 201     }
 202   }
 203
 204   // Initialize Machine-CFG for the function.
 205   for (MachineFunction::iterator i = MF.begin (), e = MF.end (); i != e; ++i) {
 206     MachineBasicBlock &MBB = *i;
 207     const BasicBlock *BB = MBB.getBasicBlock ();
 208     // for each successor S of BB, add MBBMap[S] as a successor of MBB.
 209     for (succ_const_iterator si = succ_begin(BB), se = succ_end(BB); si != se; ++si) {
 210       MachineBasicBlock *succMBB = MBBMap[*si];
 211       assert (succMBB && "Can't find MachineBasicBlock for this successor");
 212       MBB.addSuccessor (succMBB);
 213     }
 214   }
 215
 216   // Insert phi elimination code
 217   InsertCodeForPhis(F);
 218
 219   if (SelectDebugLevel >= Select_PrintMachineCode) {
 220     std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
 221     MachineFunction::get(&F).dump();
 222   }
 223
 224   return true;
 225 }
 226
 227 /// InsertCodeForPhis - This method inserts Phi elimination code for
 228 /// all Phi nodes in the given function.  After this method is called,
 229 /// the Phi nodes still exist in the LLVM code, but copies are added to the
 230 /// machine code.
 231 ///
 232 void InstructionSelection::InsertCodeForPhis(Function &F) {
 233   // Iterate over every Phi node PN in F:
 234   MachineFunction &MF = MachineFunction::get(&F);
 235   for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) {
 236     for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin();
 237          const PHINode *PN = dyn_cast<PHINode>(IIt); ++IIt) {
 238       // Create a new temporary register to hold the result of the Phi copy.
 239       // The leak detector shouldn't track these nodes.  They are not garbage,
 240       // even though their parent field is never filled in.
 241       Value *PhiCpRes = new PHINode(PN->getType(), PN->getName() + ":PhiCp");
 242       LeakDetector::removeGarbageObject(PhiCpRes);
 243
 244       // For each of PN's incoming values, insert a copy in the corresponding
 245       // predecessor block.
 246       MachineCodeForInstruction &MCforPN = MachineCodeForInstruction::get (PN);
 247       for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
 248         std::vector<MachineInstr*> mvec, CpVec;
 249         Target.getRegInfo()->cpValue2Value(PN->getIncomingValue(i),
 250                                            PhiCpRes, mvec);
 251         for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
 252              MI != mvec.end(); ++MI) {
 253           std::vector<MachineInstr*> CpVec2 =
 254             FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
 255           CpVec2.push_back(*MI);
 256           CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
 257         }
 258         // Insert the copy instructions into the predecessor BB.
 259         InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
 260         MCforPN.insert (MCforPN.end (), CpVec.begin (), CpVec.end ());
 261       }
 262       // Insert a copy instruction from PhiCpRes to PN.
 263       std::vector<MachineInstr*> mvec;
 264       Target.getRegInfo()->cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
 265                                         mvec);
 266       BB->insert(BB->begin(), mvec.begin(), mvec.end());
 267       MCforPN.insert (MCforPN.end (), mvec.begin (), mvec.end ());
 268     }  // for each Phi Instr in BB
 269   } // for all BBs in function
 270 }
 271
 272 /// InsertPhiElimInstructions - Inserts the instructions in CpVec into the
 273 /// MachineBasicBlock corresponding to BB, just before its terminator
 274 /// instruction. This is used by InsertCodeForPhis() to insert copies, above.
 275 ///
 276 void
 277 InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
 278                                         const std::vector<MachineInstr*>& CpVec)
 279 {
 280   Instruction *TermInst = (Instruction*)BB->getTerminator();
 281   MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
 282   MachineInstr *FirstMIOfTerm = MC4Term.front();
 283   assert (FirstMIOfTerm && "No Machine Instrs for terminator");
 284
 285   MachineBasicBlock *MBB = FirstMIOfTerm->getParent();
 286   assert(MBB && "Machine BB for predecessor's terminator not found");
 287   MachineBasicBlock::iterator MCIt = FirstMIOfTerm;
 288   assert(MCIt != MBB->end() && "Start inst of terminator not found");
 289
 290   // insert the copy instructions just before the first machine instruction
 291   // generated for the terminator
 292   MBB->insert(MCIt, CpVec.begin(), CpVec.end());
 293 }
 294
 295
 296 //---------------------------------------------------------------------------
 297 // Function SelectInstructionsForTree
 298 //
 299 // Recursively walk the tree to select instructions.
 300 // Do this top-down so that child instructions can exploit decisions
 301 // made at the child instructions.
 302 //
 303 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
 304 // a branch-on-integer-register instruction, then the setle node
 305 // can use that information to avoid generating the SUBcc instruction.
 306 //
 307 // Note that this cannot be done bottom-up because setle must do this
 308 // only if it is a child of the branch (otherwise, the result of setle
 309 // may be used by multiple instructions).
 310 //---------------------------------------------------------------------------
 311
 312 void
 313 InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
 314                                                 int goalnt)
 315 {
 316   // Get the rule that matches this node.
 317   //
 318   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 319
 320   if (ruleForNode == 0) {
 321     std::cerr << "Could not match instruction tree for instr selection\n";
 322     abort();
 323   }
 324
 325   // Get this rule's non-terminals and the corresponding child nodes (if any)
 326   //
 327   short *nts = burm_nts[ruleForNode];
 328
 329   // First, select instructions for the current node and rule.
 330   // (If this is a list node, not an instruction, then skip this step).
 331   // This function is specific to the target architecture.
 332   //
 333   if (treeRoot->opLabel != VRegListOp) {
 334     std::vector<MachineInstr*> minstrVec;
 335
 336     InstructionNode* instrNode = (InstructionNode*)treeRoot;
 337     assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 338
 339     GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
 340
 341     MachineCodeForInstruction &mvec =
 342       MachineCodeForInstruction::get(instrNode->getInstruction());
 343     mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
 344   }
 345
 346   // Then, recursively compile the child nodes, if any.
 347   //
 348   if (nts[0]) {
 349     // i.e., there is at least one kid
 350     InstrTreeNode* kids[2];
 351     int currentRule = ruleForNode;
 352     burm_kids(treeRoot, currentRule, kids);
 353
 354     // First skip over any chain rules so that we don't visit
 355     // the current node again.
 356     //
 357     while (ThisIsAChainRule(currentRule)) {
 358       currentRule = burm_rule(treeRoot->state, nts[0]);
 359       nts = burm_nts[currentRule];
 360       burm_kids(treeRoot, currentRule, kids);
 361     }
 362
 363     // Now we have the first non-chain rule so we have found
 364     // the actual child nodes.  Recursively compile them.
 365     //
 366     for (unsigned i = 0; nts[i]; i++) {
 367       assert(i < 2);
 368       InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
 369       if (nodeType == InstrTreeNode::NTVRegListNode ||
 370           nodeType == InstrTreeNode::NTInstructionNode)
 371         SelectInstructionsForTree(kids[i], nts[i]);
 372     }
 373   }
 374
 375   // Finally, do any post-processing on this node after its children
 376   // have been translated
 377   //
 378   if (treeRoot->opLabel != VRegListOp)
 379     PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
 380 }
 381
 382 //---------------------------------------------------------------------------
 383 // Function PostprocessMachineCodeForTree
 384 //
 385 // Apply any final cleanups to machine code for the root of a subtree
 386 // after selection for all its children has been completed.
 387 //
 388 void
 389 InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
 390                                                     int ruleForNode,
 391                                                     short* nts)
 392 {
 393   // Fix up any constant operands in the machine instructions to either
 394   // use an immediate field or to load the constant into a register
 395   // Walk backwards and use direct indexes to allow insertion before current
 396   //
 397   Instruction* vmInstr = instrNode->getInstruction();
 398   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
 399   for (unsigned i = mvec.size(); i != 0; --i) {
 400     std::vector<MachineInstr*> loadConstVec =
 401       FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
 402
 403     mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
 404   }
 405 }
 406
 407
 408 //===----------------------------------------------------------------------===//
 409 // createInstructionSelectionPass - Public entrypoint for instruction selection
 410 // and this file as a whole...
 411 //
 412 FunctionPass *llvm::createInstructionSelectionPass(TargetMachine &TM) {
 413   return new InstructionSelection(TM);
 414 }