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