lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

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