lib/Target/SparcV9/SparcV9PreSelection.cpp

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