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