lib/Target/SparcV9/SparcV9PreSelection.cpp

   1 //===- SparcV9PreSelection.cpp - Specialize LLVM code for SparcV9 ---------===//
   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
  11 // the SparcV9 instruction selector, while remaining in legal portable LLVM
  12 // form and preserving type information and type safety. This is meant to enable
  13 // dataflow optimizations on SparcV9-specific operations such as accesses to
  14 // constants, globals, and array indexing.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "SparcV9Internals.h"
  19 #include "SparcV9BurgISel.h"
  20 #include "llvm/Constants.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Instructions.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/Support/InstVisitor.h"
  26 #include "llvm/Support/GetElementPtrTypeIterator.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/Transforms/Scalar.h"
  30 #include <algorithm>
  31 using namespace llvm;
  32
  33 namespace {
  34
  35   //===--------------------------------------------------------------------===//
  36   // PreSelection Pass - Specialize LLVM code for the SparcV9 instr. selector.
  37   //
  38   class PreSelection : public FunctionPass, public InstVisitor<PreSelection> {
  39     const TargetInstrInfo &instrInfo;
  40
  41   public:
  42     PreSelection(const TargetMachine &T)
  43       : instrInfo(*T.getInstrInfo()) {}
  44
  45     // runOnFunction - apply this pass to each Function
  46     bool runOnFunction(Function &F) {
  47       visit(F);
  48       return true;
  49     }
  50     const char *getPassName() const { return "SparcV9 Instr. Pre-selection"; }
  51
  52     // These methods do the actual work of specializing code
  53     void visitInstruction(Instruction &I);   // common work for every instr.
  54     void visitGetElementPtrInst(GetElementPtrInst &I);
  55     void visitCallInst(CallInst &I);
  56     void visitPHINode(PHINode &PN);
  57
  58     void visitBasicBlock(BasicBlock &BB) {
  59       if (isa<UnreachableInst>(BB.getTerminator())) {
  60         BB.getInstList().pop_back();
  61         const Type *RetTy = BB.getParent()->getReturnType();
  62         Value *RetVal = RetTy == Type::VoidTy ? 0 : UndefValue::get(RetTy);
  63         new ReturnInst(RetVal, &BB);
  64       }
  65     }
  66
  67     // Helper functions for visiting operands of every instruction
  68     //
  69     // visitOperands() works on every operand in [firstOp, lastOp-1].
  70     // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
  71     //
  72     // visitOneOperand() does all the work for one operand.
  73     //
  74     void visitOperands(Instruction &I, int firstOp=0);
  75     void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
  76                          Instruction& insertBefore);
  77   };
  78
  79 #if 0
  80   // Register the pass...
  81   RegisterPass<PreSelection> X("preselect",
  82                                "Specialize LLVM code for a target machine"
  83                                createPreselectionPass);
  84 #endif
  85
  86 }  // end anonymous namespace
  87
  88
  89 //------------------------------------------------------------------------------
  90 // Helper functions used by methods of class PreSelection
  91 //------------------------------------------------------------------------------
  92
  93
  94 // getGlobalAddr(): Put address of a global into a v. register.
  95 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore) {
  96
  97   return (isa<GlobalVariable>(ptr))
  98     ? new GetElementPtrInst(ptr,
  99                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
 100                     "addrOfGlobal:" + ptr->getName(), &insertBefore)
 101     : NULL;
 102 }
 103
 104 // Wrapper on Constant::classof to use in find_if
 105 inline static bool nonConstant(const Use& U) {
 106   return ! isa<Constant>(U);
 107 }
 108
 109 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
 110                                           Instruction& insertBefore)
 111 {
 112   Value *getArg1, *getArg2;
 113
 114   switch(CE->getOpcode())
 115     {
 116     case Instruction::Cast:
 117       getArg1 = CE->getOperand(0);
 118       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 119         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 120       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
 121
 122     case Instruction::GetElementPtr:
 123       assert(std::find_if(CE->op_begin()+1, CE->op_end(),
 124                           nonConstant) == CE->op_end()
 125              && "All indices in ConstantExpr getelementptr must be constant!");
 126       getArg1 = CE->getOperand(0);
 127       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 128         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 129       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
 130         getArg1 = gep;
 131       return new GetElementPtrInst(getArg1,
 132                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
 133                           "constantGEP:" + getArg1->getName(), &insertBefore);
 134
 135     case Instruction::Select: {
 136       Value *C, *S1, *S2;
 137       C = CE->getOperand (0);
 138       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (C))
 139         C = DecomposeConstantExpr (CEarg, insertBefore);
 140       S1 = CE->getOperand (1);
 141       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S1))
 142         S1 = DecomposeConstantExpr (CEarg, insertBefore);
 143       S2 = CE->getOperand (2);
 144       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S2))
 145         S2 = DecomposeConstantExpr (CEarg, insertBefore);
 146       return new SelectInst (C, S1, S2, "constantSelect", &insertBefore);
 147     }
 148
 149     case Instruction::Shr: {
 150       getArg1 = CE->getOperand(0);
 151       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 152         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 153       getArg2 = CE->getOperand(1);
 154       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 155         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 156       return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()),
 157                             getArg1, getArg2,
 158                             "constantShr:" + getArg1->getName(), &insertBefore);
 159     }
 160
 161     case Instruction::Shl: {
 162       getArg1 = CE->getOperand(0);
 163       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 164         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 165       getArg2 = CE->getOperand(1);
 166       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 167         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 168       return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()),
 169                             getArg1, getArg2,
 170                             "constantShl:" + getArg1->getName(), &insertBefore);
 171     }
 172
 173     default:                            // must be a binary operator
 174       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
 175              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
 176              "Unhandled opcode in ConstantExpr");
 177       getArg1 = CE->getOperand(0);
 178       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
 179         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
 180       getArg2 = CE->getOperand(1);
 181       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
 182         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
 183       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
 184                                     getArg1, getArg2,
 185                                     "constantBinaryOp", &insertBefore);
 186     }
 187 }
 188
 189 static inline bool ConstantTypeMustBeLoaded(const Type* CVT) {
 190   assert(CVT->isPrimitiveType() || isa<PointerType>(CVT));
 191   return !(CVT->isIntegral() || isa<PointerType>(CVT));
 192 }
 193
 194 //------------------------------------------------------------------------------
 195 // Instruction visitor methods to perform instruction-specific operations
 196 //------------------------------------------------------------------------------
 197 inline void
 198 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
 199                               Instruction& insertBefore)
 200 {
 201   assert(&insertBefore != NULL && "Must have instruction to insert before.");
 202
 203   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
 204     I.setOperand(opNum, gep);           // replace global operand
 205     return;                             // nothing more to do for this op.
 206   }
 207
 208   Constant* CV  = dyn_cast<Constant>(Op);
 209   if (CV == NULL)
 210     return;
 211
 212   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV)) {
 213     // load-time constant: factor it out so we optimize as best we can
 214     Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
 215     I.setOperand(opNum, computeConst); // replace expr operand with result
 216   } else if (ConstantTypeMustBeLoaded(CV->getType())) {
 217     // load address of constant into a register, then load the constant
 218     // this is now done during instruction selection
 219     // the constant will live in the MachineConstantPool later on
 220   } else if (ConstantMayNotFitInImmedField(CV, &I)) {
 221     // put the constant into a virtual register using a cast
 222     CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
 223                                    &insertBefore);
 224     I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
 225   }
 226 }
 227
 228 /// visitOperands - transform individual operands of all instructions:
 229 /// -- Load "large" int constants into a virtual register.  What is large
 230 ///    depends on the type of instruction and on the target architecture.
 231 /// -- For any constants that cannot be put in an immediate field,
 232 ///    load address into virtual register first, and then load the constant.
 233 ///
 234 /// firstOp and lastOp can be used to skip leading and trailing operands.
 235 /// If lastOp is 0, it defaults to #operands or #incoming Phi values.
 236 ///
 237 inline void PreSelection::visitOperands(Instruction &I, int firstOp) {
 238   // For any instruction other than PHI, copies go just before the instr.
 239   for (unsigned i = firstOp, e = I.getNumOperands(); i != e; ++i)
 240     visitOneOperand(I, I.getOperand(i), i, I);
 241 }
 242
 243
 244 void PreSelection::visitPHINode(PHINode &PN) {
 245   // For a PHI, operand copies must be before the terminator of the
 246   // appropriate predecessor basic block.  Remaining logic is simple
 247   // so just handle PHIs and other instructions separately.
 248   //
 249   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 250     visitOneOperand(PN, PN.getIncomingValue(i),
 251                     PN.getOperandNumForIncomingValue(i),
 252                     *PN.getIncomingBlock(i)->getTerminator());
 253   // do not call visitOperands!
 254 }
 255
 256 // Common work for *all* instructions.  This needs to be called explicitly
 257 // by other visit<InstructionType> functions.
 258 inline void PreSelection::visitInstruction(Instruction &I) {
 259   visitOperands(I);              // Perform operand transformations
 260 }
 261
 262 // GetElementPtr instructions: check if pointer is a global
 263 void PreSelection::visitGetElementPtrInst(GetElementPtrInst &I) {
 264   Instruction* curI = &I;
 265
 266   // The Sparc backend doesn't handle array indexes that are not long types, so
 267   // insert a cast from whatever it is to long, if the sequential type index is
 268   // not a long already.
 269   unsigned Idx = 1;
 270   for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I); TI != E;
 271        ++TI, ++Idx)
 272     if (isa<SequentialType>(*TI) &&
 273         I.getOperand(Idx)->getType() != Type::LongTy) {
 274       Value *Op = I.getOperand(Idx);
 275       if (Op->getType()->isUnsigned())    // Must sign extend!
 276         Op = new CastInst(Op, Op->getType()->getSignedVersion(), "v9", &I);
 277       if (Op->getType() != Type::LongTy)
 278         Op = new CastInst(Op, Type::LongTy, "v9", &I);
 279       I.setOperand(Idx, Op);
 280     }
 281
 282
 283   // Decompose multidimensional array references
 284   if (I.getNumIndices() >= 2) {
 285     // DecomposeArrayRef() replaces I and deletes it, if successful,
 286     // so remember predecessor in order to find the replacement instruction.
 287     // Also remember the basic block in case there is no predecessor.
 288     Instruction* prevI = I.getPrev();
 289     BasicBlock* bb = I.getParent();
 290     if (DecomposeArrayRef(&I))
 291       // first instr. replacing I
 292       curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
 293   }
 294
 295   // Perform other transformations common to all instructions
 296   visitInstruction(*curI);
 297 }
 298
 299 void PreSelection::visitCallInst(CallInst &I) {
 300   // Tell visitOperands to ignore the function name if this is a direct call.
 301   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
 302 }
 303
 304 /// createPreSelectionPass - Public entry point for the PreSelection pass
 305 ///
 306 FunctionPass* llvm::createPreSelectionPass(const TargetMachine &TM) {
 307   return new PreSelection(TM);
 308 }