lib/Target/SparcV9/SparcV9PreSelection.cpp

   1 //===- PreSelection.cpp - Specialize LLVM code for target machine ---------===//
   2 //
   3 // This file defines the PreSelection pass which specializes LLVM code for a
   4 // target machine, while remaining in legal portable LLVM form and
   5 // preserving type information and type safety.  This is meant to enable
   6 // dataflow optimizations on target-specific operations such as accesses to
   7 // constants, globals, and array indexing.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #include "llvm/CodeGen/PreSelection.h"
  12 #include "llvm/Target/TargetMachine.h"
  13 #include "llvm/Target/TargetInstrInfo.h"
  14 #include "llvm/Transforms/Scalar.h"
  15 #include "llvm/Support/InstVisitor.h"
  16 #include "llvm/Module.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/iMemory.h"
  19 #include "llvm/iPHINode.h"
  20 #include "llvm/iOther.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Pass.h"
  23 #include "Support/CommandLine.h"
  24 #include <algorithm>
  25
  26 namespace {
  27   //===--------------------------------------------------------------------===//
  28   // SelectDebugLevel - Allow command line control over debugging.
  29   //
  30   enum PreSelectDebugLevel_t {
  31     PreSelect_NoDebugInfo,
  32     PreSelect_PrintOutput,
  33   };
  34
  35   // Enable Debug Options to be specified on the command line
  36   cl::opt<PreSelectDebugLevel_t>
  37   PreSelectDebugLevel("dpreselect", cl::Hidden,
  38      cl::desc("debug information for target-dependent pre-selection"),
  39      cl::values(
  40        clEnumValN(PreSelect_NoDebugInfo, "n", "disable debug output (default)"),
  41        clEnumValN(PreSelect_PrintOutput, "y", "print generated machine code"),
  42        /* default level = */ PreSelect_NoDebugInfo));
  43
  44
  45   //===--------------------------------------------------------------------===//
  46   // class ConstantPoolForModule:
  47   //
  48   // The pool of constants that must be emitted for a module.
  49   // This is a single pool for the entire module and is shared by
  50   // all invocations of the PreSelection pass for this module by putting
  51   // this as an annotation on the Module object.
  52   // A single GlobalVariable is created for each constant in the pool
  53   // representing the memory for that constant.
  54   //
  55   AnnotationID CPFM_AID(
  56                  AnnotationManager::getID("CodeGen::ConstantPoolForModule"));
  57
  58   class ConstantPoolForModule : private Annotation {
  59     Module* myModule;
  60     std::map<const Constant*, GlobalVariable*> gvars;
  61     std::map<const Constant*, GlobalVariable*> origGVars;
  62     ConstantPoolForModule(Module* M);   // called only by annotation builder
  63     ConstantPoolForModule();                      // DO NOT IMPLEMENT
  64     void operator=(const ConstantPoolForModule&); // DO NOT IMPLEMENT
  65   public:
  66     static ConstantPoolForModule& get(Module* M) {
  67       ConstantPoolForModule* cpool =
  68         (ConstantPoolForModule*) M->getAnnotation(CPFM_AID);
  69       if (cpool == NULL) // create a new annotation and add it to the Module
  70         M->addAnnotation(cpool = new ConstantPoolForModule(M));
  71       return *cpool;
  72     }
  73
  74     GlobalVariable* getGlobalForConstant(Constant* CV) {
  75       std::map<const Constant*, GlobalVariable*>::iterator I = gvars.find(CV);
  76       if (I != gvars.end())
  77         return I->second;               // global exists so return it
  78       return addToConstantPool(CV);     // create a new global and return it
  79     }
  80
  81     GlobalVariable*  addToConstantPool(Constant* CV) {
  82       GlobalVariable*& GV = gvars[CV];  // handle to global var entry in map
  83       if (GV == NULL)
  84         { // check if a global constant already existed; otherwise create one
  85           std::map<const Constant*, GlobalVariable*>::iterator PI =
  86             origGVars.find(CV);
  87           if (PI != origGVars.end())
  88             GV = PI->second;            // put in map
  89           else
  90             {
  91               GV = new GlobalVariable(CV->getType(), true, //put in map
  92                                       GlobalValue::InternalLinkage, CV);
  93               myModule->getGlobalList().push_back(GV); // GV owned by module now
  94             }
  95         }
  96       return GV;
  97     }
  98   };
  99
 100   /* ctor */
 101   ConstantPoolForModule::ConstantPoolForModule(Module* M)
 102     : Annotation(CPFM_AID), myModule(M)
 103   {
 104     // Build reverse map for pre-existing global constants so we can find them
 105     for (Module::giterator GI = M->gbegin(), GE = M->gend(); GI != GE; ++GI)
 106       if (GI->hasInitializer() && GI->isConstant())
 107         origGVars[GI->getInitializer()] = GI;
 108   }
 109
 110   //===--------------------------------------------------------------------===//
 111   // PreSelection Pass - Specialize LLVM code for the current target machine.
 112   // This was and will be a basicblock pass, but make it a FunctionPass until
 113   // BasicBlockPass ::doFinalization(Function&) is available.
 114   //
 115   class PreSelection : public BasicBlockPass, public InstVisitor<PreSelection>
 116   {
 117     const TargetMachine &target;
 118     const TargetInstrInfo &instrInfo;
 119     Function* function;
 120
 121     GlobalVariable* getGlobalForConstant(Constant* CV) {
 122       Module* M = function->getParent();
 123       return ConstantPoolForModule::get(M).getGlobalForConstant(CV);
 124     }
 125
 126   public:
 127     PreSelection (const TargetMachine &T):
 128       target(T), instrInfo(T.getInstrInfo()), function(NULL) {}
 129
 130     // runOnBasicBlock - apply this pass to each BB
 131     bool runOnBasicBlock(BasicBlock &BB) {
 132       function = BB.getParent();
 133       this->visit(BB);
 134       return true;
 135     }
 136
 137     bool doFinalization(Function &F) {
 138       if (PreSelectDebugLevel >= PreSelect_PrintOutput)
 139         std::cerr << "\n\n*** LLVM code after pre-selection for function "
 140                   << F.getName() << ":\n\n" << F;
 141       return false;
 142     }
 143
 144     // These methods do the actual work of specializing code
 145     void visitInstruction(Instruction &I);   // common work for every instr.
 146     void visitGetElementPtrInst(GetElementPtrInst &I);
 147     void visitCallInst(CallInst &I);
 148
 149     // Helper functions for visiting operands of every instruction
 150     //
 151     // visitOperands() works on every operand in [firstOp, lastOp-1].
 152     // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
 153     //
 154     // visitOneOperand() does all the work for one operand.
 155     //
 156     void visitOperands(Instruction &I, int firstOp=0, int lastOp=0);
 157     void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 158                          Instruction& insertBefore);
 159   };
 160
 161   // Register the pass...
 162   RegisterOpt<PreSelection> X("preselect",
 163                               "Specialize LLVM code for a target machine",
 164                               createPreSelectionPass);
 165 }  // end anonymous namespace
 166
 167
 168 //------------------------------------------------------------------------------
 169 // Helper functions used by methods of class PreSelection
 170 //------------------------------------------------------------------------------
 171
 172
 173 // getGlobalAddr(): Put address of a global into a v. register.
 174 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
 175 {
 176   if (isa<ConstantPointerRef>(ptr))
 177     ptr = cast<ConstantPointerRef>(ptr)->getValue();
 178
 179   return (isa<GlobalVariable>(ptr))
 180     ? new GetElementPtrInst(ptr,
 181                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
 182                     "addrOfGlobal", &insertBefore)
 183     : NULL;
 184 }
 185
 186
 187 // Wrapper on Constant::classof to use in find_if :-(
 188 inline static bool nonConstant(const Use& U)
 189 {
 190   return ! isa<Constant>(U);
 191 }
 192
 193
 194 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
 195                                           Instruction& insertBefore)
 196 {
 197   Value *getArg1, *getArg2;
 198
 199   switch(CE->getOpcode())
 200     {
 201     case Instruction::Cast:
 202       getArg1 = CE->getOperand(0);
 203       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 204         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 205       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
 206
 207     case Instruction::GetElementPtr:
 208       assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
 209              && "All indices in ConstantExpr getelementptr must be constant!");
 210       getArg1 = CE->getOperand(0);
 211       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 212         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 213       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
 214         getArg1 = gep;
 215       return new GetElementPtrInst(getArg1,
 216                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
 217                           "constantGEP", &insertBefore);
 218
 219     default:                            // must be a binary operator
 220       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
 221              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
 222              "Unrecognized opcode in ConstantExpr");
 223       getArg1 = CE->getOperand(0);
 224       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 225         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 226       getArg2 = CE->getOperand(1);
 227       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 228         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 229       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
 230                                     getArg1, getArg2,
 231                                     "constantBinaryOp", &insertBefore);
 232     }
 233 }
 234
 235
 236 //------------------------------------------------------------------------------
 237 // Instruction visitor methods to perform instruction-specific operations
 238 //------------------------------------------------------------------------------
 239 inline void
 240 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 241                               Instruction& insertBefore)
 242 {
 243   assert(&insertBefore != NULL && "Must have instruction to insert before.");
 244
 245   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
 246     I.setOperand(opNum, gep);           // replace global operand
 247     return;                             // nothing more to do for this op.
 248   }
 249
 250   Constant* CV  = dyn_cast<Constant>(Op);
 251   if (CV == NULL)
 252     return;
 253
 254   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
 255     { // load-time constant: factor it out so we optimize as best we can
 256       Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
 257       I.setOperand(opNum, computeConst); // replace expr operand with result
 258     }
 259   else if (instrInfo.ConstantTypeMustBeLoaded(CV))
 260     { // load address of constant into a register, then load the constant
 261       GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
 262                                              insertBefore);
 263       LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
 264       I.setOperand(opNum, ldI);        // replace operand with copy in v.reg.
 265     }
 266   else if (instrInfo.ConstantMayNotFitInImmedField(CV, &I))
 267     { // put the constant into a virtual register using a cast
 268       CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
 269                                      &insertBefore);
 270       I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
 271     }
 272 }
 273
 274 // visitOperands() transforms individual operands of all instructions:
 275 // -- Load "large" int constants into a virtual register.  What is large
 276 //    depends on the type of instruction and on the target architecture.
 277 // -- For any constants that cannot be put in an immediate field,
 278 //    load address into virtual register first, and then load the constant.
 279 //
 280 // firstOp and lastOp can be used to skip leading and trailing operands.
 281 // If lastOp is 0, it defaults to #operands or #incoming Phi values.
 282 //
 283 inline void
 284 PreSelection::visitOperands(Instruction &I, int firstOp, int lastOp)
 285 {
 286   // For any instruction other than PHI, copies go just before the instr.
 287   // For a PHI, operand copies must be before the terminator of the
 288   // appropriate predecessor basic block.  Remaining logic is simple
 289   // so just handle PHIs and other instructions separately.
 290   //
 291   if (PHINode* phi = dyn_cast<PHINode>(&I))
 292     {
 293       if (lastOp == 0)
 294         lastOp = phi->getNumIncomingValues();
 295       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 296         this->visitOneOperand(I, phi->getIncomingValue(i),
 297                               phi->getOperandNumForIncomingValue(i),
 298                               * phi->getIncomingBlock(i)->getTerminator());
 299     }
 300   else
 301     {
 302       if (lastOp == 0)
 303         lastOp = I.getNumOperands();
 304       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 305         this->visitOneOperand(I, I.getOperand(i), i, I);
 306     }
 307 }
 308
 309
 310
 311 // Common work for *all* instructions.  This needs to be called explicitly
 312 // by other visit<InstructionType> functions.
 313 inline void
 314 PreSelection::visitInstruction(Instruction &I)
 315 {
 316   visitOperands(I);              // Perform operand transformations
 317 }
 318
 319
 320 // GetElementPtr instructions: check if pointer is a global
 321 void
 322 PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
 323 {
 324   Instruction* curI = &I;
 325
 326   // Decompose multidimensional array references
 327   if (I.getNumIndices() >= 2) {
 328     // DecomposeArrayRef() replaces I and deletes it, if successful,
 329     // so remember predecessor in order to find the replacement instruction.
 330     // Also remember the basic block in case there is no predecessor.
 331     Instruction* prevI = I.getPrev();
 332     BasicBlock* bb = I.getParent();
 333     if (DecomposeArrayRef(&I))
 334       // first instr. replacing I
 335       curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
 336   }
 337
 338   // Perform other transformations common to all instructions
 339   visitInstruction(*curI);
 340 }
 341
 342
 343 void
 344 PreSelection::visitCallInst(CallInst &I)
 345 {
 346   // Tell visitOperands to ignore the function name if this is a direct call.
 347   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
 348 }
 349
 350
 351 //===----------------------------------------------------------------------===//
 352 // createPreSelectionPass - Public entrypoint for pre-selection pass
 353 // and this file as a whole...
 354 //
 355 Pass*
 356 createPreSelectionPass(TargetMachine &T)
 357 {
 358   return new PreSelection(T);
 359 }
 360