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/Tools/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*, ptrHashFunc>&
  56     treeRoots = instrForest.getRootSet();
  57
  58   //
  59   // Invoke BURG instruction selection for each tree
  60   //
  61   for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
  62          treeRootIter = treeRoots.begin();
  63        treeRootIter != treeRoots.end();
  64        ++treeRootIter)
  65     {
  66       BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
  67
  68       // Invoke BURM to label each tree node with a state
  69       (void) burm_label(basicNode);
  70
  71       if (DebugLevel.getValue() >= DebugBurgTrees)
  72         {
  73           printcover(basicNode, 1, 0);
  74           cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
  75           printMatches(basicNode);
  76         }
  77
  78       // Then recursively walk the tree to select instructions
  79       if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target))
  80         {
  81           failed = true;
  82           break;
  83         }
  84     }
  85
  86   if (!failed)
  87     {
  88       if (DebugLevel.getValue() >= DebugInstTrees)
  89         {
  90           cout << "\n\n*** Instruction trees for method "
  91                << (method->hasName()? method->getName() : "")
  92                << endl << endl;
  93           instrForest.dump();
  94         }
  95
  96       if (DebugLevel.getValue() > NoDebugInfo)
  97         PrintMachineInstructions(method);
  98     }
  99
 100   return false;
 101 }
 102
 103
 104 //---------------------------------------------------------------------------
 105 // Function: FoldGetElemChain
 106 //
 107 // Purpose:
 108 //   Fold a chain of GetElementPtr instructions into an equivalent
 109 //   (Pointer, IndexVector) pair.  Returns the pointer Value, and
 110 //   stores the resulting IndexVector in argument chainIdxVec.
 111 //---------------------------------------------------------------------------
 112
 113 Value*
 114 FoldGetElemChain(const InstructionNode* getElemInstrNode,
 115                  vector<ConstPoolVal*>& chainIdxVec)
 116 {
 117   MemAccessInst* getElemInst = (MemAccessInst*)
 118     getElemInstrNode->getInstruction();
 119
 120   // Initialize return values from the incoming instruction
 121   Value* ptrVal = getElemInst->getPtrOperand();
 122   chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
 123
 124   // Now chase the chain of getElementInstr instructions, if any
 125   InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
 126   while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
 127          ptrChild->getOpLabel() == GetElemPtrIdx)
 128     {
 129       // Child is a GetElemPtr instruction
 130       getElemInst = (MemAccessInst*)
 131         ((InstructionNode*) ptrChild)->getInstruction();
 132       const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
 133
 134       // Get the pointer value out of ptrChild and *prepend* its index vector
 135       ptrVal = getElemInst->getPtrOperand();
 136       chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
 137
 138       ptrChild = ptrChild->leftChild();
 139     }
 140
 141   return ptrVal;
 142 }
 143
 144
 145 void PrintMachineInstructions(Method* method) {
 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                           TargetMachine &Target)
 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, Target,
 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               if (SelectInstructionsForTree(kids[i], nts[i], Target))
 263                 return true;                    // failure
 264             }
 265         }
 266     }
 267
 268   return false;                         // success
 269 }
 270