lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

   1 // $Id$ -*-c++-*-
   2 //***************************************************************************
   3 // File:
   4 //      InstrSelection.cpp
   5 //
   6 // Purpose:
   7 //      Machine-independent driver file for instruction selection.
   8 //      This file constructs a forest of BURG instruction trees and then
   9 //      use the BURG-generated tree grammar (BURM) to find the optimal
  10 //      instruction sequences for a given machine.
  11 //
  12 // History:
  13 //      7/02/01  -  Vikram Adve  -  Created
  14 //**************************************************************************/
  15
  16
  17 #include "llvm/CodeGen/InstrSelection.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Type.h"
  21 #include "llvm/iMemory.h"
  22 #include "llvm/Instruction.h"
  23 #include "llvm/BasicBlock.h"
  24 #include "llvm/Method.h"
  25
  26 static bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
  27                                       TargetMachine &Target);
  28
  29
  30 enum SelectDebugLevel_t {
  31   Select_NoDebugInfo,
  32   Select_PrintMachineCode,
  33   Select_DebugInstTrees,
  34   Select_DebugBurgTrees,
  35 };
  36
  37 // Enable Debug Options to be specified on the command line
  38 cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags,
  39    "enable instruction selection debugging information",
  40    clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
  41    clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
  42    clEnumValN(Select_DebugInstTrees,   "i", "print debugging info for instruction selection "),
  43    clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"), 0);
  44
  45
  46
  47 //---------------------------------------------------------------------------
  48 // Entry point for instruction selection using BURG.
  49 // Returns true if instruction selection failed, false otherwise.
  50 //---------------------------------------------------------------------------
  51
  52 bool
  53 SelectInstructionsForMethod(Method* method, TargetMachine &Target)
  54 {
  55   bool failed = false;
  56
  57   //
  58   // Build the instruction trees to be given as inputs to BURG.
  59   //
  60   InstrForest instrForest(method);
  61
  62   if (SelectDebugLevel >= Select_DebugInstTrees)
  63     {
  64       cout << "\n\n*** Instruction trees for method "
  65            << (method->hasName()? method->getName() : "")
  66            << endl << endl;
  67       instrForest.dump();
  68     }
  69
  70   //
  71   // Invoke BURG instruction selection for each tree
  72   //
  73   const hash_set<InstructionNode*> &treeRoots = instrForest.getRootSet();
  74   for (hash_set<InstructionNode*>::const_iterator
  75          treeRootIter = treeRoots.begin(); treeRootIter != treeRoots.end();
  76        ++treeRootIter)
  77     {
  78       InstrTreeNode* basicNode = *treeRootIter;
  79
  80       // Invoke BURM to label each tree node with a state
  81       burm_label(basicNode);
  82
  83       if (SelectDebugLevel >= Select_DebugBurgTrees)
  84         {
  85           printcover(basicNode, 1, 0);
  86           cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
  87           printMatches(basicNode);
  88         }
  89
  90       // Then recursively walk the tree to select instructions
  91       if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target))
  92         {
  93           failed = true;
  94           break;
  95         }
  96     }
  97
  98   //
  99   // Record instructions in the vector for each basic block
 100   //
 101   for (Method::iterator BI = method->begin(); BI != method->end(); ++BI)
 102     {
 103       MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
 104       for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II)
 105         {
 106           MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
 107           for (unsigned i=0; i < mvec.size(); i++)
 108             bbMvec.push_back(mvec[i]);
 109         }
 110     }
 111
 112   if (SelectDebugLevel >= Select_PrintMachineCode)
 113     {
 114       cout << endl << "*** Machine instructions after INSTRUCTION SELECTION" << endl;
 115       PrintMachineInstructions(method);
 116     }
 117
 118   return false;
 119 }
 120
 121
 122 //---------------------------------------------------------------------------
 123 // Function: FoldGetElemChain
 124 //
 125 // Purpose:
 126 //   Fold a chain of GetElementPtr instructions into an equivalent
 127 //   (Pointer, IndexVector) pair.  Returns the pointer Value, and
 128 //   stores the resulting IndexVector in argument chainIdxVec.
 129 //---------------------------------------------------------------------------
 130
 131 Value*
 132 FoldGetElemChain(const InstructionNode* getElemInstrNode,
 133                  vector<ConstPoolVal*>& chainIdxVec)
 134 {
 135   MemAccessInst* getElemInst = (MemAccessInst*)
 136     getElemInstrNode->getInstruction();
 137
 138   // Initialize return values from the incoming instruction
 139   Value* ptrVal = getElemInst->getPtrOperand();
 140   chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
 141
 142   // Now chase the chain of getElementInstr instructions, if any
 143   InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
 144   while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
 145          ptrChild->getOpLabel() == GetElemPtrIdx)
 146     {
 147       // Child is a GetElemPtr instruction
 148       getElemInst = (MemAccessInst*)
 149         ((InstructionNode*) ptrChild)->getInstruction();
 150       const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
 151
 152       // Get the pointer value out of ptrChild and *prepend* its index vector
 153       ptrVal = getElemInst->getPtrOperand();
 154       chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
 155
 156       ptrChild = ptrChild->leftChild();
 157     }
 158
 159   return ptrVal;
 160 }
 161
 162
 163 //*********************** Private Functions *****************************/
 164
 165
 166 //---------------------------------------------------------------------------
 167 // Function SelectInstructionsForTree
 168 //
 169 // Recursively walk the tree to select instructions.
 170 // Do this top-down so that child instructions can exploit decisions
 171 // made at the child instructions.
 172 //
 173 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
 174 // a branch-on-integer-register instruction, then the setle node
 175 // can use that information to avoid generating the SUBcc instruction.
 176 //
 177 // Note that this cannot be done bottom-up because setle must do this
 178 // only if it is a child of the branch (otherwise, the result of setle
 179 // may be used by multiple instructions).
 180 //---------------------------------------------------------------------------
 181
 182 bool
 183 SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
 184                           TargetMachine &Target)
 185 {
 186   // Use a static vector to avoid allocating a new one per VM instruction
 187   static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
 188
 189   // Get the rule that matches this node.
 190   //
 191   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 192
 193   if (ruleForNode == 0)
 194     {
 195       cerr << "Could not match instruction tree for instr selection" << endl;
 196       assert(0);
 197       return true;
 198     }
 199
 200   // Get this rule's non-terminals and the corresponding child nodes (if any)
 201   //
 202   short *nts = burm_nts[ruleForNode];
 203
 204
 205   // First, select instructions for the current node and rule.
 206   // (If this is a list node, not an instruction, then skip this step).
 207   // This function is specific to the target architecture.
 208   //
 209   if (treeRoot->opLabel != VRegListOp)
 210     {
 211       InstructionNode* instrNode = (InstructionNode*)treeRoot;
 212       assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 213
 214       unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
 215                                          minstrVec);
 216       assert(N <= MAX_INSTR_PER_VMINSTR);
 217       for (unsigned i=0; i < N; i++)
 218         {
 219           assert(minstrVec[i] != NULL);
 220           instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
 221         }
 222     }
 223
 224   // Then, recursively compile the child nodes, if any.
 225   //
 226   if (nts[0])
 227     { // i.e., there is at least one kid
 228       InstrTreeNode* kids[2];
 229       int currentRule = ruleForNode;
 230       burm_kids(treeRoot, currentRule, kids);
 231
 232       // First skip over any chain rules so that we don't visit
 233       // the current node again.
 234       //
 235       while (ThisIsAChainRule(currentRule))
 236         {
 237           currentRule = burm_rule(treeRoot->state, nts[0]);
 238           nts = burm_nts[currentRule];
 239           burm_kids(treeRoot, currentRule, kids);
 240         }
 241
 242       // Now we have the first non-chain rule so we have found
 243       // the actual child nodes.  Recursively compile them.
 244       //
 245       for (int i = 0; nts[i]; i++)
 246         {
 247           assert(i < 2);
 248           InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
 249           if (nodeType == InstrTreeNode::NTVRegListNode ||
 250               nodeType == InstrTreeNode::NTInstructionNode)
 251             {
 252               if (SelectInstructionsForTree(kids[i], nts[i], Target))
 253                 return true;                    // failure
 254             }
 255         }
 256     }
 257
 258   return false;                         // success
 259 }
 260