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   static AnnotationID CPFM_AID(
  56                  AnnotationManager::getID("CodeGen::ConstantPoolForModule"));
  57
  58   class ConstantPoolForModule: private Annotation, public NonCopyable {
  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   public:
  65     static ConstantPoolForModule& get(Module* M) {
  66       ConstantPoolForModule* cpool =
  67         (ConstantPoolForModule*) M->getAnnotation(CPFM_AID);
  68       if (cpool == NULL) // create a new annotation and add it to the Module
  69         M->addAnnotation(cpool = new ConstantPoolForModule(M));
  70       return *cpool;
  71     }
  72
  73     GlobalVariable* getGlobalForConstant(Constant* CV) {
  74       std::map<const Constant*, GlobalVariable*>::iterator I = gvars.find(CV);
  75       if (I != gvars.end())
  76         return I->second;               // global exists so return it
  77       return addToConstantPool(CV);     // create a new global and return it
  78     }
  79
  80     GlobalVariable*  addToConstantPool(Constant* CV) {
  81       GlobalVariable*& GV = gvars[CV];  // handle to global var entry in map
  82       if (GV == NULL)
  83         { // check if a global constant already existed; otherwise create one
  84           std::map<const Constant*, GlobalVariable*>::iterator PI =
  85             origGVars.find(CV);
  86           if (PI != origGVars.end())
  87             GV = PI->second;            // put in map
  88           else
  89             {
  90               GV = new GlobalVariable(CV->getType(), true, //put in map
  91                                       GlobalValue::InternalLinkage, CV);
  92               myModule->getGlobalList().push_back(GV); // GV owned by module now
  93             }
  94         }
  95       return GV;
  96     }
  97   };
  98
  99   /* ctor */
 100   ConstantPoolForModule::ConstantPoolForModule(Module* M)
 101     : Annotation(CPFM_AID), myModule(M)
 102   {
 103     // Build reverse map for pre-existing global constants so we can find them
 104     for (Module::giterator GI = M->gbegin(), GE = M->gend(); GI != GE; ++GI)
 105       if (GI->hasInitializer() && GI->isConstant())
 106         origGVars[GI->getInitializer()] = GI;
 107   }
 108
 109   //===--------------------------------------------------------------------===//
 110   // PreSelection Pass - Specialize LLVM code for the current target machine.
 111   // This was and will be a basicblock pass, but make it a FunctionPass until
 112   // BasicBlockPass ::doFinalization(Function&) is available.
 113   //
 114   class PreSelection : public BasicBlockPass, public InstVisitor<PreSelection>
 115   {
 116     const TargetMachine &target;
 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): target(T), function(NULL) {}
 126
 127     // runOnBasicBlock - apply this pass to each BB
 128     bool runOnBasicBlock(BasicBlock &BB) {
 129       function = BB.getParent();
 130       this->visit(BB);
 131       return true;
 132     }
 133
 134     bool doFinalization(Function &F) {
 135       if (PreSelectDebugLevel >= PreSelect_PrintOutput)
 136         std::cerr << "\n\n*** LLVM code after pre-selection for function "
 137                   << F.getName() << ":\n\n" << F;
 138       return false;
 139     }
 140
 141     // These methods do the actual work of specializing code
 142     void visitInstruction(Instruction &I);   // common work for every instr.
 143     void visitGetElementPtrInst(GetElementPtrInst &I);
 144     void visitLoadInst(LoadInst &I);
 145     void visitCastInst(CastInst &I);
 146     void visitStoreInst(StoreInst &I);
 147
 148     // Helper functions for visiting operands of every instruction
 149     void visitOperands(Instruction &I);    // work on all operands of instr.
 150     void visitOneOperand(Instruction &I, Constant* CV, unsigned opNum,
 151                          Instruction& insertBefore); // iworks on one operand
 152   };
 153
 154   // Register the pass...
 155   RegisterOpt<PreSelection> X("preselect",
 156                               "Specialize LLVM code for a target machine",
 157                               createPreSelectionPass);
 158 }  // end anonymous namespace
 159
 160
 161 //------------------------------------------------------------------------------
 162 // Helper functions used by methods of class PreSelection
 163 //------------------------------------------------------------------------------
 164
 165
 166 // getGlobalAddr(): Put address of a global into a v. register.
 167 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
 168 {
 169   if (isa<ConstantPointerRef>(ptr))
 170     ptr = cast<ConstantPointerRef>(ptr)->getValue();
 171
 172   return (isa<GlobalValue>(ptr))
 173     ? new GetElementPtrInst(ptr,
 174                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
 175                     "addrOfGlobal", &insertBefore)
 176     : NULL;
 177 }
 178
 179
 180 // Wrapper on Constant::classof to use in find_if :-(
 181 inline static bool nonConstant(const Use& U)
 182 {
 183   return ! isa<Constant>(U);
 184 }
 185
 186
 187 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
 188                                           Instruction& insertBefore)
 189 {
 190   Value *getArg1, *getArg2;
 191
 192   switch(CE->getOpcode())
 193     {
 194     case Instruction::Cast:
 195       getArg1 = CE->getOperand(0);
 196       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 197         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 198       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
 199
 200     case Instruction::GetElementPtr:
 201       assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
 202              && "All indices in ConstantExpr getelementptr must be constant!");
 203       getArg1 = CE->getOperand(0);
 204       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 205         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 206       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
 207         getArg1 = gep;
 208       return new GetElementPtrInst(getArg1,
 209                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
 210                           "constantGEP", &insertBefore);
 211
 212     default:                            // must be a binary operator
 213       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
 214              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
 215              "Unrecognized opcode in ConstantExpr");
 216       getArg1 = CE->getOperand(0);
 217       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 218         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 219       getArg2 = CE->getOperand(1);
 220       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 221         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 222       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
 223                                     getArg1, getArg2,
 224                                     "constantBinaryOp", &insertBefore);
 225     }
 226 }
 227
 228
 229 //------------------------------------------------------------------------------
 230 // Instruction visitor methods to perform instruction-specific operations
 231 //------------------------------------------------------------------------------
 232
 233 // Common work for *all* instructions.  This needs to be called explicitly
 234 // by other visit<InstructionType> functions.
 235 inline void
 236 PreSelection::visitInstruction(Instruction &I)
 237 {
 238   visitOperands(I);              // Perform operand transformations
 239 }
 240
 241
 242 // GetElementPtr instructions: check if pointer is a global
 243 void
 244 PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
 245 {
 246   // Check for a global and put its address into a register before this instr
 247   if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
 248     I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
 249
 250   // Decompose multidimensional array references
 251   DecomposeArrayRef(&I);
 252
 253   // Perform other transformations common to all instructions
 254   visitInstruction(I);
 255 }
 256
 257
 258 // Load instructions: check if pointer is a global
 259 void
 260 PreSelection::visitLoadInst(LoadInst &I)
 261 {
 262   // Check for a global and put its address into a register before this instr
 263   if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
 264     I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
 265
 266   // Perform other transformations common to all instructions
 267   visitInstruction(I);
 268 }
 269
 270
 271 // Store instructions: check if pointer is a global
 272 void
 273 PreSelection::visitStoreInst(StoreInst &I)
 274 {
 275   // Check for a global and put its address into a register before this instr
 276   if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
 277     I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
 278
 279   // Perform other transformations common to all instructions
 280   visitInstruction(I);
 281 }
 282
 283
 284 // Cast instructions:
 285 // -- check if argument is a global
 286 // -- make multi-step casts explicit:
 287 //    -- float/double to uint32_t:
 288 //         If target does not have a float-to-unsigned instruction, we
 289 //         need to convert to uint64_t and then to uint32_t, or we may
 290 //         overflow the signed int representation for legal uint32_t
 291 //         values.  Expand this without checking target.
 292 //
 293 void
 294 PreSelection::visitCastInst(CastInst &I)
 295 {
 296   CastInst* castI = NULL;
 297
 298   // Check for a global and put its address into a register before this instr
 299   if (GetElementPtrInst* gep = getGlobalAddr(I.getOperand(0), I))
 300     {
 301       I.setOperand(0, gep);             // replace pointer operand
 302     }
 303   else if (I.getType() == Type::UIntTy &&
 304            I.getOperand(0)->getType()->isFloatingPoint())
 305     { // insert a cast-fp-to-long before I, and then replace the operand of I
 306       castI = new CastInst(I.getOperand(0), Type::LongTy, "fp2Long2Uint", &I);
 307       I.setOperand(0, castI);           // replace fp operand with long
 308     }
 309
 310   // Perform other transformations common to all instructions
 311   visitInstruction(I);
 312   if (castI)
 313     visitInstruction(*castI);
 314 }
 315
 316
 317 // visitOperands() transforms individual operands of all instructions:
 318 // -- Load "large" int constants into a virtual register.  What is large
 319 //    depends on the type of instruction and on the target architecture.
 320 // -- For any constants that cannot be put in an immediate field,
 321 //    load address into virtual register first, and then load the constant.
 322 //
 323 void
 324 PreSelection::visitOperands(Instruction &I)
 325 {
 326   // For any instruction other than PHI, copies go just before the instr.
 327   // For a PHI, operand copies must be before the terminator of the
 328   // appropriate predecessor basic block.  Remaining logic is simple
 329   // so just handle PHIs and other instructions separately.
 330   //
 331   if (PHINode* phi = dyn_cast<PHINode>(&I))
 332     {
 333       for (unsigned i=0, N=phi->getNumIncomingValues(); i < N; ++i)
 334         if (Constant* CV = dyn_cast<Constant>(phi->getIncomingValue(i)))
 335           this->visitOneOperand(I, CV, phi->getOperandNumForIncomingValue(i),
 336                                 * phi->getIncomingBlock(i)->getTerminator());
 337     }
 338   else
 339     for (unsigned i=0, N=I.getNumOperands(); i < N; ++i)
 340       if (Constant* CV = dyn_cast<Constant>(I.getOperand(i)))
 341         this->visitOneOperand(I, CV, i, I);
 342 }
 343
 344 void
 345 PreSelection::visitOneOperand(Instruction &I, Constant* CV, unsigned opNum,
 346                               Instruction& insertBefore)
 347 {
 348   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
 349     { // load-time constant: factor it out so we optimize as best we can
 350       Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
 351       I.setOperand(opNum, computeConst); // replace expr operand with result
 352     }
 353   else if (target.getInstrInfo().ConstantTypeMustBeLoaded(CV))
 354     { // load address of constant into a register, then load the constant
 355       GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
 356                                              insertBefore);
 357       LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
 358       I.setOperand(opNum, ldI);        // replace operand with copy in v.reg.
 359     }
 360   else if (target.getInstrInfo().ConstantMayNotFitInImmedField(CV, &I))
 361     { // put the constant into a virtual register using a cast
 362       CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
 363                                      &insertBefore);
 364       I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
 365     }
 366 }
 367
 368
 369 //===----------------------------------------------------------------------===//
 370 // createPreSelectionPass - Public entrypoint for pre-selection pass
 371 // and this file as a whole...
 372 //
 373 Pass*
 374 createPreSelectionPass(TargetMachine &T)
 375 {
 376   return new PreSelection(T);
 377 }
 378