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