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