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 "SparcInternals.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   //
 113   class PreSelection : public BasicBlockPass, public InstVisitor<PreSelection>
 114   {
 115     const TargetMachine &target;
 116     const TargetInstrInfo &instrInfo;
 117     Function* function;
 118
 119     GlobalVariable* getGlobalForConstant(Constant* CV) {
 120       Module* M = function->getParent();
 121       return ConstantPoolForModule::get(M).getGlobalForConstant(CV);
 122     }
 123
 124   public:
 125     PreSelection (const TargetMachine &T):
 126       target(T), instrInfo(T.getInstrInfo()), function(NULL) {}
 127
 128     // runOnBasicBlock - apply this pass to each BB
 129     bool runOnBasicBlock(BasicBlock &BB) {
 130       function = BB.getParent();
 131       this->visit(BB);
 132       return true;
 133     }
 134
 135     bool doFinalization(Function &F) {
 136       if (PreSelectDebugLevel >= PreSelect_PrintOutput)
 137         std::cerr << "\n\n*** LLVM code after pre-selection for function "
 138                   << F.getName() << ":\n\n" << F;
 139       return false;
 140     }
 141
 142     // These methods do the actual work of specializing code
 143     void visitInstruction(Instruction &I);   // common work for every instr.
 144     void visitGetElementPtrInst(GetElementPtrInst &I);
 145     void visitCallInst(CallInst &I);
 146
 147     // Helper functions for visiting operands of every instruction
 148     //
 149     // visitOperands() works on every operand in [firstOp, lastOp-1].
 150     // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
 151     //
 152     // visitOneOperand() does all the work for one operand.
 153     //
 154     void visitOperands(Instruction &I, int firstOp=0, int lastOp=0);
 155     void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 156                          Instruction& insertBefore);
 157   };
 158
 159   // Register the pass...
 160   RegisterOpt<PreSelection> X("preselect",
 161                               "Specialize LLVM code for a target machine",
 162                               createPreSelectionPass);
 163 }  // end anonymous namespace
 164
 165
 166 //------------------------------------------------------------------------------
 167 // Helper functions used by methods of class PreSelection
 168 //------------------------------------------------------------------------------
 169
 170
 171 // getGlobalAddr(): Put address of a global into a v. register.
 172 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
 173 {
 174   if (isa<ConstantPointerRef>(ptr))
 175     ptr = cast<ConstantPointerRef>(ptr)->getValue();
 176
 177   return (isa<GlobalVariable>(ptr))
 178     ? new GetElementPtrInst(ptr,
 179                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
 180                     "addrOfGlobal", &insertBefore)
 181     : NULL;
 182 }
 183
 184
 185 // Wrapper on Constant::classof to use in find_if :-(
 186 inline static bool nonConstant(const Use& U)
 187 {
 188   return ! isa<Constant>(U);
 189 }
 190
 191
 192 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
 193                                           Instruction& insertBefore)
 194 {
 195   Value *getArg1, *getArg2;
 196
 197   switch(CE->getOpcode())
 198     {
 199     case Instruction::Cast:
 200       getArg1 = CE->getOperand(0);
 201       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 202         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 203       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
 204
 205     case Instruction::GetElementPtr:
 206       assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
 207              && "All indices in ConstantExpr getelementptr must be constant!");
 208       getArg1 = CE->getOperand(0);
 209       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 210         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 211       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
 212         getArg1 = gep;
 213       return new GetElementPtrInst(getArg1,
 214                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
 215                           "constantGEP", &insertBefore);
 216
 217     default:                            // must be a binary operator
 218       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
 219              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
 220              "Unrecognized opcode in ConstantExpr");
 221       getArg1 = CE->getOperand(0);
 222       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 223         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 224       getArg2 = CE->getOperand(1);
 225       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 226         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 227       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
 228                                     getArg1, getArg2,
 229                                     "constantBinaryOp", &insertBefore);
 230     }
 231 }
 232
 233
 234 //------------------------------------------------------------------------------
 235 // Instruction visitor methods to perform instruction-specific operations
 236 //------------------------------------------------------------------------------
 237 inline void
 238 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 239                               Instruction& insertBefore)
 240 {
 241   assert(&insertBefore != NULL && "Must have instruction to insert before.");
 242
 243   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
 244     I.setOperand(opNum, gep);           // replace global operand
 245     return;                             // nothing more to do for this op.
 246   }
 247
 248   Constant* CV  = dyn_cast<Constant>(Op);
 249   if (CV == NULL)
 250     return;
 251
 252   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
 253     { // load-time constant: factor it out so we optimize as best we can
 254       Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
 255       I.setOperand(opNum, computeConst); // replace expr operand with result
 256     }
 257   else if (instrInfo.ConstantTypeMustBeLoaded(CV))
 258     { // load address of constant into a register, then load the constant
 259       GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
 260                                              insertBefore);
 261       LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
 262       I.setOperand(opNum, ldI);        // replace operand with copy in v.reg.
 263     }
 264   else if (instrInfo.ConstantMayNotFitInImmedField(CV, &I))
 265     { // put the constant into a virtual register using a cast
 266       CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
 267                                      &insertBefore);
 268       I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
 269     }
 270 }
 271
 272 // visitOperands() transforms individual operands of all instructions:
 273 // -- Load "large" int constants into a virtual register.  What is large
 274 //    depends on the type of instruction and on the target architecture.
 275 // -- For any constants that cannot be put in an immediate field,
 276 //    load address into virtual register first, and then load the constant.
 277 //
 278 // firstOp and lastOp can be used to skip leading and trailing operands.
 279 // If lastOp is 0, it defaults to #operands or #incoming Phi values.
 280 //
 281 inline void
 282 PreSelection::visitOperands(Instruction &I, int firstOp, int lastOp)
 283 {
 284   // For any instruction other than PHI, copies go just before the instr.
 285   // For a PHI, operand copies must be before the terminator of the
 286   // appropriate predecessor basic block.  Remaining logic is simple
 287   // so just handle PHIs and other instructions separately.
 288   //
 289   if (PHINode* phi = dyn_cast<PHINode>(&I))
 290     {
 291       if (lastOp == 0)
 292         lastOp = phi->getNumIncomingValues();
 293       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 294         this->visitOneOperand(I, phi->getIncomingValue(i),
 295                               phi->getOperandNumForIncomingValue(i),
 296                               * phi->getIncomingBlock(i)->getTerminator());
 297     }
 298   else
 299     {
 300       if (lastOp == 0)
 301         lastOp = I.getNumOperands();
 302       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 303         this->visitOneOperand(I, I.getOperand(i), i, I);
 304     }
 305 }
 306
 307
 308
 309 // Common work for *all* instructions.  This needs to be called explicitly
 310 // by other visit<InstructionType> functions.
 311 inline void
 312 PreSelection::visitInstruction(Instruction &I)
 313 {
 314   visitOperands(I);              // Perform operand transformations
 315 }
 316
 317
 318 // GetElementPtr instructions: check if pointer is a global
 319 void
 320 PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
 321 {
 322   Instruction* curI = &I;
 323
 324   // Decompose multidimensional array references
 325   if (I.getNumIndices() >= 2) {
 326     // DecomposeArrayRef() replaces I and deletes it, if successful,
 327     // so remember predecessor in order to find the replacement instruction.
 328     // Also remember the basic block in case there is no predecessor.
 329     Instruction* prevI = I.getPrev();
 330     BasicBlock* bb = I.getParent();
 331     if (DecomposeArrayRef(&I))
 332       // first instr. replacing I
 333       curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
 334   }
 335
 336   // Perform other transformations common to all instructions
 337   visitInstruction(*curI);
 338 }
 339
 340
 341 void
 342 PreSelection::visitCallInst(CallInst &I)
 343 {
 344   // Tell visitOperands to ignore the function name if this is a direct call.
 345   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
 346 }
 347
 348
 349 //===----------------------------------------------------------------------===//
 350 // createPreSelectionPass - Public entrypoint for pre-selection pass
 351 // and this file as a whole...
 352 //
 353 Pass*
 354 createPreSelectionPass(TargetMachine &T)
 355 {
 356   return new PreSelection(T);
 357 }
 358