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     Function* function;
 119
 120     GlobalVariable* getGlobalForConstant(Constant* CV) {
 121       Module* M = function->getParent();
 122       return ConstantPoolForModule::get(M).getGlobalForConstant(CV);
 123     }
 124
 125   public:
 126     PreSelection (const TargetMachine &T): target(T), 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 visitLoadInst(LoadInst &I);
 146     void visitCastInst(CastInst &I);
 147     void visitCallInst(CallInst &I);
 148     void visitStoreInst(StoreInst &I);
 149
 150     // Helper functions for visiting operands of every instruction
 151     //
 152     // visitOperands() works on every operand in [firstOp, lastOp-1].
 153     // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
 154     //
 155     // visitOneOperand() does all the work for one operand.
 156     //
 157     void visitOperands(Instruction &I, int firstOp=0, int lastOp=0);
 158     void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 159                          Instruction& insertBefore);
 160   };
 161
 162   // Register the pass...
 163   RegisterOpt<PreSelection> X("preselect",
 164                               "Specialize LLVM code for a target machine",
 165                               createPreSelectionPass);
 166 }  // end anonymous namespace
 167
 168
 169 //------------------------------------------------------------------------------
 170 // Helper functions used by methods of class PreSelection
 171 //------------------------------------------------------------------------------
 172
 173
 174 // getGlobalAddr(): Put address of a global into a v. register.
 175 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
 176 {
 177   if (isa<ConstantPointerRef>(ptr))
 178     ptr = cast<ConstantPointerRef>(ptr)->getValue();
 179
 180   return (isa<GlobalVariable>(ptr))
 181     ? new GetElementPtrInst(ptr,
 182                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
 183                     "addrOfGlobal", &insertBefore)
 184     : NULL;
 185 }
 186
 187
 188 // Wrapper on Constant::classof to use in find_if :-(
 189 inline static bool nonConstant(const Use& U)
 190 {
 191   return ! isa<Constant>(U);
 192 }
 193
 194
 195 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
 196                                           Instruction& insertBefore)
 197 {
 198   Value *getArg1, *getArg2;
 199
 200   switch(CE->getOpcode())
 201     {
 202     case Instruction::Cast:
 203       getArg1 = CE->getOperand(0);
 204       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 205         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 206       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
 207
 208     case Instruction::GetElementPtr:
 209       assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
 210              && "All indices in ConstantExpr getelementptr must be constant!");
 211       getArg1 = CE->getOperand(0);
 212       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 213         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 214       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
 215         getArg1 = gep;
 216       return new GetElementPtrInst(getArg1,
 217                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
 218                           "constantGEP", &insertBefore);
 219
 220     default:                            // must be a binary operator
 221       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
 222              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
 223              "Unrecognized opcode in ConstantExpr");
 224       getArg1 = CE->getOperand(0);
 225       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 226         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 227       getArg2 = CE->getOperand(1);
 228       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 229         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 230       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
 231                                     getArg1, getArg2,
 232                                     "constantBinaryOp", &insertBefore);
 233     }
 234 }
 235
 236
 237 //------------------------------------------------------------------------------
 238 // Instruction visitor methods to perform instruction-specific operations
 239 //------------------------------------------------------------------------------
 240
 241 // Common work for *all* instructions.  This needs to be called explicitly
 242 // by other visit<InstructionType> functions.
 243 inline void
 244 PreSelection::visitInstruction(Instruction &I)
 245 {
 246   visitOperands(I);              // Perform operand transformations
 247 }
 248
 249
 250 // GetElementPtr instructions: check if pointer is a global
 251 void
 252 PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
 253 {
 254   // Check for a global and put its address into a register before this instr
 255   if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
 256     I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
 257
 258   // Decompose multidimensional array references
 259   DecomposeArrayRef(&I);
 260
 261   // Perform other transformations common to all instructions
 262   visitInstruction(I);
 263 }
 264
 265
 266 // Load instructions: check if pointer is a global
 267 void
 268 PreSelection::visitLoadInst(LoadInst &I)
 269 {
 270   // Check for a global and put its address into a register before this instr
 271   if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
 272     I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
 273
 274   // Perform other transformations common to all instructions
 275   visitInstruction(I);
 276 }
 277
 278
 279 // Store instructions: check if pointer is a global
 280 void
 281 PreSelection::visitStoreInst(StoreInst &I)
 282 {
 283   // Check for a global and put its address into a register before this instr
 284   if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
 285     I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
 286
 287   // Perform other transformations common to all instructions
 288   visitInstruction(I);
 289 }
 290
 291
 292 // Cast instructions:
 293 // -- check if argument is a global
 294 // -- make multi-step casts explicit:
 295 //    -- float/double to uint32_t:
 296 //         If target does not have a float-to-unsigned instruction, we
 297 //         need to convert to uint64_t and then to uint32_t, or we may
 298 //         overflow the signed int representation for legal uint32_t
 299 //         values.  Expand this without checking target.
 300 //
 301 void
 302 PreSelection::visitCastInst(CastInst &I)
 303 {
 304   CastInst* castI = NULL;
 305
 306   // Check for a global and put its address into a register before this instr
 307   if (GetElementPtrInst* gep = getGlobalAddr(I.getOperand(0), I))
 308     {
 309       I.setOperand(0, gep);             // replace pointer operand
 310     }
 311   else if (I.getType() == Type::UIntTy &&
 312            I.getOperand(0)->getType()->isFloatingPoint())
 313     { // insert a cast-fp-to-long before I, and then replace the operand of I
 314       castI = new CastInst(I.getOperand(0), Type::LongTy, "fp2Long2Uint", &I);
 315       I.setOperand(0, castI);           // replace fp operand with long
 316     }
 317
 318   // Perform other transformations common to all instructions
 319   visitInstruction(I);
 320   if (castI)
 321     visitInstruction(*castI);
 322 }
 323
 324 void
 325 PreSelection::visitCallInst(CallInst &I)
 326 {
 327   // Tell visitOperands to ignore the function name if this is a direct call.
 328   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
 329 }
 330
 331
 332 // visitOperands() transforms individual operands of all instructions:
 333 // -- Load "large" int constants into a virtual register.  What is large
 334 //    depends on the type of instruction and on the target architecture.
 335 // -- For any constants that cannot be put in an immediate field,
 336 //    load address into virtual register first, and then load the constant.
 337 //
 338 // firstOp and lastOp can be used to skip leading and trailing operands.
 339 // If lastOp is 0, it defaults to #operands or #incoming Phi values.
 340 //
 341 void
 342 PreSelection::visitOperands(Instruction &I, int firstOp, int lastOp)
 343 {
 344   // For any instruction other than PHI, copies go just before the instr.
 345   // For a PHI, operand copies must be before the terminator of the
 346   // appropriate predecessor basic block.  Remaining logic is simple
 347   // so just handle PHIs and other instructions separately.
 348   //
 349   if (PHINode* phi = dyn_cast<PHINode>(&I))
 350     {
 351       if (lastOp == 0)
 352         lastOp = phi->getNumIncomingValues();
 353       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 354         this->visitOneOperand(I, phi->getIncomingValue(i),
 355                               phi->getOperandNumForIncomingValue(i),
 356                               * phi->getIncomingBlock(i)->getTerminator());
 357     }
 358   else
 359     {
 360       if (lastOp == 0)
 361         lastOp = I.getNumOperands();
 362       for (unsigned i=firstOp, N=lastOp; i < N; ++i)
 363         this->visitOneOperand(I, I.getOperand(i), i, I);
 364     }
 365 }
 366
 367 void
 368 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 369                               Instruction& insertBefore)
 370 {
 371   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
 372     I.setOperand(opNum, gep);           // replace global operand
 373     return;
 374   }
 375
 376   Constant* CV  = dyn_cast<Constant>(Op);
 377   if (CV == NULL)
 378     return;
 379
 380   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
 381     { // load-time constant: factor it out so we optimize as best we can
 382       Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
 383       I.setOperand(opNum, computeConst); // replace expr operand with result
 384     }
 385   else if (target.getInstrInfo().ConstantTypeMustBeLoaded(CV))
 386     { // load address of constant into a register, then load the constant
 387       GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
 388                                              insertBefore);
 389       LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
 390       I.setOperand(opNum, ldI);        // replace operand with copy in v.reg.
 391     }
 392   else if (target.getInstrInfo().ConstantMayNotFitInImmedField(CV, &I))
 393     { // put the constant into a virtual register using a cast
 394       CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
 395                                      &insertBefore);
 396       I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
 397     }
 398 }
 399
 400
 401 //===----------------------------------------------------------------------===//
 402 // createPreSelectionPass - Public entrypoint for pre-selection pass
 403 // and this file as a whole...
 404 //
 405 Pass*
 406 createPreSelectionPass(TargetMachine &T)
 407 {
 408   return new PreSelection(T);
 409 }
 410