lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

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