1 //===- PreSelection.cpp - Specialize LLVM code for target machine ---------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
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"
34 //===--------------------------------------------------------------------===//
35 // PreSelection Pass - Specialize LLVM code for the current target machine.
37 class PreSelection : public Pass, public InstVisitor<PreSelection> {
38 const TargetInstrInfo &instrInfo;
41 std::map<const Constant*, GlobalVariable*> gvars;
43 GlobalVariable* getGlobalForConstant(Constant* CV) {
44 std::map<const Constant*, GlobalVariable*>::iterator I = gvars.find(CV);
45 if (I != gvars.end()) return I->second; // global exists so return it
47 return I->second = new GlobalVariable(CV->getType(), true,
48 GlobalValue::InternalLinkage, CV,
53 PreSelection(const TargetMachine &T)
54 : instrInfo(T.getInstrInfo()), TheModule(0) {}
56 // runOnBasicBlock - apply this pass to each BB
60 // Build reverse map for pre-existing global constants so we can find them
61 for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
62 if (I->hasInitializer() && I->isConstant())
63 gvars[I->getInitializer()] = I;
65 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
72 // These methods do the actual work of specializing code
73 void visitInstruction(Instruction &I); // common work for every instr.
74 void visitGetElementPtrInst(GetElementPtrInst &I);
75 void visitCallInst(CallInst &I);
77 // Helper functions for visiting operands of every instruction
79 // visitOperands() works on every operand in [firstOp, lastOp-1].
80 // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
82 // visitOneOperand() does all the work for one operand.
84 void visitOperands(Instruction &I, int firstOp=0);
85 void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
86 Instruction& insertBefore);
89 // Register the pass...
90 RegisterOpt<PreSelection> X("preselect",
91 "Specialize LLVM code for a target machine",
92 createPreSelectionPass);
93 } // end anonymous namespace
96 //------------------------------------------------------------------------------
97 // Helper functions used by methods of class PreSelection
98 //------------------------------------------------------------------------------
101 // getGlobalAddr(): Put address of a global into a v. register.
102 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
104 if (isa<ConstantPointerRef>(ptr))
105 ptr = cast<ConstantPointerRef>(ptr)->getValue();
107 return (isa<GlobalVariable>(ptr))
108 ? new GetElementPtrInst(ptr,
109 std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
110 "addrOfGlobal", &insertBefore)
115 // Wrapper on Constant::classof to use in find_if :-(
116 inline static bool nonConstant(const Use& U)
118 return ! isa<Constant>(U);
122 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
123 Instruction& insertBefore)
125 Value *getArg1, *getArg2;
127 switch(CE->getOpcode())
129 case Instruction::Cast:
130 getArg1 = CE->getOperand(0);
131 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
132 getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
133 return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
135 case Instruction::GetElementPtr:
136 assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
137 && "All indices in ConstantExpr getelementptr must be constant!");
138 getArg1 = CE->getOperand(0);
139 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
140 getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
141 else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
143 return new GetElementPtrInst(getArg1,
144 std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
145 "constantGEP", &insertBefore);
147 default: // must be a binary operator
148 assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
149 CE->getOpcode() < Instruction::BinaryOpsEnd &&
150 "Unrecognized opcode in ConstantExpr");
151 getArg1 = CE->getOperand(0);
152 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
153 getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
154 getArg2 = CE->getOperand(1);
155 if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
156 getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
157 return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
159 "constantBinaryOp", &insertBefore);
164 //------------------------------------------------------------------------------
165 // Instruction visitor methods to perform instruction-specific operations
166 //------------------------------------------------------------------------------
168 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
169 Instruction& insertBefore)
171 assert(&insertBefore != NULL && "Must have instruction to insert before.");
173 if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
174 I.setOperand(opNum, gep); // replace global operand
175 return; // nothing more to do for this op.
178 Constant* CV = dyn_cast<Constant>(Op);
182 if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
183 { // load-time constant: factor it out so we optimize as best we can
184 Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
185 I.setOperand(opNum, computeConst); // replace expr operand with result
187 else if (instrInfo.ConstantTypeMustBeLoaded(CV))
188 { // load address of constant into a register, then load the constant
189 GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
191 LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
192 I.setOperand(opNum, ldI); // replace operand with copy in v.reg.
194 else if (instrInfo.ConstantMayNotFitInImmedField(CV, &I))
195 { // put the constant into a virtual register using a cast
196 CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
198 I.setOperand(opNum, castI); // replace operand with copy in v.reg.
202 // visitOperands() transforms individual operands of all instructions:
203 // -- Load "large" int constants into a virtual register. What is large
204 // depends on the type of instruction and on the target architecture.
205 // -- For any constants that cannot be put in an immediate field,
206 // load address into virtual register first, and then load the constant.
208 // firstOp and lastOp can be used to skip leading and trailing operands.
209 // If lastOp is 0, it defaults to #operands or #incoming Phi values.
211 inline void PreSelection::visitOperands(Instruction &I, int firstOp) {
212 // For any instruction other than PHI, copies go just before the instr.
213 // For a PHI, operand copies must be before the terminator of the
214 // appropriate predecessor basic block. Remaining logic is simple
215 // so just handle PHIs and other instructions separately.
217 if (PHINode* phi = dyn_cast<PHINode>(&I)) {
218 for (unsigned i=firstOp, N=phi->getNumIncomingValues(); i != N; ++i)
219 visitOneOperand(I, phi->getIncomingValue(i),
220 phi->getOperandNumForIncomingValue(i),
221 * phi->getIncomingBlock(i)->getTerminator());
223 for (unsigned i=firstOp, N=lastOp; i != I.getNumOperands(); ++i)
224 visitOneOperand(I, I.getOperand(i), i, I);
230 // Common work for *all* instructions. This needs to be called explicitly
231 // by other visit<InstructionType> functions.
233 PreSelection::visitInstruction(Instruction &I)
235 visitOperands(I); // Perform operand transformations
239 // GetElementPtr instructions: check if pointer is a global
241 PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
243 Instruction* curI = &I;
245 // Decompose multidimensional array references
246 if (I.getNumIndices() >= 2) {
247 // DecomposeArrayRef() replaces I and deletes it, if successful,
248 // so remember predecessor in order to find the replacement instruction.
249 // Also remember the basic block in case there is no predecessor.
250 Instruction* prevI = I.getPrev();
251 BasicBlock* bb = I.getParent();
252 if (DecomposeArrayRef(&I))
253 // first instr. replacing I
254 curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
257 // Perform other transformations common to all instructions
258 visitInstruction(*curI);
263 PreSelection::visitCallInst(CallInst &I)
265 // Tell visitOperands to ignore the function name if this is a direct call.
266 visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
270 //===----------------------------------------------------------------------===//
271 // createPreSelectionPass - Public entrypoint for pre-selection pass
272 // and this file as a whole...
274 Pass* createPreSelectionPass(TargetMachine &T) {
275 return new PreSelection(T);