lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

   1 //===- InstrSelection.cpp - Machine Independant Inst Selection Driver -----===//
   2 //
   3 // Machine-independent driver file for instruction selection.  This file
   4 // constructs a forest of BURG instruction trees and then uses the
   5 // BURG-generated tree grammar (BURM) to find the optimal instruction sequences
   6 // for a given machine.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/CodeGen/InstrSelection.h"
  11 #include "llvm/CodeGen/InstrSelectionSupport.h"
  12 #include "llvm/CodeGen/InstrForest.h"
  13 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  14 #include "llvm/CodeGen/MachineCodeForBasicBlock.h"
  15 #include "llvm/CodeGen/MachineCodeForMethod.h"
  16 #include "llvm/Target/MachineRegInfo.h"
  17 #include "llvm/Target/TargetMachine.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/iPHINode.h"
  20 #include "llvm/Pass.h"
  21 #include "Support/CommandLine.h"
  22 using std::cerr;
  23 using std::vector;
  24
  25 namespace {
  26   //===--------------------------------------------------------------------===//
  27   // SelectDebugLevel - Allow command line control over debugging.
  28   //
  29   enum SelectDebugLevel_t {
  30     Select_NoDebugInfo,
  31     Select_PrintMachineCode,
  32     Select_DebugInstTrees,
  33     Select_DebugBurgTrees,
  34   };
  35
  36   // Enable Debug Options to be specified on the command line
  37   cl::opt<SelectDebugLevel_t>
  38   SelectDebugLevel("dselect", cl::Hidden,
  39                    cl::desc("enable instruction selection debug information"),
  40                    cl::values(
  41      clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
  42      clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
  43      clEnumValN(Select_DebugInstTrees,   "i",
  44                 "print debugging info for instruction selection"),
  45      clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"),
  46                               0));
  47
  48
  49   //===--------------------------------------------------------------------===//
  50   //  InstructionSelection Pass
  51   //
  52   // This is the actual pass object that drives the instruction selection
  53   // process.
  54   //
  55   class InstructionSelection : public FunctionPass {
  56     TargetMachine &Target;
  57     void InsertCodeForPhis(Function &F);
  58     void InsertPhiElimInstructions(BasicBlock *BB,
  59                                    const std::vector<MachineInstr*>& CpVec);
  60     void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
  61     void PostprocessMachineCodeForTree(InstructionNode* instrNode,
  62                                        int ruleForNode, short* nts);
  63   public:
  64     InstructionSelection(TargetMachine &T) : Target(T) {}
  65
  66     bool runOnFunction(Function &F);
  67   };
  68 }
  69
  70 // Register the pass...
  71 static RegisterLLC<InstructionSelection>
  72 X("instselect", "Instruction Selection", createInstructionSelectionPass);
  73
  74
  75 bool InstructionSelection::runOnFunction(Function &F)
  76 {
  77   //
  78   // Build the instruction trees to be given as inputs to BURG.
  79   //
  80   InstrForest instrForest(&F);
  81
  82   if (SelectDebugLevel >= Select_DebugInstTrees)
  83     {
  84       cerr << "\n\n*** Input to instruction selection for function "
  85            << F.getName() << "\n\n" << F
  86            << "\n\n*** Instruction trees for function "
  87            << F.getName() << "\n\n";
  88       instrForest.dump();
  89     }
  90
  91   //
  92   // Invoke BURG instruction selection for each tree
  93   //
  94   for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
  95        RI != instrForest.roots_end(); ++RI)
  96     {
  97       InstructionNode* basicNode = *RI;
  98       assert(basicNode->parent() == NULL && "A `root' node has a parent?");
  99
 100       // Invoke BURM to label each tree node with a state
 101       burm_label(basicNode);
 102
 103       if (SelectDebugLevel >= Select_DebugBurgTrees)
 104         {
 105           printcover(basicNode, 1, 0);
 106           cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
 107           printMatches(basicNode);
 108         }
 109
 110       // Then recursively walk the tree to select instructions
 111       SelectInstructionsForTree(basicNode, /*goalnt*/1);
 112     }
 113
 114   //
 115   // Record instructions in the vector for each basic block
 116   //
 117   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI)
 118     for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
 119       MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
 120       MachineCodeForBasicBlock &MCBB = MachineCodeForBasicBlock::get(BI);
 121       MCBB.insert(MCBB.end(), mvec.begin(), mvec.end());
 122     }
 123
 124   // Insert phi elimination code
 125   InsertCodeForPhis(F);
 126
 127   if (SelectDebugLevel >= Select_PrintMachineCode)
 128     {
 129       cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
 130       MachineCodeForMethod::get(&F).dump();
 131     }
 132
 133   return true;
 134 }
 135
 136
 137 //-------------------------------------------------------------------------
 138 // This method inserts phi elimination code for all BBs in a method
 139 //-------------------------------------------------------------------------
 140
 141 void
 142 InstructionSelection::InsertCodeForPhis(Function &F)
 143 {
 144   // for all basic blocks in function
 145   //
 146   for (Function::iterator BB = F.begin(); BB != F.end(); ++BB) {
 147     BasicBlock::InstListType &InstList = BB->getInstList();
 148     for (BasicBlock::iterator IIt = InstList.begin();
 149          PHINode *PN = dyn_cast<PHINode>(&*IIt); ++IIt) {
 150       // FIXME: This is probably wrong...
 151       Value *PhiCpRes = new PHINode(PN->getType(), "PhiCp:");
 152
 153       // for each incoming value of the phi, insert phi elimination
 154       //
 155       for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
 156         // insert the copy instruction to the predecessor BB
 157         vector<MachineInstr*> mvec, CpVec;
 158         Target.getRegInfo().cpValue2Value(PN->getIncomingValue(i), PhiCpRes,
 159                                           mvec);
 160         for (vector<MachineInstr*>::iterator MI=mvec.begin();
 161              MI != mvec.end(); ++MI) {
 162           vector<MachineInstr*> CpVec2 =
 163             FixConstantOperandsForInstr(PN, *MI, Target);
 164           CpVec2.push_back(*MI);
 165           CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
 166         }
 167
 168         InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
 169       }
 170
 171       vector<MachineInstr*> mvec;
 172       Target.getRegInfo().cpValue2Value(PhiCpRes, PN, mvec);
 173
 174       // get an iterator to machine instructions in the BB
 175       MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(BB);
 176
 177       bbMvec.insert(bbMvec.begin(), mvec.begin(), mvec.end());
 178     }  // for each Phi Instr in BB
 179   } // for all BBs in function
 180 }
 181
 182 //-------------------------------------------------------------------------
 183 // Thid method inserts a copy instruction to a predecessor BB as a result
 184 // of phi elimination.
 185 //-------------------------------------------------------------------------
 186
 187 void
 188 InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
 189                                                 const std::vector<MachineInstr*>& CpVec)
 190 {
 191   Instruction *TermInst = (Instruction*)BB->getTerminator();
 192   MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
 193   MachineInstr *FirstMIOfTerm = MC4Term.front();
 194
 195   assert (FirstMIOfTerm && "No Machine Instrs for terminator");
 196
 197   MachineCodeForBasicBlock &bbMvec = MachineCodeForBasicBlock::get(BB);
 198
 199   // find the position of first machine instruction generated by the
 200   // terminator of this BB
 201   MachineCodeForBasicBlock::iterator MCIt =
 202     std::find(bbMvec.begin(), bbMvec.end(), FirstMIOfTerm);
 203
 204   assert( MCIt != bbMvec.end() && "Start inst of terminator not found");
 205
 206   // insert the copy instructions just before the first machine instruction
 207   // generated for the terminator
 208   bbMvec.insert(MCIt, CpVec.begin(), CpVec.end());
 209 }
 210
 211
 212 //---------------------------------------------------------------------------
 213 // Function SelectInstructionsForTree
 214 //
 215 // Recursively walk the tree to select instructions.
 216 // Do this top-down so that child instructions can exploit decisions
 217 // made at the child instructions.
 218 //
 219 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
 220 // a branch-on-integer-register instruction, then the setle node
 221 // can use that information to avoid generating the SUBcc instruction.
 222 //
 223 // Note that this cannot be done bottom-up because setle must do this
 224 // only if it is a child of the branch (otherwise, the result of setle
 225 // may be used by multiple instructions).
 226 //---------------------------------------------------------------------------
 227
 228 void
 229 InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
 230                                                 int goalnt)
 231 {
 232   // Get the rule that matches this node.
 233   //
 234   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 235
 236   if (ruleForNode == 0) {
 237     cerr << "Could not match instruction tree for instr selection\n";
 238     abort();
 239   }
 240
 241   // Get this rule's non-terminals and the corresponding child nodes (if any)
 242   //
 243   short *nts = burm_nts[ruleForNode];
 244
 245   // First, select instructions for the current node and rule.
 246   // (If this is a list node, not an instruction, then skip this step).
 247   // This function is specific to the target architecture.
 248   //
 249   if (treeRoot->opLabel != VRegListOp)
 250     {
 251       std::vector<MachineInstr*> minstrVec;
 252
 253       InstructionNode* instrNode = (InstructionNode*)treeRoot;
 254       assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 255
 256       GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
 257
 258       MachineCodeForInstruction &mvec =
 259         MachineCodeForInstruction::get(instrNode->getInstruction());
 260       mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
 261     }
 262
 263   // Then, recursively compile the child nodes, if any.
 264   //
 265   if (nts[0])
 266     { // i.e., there is at least one kid
 267       InstrTreeNode* kids[2];
 268       int currentRule = ruleForNode;
 269       burm_kids(treeRoot, currentRule, kids);
 270
 271       // First skip over any chain rules so that we don't visit
 272       // the current node again.
 273       //
 274       while (ThisIsAChainRule(currentRule))
 275         {
 276           currentRule = burm_rule(treeRoot->state, nts[0]);
 277           nts = burm_nts[currentRule];
 278           burm_kids(treeRoot, currentRule, kids);
 279         }
 280
 281       // Now we have the first non-chain rule so we have found
 282       // the actual child nodes.  Recursively compile them.
 283       //
 284       for (unsigned i = 0; nts[i]; i++)
 285         {
 286           assert(i < 2);
 287           InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
 288           if (nodeType == InstrTreeNode::NTVRegListNode ||
 289               nodeType == InstrTreeNode::NTInstructionNode)
 290             SelectInstructionsForTree(kids[i], nts[i]);
 291         }
 292     }
 293
 294   // Finally, do any postprocessing on this node after its children
 295   // have been translated
 296   //
 297   if (treeRoot->opLabel != VRegListOp)
 298     PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
 299 }
 300
 301 //---------------------------------------------------------------------------
 302 // Function PostprocessMachineCodeForTree
 303 //
 304 // Apply any final cleanups to machine code for the root of a subtree
 305 // after selection for all its children has been completed.
 306 //
 307 void
 308 InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
 309                                                     int ruleForNode,
 310                                                     short* nts)
 311 {
 312   // Fix up any constant operands in the machine instructions to either
 313   // use an immediate field or to load the constant into a register
 314   // Walk backwards and use direct indexes to allow insertion before current
 315   //
 316   Instruction* vmInstr = instrNode->getInstruction();
 317   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
 318   for (int i = (int) mvec.size()-1; i >= 0; i--)
 319     {
 320       std::vector<MachineInstr*> loadConstVec =
 321         FixConstantOperandsForInstr(vmInstr, mvec[i], Target);
 322
 323       if (loadConstVec.size() > 0)
 324         mvec.insert(mvec.begin()+i, loadConstVec.begin(), loadConstVec.end());
 325     }
 326 }
 327
 328
 329
 330 //===----------------------------------------------------------------------===//
 331 // createInstructionSelectionPass - Public entrypoint for instruction selection
 332 // and this file as a whole...
 333 //
 334 Pass *createInstructionSelectionPass(TargetMachine &T) {
 335   return new InstructionSelection(T);
 336 }
 337