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/InstrSelectionSupport.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/Support/CommandLine.h"
  21 #include "llvm/Instruction.h"
  22 #include "llvm/BasicBlock.h"
  23 #include "llvm/Method.h"
  24
  25
  26 //******************** Internal Data Declarations ************************/
  27
  28 // Use a static vector to avoid allocating a new one per VM instruction
  29 static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
  30
  31
  32 enum SelectDebugLevel_t {
  33   Select_NoDebugInfo,
  34   Select_PrintMachineCode,
  35   Select_DebugInstTrees,
  36   Select_DebugBurgTrees,
  37 };
  38
  39 // Enable Debug Options to be specified on the command line
  40 cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags,
  41    "enable instruction selection debugging information",
  42    clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
  43    clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
  44    clEnumValN(Select_DebugInstTrees,   "i", "print debugging info for instruction selection "),
  45    clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"), 0);
  46
  47
  48 //******************** Forward Function Declarations ***********************/
  49
  50
  51 static bool SelectInstructionsForTree   (InstrTreeNode* treeRoot,
  52                                          int goalnt,
  53                                          TargetMachine &target);
  54
  55 static void PostprocessMachineCodeForTree(InstructionNode* instrNode,
  56                                           int ruleForNode,
  57                                           short* nts,
  58                                           TargetMachine &target);
  59
  60
  61 //******************* Externally Visible Functions *************************/
  62
  63
  64 //---------------------------------------------------------------------------
  65 // Entry point for instruction selection using BURG.
  66 // Returns true if instruction selection failed, false otherwise.
  67 //---------------------------------------------------------------------------
  68
  69 bool
  70 SelectInstructionsForMethod(Method* method, TargetMachine &target)
  71 {
  72   bool failed = false;
  73
  74   //
  75   // Build the instruction trees to be given as inputs to BURG.
  76   //
  77   InstrForest instrForest(method);
  78
  79   if (SelectDebugLevel >= Select_DebugInstTrees)
  80     {
  81       cout << "\n\n*** Instruction trees for method "
  82            << (method->hasName()? method->getName() : "")
  83            << endl << endl;
  84       instrForest.dump();
  85     }
  86
  87   //
  88   // Invoke BURG instruction selection for each tree
  89   //
  90   const hash_set<InstructionNode*> &treeRoots = instrForest.getRootSet();
  91   for (hash_set<InstructionNode*>::const_iterator
  92          treeRootIter = treeRoots.begin(); treeRootIter != treeRoots.end();
  93        ++treeRootIter)
  94     {
  95       InstrTreeNode* basicNode = *treeRootIter;
  96
  97       // Invoke BURM to label each tree node with a state
  98       burm_label(basicNode);
  99
 100       if (SelectDebugLevel >= Select_DebugBurgTrees)
 101         {
 102           printcover(basicNode, 1, 0);
 103           cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
 104           printMatches(basicNode);
 105         }
 106
 107       // Then recursively walk the tree to select instructions
 108       if (SelectInstructionsForTree(basicNode, /*goalnt*/1, target))
 109         {
 110           failed = true;
 111           break;
 112         }
 113     }
 114
 115   //
 116   // Record instructions in the vector for each basic block
 117   //
 118   for (Method::iterator BI = method->begin(); BI != method->end(); ++BI)
 119     {
 120       MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
 121       for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II)
 122         {
 123           MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
 124           for (unsigned i=0; i < mvec.size(); i++)
 125             bbMvec.push_back(mvec[i]);
 126         }
 127     }
 128
 129   if (SelectDebugLevel >= Select_PrintMachineCode)
 130     {
 131       cout << endl
 132            << "*** Machine instructions after INSTRUCTION SELECTION" << endl;
 133       method->getMachineCode().dump();
 134     }
 135
 136   return false;
 137 }
 138
 139
 140 //*********************** Private Functions *****************************/
 141
 142
 143 //---------------------------------------------------------------------------
 144 // Function AppendMachineCodeForVMInstr
 145 //
 146 // Append machine instr sequence to the machine code vec for a VM instr
 147 //---------------------------------------------------------------------------
 148
 149 inline void
 150 AppendMachineCodeForVMInstr(MachineInstr** minstrVec,
 151                             unsigned int N,
 152                             Instruction* vmInstr)
 153 {
 154   if (N == 0)
 155     return;
 156   MachineCodeForVMInstr& mvec = vmInstr->getMachineInstrVec();
 157   mvec.insert(mvec.end(), minstrVec, minstrVec+N);
 158 }
 159
 160
 161
 162 //---------------------------------------------------------------------------
 163 // Function PostprocessMachineCodeForTree
 164 //
 165 // Apply any final cleanups to machine code for the root of a subtree
 166 // after selection for all its children has been completed.
 167 //---------------------------------------------------------------------------
 168
 169 static void
 170 PostprocessMachineCodeForTree(InstructionNode* instrNode,
 171                               int ruleForNode,
 172                               short* nts,
 173                               TargetMachine &target)
 174 {
 175   // Fix up any constant operands in the machine instructions to either
 176   // use an immediate field or to load the constant into a register
 177   // Walk backwards and use direct indexes to allow insertion before current
 178   //
 179   Instruction* vmInstr = instrNode->getInstruction();
 180   MachineCodeForVMInstr& mvec = vmInstr->getMachineInstrVec();
 181   for (int i = (int) mvec.size()-1; i >= 0; i--)
 182     {
 183       vector<MachineInstr*> loadConstVec =
 184         FixConstantOperandsForInstr(vmInstr, mvec[i], target);
 185
 186       if (loadConstVec.size() > 0)
 187         mvec.insert(mvec.begin()+i, loadConstVec.begin(), loadConstVec.end());
 188     }
 189 }
 190
 191 //---------------------------------------------------------------------------
 192 // Function SelectInstructionsForTree
 193 //
 194 // Recursively walk the tree to select instructions.
 195 // Do this top-down so that child instructions can exploit decisions
 196 // made at the child instructions.
 197 //
 198 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
 199 // a branch-on-integer-register instruction, then the setle node
 200 // can use that information to avoid generating the SUBcc instruction.
 201 //
 202 // Note that this cannot be done bottom-up because setle must do this
 203 // only if it is a child of the branch (otherwise, the result of setle
 204 // may be used by multiple instructions).
 205 //---------------------------------------------------------------------------
 206
 207 bool
 208 SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
 209                           TargetMachine &target)
 210 {
 211   // Get the rule that matches this node.
 212   //
 213   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 214
 215   if (ruleForNode == 0)
 216     {
 217       cerr << "Could not match instruction tree for instr selection" << endl;
 218       assert(0);
 219       return true;
 220     }
 221
 222   // Get this rule's non-terminals and the corresponding child nodes (if any)
 223   //
 224   short *nts = burm_nts[ruleForNode];
 225
 226   // First, select instructions for the current node and rule.
 227   // (If this is a list node, not an instruction, then skip this step).
 228   // This function is specific to the target architecture.
 229   //
 230   if (treeRoot->opLabel != VRegListOp)
 231     {
 232       InstructionNode* instrNode = (InstructionNode*)treeRoot;
 233       assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 234
 235       unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, target,
 236                                          minstrVec);
 237       if (N > 0)
 238         {
 239           assert(N <= MAX_INSTR_PER_VMINSTR);
 240           AppendMachineCodeForVMInstr(minstrVec,N,instrNode->getInstruction());
 241         }
 242     }
 243
 244   // Then, recursively compile the child nodes, if any.
 245   //
 246   if (nts[0])
 247     { // i.e., there is at least one kid
 248       InstrTreeNode* kids[2];
 249       int currentRule = ruleForNode;
 250       burm_kids(treeRoot, currentRule, kids);
 251
 252       // First skip over any chain rules so that we don't visit
 253       // the current node again.
 254       //
 255       while (ThisIsAChainRule(currentRule))
 256         {
 257           currentRule = burm_rule(treeRoot->state, nts[0]);
 258           nts = burm_nts[currentRule];
 259           burm_kids(treeRoot, currentRule, kids);
 260         }
 261
 262       // Now we have the first non-chain rule so we have found
 263       // the actual child nodes.  Recursively compile them.
 264       //
 265       for (int i = 0; nts[i]; i++)
 266         {
 267           assert(i < 2);
 268           InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
 269           if (nodeType == InstrTreeNode::NTVRegListNode ||
 270               nodeType == InstrTreeNode::NTInstructionNode)
 271             {
 272               if (SelectInstructionsForTree(kids[i], nts[i], target))
 273                 return true;                    // failure
 274             }
 275         }
 276     }
 277
 278   // Finally, do any postprocessing on this node after its children
 279   // have been translated
 280   //
 281   if (treeRoot->opLabel != VRegListOp)
 282     {
 283       InstructionNode* instrNode = (InstructionNode*)treeRoot;
 284       PostprocessMachineCodeForTree(instrNode, ruleForNode, nts, target);
 285     }
 286
 287   return false;                         // success
 288 }
 289