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