lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

   1 //===- InstrSelection.cpp - Machine Independent Inst Selection Driver -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Machine-independent driver file for instruction selection.  This file
  11 // constructs a forest of BURG instruction trees and then uses the
  12 // BURG-generated tree grammar (BURM) to find the optimal instruction sequences
  13 // for a given machine.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/CodeGen/InstrSelection.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/IntrinsicLowering.h"
  20 #include "llvm/iPHINode.h"
  21 #include "llvm/iOther.h"
  22 #include "llvm/Pass.h"
  23 #include "llvm/CodeGen/InstrForest.h"
  24 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "../SparcV9RegInfo.h"
  28 #include "Support/CommandLine.h"
  29 #include "Support/LeakDetector.h"
  30
  31 namespace llvm {
  32   std::vector<MachineInstr*>
  33   FixConstantOperandsForInstr(Instruction *I, MachineInstr *MI,
  34                               TargetMachine &TM);
  35 }
  36
  37 namespace {
  38   //===--------------------------------------------------------------------===//
  39   // SelectDebugLevel - Allow command line control over debugging.
  40   //
  41   enum SelectDebugLevel_t {
  42     Select_NoDebugInfo,
  43     Select_PrintMachineCode,
  44     Select_DebugInstTrees,
  45     Select_DebugBurgTrees,
  46   };
  47
  48   // Enable Debug Options to be specified on the command line
  49   cl::opt<SelectDebugLevel_t>
  50   SelectDebugLevel("dselect", cl::Hidden,
  51                    cl::desc("enable instruction selection debug information"),
  52                    cl::values(
  53      clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
  54      clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
  55      clEnumValN(Select_DebugInstTrees,   "i",
  56                 "print debugging info for instruction selection"),
  57      clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"),
  58                               0));
  59
  60
  61   //===--------------------------------------------------------------------===//
  62   //  InstructionSelection Pass
  63   //
  64   // This is the actual pass object that drives the instruction selection
  65   // process.
  66   //
  67   class InstructionSelection : public FunctionPass {
  68     TargetMachine &Target;
  69     void InsertCodeForPhis(Function &F);
  70     void InsertPhiElimInstructions(BasicBlock *BB,
  71                                    const std::vector<MachineInstr*>& CpVec);
  72     void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
  73     void PostprocessMachineCodeForTree(InstructionNode* instrNode,
  74                                        int ruleForNode, short* nts);
  75   public:
  76     InstructionSelection(TargetMachine &TM) : Target(TM) {}
  77
  78     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  79       AU.setPreservesCFG();
  80     }
  81
  82     bool runOnFunction(Function &F);
  83     virtual const char *getPassName() const { return "Instruction Selection"; }
  84   };
  85 }
  86
  87 TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
  88                                Value *s1, Value *s2, const std::string &name)
  89   : Instruction(s1->getType(), Instruction::UserOp1, name)
  90 {
  91   mcfi.addTemp(this);
  92
  93   Operands.push_back(Use(s1, this));  // s1 must be non-null
  94   if (s2)
  95     Operands.push_back(Use(s2, this));
  96
  97   // TmpInstructions should not be garbage checked.
  98   LeakDetector::removeGarbageObject(this);
  99 }
 100
 101 // Constructor that requires the type of the temporary to be specified.
 102 // Both S1 and S2 may be NULL.(
 103 TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
 104                                const Type *Ty, Value *s1, Value* s2,
 105                                const std::string &name)
 106   : Instruction(Ty, Instruction::UserOp1, name)
 107 {
 108   mcfi.addTemp(this);
 109
 110   if (s1)
 111     Operands.push_back(Use(s1, this));
 112   if (s2)
 113     Operands.push_back(Use(s2, this));
 114
 115   // TmpInstructions should not be garbage checked.
 116   LeakDetector::removeGarbageObject(this);
 117 }
 118
 119 bool InstructionSelection::runOnFunction(Function &F) {
 120   // First pass - Walk the function, lowering any calls to intrinsic functions
 121   // which the instruction selector cannot handle.
 122   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 123     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
 124       if (CallInst *CI = dyn_cast<CallInst>(I++))
 125         if (Function *F = CI->getCalledFunction())
 126           switch (F->getIntrinsicID()) {
 127           case Intrinsic::not_intrinsic:
 128           case Intrinsic::vastart:
 129           case Intrinsic::vacopy:
 130           case Intrinsic::vaend:
 131             // We directly implement these intrinsics.  Note that this knowledge
 132             // is incestuously entangled with the code in
 133             // SparcInstrSelection.cpp and must be updated when it is updated.
 134             // Since ALL of the code in this library is incestuously intertwined
 135             // with it already and sparc specific, we will live with this.
 136             break;
 137           default:
 138             // All other intrinsic calls we must lower.
 139             Instruction *Before = CI->getPrev();
 140             Target.getIntrinsicLowering().LowerIntrinsicCall(CI);
 141             if (Before) {        // Move iterator to instruction after call
 142               I = Before;  ++I;
 143             } else {
 144               I = BB->begin();
 145             }
 146           }
 147
 148   // Build the instruction trees to be given as inputs to BURG.
 149   InstrForest instrForest(&F);
 150   if (SelectDebugLevel >= Select_DebugInstTrees) {
 151     std::cerr << "\n\n*** Input to instruction selection for function "
 152               << F.getName() << "\n\n" << F
 153               << "\n\n*** Instruction trees for function "
 154               << F.getName() << "\n\n";
 155     instrForest.dump();
 156   }
 157
 158   // Invoke BURG instruction selection for each tree
 159   for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
 160        RI != instrForest.roots_end(); ++RI) {
 161     InstructionNode* basicNode = *RI;
 162     assert(basicNode->parent() == NULL && "A `root' node has a parent?");
 163
 164     // Invoke BURM to label each tree node with a state
 165     burm_label(basicNode);
 166     if (SelectDebugLevel >= Select_DebugBurgTrees) {
 167       printcover(basicNode, 1, 0);
 168       std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
 169       printMatches(basicNode);
 170     }
 171
 172     // Then recursively walk the tree to select instructions
 173     SelectInstructionsForTree(basicNode, /*goalnt*/1);
 174   }
 175
 176   // Create the MachineBasicBlock records and add all of the MachineInstrs
 177   // defined in the MachineCodeForInstruction objects to also live in the
 178   // MachineBasicBlock objects.
 179   MachineFunction &MF = MachineFunction::get(&F);
 180   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
 181     MachineBasicBlock *MCBB = new MachineBasicBlock(BI);
 182     MF.getBasicBlockList().push_back(MCBB);
 183
 184     for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
 185       MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
 186       MCBB->insert(MCBB->end(), mvec.begin(), mvec.end());
 187     }
 188   }
 189
 190   // Insert phi elimination code
 191   InsertCodeForPhis(F);
 192
 193   if (SelectDebugLevel >= Select_PrintMachineCode) {
 194     std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
 195     MachineFunction::get(&F).dump();
 196   }
 197
 198   return true;
 199 }
 200
 201 /// InsertCodeForPhis - This method inserts Phi elimination code for
 202 /// all Phi nodes in the given function.  After this method is called,
 203 /// the Phi nodes still exist in the LLVM code, but copies are added to the
 204 /// machine code.
 205 ///
 206 void InstructionSelection::InsertCodeForPhis(Function &F) {
 207   // Iterate over every Phi node PN in F:
 208   MachineFunction &MF = MachineFunction::get(&F);
 209   for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) {
 210     for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin();
 211          const PHINode *PN = dyn_cast<PHINode>(IIt); ++IIt) {
 212       // Create a new temporary register to hold the result of the Phi copy.
 213       // The leak detector shouldn't track these nodes.  They are not garbage,
 214       // even though their parent field is never filled in.
 215       Value *PhiCpRes = new PHINode(PN->getType(), PN->getName() + ":PhiCp");
 216       LeakDetector::removeGarbageObject(PhiCpRes);
 217
 218       // For each of PN's incoming values, insert a copy in the corresponding
 219       // predecessor block.
 220       MachineCodeForInstruction &MCforPN = MachineCodeForInstruction::get (PN);
 221       for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
 222         std::vector<MachineInstr*> mvec, CpVec;
 223         Target.getRegInfo()->cpValue2Value(PN->getIncomingValue(i),
 224                                            PhiCpRes, mvec);
 225         for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
 226              MI != mvec.end(); ++MI) {
 227           std::vector<MachineInstr*> CpVec2 =
 228             FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
 229           CpVec2.push_back(*MI);
 230           CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
 231         }
 232         // Insert the copy instructions into the predecessor BB.
 233         InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
 234         MCforPN.insert (MCforPN.end (), CpVec.begin (), CpVec.end ());
 235       }
 236       // Insert a copy instruction from PhiCpRes to PN.
 237       std::vector<MachineInstr*> mvec;
 238       Target.getRegInfo()->cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
 239                                         mvec);
 240       BB->insert(BB->begin(), mvec.begin(), mvec.end());
 241       MCforPN.insert (MCforPN.end (), mvec.begin (), mvec.end ());
 242     }  // for each Phi Instr in BB
 243   } // for all BBs in function
 244 }
 245
 246 /// InsertPhiElimInstructions - Inserts the instructions in CpVec into the
 247 /// MachineBasicBlock corresponding to BB, just before its terminator
 248 /// instruction. This is used by InsertCodeForPhis() to insert copies, above.
 249 ///
 250 void
 251 InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
 252                                         const std::vector<MachineInstr*>& CpVec)
 253 {
 254   Instruction *TermInst = (Instruction*)BB->getTerminator();
 255   MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
 256   MachineInstr *FirstMIOfTerm = MC4Term.front();
 257   assert (FirstMIOfTerm && "No Machine Instrs for terminator");
 258
 259   MachineBasicBlock *MBB = FirstMIOfTerm->getParent();
 260   assert(MBB && "Machine BB for predecessor's terminator not found");
 261   MachineBasicBlock::iterator MCIt = FirstMIOfTerm;
 262   assert(MCIt != MBB->end() && "Start inst of terminator not found");
 263
 264   // insert the copy instructions just before the first machine instruction
 265   // generated for the terminator
 266   MBB->insert(MCIt, CpVec.begin(), CpVec.end());
 267 }
 268
 269
 270 //---------------------------------------------------------------------------
 271 // Function SelectInstructionsForTree
 272 //
 273 // Recursively walk the tree to select instructions.
 274 // Do this top-down so that child instructions can exploit decisions
 275 // made at the child instructions.
 276 //
 277 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
 278 // a branch-on-integer-register instruction, then the setle node
 279 // can use that information to avoid generating the SUBcc instruction.
 280 //
 281 // Note that this cannot be done bottom-up because setle must do this
 282 // only if it is a child of the branch (otherwise, the result of setle
 283 // may be used by multiple instructions).
 284 //---------------------------------------------------------------------------
 285
 286 void
 287 InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
 288                                                 int goalnt)
 289 {
 290   // Get the rule that matches this node.
 291   //
 292   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 293
 294   if (ruleForNode == 0) {
 295     std::cerr << "Could not match instruction tree for instr selection\n";
 296     abort();
 297   }
 298
 299   // Get this rule's non-terminals and the corresponding child nodes (if any)
 300   //
 301   short *nts = burm_nts[ruleForNode];
 302
 303   // First, select instructions for the current node and rule.
 304   // (If this is a list node, not an instruction, then skip this step).
 305   // This function is specific to the target architecture.
 306   //
 307   if (treeRoot->opLabel != VRegListOp) {
 308     std::vector<MachineInstr*> minstrVec;
 309
 310     InstructionNode* instrNode = (InstructionNode*)treeRoot;
 311     assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 312
 313     GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
 314
 315     MachineCodeForInstruction &mvec =
 316       MachineCodeForInstruction::get(instrNode->getInstruction());
 317     mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
 318   }
 319
 320   // Then, recursively compile the child nodes, if any.
 321   //
 322   if (nts[0]) {
 323     // i.e., there is at least one kid
 324     InstrTreeNode* kids[2];
 325     int currentRule = ruleForNode;
 326     burm_kids(treeRoot, currentRule, kids);
 327
 328     // First skip over any chain rules so that we don't visit
 329     // the current node again.
 330     //
 331     while (ThisIsAChainRule(currentRule)) {
 332       currentRule = burm_rule(treeRoot->state, nts[0]);
 333       nts = burm_nts[currentRule];
 334       burm_kids(treeRoot, currentRule, kids);
 335     }
 336
 337     // Now we have the first non-chain rule so we have found
 338     // the actual child nodes.  Recursively compile them.
 339     //
 340     for (unsigned i = 0; nts[i]; i++) {
 341       assert(i < 2);
 342       InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
 343       if (nodeType == InstrTreeNode::NTVRegListNode ||
 344           nodeType == InstrTreeNode::NTInstructionNode)
 345         SelectInstructionsForTree(kids[i], nts[i]);
 346     }
 347   }
 348
 349   // Finally, do any post-processing on this node after its children
 350   // have been translated
 351   //
 352   if (treeRoot->opLabel != VRegListOp)
 353     PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
 354 }
 355
 356 //---------------------------------------------------------------------------
 357 // Function PostprocessMachineCodeForTree
 358 //
 359 // Apply any final cleanups to machine code for the root of a subtree
 360 // after selection for all its children has been completed.
 361 //
 362 void
 363 InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
 364                                                     int ruleForNode,
 365                                                     short* nts)
 366 {
 367   // Fix up any constant operands in the machine instructions to either
 368   // use an immediate field or to load the constant into a register
 369   // Walk backwards and use direct indexes to allow insertion before current
 370   //
 371   Instruction* vmInstr = instrNode->getInstruction();
 372   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
 373   for (unsigned i = mvec.size(); i != 0; --i) {
 374     std::vector<MachineInstr*> loadConstVec =
 375       FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
 376
 377     mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
 378   }
 379 }
 380
 381
 382 //===----------------------------------------------------------------------===//
 383 // createInstructionSelectionPass - Public entrypoint for instruction selection
 384 // and this file as a whole...
 385 //
 386 FunctionPass *llvm::createInstructionSelectionPass(TargetMachine &TM) {
 387   return new InstructionSelection(TM);
 388 }