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