LLVM API Documentation
00001 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===// 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 contains the implementation of the scalar evolution expander, 00011 // which is used to generate the code corresponding to a given scalar evolution 00012 // expression. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/Analysis/LoopInfo.h" 00017 #include "llvm/Analysis/ScalarEvolutionExpander.h" 00018 using namespace llvm; 00019 00020 /// InsertCastOfTo - Insert a cast of V to the specified type, doing what 00021 /// we can to share the casts. 00022 Value *SCEVExpander::InsertCastOfTo(Value *V, const Type *Ty) { 00023 // FIXME: keep track of the cast instruction. 00024 if (Constant *C = dyn_cast<Constant>(V)) 00025 return ConstantExpr::getCast(C, Ty); 00026 00027 if (Argument *A = dyn_cast<Argument>(V)) { 00028 // Check to see if there is already a cast! 00029 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 00030 UI != E; ++UI) { 00031 if ((*UI)->getType() == Ty) 00032 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) { 00033 // If the cast isn't in the first instruction of the function, 00034 // move it. 00035 if (BasicBlock::iterator(CI) != 00036 A->getParent()->getEntryBlock().begin()) { 00037 CI->moveBefore(A->getParent()->getEntryBlock().begin()); 00038 } 00039 return CI; 00040 } 00041 } 00042 return new CastInst(V, Ty, V->getName(), 00043 A->getParent()->getEntryBlock().begin()); 00044 } 00045 00046 Instruction *I = cast<Instruction>(V); 00047 00048 // Check to see if there is already a cast. If there is, use it. 00049 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00050 UI != E; ++UI) { 00051 if ((*UI)->getType() == Ty) 00052 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) { 00053 BasicBlock::iterator It = I; ++It; 00054 if (isa<InvokeInst>(I)) 00055 It = cast<InvokeInst>(I)->getNormalDest()->begin(); 00056 while (isa<PHINode>(It)) ++It; 00057 if (It != BasicBlock::iterator(CI)) { 00058 // Splice the cast immediately after the operand in question. 00059 CI->moveBefore(It); 00060 } 00061 return CI; 00062 } 00063 } 00064 BasicBlock::iterator IP = I; ++IP; 00065 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 00066 IP = II->getNormalDest()->begin(); 00067 while (isa<PHINode>(IP)) ++IP; 00068 return new CastInst(V, Ty, V->getName(), IP); 00069 } 00070 00071 Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) { 00072 const Type *Ty = S->getType(); 00073 int FirstOp = 0; // Set if we should emit a subtract. 00074 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 00075 if (SC->getValue()->isAllOnesValue()) 00076 FirstOp = 1; 00077 00078 int i = S->getNumOperands()-2; 00079 Value *V = expandInTy(S->getOperand(i+1), Ty); 00080 00081 // Emit a bunch of multiply instructions 00082 for (; i >= FirstOp; --i) 00083 V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty), 00084 "tmp.", InsertPt); 00085 // -1 * ... ---> 0 - ... 00086 if (FirstOp == 1) 00087 V = BinaryOperator::createNeg(V, "tmp.", InsertPt); 00088 return V; 00089 } 00090 00091 Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { 00092 const Type *Ty = S->getType(); 00093 const Loop *L = S->getLoop(); 00094 // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} 00095 assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!"); 00096 00097 // {X,+,F} --> X + {0,+,F} 00098 if (!isa<SCEVConstant>(S->getStart()) || 00099 !cast<SCEVConstant>(S->getStart())->getValue()->isNullValue()) { 00100 Value *Start = expandInTy(S->getStart(), Ty); 00101 std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end()); 00102 NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty); 00103 Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty); 00104 00105 // FIXME: look for an existing add to use. 00106 return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt); 00107 } 00108 00109 // {0,+,1} --> Insert a canonical induction variable into the loop! 00110 if (S->getNumOperands() == 2 && 00111 S->getOperand(1) == SCEVUnknown::getIntegerSCEV(1, Ty)) { 00112 // Create and insert the PHI node for the induction variable in the 00113 // specified loop. 00114 BasicBlock *Header = L->getHeader(); 00115 PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); 00116 PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 00117 00118 pred_iterator HPI = pred_begin(Header); 00119 assert(HPI != pred_end(Header) && "Loop with zero preds???"); 00120 if (!L->contains(*HPI)) ++HPI; 00121 assert(HPI != pred_end(Header) && L->contains(*HPI) && 00122 "No backedge in loop?"); 00123 00124 // Insert a unit add instruction right before the terminator corresponding 00125 // to the back-edge. 00126 Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0) 00127 : ConstantInt::get(Ty, 1); 00128 Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next", 00129 (*HPI)->getTerminator()); 00130 00131 pred_iterator PI = pred_begin(Header); 00132 if (*PI == L->getLoopPreheader()) 00133 ++PI; 00134 PN->addIncoming(Add, *PI); 00135 return PN; 00136 } 00137 00138 // Get the canonical induction variable I for this loop. 00139 Value *I = getOrInsertCanonicalInductionVariable(L, Ty); 00140 00141 // If this is a simple linear addrec, emit it now as a special case. 00142 if (S->getNumOperands() == 2) { // {0,+,F} --> i*F 00143 Value *F = expandInTy(S->getOperand(1), Ty); 00144 00145 // IF the step is by one, just return the inserted IV. 00146 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(F)) 00147 if (CI->getRawValue() == 1) 00148 return I; 00149 00150 // If the insert point is directly inside of the loop, emit the multiply at 00151 // the insert point. Otherwise, L is a loop that is a parent of the insert 00152 // point loop. If we can, move the multiply to the outer most loop that it 00153 // is safe to be in. 00154 Instruction *MulInsertPt = InsertPt; 00155 Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent()); 00156 if (InsertPtLoop != L && InsertPtLoop && 00157 L->contains(InsertPtLoop->getHeader())) { 00158 while (InsertPtLoop != L) { 00159 // If we cannot hoist the multiply out of this loop, don't. 00160 if (!InsertPtLoop->isLoopInvariant(F)) break; 00161 00162 // Otherwise, move the insert point to the preheader of the loop. 00163 MulInsertPt = InsertPtLoop->getLoopPreheader()->getTerminator(); 00164 InsertPtLoop = InsertPtLoop->getParentLoop(); 00165 } 00166 } 00167 00168 return BinaryOperator::createMul(I, F, "tmp.", MulInsertPt); 00169 } 00170 00171 // If this is a chain of recurrences, turn it into a closed form, using the 00172 // folders, then expandCodeFor the closed form. This allows the folders to 00173 // simplify the expression without having to build a bunch of special code 00174 // into this folder. 00175 SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. 00176 00177 SCEVHandle V = S->evaluateAtIteration(IH); 00178 //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 00179 00180 return expandInTy(V, Ty); 00181 }