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