lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

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