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