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 //*************************** User Include Files ***************************/
  14
  15 #include "llvm/CodeGen/InstrSelection.h"
  16 #include "llvm/Method.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/Type.h"
  19 #include "llvm/iMemory.h"
  20 #include "llvm/Instruction.h"
  21 #include "llvm/LLC/CompileContext.h"
  22 #include "llvm/CodeGen/MachineInstr.h"
  23
  24
  25 //************************* Forward Declarations ***************************/
  26
  27 static bool SelectInstructionsForTree(BasicTreeNode* treeRoot, int goalnt,
  28                                       CompileContext& ccontext);
  29
  30
  31 //******************* Externally Visible Functions *************************/
  32
  33
  34 //---------------------------------------------------------------------------
  35 // Entry point for instruction selection using BURG.
  36 // Returns true if instruction selection failed, false otherwise.
  37 //---------------------------------------------------------------------------
  38
  39 bool SelectInstructionsForMethod(Method* method, CompileContext& ccontext,
  40                                  int DebugLevel) {
  41   bool failed = false;
  42
  43   InstrForest instrForest;
  44   instrForest.buildTreesForMethod(method);
  45
  46   const hash_set<InstructionNode*, ptrHashFunc>&
  47     treeRoots = instrForest.getRootSet();
  48
  49   //
  50   // Invoke BURG instruction selection for each tree
  51   //
  52   for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
  53          treeRootIter = treeRoots.begin();
  54        treeRootIter != treeRoots.end();
  55        ++treeRootIter)
  56     {
  57       BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
  58
  59       // Invoke BURM to label each tree node with a state
  60       (void) burm_label(basicNode);
  61
  62       if (DebugLevel >= DEBUG_BURG_TREES)
  63         {
  64           printcover(basicNode, 1, 0);
  65           cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
  66           printMatches(basicNode);
  67         }
  68
  69       // Then recursively walk the tree to select instructions
  70       if (SelectInstructionsForTree(basicNode, /*goalnt*/1, ccontext))
  71         {
  72           failed = true;
  73           break;
  74         }
  75     }
  76
  77   if (!failed)
  78     {
  79       if (DebugLevel >= DEBUG_INSTR_TREES)
  80         {
  81           cout << "\n\n*** Instruction trees for method "
  82                << (method->hasName()? method->getName() : "")
  83                << endl << endl;
  84           instrForest.dump();
  85         }
  86
  87       if (DebugLevel >= DEBUG_TREES_NONE)
  88         PrintMachineInstructions(method);
  89     }
  90
  91   return false;
  92 }
  93
  94
  95 //---------------------------------------------------------------------------
  96 // Function: FoldGetElemChain
  97 //
  98 // Purpose:
  99 //   Fold a chain of GetElementPtr instructions into an equivalent
 100 //   (Pointer, IndexVector) pair.  Returns the pointer Value, and
 101 //   stores the resulting IndexVector in argument chainIdxVec.
 102 //---------------------------------------------------------------------------
 103
 104 Value*
 105 FoldGetElemChain(const InstructionNode* getElemInstrNode,
 106                  vector<ConstPoolVal*>& chainIdxVec)
 107 {
 108   MemAccessInst* getElemInst = (MemAccessInst*)
 109     getElemInstrNode->getInstruction();
 110
 111   // Initialize return values from the incoming instruction
 112   Value* ptrVal = getElemInst->getPtrOperand();
 113   chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
 114
 115   // Now chase the chain of getElementInstr instructions, if any
 116   InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
 117   while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
 118          ptrChild->getOpLabel() == GetElemPtrIdx)
 119     {
 120       // Child is a GetElemPtr instruction
 121       getElemInst = (MemAccessInst*)
 122         ((InstructionNode*) ptrChild)->getInstruction();
 123       const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
 124
 125       // Get the pointer value out of ptrChild and *prepend* its index vector
 126       ptrVal = getElemInst->getPtrOperand();
 127       chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
 128
 129       ptrChild = ptrChild->leftChild();
 130     }
 131
 132   return ptrVal;
 133 }
 134
 135
 136 void PrintMachineInstructions(Method* method) {
 137   cout << "\n" << method->getReturnType()
 138        << " \"" << method->getName() << "\"" << endl;
 139
 140   for (Method::const_iterator bbIter = method->begin();
 141        bbIter != method->end();
 142        ++bbIter)
 143     {
 144       BasicBlock* bb = *bbIter;
 145       cout << "\n"
 146            << (bb->hasName()? bb->getName() : "Label")
 147            << " (" << bb << ")" << ":"
 148            << endl;
 149
 150       for (BasicBlock::const_iterator instrIter = bb->begin();
 151            instrIter != bb->end();
 152            ++instrIter)
 153         {
 154           Instruction *instr = *instrIter;
 155           const MachineCodeForVMInstr& minstrVec = instr->getMachineInstrVec();
 156           for (unsigned i=0, N=minstrVec.size(); i < N; i++)
 157             cout << "\t" << *minstrVec[i] << endl;
 158         }
 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(BasicTreeNode* treeRoot,
 183                           int goalnt,
 184                           CompileContext& ccontext)
 185 {
 186   // Use a static vector to avoid allocating a new one per VM instruction
 187   static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
 188
 189   // Get the rule that matches this node.
 190   //
 191   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 192
 193   if (ruleForNode == 0)
 194     {
 195       cerr << "Could not match instruction tree for instr selection" << endl;
 196       return true;
 197     }
 198
 199   // Get this rule's non-terminals and the corresponding child nodes (if any)
 200   //
 201   short *nts = burm_nts[ruleForNode];
 202
 203
 204   // First, select instructions for the current node and rule.
 205   // (If this is a list node, not an instruction, then skip this step).
 206   // This function is specific to the target architecture.
 207   //
 208   if (treeRoot->opLabel != VRegListOp)
 209     {
 210       InstructionNode* instrNode = (InstructionNode*) MainTreeNode(treeRoot);
 211       assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 212
 213       unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, ccontext,
 214                                          minstrVec);
 215       assert(N <= MAX_INSTR_PER_VMINSTR);
 216       for (unsigned i=0; i < N; i++)
 217         {
 218           assert(minstrVec[i] != NULL);
 219           instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
 220         }
 221     }
 222
 223   // Then, recursively compile the child nodes, if any.
 224   //
 225   if (nts[0])
 226     { // i.e., there is at least one kid
 227
 228       BasicTreeNode* kids[2];
 229       int currentRule = ruleForNode;
 230       burm_kids(treeRoot, currentRule, kids);
 231
 232       // First skip over any chain rules so that we don't visit
 233       // the current node again.
 234       //
 235       while (ThisIsAChainRule(currentRule))
 236         {
 237           currentRule = burm_rule(treeRoot->state, nts[0]);
 238           nts = burm_nts[currentRule];
 239           burm_kids(treeRoot, currentRule, kids);
 240         }
 241
 242       // Now we have the first non-chain rule so we have found
 243       // the actual child nodes.  Recursively compile them.
 244       //
 245       for (int i = 0; nts[i]; i++)
 246         {
 247           assert(i < 2);
 248           InstrTreeNode::InstrTreeNodeType
 249             nodeType = MainTreeNode(kids[i])->getNodeType();
 250           if (nodeType == InstrTreeNode::NTVRegListNode ||
 251               nodeType == InstrTreeNode::NTInstructionNode)
 252             {
 253               bool failed= SelectInstructionsForTree(kids[i], nts[i],ccontext);
 254               if (failed)
 255                 return true;                    // failure
 256             }
 257         }
 258     }
 259
 260   return false;                         // success
 261 }
 262