LLVM API Documentation
00001 //===- SparcV9PreSelection.cpp - Specialize LLVM code for SparcV9 ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the PreSelection pass which specializes LLVM code for 00011 // the SparcV9 instruction selector, while remaining in legal portable LLVM 00012 // form and preserving type information and type safety. This is meant to enable 00013 // dataflow optimizations on SparcV9-specific operations such as accesses to 00014 // constants, globals, and array indexing. 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #include "SparcV9Internals.h" 00019 #include "SparcV9BurgISel.h" 00020 #include "llvm/Constants.h" 00021 #include "llvm/DerivedTypes.h" 00022 #include "llvm/Instructions.h" 00023 #include "llvm/Module.h" 00024 #include "llvm/Pass.h" 00025 #include "llvm/Support/InstVisitor.h" 00026 #include "llvm/Support/GetElementPtrTypeIterator.h" 00027 #include "llvm/Target/TargetInstrInfo.h" 00028 #include "llvm/Target/TargetMachine.h" 00029 #include "llvm/Transforms/Scalar.h" 00030 #include <algorithm> 00031 using namespace llvm; 00032 00033 namespace { 00034 00035 //===--------------------------------------------------------------------===// 00036 // PreSelection Pass - Specialize LLVM code for the SparcV9 instr. selector. 00037 // 00038 class PreSelection : public FunctionPass, public InstVisitor<PreSelection> { 00039 const TargetInstrInfo &instrInfo; 00040 00041 public: 00042 PreSelection(const TargetMachine &T) 00043 : instrInfo(*T.getInstrInfo()) {} 00044 00045 // runOnFunction - apply this pass to each Function 00046 bool runOnFunction(Function &F) { 00047 visit(F); 00048 return true; 00049 } 00050 const char *getPassName() const { return "SparcV9 Instr. Pre-selection"; } 00051 00052 // These methods do the actual work of specializing code 00053 void visitInstruction(Instruction &I); // common work for every instr. 00054 void visitGetElementPtrInst(GetElementPtrInst &I); 00055 void visitCallInst(CallInst &I); 00056 void visitPHINode(PHINode &PN); 00057 00058 void visitBasicBlock(BasicBlock &BB) { 00059 if (isa<UnreachableInst>(BB.getTerminator())) { 00060 BB.getInstList().pop_back(); 00061 const Type *RetTy = BB.getParent()->getReturnType(); 00062 Value *RetVal = RetTy == Type::VoidTy ? 0 : UndefValue::get(RetTy); 00063 new ReturnInst(RetVal, &BB); 00064 } 00065 } 00066 00067 // Helper functions for visiting operands of every instruction 00068 // 00069 // visitOperands() works on every operand in [firstOp, lastOp-1]. 00070 // If lastOp==0, lastOp defaults to #operands or #incoming Phi values. 00071 // 00072 // visitOneOperand() does all the work for one operand. 00073 // 00074 void visitOperands(Instruction &I, int firstOp=0); 00075 void visitOneOperand(Instruction &I, Value* Op, unsigned opNum, 00076 Instruction& insertBefore); 00077 }; 00078 00079 #if 0 00080 // Register the pass... 00081 RegisterPass<PreSelection> X("preselect", 00082 "Specialize LLVM code for a target machine" 00083 createPreselectionPass); 00084 #endif 00085 00086 } // end anonymous namespace 00087 00088 00089 //------------------------------------------------------------------------------ 00090 // Helper functions used by methods of class PreSelection 00091 //------------------------------------------------------------------------------ 00092 00093 00094 // getGlobalAddr(): Put address of a global into a v. register. 00095 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore) { 00096 00097 return (isa<GlobalVariable>(ptr)) 00098 ? new GetElementPtrInst(ptr, 00099 std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)), 00100 "addrOfGlobal:" + ptr->getName(), &insertBefore) 00101 : NULL; 00102 } 00103 00104 // Wrapper on Constant::classof to use in find_if 00105 inline static bool nonConstant(const Use& U) { 00106 return ! isa<Constant>(U); 00107 } 00108 00109 static Instruction* DecomposeConstantExpr(ConstantExpr* CE, 00110 Instruction& insertBefore) 00111 { 00112 Value *getArg1, *getArg2; 00113 00114 switch(CE->getOpcode()) 00115 { 00116 case Instruction::Cast: 00117 getArg1 = CE->getOperand(0); 00118 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1)) 00119 getArg1 = DecomposeConstantExpr(CEarg, insertBefore); 00120 return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore); 00121 00122 case Instruction::GetElementPtr: 00123 assert(std::find_if(CE->op_begin()+1, CE->op_end(), 00124 nonConstant) == CE->op_end() 00125 && "All indices in ConstantExpr getelementptr must be constant!"); 00126 getArg1 = CE->getOperand(0); 00127 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1)) 00128 getArg1 = DecomposeConstantExpr(CEarg, insertBefore); 00129 else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore)) 00130 getArg1 = gep; 00131 return new GetElementPtrInst(getArg1, 00132 std::vector<Value*>(CE->op_begin()+1, CE->op_end()), 00133 "constantGEP:" + getArg1->getName(), &insertBefore); 00134 00135 case Instruction::Select: { 00136 Value *C, *S1, *S2; 00137 C = CE->getOperand (0); 00138 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (C)) 00139 C = DecomposeConstantExpr (CEarg, insertBefore); 00140 S1 = CE->getOperand (1); 00141 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S1)) 00142 S1 = DecomposeConstantExpr (CEarg, insertBefore); 00143 S2 = CE->getOperand (2); 00144 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S2)) 00145 S2 = DecomposeConstantExpr (CEarg, insertBefore); 00146 return new SelectInst (C, S1, S2, "constantSelect", &insertBefore); 00147 } 00148 00149 case Instruction::Shr: { 00150 getArg1 = CE->getOperand(0); 00151 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1)) 00152 getArg1 = DecomposeConstantExpr(CEarg, insertBefore); 00153 getArg2 = CE->getOperand(1); 00154 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2)) 00155 getArg2 = DecomposeConstantExpr(CEarg, insertBefore); 00156 return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()), 00157 getArg1, getArg2, 00158 "constantShr:" + getArg1->getName(), &insertBefore); 00159 } 00160 00161 case Instruction::Shl: { 00162 getArg1 = CE->getOperand(0); 00163 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1)) 00164 getArg1 = DecomposeConstantExpr(CEarg, insertBefore); 00165 getArg2 = CE->getOperand(1); 00166 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2)) 00167 getArg2 = DecomposeConstantExpr(CEarg, insertBefore); 00168 return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()), 00169 getArg1, getArg2, 00170 "constantShl:" + getArg1->getName(), &insertBefore); 00171 } 00172 00173 default: // must be a binary operator 00174 assert(CE->getOpcode() >= Instruction::BinaryOpsBegin && 00175 CE->getOpcode() < Instruction::BinaryOpsEnd && 00176 "Unhandled opcode in ConstantExpr"); 00177 getArg1 = CE->getOperand(0); 00178 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1)) 00179 getArg1 = DecomposeConstantExpr(CEarg, insertBefore); 00180 getArg2 = CE->getOperand(1); 00181 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2)) 00182 getArg2 = DecomposeConstantExpr(CEarg, insertBefore); 00183 return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(), 00184 getArg1, getArg2, 00185 "constantBinaryOp", &insertBefore); 00186 } 00187 } 00188 00189 static inline bool ConstantTypeMustBeLoaded(const Type* CVT) { 00190 assert(CVT->isPrimitiveType() || isa<PointerType>(CVT)); 00191 return !(CVT->isIntegral() || isa<PointerType>(CVT)); 00192 } 00193 00194 //------------------------------------------------------------------------------ 00195 // Instruction visitor methods to perform instruction-specific operations 00196 //------------------------------------------------------------------------------ 00197 inline void 00198 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum, 00199 Instruction& insertBefore) 00200 { 00201 assert(&insertBefore != NULL && "Must have instruction to insert before."); 00202 00203 if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) { 00204 I.setOperand(opNum, gep); // replace global operand 00205 return; // nothing more to do for this op. 00206 } 00207 00208 Constant* CV = dyn_cast<Constant>(Op); 00209 if (CV == NULL) 00210 return; 00211 00212 if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV)) { 00213 // load-time constant: factor it out so we optimize as best we can 00214 Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore); 00215 I.setOperand(opNum, computeConst); // replace expr operand with result 00216 } else if (ConstantTypeMustBeLoaded(CV->getType())) { 00217 // load address of constant into a register, then load the constant 00218 // this is now done during instruction selection 00219 // the constant will live in the MachineConstantPool later on 00220 } else if (ConstantMayNotFitInImmedField(CV, &I)) { 00221 // put the constant into a virtual register using a cast 00222 CastInst* castI = new CastInst(CV, CV->getType(), "copyConst", 00223 &insertBefore); 00224 I.setOperand(opNum, castI); // replace operand with copy in v.reg. 00225 } 00226 } 00227 00228 /// visitOperands - transform individual operands of all instructions: 00229 /// -- Load "large" int constants into a virtual register. What is large 00230 /// depends on the type of instruction and on the target architecture. 00231 /// -- For any constants that cannot be put in an immediate field, 00232 /// load address into virtual register first, and then load the constant. 00233 /// 00234 /// firstOp and lastOp can be used to skip leading and trailing operands. 00235 /// If lastOp is 0, it defaults to #operands or #incoming Phi values. 00236 /// 00237 inline void PreSelection::visitOperands(Instruction &I, int firstOp) { 00238 // For any instruction other than PHI, copies go just before the instr. 00239 for (unsigned i = firstOp, e = I.getNumOperands(); i != e; ++i) 00240 visitOneOperand(I, I.getOperand(i), i, I); 00241 } 00242 00243 00244 void PreSelection::visitPHINode(PHINode &PN) { 00245 // For a PHI, operand copies must be before the terminator of the 00246 // appropriate predecessor basic block. Remaining logic is simple 00247 // so just handle PHIs and other instructions separately. 00248 // 00249 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 00250 visitOneOperand(PN, PN.getIncomingValue(i), 00251 PN.getOperandNumForIncomingValue(i), 00252 *PN.getIncomingBlock(i)->getTerminator()); 00253 // do not call visitOperands! 00254 } 00255 00256 // Common work for *all* instructions. This needs to be called explicitly 00257 // by other visit<InstructionType> functions. 00258 inline void PreSelection::visitInstruction(Instruction &I) { 00259 visitOperands(I); // Perform operand transformations 00260 } 00261 00262 // GetElementPtr instructions: check if pointer is a global 00263 void PreSelection::visitGetElementPtrInst(GetElementPtrInst &I) { 00264 Instruction* curI = &I; 00265 00266 // The Sparc backend doesn't handle array indexes that are not long types, so 00267 // insert a cast from whatever it is to long, if the sequential type index is 00268 // not a long already. 00269 unsigned Idx = 1; 00270 for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I); TI != E; 00271 ++TI, ++Idx) 00272 if (isa<SequentialType>(*TI) && 00273 I.getOperand(Idx)->getType() != Type::LongTy) { 00274 Value *Op = I.getOperand(Idx); 00275 if (Op->getType()->isUnsigned()) // Must sign extend! 00276 Op = new CastInst(Op, Op->getType()->getSignedVersion(), "v9", &I); 00277 if (Op->getType() != Type::LongTy) 00278 Op = new CastInst(Op, Type::LongTy, "v9", &I); 00279 I.setOperand(Idx, Op); 00280 } 00281 00282 00283 // Decompose multidimensional array references 00284 if (I.getNumIndices() >= 2) { 00285 // DecomposeArrayRef() replaces I and deletes it, if successful, 00286 // so remember predecessor in order to find the replacement instruction. 00287 // Also remember the basic block in case there is no predecessor. 00288 Instruction* prevI = I.getPrev(); 00289 BasicBlock* bb = I.getParent(); 00290 if (DecomposeArrayRef(&I)) 00291 // first instr. replacing I 00292 curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front()); 00293 } 00294 00295 // Perform other transformations common to all instructions 00296 visitInstruction(*curI); 00297 } 00298 00299 void PreSelection::visitCallInst(CallInst &I) { 00300 // Tell visitOperands to ignore the function name if this is a direct call. 00301 visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0)); 00302 } 00303 00304 /// createPreSelectionPass - Public entry point for the PreSelection pass 00305 /// 00306 FunctionPass* llvm::createPreSelectionPass(const TargetMachine &TM) { 00307 return new PreSelection(TM); 00308 }