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