lib/Target/SparcV9/SparcV9PreSelection.cpp

   1 //===- PreSelection.cpp - Specialize LLVM code for target machine ---------===//
   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 // This file defines the PreSelection pass which specializes LLVM code for a
  11 // target machine, while remaining in legal portable LLVM form and
  12 // preserving type information and type safety.  This is meant to enable
  13 // dataflow optimizations on target-specific operations such as accesses to
  14 // constants, globals, and array indexing.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "SparcInternals.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/TargetInstrInfo.h"
  21 #include "llvm/Transforms/Scalar.h"
  22 #include "llvm/Support/InstVisitor.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Constants.h"
  25 #include "llvm/iMemory.h"
  26 #include "llvm/iPHINode.h"
  27 #include "llvm/iOther.h"
  28 #include "llvm/DerivedTypes.h"
  29 #include "llvm/Pass.h"
  30 #include <algorithm>
  31
  32 namespace {
  33
  34   //===--------------------------------------------------------------------===//
  35   // PreSelection Pass - Specialize LLVM code for the current target machine.
  36   //
  37   class PreSelection : public Pass, public InstVisitor<PreSelection> {
  38     const TargetInstrInfo &instrInfo;
  39     Module *TheModule;
  40
  41     std::map<const Constant*, GlobalVariable*> gvars;
  42
  43     GlobalVariable* getGlobalForConstant(Constant* CV) {
  44       std::map<const Constant*, GlobalVariable*>::iterator I = gvars.find(CV);
  45       if (I != gvars.end()) return I->second;    // global exists so return it
  46
  47       return I->second = new GlobalVariable(CV->getType(), true,
  48                                             GlobalValue::InternalLinkage, CV,
  49                                             "immcst", TheModule);
  50     }
  51
  52   public:
  53     PreSelection(const TargetMachine &T)
  54       : instrInfo(T.getInstrInfo()), TheModule(0) {}
  55
  56     // runOnBasicBlock - apply this pass to each BB
  57     bool run(Module &M) {
  58       TheModule = &M;
  59
  60       // Build reverse map for pre-existing global constants so we can find them
  61       for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
  62         if (I->hasInitializer() && I->isConstant())
  63           gvars[I->getInitializer()] = I;
  64
  65       for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  66         visit(*I);
  67
  68       gvars.clear();
  69       return true;
  70     }
  71
  72     // These methods do the actual work of specializing code
  73     void visitInstruction(Instruction &I);   // common work for every instr.
  74     void visitGetElementPtrInst(GetElementPtrInst &I);
  75     void visitCallInst(CallInst &I);
  76
  77     // Helper functions for visiting operands of every instruction
  78     //
  79     // visitOperands() works on every operand in [firstOp, lastOp-1].
  80     // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
  81     //
  82     // visitOneOperand() does all the work for one operand.
  83     //
  84     void visitOperands(Instruction &I, int firstOp=0, int lastOp=0);
  85     void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
  86                          Instruction& insertBefore);
  87   };
  88
  89   // Register the pass...
  90   RegisterOpt<PreSelection> X("preselect",
  91                               "Specialize LLVM code for a target machine",
  92                               createPreSelectionPass);
  93 }  // end anonymous namespace
  94
  95
  96 //------------------------------------------------------------------------------
  97 // Helper functions used by methods of class PreSelection
  98 //------------------------------------------------------------------------------
  99
 100
 101 // getGlobalAddr(): Put address of a global into a v. register.
 102 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
 103 {
 104   if (isa<ConstantPointerRef>(ptr))
 105     ptr = cast<ConstantPointerRef>(ptr)->getValue();
 106
 107   return (isa<GlobalVariable>(ptr))
 108     ? new GetElementPtrInst(ptr,
 109                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
 110                     "addrOfGlobal", &insertBefore)
 111     : NULL;
 112 }
 113
 114
 115 // Wrapper on Constant::classof to use in find_if :-(
 116 inline static bool nonConstant(const Use& U)
 117 {
 118   return ! isa<Constant>(U);
 119 }
 120
 121
 122 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
 123                                           Instruction& insertBefore)
 124 {
 125   Value *getArg1, *getArg2;
 126
 127   switch(CE->getOpcode())
 128     {
 129     case Instruction::Cast:
 130       getArg1 = CE->getOperand(0);
 131       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 132         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 133       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
 134
 135     case Instruction::GetElementPtr:
 136       assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
 137              && "All indices in ConstantExpr getelementptr must be constant!");
 138       getArg1 = CE->getOperand(0);
 139       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 140         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 141       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
 142         getArg1 = gep;
 143       return new GetElementPtrInst(getArg1,
 144                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
 145                           "constantGEP", &insertBefore);
 146
 147     default:                            // must be a binary operator
 148       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
 149              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
 150              "Unrecognized opcode in ConstantExpr");
 151       getArg1 = CE->getOperand(0);
 152       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 153         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 154       getArg2 = CE->getOperand(1);
 155       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 156         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 157       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
 158                                     getArg1, getArg2,
 159                                     "constantBinaryOp", &insertBefore);
 160     }
 161 }
 162
 163
 164 //------------------------------------------------------------------------------
 165 // Instruction visitor methods to perform instruction-specific operations
 166 //------------------------------------------------------------------------------
 167 inline void
 168 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 169                               Instruction& insertBefore)
 170 {
 171   assert(&insertBefore != NULL && "Must have instruction to insert before.");
 172
 173   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
 174     I.setOperand(opNum, gep);           // replace global operand
 175     return;                             // nothing more to do for this op.
 176   }
 177
 178   Constant* CV  = dyn_cast<Constant>(Op);
 179   if (CV == NULL)
 180     return;
 181
 182   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
 183     { // load-time constant: factor it out so we optimize as best we can
 184       Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
 185       I.setOperand(opNum, computeConst); // replace expr operand with result
 186     }
 187   else if (instrInfo.ConstantTypeMustBeLoaded(CV))
 188     { // load address of constant into a register, then load the constant
 189       GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
 190                                              insertBefore);
 191       LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
 192       I.setOperand(opNum, ldI);        // replace operand with copy in v.reg.
 193     }
 194   else if (instrInfo.ConstantMayNotFitInImmedField(CV, &I))
 195     { // put the constant into a virtual register using a cast
 196       CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
 197                                      &insertBefore);
 198       I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
 199     }
 200 }
 201
 202 // visitOperands() transforms individual operands of all instructions:
 203 // -- Load "large" int constants into a virtual register.  What is large
 204 //    depends on the type of instruction and on the target architecture.
 205 // -- For any constants that cannot be put in an immediate field,
 206 //    load address into virtual register first, and then load the constant.
 207 //
 208 // firstOp and lastOp can be used to skip leading and trailing operands.
 209 // If lastOp is 0, it defaults to #operands or #incoming Phi values.
 210 //
 211 inline void
 212 PreSelection::visitOperands(Instruction &I, int firstOp, int lastOp)
 213 {
 214   // For any instruction other than PHI, copies go just before the instr.
 215   // For a PHI, operand copies must be before the terminator of the
 216   // appropriate predecessor basic block.  Remaining logic is simple
 217   // so just handle PHIs and other instructions separately.
 218   //
 219   if (PHINode* phi = dyn_cast<PHINode>(&I))
 220     {
 221       if (lastOp == 0)
 222         lastOp = phi->getNumIncomingValues();
 223       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 224         this->visitOneOperand(I, phi->getIncomingValue(i),
 225                               phi->getOperandNumForIncomingValue(i),
 226                               * phi->getIncomingBlock(i)->getTerminator());
 227     }
 228   else
 229     {
 230       if (lastOp == 0)
 231         lastOp = I.getNumOperands();
 232       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 233         this->visitOneOperand(I, I.getOperand(i), i, I);
 234     }
 235 }
 236
 237
 238
 239 // Common work for *all* instructions.  This needs to be called explicitly
 240 // by other visit<InstructionType> functions.
 241 inline void
 242 PreSelection::visitInstruction(Instruction &I)
 243 {
 244   visitOperands(I);              // Perform operand transformations
 245 }
 246
 247
 248 // GetElementPtr instructions: check if pointer is a global
 249 void
 250 PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
 251 {
 252   Instruction* curI = &I;
 253
 254   // Decompose multidimensional array references
 255   if (I.getNumIndices() >= 2) {
 256     // DecomposeArrayRef() replaces I and deletes it, if successful,
 257     // so remember predecessor in order to find the replacement instruction.
 258     // Also remember the basic block in case there is no predecessor.
 259     Instruction* prevI = I.getPrev();
 260     BasicBlock* bb = I.getParent();
 261     if (DecomposeArrayRef(&I))
 262       // first instr. replacing I
 263       curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
 264   }
 265
 266   // Perform other transformations common to all instructions
 267   visitInstruction(*curI);
 268 }
 269
 270
 271 void
 272 PreSelection::visitCallInst(CallInst &I)
 273 {
 274   // Tell visitOperands to ignore the function name if this is a direct call.
 275   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
 276 }
 277
 278
 279 //===----------------------------------------------------------------------===//
 280 // createPreSelectionPass - Public entrypoint for pre-selection pass
 281 // and this file as a whole...
 282 //
 283 Pass* createPreSelectionPass(TargetMachine &T) {
 284   return new PreSelection(T);
 285 }
 286