lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

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