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
  88 TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
  89                                Value *s1, Value *s2, const std::string &name)
  90   : Instruction(s1->getType(), Instruction::UserOp1, name)
  91 {
  92   mcfi.addTemp(this);
  93
  94   Operands.push_back(Use(s1, this));  // s1 must be non-null
  95   if (s2)
  96     Operands.push_back(Use(s2, this));
  97
  98   // TmpInstructions should not be garbage checked.
  99   LeakDetector::removeGarbageObject(this);
 100 }
 101
 102 // Constructor that requires the type of the temporary to be specified.
 103 // Both S1 and S2 may be NULL.(
 104 TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
 105                                const Type *Ty, Value *s1, Value* s2,
 106                                const std::string &name)
 107   : Instruction(Ty, Instruction::UserOp1, name)
 108 {
 109   mcfi.addTemp(this);
 110
 111   if (s1)
 112     Operands.push_back(Use(s1, this));
 113   if (s2)
 114     Operands.push_back(Use(s2, this));
 115
 116   // TmpInstructions should not be garbage checked.
 117   LeakDetector::removeGarbageObject(this);
 118 }
 119
 120 bool InstructionSelection::runOnFunction(Function &F) {
 121   // First pass - Walk the function, lowering any calls to intrinsic functions
 122   // which the instruction selector cannot handle.
 123   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 124     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
 125       if (CallInst *CI = dyn_cast<CallInst>(I++))
 126         if (Function *F = CI->getCalledFunction())
 127           switch (F->getIntrinsicID()) {
 128           case Intrinsic::not_intrinsic:
 129           case Intrinsic::vastart:
 130           case Intrinsic::vacopy:
 131           case Intrinsic::vaend:
 132             // We directly implement these intrinsics.  Note that this knowledge
 133             // is incestuously entangled with the code in
 134             // SparcInstrSelection.cpp and must be updated when it is updated.
 135             // Since ALL of the code in this library is incestuously intertwined
 136             // with it already and sparc specific, we will live with this.
 137             break;
 138           default:
 139             // All other intrinsic calls we must lower.
 140             Instruction *Before = CI->getPrev();
 141             Target.getIntrinsicLowering().LowerIntrinsicCall(CI);
 142             if (Before) {        // Move iterator to instruction after call
 143               I = Before;  ++I;
 144             } else {
 145               I = BB->begin();
 146             }
 147           }
 148
 149   //
 150   // Build the instruction trees to be given as inputs to BURG.
 151   //
 152   InstrForest instrForest(&F);
 153
 154   if (SelectDebugLevel >= Select_DebugInstTrees) {
 155     std::cerr << "\n\n*** Input to instruction selection for function "
 156               << F.getName() << "\n\n" << F
 157               << "\n\n*** Instruction trees for function "
 158               << F.getName() << "\n\n";
 159     instrForest.dump();
 160   }
 161
 162   //
 163   // Invoke BURG instruction selection for each tree
 164   //
 165   for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
 166        RI != instrForest.roots_end(); ++RI) {
 167     InstructionNode* basicNode = *RI;
 168     assert(basicNode->parent() == NULL && "A `root' node has a parent?");
 169
 170     // Invoke BURM to label each tree node with a state
 171     burm_label(basicNode);
 172
 173     if (SelectDebugLevel >= Select_DebugBurgTrees) {
 174       printcover(basicNode, 1, 0);
 175       std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
 176       printMatches(basicNode);
 177     }
 178
 179     // Then recursively walk the tree to select instructions
 180     SelectInstructionsForTree(basicNode, /*goalnt*/1);
 181   }
 182
 183   //
 184   // Create the MachineBasicBlock records and add all of the MachineInstrs
 185   // defined in the MachineCodeForInstruction objects to also live in the
 186   // MachineBasicBlock objects.
 187   //
 188   MachineFunction &MF = MachineFunction::get(&F);
 189   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
 190     MachineBasicBlock *MCBB = new MachineBasicBlock(BI);
 191     MF.getBasicBlockList().push_back(MCBB);
 192
 193     for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
 194       MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
 195       MCBB->insert(MCBB->end(), mvec.begin(), mvec.end());
 196     }
 197   }
 198
 199   // Insert phi elimination code
 200   InsertCodeForPhis(F);
 201
 202   if (SelectDebugLevel >= Select_PrintMachineCode) {
 203     std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
 204     MachineFunction::get(&F).dump();
 205   }
 206
 207   return true;
 208 }
 209
 210
 211 //-------------------------------------------------------------------------
 212 // This method inserts phi elimination code for all BBs in a method
 213 //-------------------------------------------------------------------------
 214
 215 void
 216 InstructionSelection::InsertCodeForPhis(Function &F) {
 217   // for all basic blocks in function
 218   //
 219   MachineFunction &MF = MachineFunction::get(&F);
 220   for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) {
 221     for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin();
 222          const PHINode *PN = dyn_cast<PHINode>(IIt); ++IIt) {
 223       // FIXME: This is probably wrong...
 224       Value *PhiCpRes = new PHINode(PN->getType(), "PhiCp:");
 225
 226       // The leak detector shouldn't track these nodes.  They are not garbage,
 227       // even though their parent field is never filled in.
 228       //
 229       LeakDetector::removeGarbageObject(PhiCpRes);
 230
 231       // for each incoming value of the phi, insert phi elimination
 232       //
 233       for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
 234         // insert the copy instruction to the predecessor BB
 235         std::vector<MachineInstr*> mvec, CpVec;
 236         Target.getRegInfo().cpValue2Value(PN->getIncomingValue(i), PhiCpRes,
 237                                           mvec);
 238         for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
 239              MI != mvec.end(); ++MI) {
 240           std::vector<MachineInstr*> CpVec2 =
 241             FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
 242           CpVec2.push_back(*MI);
 243           CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
 244         }
 245
 246         InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
 247       }
 248
 249       std::vector<MachineInstr*> mvec;
 250       Target.getRegInfo().cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
 251                                         mvec);
 252       BB->insert(BB->begin(), mvec.begin(), mvec.end());
 253     }  // for each Phi Instr in BB
 254   } // for all BBs in function
 255 }
 256
 257 //-------------------------------------------------------------------------
 258 // Thid method inserts a copy instruction to a predecessor BB as a result
 259 // of phi elimination.
 260 //-------------------------------------------------------------------------
 261
 262 void
 263 InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
 264                                         const std::vector<MachineInstr*>& CpVec)
 265 {
 266   Instruction *TermInst = (Instruction*)BB->getTerminator();
 267   MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
 268   MachineInstr *FirstMIOfTerm = MC4Term.front();
 269   assert (FirstMIOfTerm && "No Machine Instrs for terminator");
 270
 271   MachineFunction &MF = MachineFunction::get(BB->getParent());
 272
 273   // FIXME: if PHI instructions existed in the machine code, this would be
 274   // unnecessary.
 275   MachineBasicBlock *MBB = 0;
 276   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 277     if (I->getBasicBlock() == BB) {
 278       MBB = I;
 279       break;
 280     }
 281
 282   MachineBasicBlock::iterator MCIt = FirstMIOfTerm;
 283
 284   assert(MCIt != MBB->end() && "Start inst of terminator not found");
 285
 286   // insert the copy instructions just before the first machine instruction
 287   // generated for the terminator
 288   MBB->insert(MCIt, CpVec.begin(), CpVec.end());
 289 }
 290
 291
 292 //---------------------------------------------------------------------------
 293 // Function SelectInstructionsForTree
 294 //
 295 // Recursively walk the tree to select instructions.
 296 // Do this top-down so that child instructions can exploit decisions
 297 // made at the child instructions.
 298 //
 299 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
 300 // a branch-on-integer-register instruction, then the setle node
 301 // can use that information to avoid generating the SUBcc instruction.
 302 //
 303 // Note that this cannot be done bottom-up because setle must do this
 304 // only if it is a child of the branch (otherwise, the result of setle
 305 // may be used by multiple instructions).
 306 //---------------------------------------------------------------------------
 307
 308 void
 309 InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
 310                                                 int goalnt)
 311 {
 312   // Get the rule that matches this node.
 313   //
 314   int ruleForNode = burm_rule(treeRoot->state, goalnt);
 315
 316   if (ruleForNode == 0) {
 317     std::cerr << "Could not match instruction tree for instr selection\n";
 318     abort();
 319   }
 320
 321   // Get this rule's non-terminals and the corresponding child nodes (if any)
 322   //
 323   short *nts = burm_nts[ruleForNode];
 324
 325   // First, select instructions for the current node and rule.
 326   // (If this is a list node, not an instruction, then skip this step).
 327   // This function is specific to the target architecture.
 328   //
 329   if (treeRoot->opLabel != VRegListOp) {
 330     std::vector<MachineInstr*> minstrVec;
 331
 332     InstructionNode* instrNode = (InstructionNode*)treeRoot;
 333     assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 334
 335     GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
 336
 337     MachineCodeForInstruction &mvec =
 338       MachineCodeForInstruction::get(instrNode->getInstruction());
 339     mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
 340   }
 341
 342   // Then, recursively compile the child nodes, if any.
 343   //
 344   if (nts[0]) {
 345     // i.e., there is at least one kid
 346     InstrTreeNode* kids[2];
 347     int currentRule = ruleForNode;
 348     burm_kids(treeRoot, currentRule, kids);
 349
 350     // First skip over any chain rules so that we don't visit
 351     // the current node again.
 352     //
 353     while (ThisIsAChainRule(currentRule)) {
 354       currentRule = burm_rule(treeRoot->state, nts[0]);
 355       nts = burm_nts[currentRule];
 356       burm_kids(treeRoot, currentRule, kids);
 357     }
 358
 359     // Now we have the first non-chain rule so we have found
 360     // the actual child nodes.  Recursively compile them.
 361     //
 362     for (unsigned i = 0; nts[i]; i++) {
 363       assert(i < 2);
 364       InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
 365       if (nodeType == InstrTreeNode::NTVRegListNode ||
 366           nodeType == InstrTreeNode::NTInstructionNode)
 367         SelectInstructionsForTree(kids[i], nts[i]);
 368     }
 369   }
 370
 371   // Finally, do any post-processing on this node after its children
 372   // have been translated
 373   //
 374   if (treeRoot->opLabel != VRegListOp)
 375     PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
 376 }
 377
 378 //---------------------------------------------------------------------------
 379 // Function PostprocessMachineCodeForTree
 380 //
 381 // Apply any final cleanups to machine code for the root of a subtree
 382 // after selection for all its children has been completed.
 383 //
 384 void
 385 InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
 386                                                     int ruleForNode,
 387                                                     short* nts)
 388 {
 389   // Fix up any constant operands in the machine instructions to either
 390   // use an immediate field or to load the constant into a register
 391   // Walk backwards and use direct indexes to allow insertion before current
 392   //
 393   Instruction* vmInstr = instrNode->getInstruction();
 394   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
 395   for (unsigned i = mvec.size(); i != 0; --i) {
 396     std::vector<MachineInstr*> loadConstVec =
 397       FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
 398
 399     mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
 400   }
 401 }
 402
 403
 404 //===----------------------------------------------------------------------===//
 405 // createInstructionSelectionPass - Public entrypoint for instruction selection
 406 // and this file as a whole...
 407 //
 408 FunctionPass *llvm::createInstructionSelectionPass(TargetMachine &TM) {
 409   return new InstructionSelection(TM);
 410 }