LLVM API Documentation
00001 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/ScalarEvolutionExpander.h" 00017 #include "llvm/Analysis/LoopInfo.h" 00018 #include "llvm/LLVMContext.h" 00019 #include "llvm/Target/TargetData.h" 00020 #include "llvm/ADT/STLExtras.h" 00021 using namespace llvm; 00022 00023 /// InsertNoopCastOfTo - Insert a cast of V to the specified type, 00024 /// which must be possible with a noop cast, doing what we can to share 00025 /// the casts. 00026 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 00027 Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 00028 assert((Op == Instruction::BitCast || 00029 Op == Instruction::PtrToInt || 00030 Op == Instruction::IntToPtr) && 00031 "InsertNoopCastOfTo cannot perform non-noop casts!"); 00032 assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 00033 "InsertNoopCastOfTo cannot change sizes!"); 00034 00035 // Short-circuit unnecessary bitcasts. 00036 if (Op == Instruction::BitCast && V->getType() == Ty) 00037 return V; 00038 00039 // Short-circuit unnecessary inttoptr<->ptrtoint casts. 00040 if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && 00041 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 00042 if (CastInst *CI = dyn_cast<CastInst>(V)) 00043 if ((CI->getOpcode() == Instruction::PtrToInt || 00044 CI->getOpcode() == Instruction::IntToPtr) && 00045 SE.getTypeSizeInBits(CI->getType()) == 00046 SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 00047 return CI->getOperand(0); 00048 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00049 if ((CE->getOpcode() == Instruction::PtrToInt || 00050 CE->getOpcode() == Instruction::IntToPtr) && 00051 SE.getTypeSizeInBits(CE->getType()) == 00052 SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 00053 return CE->getOperand(0); 00054 } 00055 00056 if (Constant *C = dyn_cast<Constant>(V)) 00057 return ConstantExpr::getCast(Op, C, Ty); 00058 00059 if (Argument *A = dyn_cast<Argument>(V)) { 00060 // Check to see if there is already a cast! 00061 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 00062 UI != E; ++UI) 00063 if ((*UI)->getType() == Ty) 00064 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 00065 if (CI->getOpcode() == Op) { 00066 // If the cast isn't the first instruction of the function, move it. 00067 if (BasicBlock::iterator(CI) != 00068 A->getParent()->getEntryBlock().begin()) { 00069 // Recreate the cast at the beginning of the entry block. 00070 // The old cast is left in place in case it is being used 00071 // as an insert point. 00072 Instruction *NewCI = 00073 CastInst::Create(Op, V, Ty, "", 00074 A->getParent()->getEntryBlock().begin()); 00075 NewCI->takeName(CI); 00076 CI->replaceAllUsesWith(NewCI); 00077 return NewCI; 00078 } 00079 return CI; 00080 } 00081 00082 Instruction *I = CastInst::Create(Op, V, Ty, V->getName(), 00083 A->getParent()->getEntryBlock().begin()); 00084 InsertedValues.insert(I); 00085 return I; 00086 } 00087 00088 Instruction *I = cast<Instruction>(V); 00089 00090 // Check to see if there is already a cast. If there is, use it. 00091 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00092 UI != E; ++UI) { 00093 if ((*UI)->getType() == Ty) 00094 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 00095 if (CI->getOpcode() == Op) { 00096 BasicBlock::iterator It = I; ++It; 00097 if (isa<InvokeInst>(I)) 00098 It = cast<InvokeInst>(I)->getNormalDest()->begin(); 00099 while (isa<PHINode>(It)) ++It; 00100 if (It != BasicBlock::iterator(CI)) { 00101 // Recreate the cast at the beginning of the entry block. 00102 // The old cast is left in place in case it is being used 00103 // as an insert point. 00104 Instruction *NewCI = CastInst::Create(Op, V, Ty, "", It); 00105 NewCI->takeName(CI); 00106 CI->replaceAllUsesWith(NewCI); 00107 return NewCI; 00108 } 00109 return CI; 00110 } 00111 } 00112 BasicBlock::iterator IP = I; ++IP; 00113 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 00114 IP = II->getNormalDest()->begin(); 00115 while (isa<PHINode>(IP)) ++IP; 00116 Instruction *CI = CastInst::Create(Op, V, Ty, V->getName(), IP); 00117 InsertedValues.insert(CI); 00118 return CI; 00119 } 00120 00121 /// InsertBinop - Insert the specified binary operator, doing a small amount 00122 /// of work to avoid inserting an obviously redundant operation. 00123 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, 00124 Value *LHS, Value *RHS) { 00125 // Fold a binop with constant operands. 00126 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 00127 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 00128 return ConstantExpr::get(Opcode, CLHS, CRHS); 00129 00130 // Do a quick scan to see if we have this binop nearby. If so, reuse it. 00131 unsigned ScanLimit = 6; 00132 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 00133 // Scanning starts from the last instruction before the insertion point. 00134 BasicBlock::iterator IP = Builder.GetInsertPoint(); 00135 if (IP != BlockBegin) { 00136 --IP; 00137 for (; ScanLimit; --IP, --ScanLimit) { 00138 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 00139 IP->getOperand(1) == RHS) 00140 return IP; 00141 if (IP == BlockBegin) break; 00142 } 00143 } 00144 00145 // If we haven't found this binop, insert it. 00146 Value *BO = Builder.CreateBinOp(Opcode, LHS, RHS, "tmp"); 00147 InsertedValues.insert(BO); 00148 return BO; 00149 } 00150 00151 /// FactorOutConstant - Test if S is divisible by Factor, using signed 00152 /// division. If so, update S with Factor divided out and return true. 00153 /// S need not be evenly divisble if a reasonable remainder can be 00154 /// computed. 00155 /// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 00156 /// unnecessary; in its place, just signed-divide Ops[i] by the scale and 00157 /// check to see if the divide was folded. 00158 static bool FactorOutConstant(const SCEV *&S, 00159 const SCEV *&Remainder, 00160 const SCEV *Factor, 00161 ScalarEvolution &SE, 00162 const TargetData *TD) { 00163 // Everything is divisible by one. 00164 if (Factor->isOne()) 00165 return true; 00166 00167 // x/x == 1. 00168 if (S == Factor) { 00169 S = SE.getIntegerSCEV(1, S->getType()); 00170 return true; 00171 } 00172 00173 // For a Constant, check for a multiple of the given factor. 00174 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 00175 // 0/x == 0. 00176 if (C->isZero()) 00177 return true; 00178 // Check for divisibility. 00179 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) { 00180 ConstantInt *CI = 00181 ConstantInt::get(SE.getContext(), 00182 C->getValue()->getValue().sdiv( 00183 FC->getValue()->getValue())); 00184 // If the quotient is zero and the remainder is non-zero, reject 00185 // the value at this scale. It will be considered for subsequent 00186 // smaller scales. 00187 if (!CI->isZero()) { 00188 const SCEV *Div = SE.getConstant(CI); 00189 S = Div; 00190 Remainder = 00191 SE.getAddExpr(Remainder, 00192 SE.getConstant(C->getValue()->getValue().srem( 00193 FC->getValue()->getValue()))); 00194 return true; 00195 } 00196 } 00197 } 00198 00199 // In a Mul, check if there is a constant operand which is a multiple 00200 // of the given factor. 00201 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 00202 if (TD) { 00203 // With TargetData, the size is known. Check if there is a constant 00204 // operand which is a multiple of the given factor. If so, we can 00205 // factor it. 00206 const SCEVConstant *FC = cast<SCEVConstant>(Factor); 00207 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 00208 if (!C->getValue()->getValue().srem(FC->getValue()->getValue())) { 00209 const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands(); 00210 SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(), 00211 MOperands.end()); 00212 NewMulOps[0] = 00213 SE.getConstant(C->getValue()->getValue().sdiv( 00214 FC->getValue()->getValue())); 00215 S = SE.getMulExpr(NewMulOps); 00216 return true; 00217 } 00218 } else { 00219 // Without TargetData, check if Factor can be factored out of any of the 00220 // Mul's operands. If so, we can just remove it. 00221 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { 00222 const SCEV *SOp = M->getOperand(i); 00223 const SCEV *Remainder = SE.getIntegerSCEV(0, SOp->getType()); 00224 if (FactorOutConstant(SOp, Remainder, Factor, SE, TD) && 00225 Remainder->isZero()) { 00226 const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands(); 00227 SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(), 00228 MOperands.end()); 00229 NewMulOps[i] = SOp; 00230 S = SE.getMulExpr(NewMulOps); 00231 return true; 00232 } 00233 } 00234 } 00235 } 00236 00237 // In an AddRec, check if both start and step are divisible. 00238 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 00239 const SCEV *Step = A->getStepRecurrence(SE); 00240 const SCEV *StepRem = SE.getIntegerSCEV(0, Step->getType()); 00241 if (!FactorOutConstant(Step, StepRem, Factor, SE, TD)) 00242 return false; 00243 if (!StepRem->isZero()) 00244 return false; 00245 const SCEV *Start = A->getStart(); 00246 if (!FactorOutConstant(Start, Remainder, Factor, SE, TD)) 00247 return false; 00248 S = SE.getAddRecExpr(Start, Step, A->getLoop()); 00249 return true; 00250 } 00251 00252 return false; 00253 } 00254 00255 /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs 00256 /// is the number of SCEVAddRecExprs present, which are kept at the end of 00257 /// the list. 00258 /// 00259 static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops, 00260 const Type *Ty, 00261 ScalarEvolution &SE) { 00262 unsigned NumAddRecs = 0; 00263 for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i) 00264 ++NumAddRecs; 00265 // Group Ops into non-addrecs and addrecs. 00266 SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs); 00267 SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end()); 00268 // Let ScalarEvolution sort and simplify the non-addrecs list. 00269 const SCEV *Sum = NoAddRecs.empty() ? 00270 SE.getIntegerSCEV(0, Ty) : 00271 SE.getAddExpr(NoAddRecs); 00272 // If it returned an add, use the operands. Otherwise it simplified 00273 // the sum into a single value, so just use that. 00274 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum)) 00275 Ops = Add->getOperands(); 00276 else { 00277 Ops.clear(); 00278 if (!Sum->isZero()) 00279 Ops.push_back(Sum); 00280 } 00281 // Then append the addrecs. 00282 Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); 00283 } 00284 00285 /// SplitAddRecs - Flatten a list of add operands, moving addrec start values 00286 /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}. 00287 /// This helps expose more opportunities for folding parts of the expressions 00288 /// into GEP indices. 00289 /// 00290 static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, 00291 const Type *Ty, 00292 ScalarEvolution &SE) { 00293 // Find the addrecs. 00294 SmallVector<const SCEV *, 8> AddRecs; 00295 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 00296 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) { 00297 const SCEV *Start = A->getStart(); 00298 if (Start->isZero()) break; 00299 const SCEV *Zero = SE.getIntegerSCEV(0, Ty); 00300 AddRecs.push_back(SE.getAddRecExpr(Zero, 00301 A->getStepRecurrence(SE), 00302 A->getLoop())); 00303 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { 00304 Ops[i] = Zero; 00305 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 00306 e += Add->getNumOperands(); 00307 } else { 00308 Ops[i] = Start; 00309 } 00310 } 00311 if (!AddRecs.empty()) { 00312 // Add the addrecs onto the end of the list. 00313 Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); 00314 // Resort the operand list, moving any constants to the front. 00315 SimplifyAddOperands(Ops, Ty, SE); 00316 } 00317 } 00318 00319 /// expandAddToGEP - Expand an addition expression with a pointer type into 00320 /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps 00321 /// BasicAliasAnalysis and other passes analyze the result. See the rules 00322 /// for getelementptr vs. inttoptr in 00323 /// http://llvm.org/docs/LangRef.html#pointeraliasing 00324 /// for details. 00325 /// 00326 /// Design note: The correctness of using getelmeentptr here depends on 00327 /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as 00328 /// they may introduce pointer arithmetic which may not be safely converted 00329 /// into getelementptr. 00330 /// 00331 /// Design note: It might seem desirable for this function to be more 00332 /// loop-aware. If some of the indices are loop-invariant while others 00333 /// aren't, it might seem desirable to emit multiple GEPs, keeping the 00334 /// loop-invariant portions of the overall computation outside the loop. 00335 /// However, there are a few reasons this is not done here. Hoisting simple 00336 /// arithmetic is a low-level optimization that often isn't very 00337 /// important until late in the optimization process. In fact, passes 00338 /// like InstructionCombining will combine GEPs, even if it means 00339 /// pushing loop-invariant computation down into loops, so even if the 00340 /// GEPs were split here, the work would quickly be undone. The 00341 /// LoopStrengthReduction pass, which is usually run quite late (and 00342 /// after the last InstructionCombining pass), takes care of hoisting 00343 /// loop-invariant portions of expressions, after considering what 00344 /// can be folded using target addressing modes. 00345 /// 00346 Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, 00347 const SCEV *const *op_end, 00348 const PointerType *PTy, 00349 const Type *Ty, 00350 Value *V) { 00351 const Type *ElTy = PTy->getElementType(); 00352 SmallVector<Value *, 4> GepIndices; 00353 SmallVector<const SCEV *, 8> Ops(op_begin, op_end); 00354 bool AnyNonZeroIndices = false; 00355 00356 // Split AddRecs up into parts as either of the parts may be usable 00357 // without the other. 00358 SplitAddRecs(Ops, Ty, SE); 00359 00360 // Decend down the pointer's type and attempt to convert the other 00361 // operands into GEP indices, at each level. The first index in a GEP 00362 // indexes into the array implied by the pointer operand; the rest of 00363 // the indices index into the element or field type selected by the 00364 // preceding index. 00365 for (;;) { 00366 const SCEV *ElSize = SE.getAllocSizeExpr(ElTy); 00367 // If the scale size is not 0, attempt to factor out a scale for 00368 // array indexing. 00369 SmallVector<const SCEV *, 8> ScaledOps; 00370 if (ElTy->isSized() && !ElSize->isZero()) { 00371 SmallVector<const SCEV *, 8> NewOps; 00372 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 00373 const SCEV *Op = Ops[i]; 00374 const SCEV *Remainder = SE.getIntegerSCEV(0, Ty); 00375 if (FactorOutConstant(Op, Remainder, ElSize, SE, SE.TD)) { 00376 // Op now has ElSize factored out. 00377 ScaledOps.push_back(Op); 00378 if (!Remainder->isZero()) 00379 NewOps.push_back(Remainder); 00380 AnyNonZeroIndices = true; 00381 } else { 00382 // The operand was not divisible, so add it to the list of operands 00383 // we'll scan next iteration. 00384 NewOps.push_back(Ops[i]); 00385 } 00386 } 00387 // If we made any changes, update Ops. 00388 if (!ScaledOps.empty()) { 00389 Ops = NewOps; 00390 SimplifyAddOperands(Ops, Ty, SE); 00391 } 00392 } 00393 00394 // Record the scaled array index for this level of the type. If 00395 // we didn't find any operands that could be factored, tentatively 00396 // assume that element zero was selected (since the zero offset 00397 // would obviously be folded away). 00398 Value *Scaled = ScaledOps.empty() ? 00399 Constant::getNullValue(Ty) : 00400 expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 00401 GepIndices.push_back(Scaled); 00402 00403 // Collect struct field index operands. 00404 while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 00405 bool FoundFieldNo = false; 00406 // An empty struct has no fields. 00407 if (STy->getNumElements() == 0) break; 00408 if (SE.TD) { 00409 // With TargetData, field offsets are known. See if a constant offset 00410 // falls within any of the struct fields. 00411 if (Ops.empty()) break; 00412 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 00413 if (SE.getTypeSizeInBits(C->getType()) <= 64) { 00414 const StructLayout &SL = *SE.TD->getStructLayout(STy); 00415 uint64_t FullOffset = C->getValue()->getZExtValue(); 00416 if (FullOffset < SL.getSizeInBytes()) { 00417 unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 00418 GepIndices.push_back( 00419 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx)); 00420 ElTy = STy->getTypeAtIndex(ElIdx); 00421 Ops[0] = 00422 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 00423 AnyNonZeroIndices = true; 00424 FoundFieldNo = true; 00425 } 00426 } 00427 } else { 00428 // Without TargetData, just check for a SCEVFieldOffsetExpr of the 00429 // appropriate struct type. 00430 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 00431 if (const SCEVFieldOffsetExpr *FO = 00432 dyn_cast<SCEVFieldOffsetExpr>(Ops[i])) 00433 if (FO->getStructType() == STy) { 00434 unsigned FieldNo = FO->getFieldNo(); 00435 GepIndices.push_back( 00436 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), 00437 FieldNo)); 00438 ElTy = STy->getTypeAtIndex(FieldNo); 00439 Ops[i] = SE.getConstant(Ty, 0); 00440 AnyNonZeroIndices = true; 00441 FoundFieldNo = true; 00442 break; 00443 } 00444 } 00445 // If no struct field offsets were found, tentatively assume that 00446 // field zero was selected (since the zero offset would obviously 00447 // be folded away). 00448 if (!FoundFieldNo) { 00449 ElTy = STy->getTypeAtIndex(0u); 00450 GepIndices.push_back( 00451 Constant::getNullValue(Type::getInt32Ty(Ty->getContext()))); 00452 } 00453 } 00454 00455 if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) 00456 ElTy = ATy->getElementType(); 00457 else 00458 break; 00459 } 00460 00461 // If none of the operands were convertable to proper GEP indices, cast 00462 // the base to i8* and do an ugly getelementptr with that. It's still 00463 // better than ptrtoint+arithmetic+inttoptr at least. 00464 if (!AnyNonZeroIndices) { 00465 // Cast the base to i8*. 00466 V = InsertNoopCastOfTo(V, 00467 Type::getInt8Ty(Ty->getContext())->getPointerTo(PTy->getAddressSpace())); 00468 00469 // Expand the operands for a plain byte offset. 00470 Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 00471 00472 // Fold a GEP with constant operands. 00473 if (Constant *CLHS = dyn_cast<Constant>(V)) 00474 if (Constant *CRHS = dyn_cast<Constant>(Idx)) 00475 return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 00476 00477 // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 00478 unsigned ScanLimit = 6; 00479 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 00480 // Scanning starts from the last instruction before the insertion point. 00481 BasicBlock::iterator IP = Builder.GetInsertPoint(); 00482 if (IP != BlockBegin) { 00483 --IP; 00484 for (; ScanLimit; --IP, --ScanLimit) { 00485 if (IP->getOpcode() == Instruction::GetElementPtr && 00486 IP->getOperand(0) == V && IP->getOperand(1) == Idx) 00487 return IP; 00488 if (IP == BlockBegin) break; 00489 } 00490 } 00491 00492 // Emit a GEP. 00493 Value *GEP = Builder.CreateGEP(V, Idx, "uglygep"); 00494 InsertedValues.insert(GEP); 00495 return GEP; 00496 } 00497 00498 // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, 00499 // because ScalarEvolution may have changed the address arithmetic to 00500 // compute a value which is beyond the end of the allocated object. 00501 Value *GEP = Builder.CreateGEP(V, 00502 GepIndices.begin(), 00503 GepIndices.end(), 00504 "scevgep"); 00505 Ops.push_back(SE.getUnknown(GEP)); 00506 InsertedValues.insert(GEP); 00507 return expand(SE.getAddExpr(Ops)); 00508 } 00509 00510 Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 00511 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00512 Value *V = expand(S->getOperand(S->getNumOperands()-1)); 00513 00514 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 00515 // comments on expandAddToGEP for details. 00516 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 00517 const SmallVectorImpl<const SCEV *> &Ops = S->getOperands(); 00518 return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], PTy, Ty, V); 00519 } 00520 00521 V = InsertNoopCastOfTo(V, Ty); 00522 00523 // Emit a bunch of add instructions 00524 for (int i = S->getNumOperands()-2; i >= 0; --i) { 00525 Value *W = expandCodeFor(S->getOperand(i), Ty); 00526 V = InsertBinop(Instruction::Add, V, W); 00527 } 00528 return V; 00529 } 00530 00531 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 00532 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00533 int FirstOp = 0; // Set if we should emit a subtract. 00534 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 00535 if (SC->getValue()->isAllOnesValue()) 00536 FirstOp = 1; 00537 00538 int i = S->getNumOperands()-2; 00539 Value *V = expandCodeFor(S->getOperand(i+1), Ty); 00540 00541 // Emit a bunch of multiply instructions 00542 for (; i >= FirstOp; --i) { 00543 Value *W = expandCodeFor(S->getOperand(i), Ty); 00544 V = InsertBinop(Instruction::Mul, V, W); 00545 } 00546 00547 // -1 * ... ---> 0 - ... 00548 if (FirstOp == 1) 00549 V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V); 00550 return V; 00551 } 00552 00553 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 00554 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00555 00556 Value *LHS = expandCodeFor(S->getLHS(), Ty); 00557 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 00558 const APInt &RHS = SC->getValue()->getValue(); 00559 if (RHS.isPowerOf2()) 00560 return InsertBinop(Instruction::LShr, LHS, 00561 ConstantInt::get(Ty, RHS.logBase2())); 00562 } 00563 00564 Value *RHS = expandCodeFor(S->getRHS(), Ty); 00565 return InsertBinop(Instruction::UDiv, LHS, RHS); 00566 } 00567 00568 /// Move parts of Base into Rest to leave Base with the minimal 00569 /// expression that provides a pointer operand suitable for a 00570 /// GEP expansion. 00571 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, 00572 ScalarEvolution &SE) { 00573 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 00574 Base = A->getStart(); 00575 Rest = SE.getAddExpr(Rest, 00576 SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 00577 A->getStepRecurrence(SE), 00578 A->getLoop())); 00579 } 00580 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 00581 Base = A->getOperand(A->getNumOperands()-1); 00582 SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end()); 00583 NewAddOps.back() = Rest; 00584 Rest = SE.getAddExpr(NewAddOps); 00585 ExposePointerBase(Base, Rest, SE); 00586 } 00587 } 00588 00589 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 00590 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00591 const Loop *L = S->getLoop(); 00592 00593 // First check for an existing canonical IV in a suitable type. 00594 PHINode *CanonicalIV = 0; 00595 if (PHINode *PN = L->getCanonicalInductionVariable()) 00596 if (SE.isSCEVable(PN->getType()) && 00597 isa<IntegerType>(SE.getEffectiveSCEVType(PN->getType())) && 00598 SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 00599 CanonicalIV = PN; 00600 00601 // Rewrite an AddRec in terms of the canonical induction variable, if 00602 // its type is more narrow. 00603 if (CanonicalIV && 00604 SE.getTypeSizeInBits(CanonicalIV->getType()) > 00605 SE.getTypeSizeInBits(Ty)) { 00606 const SCEV *Start = SE.getAnyExtendExpr(S->getStart(), 00607 CanonicalIV->getType()); 00608 const SCEV *Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE), 00609 CanonicalIV->getType()); 00610 Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop())); 00611 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 00612 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 00613 BasicBlock::iterator NewInsertPt = 00614 next(BasicBlock::iterator(cast<Instruction>(V))); 00615 while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; 00616 V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, 00617 NewInsertPt); 00618 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 00619 return V; 00620 } 00621 00622 // {X,+,F} --> X + {0,+,F} 00623 if (!S->getStart()->isZero()) { 00624 const SmallVectorImpl<const SCEV *> &SOperands = S->getOperands(); 00625 SmallVector<const SCEV *, 4> NewOps(SOperands.begin(), SOperands.end()); 00626 NewOps[0] = SE.getIntegerSCEV(0, Ty); 00627 const SCEV *Rest = SE.getAddRecExpr(NewOps, L); 00628 00629 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 00630 // comments on expandAddToGEP for details. 00631 const SCEV *Base = S->getStart(); 00632 const SCEV *RestArray[1] = { Rest }; 00633 // Dig into the expression to find the pointer base for a GEP. 00634 ExposePointerBase(Base, RestArray[0], SE); 00635 // If we found a pointer, expand the AddRec with a GEP. 00636 if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 00637 // Make sure the Base isn't something exotic, such as a multiplied 00638 // or divided pointer value. In those cases, the result type isn't 00639 // actually a pointer type. 00640 if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 00641 Value *StartV = expand(Base); 00642 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 00643 return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 00644 } 00645 } 00646 00647 // Just do a normal add. Pre-expand the operands to suppress folding. 00648 return expand(SE.getAddExpr(SE.getUnknown(expand(S->getStart())), 00649 SE.getUnknown(expand(Rest)))); 00650 } 00651 00652 // {0,+,1} --> Insert a canonical induction variable into the loop! 00653 if (S->isAffine() && 00654 S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 00655 // If there's a canonical IV, just use it. 00656 if (CanonicalIV) { 00657 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 00658 "IVs with types different from the canonical IV should " 00659 "already have been handled!"); 00660 return CanonicalIV; 00661 } 00662 00663 // Create and insert the PHI node for the induction variable in the 00664 // specified loop. 00665 BasicBlock *Header = L->getHeader(); 00666 BasicBlock *Preheader = L->getLoopPreheader(); 00667 PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 00668 InsertedValues.insert(PN); 00669 PN->addIncoming(Constant::getNullValue(Ty), Preheader); 00670 00671 pred_iterator HPI = pred_begin(Header); 00672 assert(HPI != pred_end(Header) && "Loop with zero preds???"); 00673 if (!L->contains(*HPI)) ++HPI; 00674 assert(HPI != pred_end(Header) && L->contains(*HPI) && 00675 "No backedge in loop?"); 00676 00677 // Insert a unit add instruction right before the terminator corresponding 00678 // to the back-edge. 00679 Constant *One = ConstantInt::get(Ty, 1); 00680 Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 00681 (*HPI)->getTerminator()); 00682 InsertedValues.insert(Add); 00683 00684 pred_iterator PI = pred_begin(Header); 00685 if (*PI == Preheader) 00686 ++PI; 00687 PN->addIncoming(Add, *PI); 00688 return PN; 00689 } 00690 00691 // {0,+,F} --> {0,+,1} * F 00692 // Get the canonical induction variable I for this loop. 00693 Value *I = CanonicalIV ? 00694 CanonicalIV : 00695 getOrInsertCanonicalInductionVariable(L, Ty); 00696 00697 // If this is a simple linear addrec, emit it now as a special case. 00698 if (S->isAffine()) // {0,+,F} --> i*F 00699 return 00700 expand(SE.getTruncateOrNoop( 00701 SE.getMulExpr(SE.getUnknown(I), 00702 SE.getNoopOrAnyExtend(S->getOperand(1), 00703 I->getType())), 00704 Ty)); 00705 00706 // If this is a chain of recurrences, turn it into a closed form, using the 00707 // folders, then expandCodeFor the closed form. This allows the folders to 00708 // simplify the expression without having to build a bunch of special code 00709 // into this folder. 00710 const SCEV *IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 00711 00712 // Promote S up to the canonical IV type, if the cast is foldable. 00713 const SCEV *NewS = S; 00714 const SCEV *Ext = SE.getNoopOrAnyExtend(S, I->getType()); 00715 if (isa<SCEVAddRecExpr>(Ext)) 00716 NewS = Ext; 00717 00718 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 00719 //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 00720 00721 // Truncate the result down to the original type, if needed. 00722 const SCEV *T = SE.getTruncateOrNoop(V, Ty); 00723 return expand(T); 00724 } 00725 00726 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 00727 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00728 Value *V = expandCodeFor(S->getOperand(), 00729 SE.getEffectiveSCEVType(S->getOperand()->getType())); 00730 Value *I = Builder.CreateTrunc(V, Ty, "tmp"); 00731 InsertedValues.insert(I); 00732 return I; 00733 } 00734 00735 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 00736 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00737 Value *V = expandCodeFor(S->getOperand(), 00738 SE.getEffectiveSCEVType(S->getOperand()->getType())); 00739 Value *I = Builder.CreateZExt(V, Ty, "tmp"); 00740 InsertedValues.insert(I); 00741 return I; 00742 } 00743 00744 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 00745 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 00746 Value *V = expandCodeFor(S->getOperand(), 00747 SE.getEffectiveSCEVType(S->getOperand()->getType())); 00748 Value *I = Builder.CreateSExt(V, Ty, "tmp"); 00749 InsertedValues.insert(I); 00750 return I; 00751 } 00752 00753 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 00754 Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 00755 const Type *Ty = LHS->getType(); 00756 for (int i = S->getNumOperands()-2; i >= 0; --i) { 00757 // In the case of mixed integer and pointer types, do the 00758 // rest of the comparisons as integer. 00759 if (S->getOperand(i)->getType() != Ty) { 00760 Ty = SE.getEffectiveSCEVType(Ty); 00761 LHS = InsertNoopCastOfTo(LHS, Ty); 00762 } 00763 Value *RHS = expandCodeFor(S->getOperand(i), Ty); 00764 Value *ICmp = Builder.CreateICmpSGT(LHS, RHS, "tmp"); 00765 InsertedValues.insert(ICmp); 00766 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax"); 00767 InsertedValues.insert(Sel); 00768 LHS = Sel; 00769 } 00770 // In the case of mixed integer and pointer types, cast the 00771 // final result back to the pointer type. 00772 if (LHS->getType() != S->getType()) 00773 LHS = InsertNoopCastOfTo(LHS, S->getType()); 00774 return LHS; 00775 } 00776 00777 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 00778 Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 00779 const Type *Ty = LHS->getType(); 00780 for (int i = S->getNumOperands()-2; i >= 0; --i) { 00781 // In the case of mixed integer and pointer types, do the 00782 // rest of the comparisons as integer. 00783 if (S->getOperand(i)->getType() != Ty) { 00784 Ty = SE.getEffectiveSCEVType(Ty); 00785 LHS = InsertNoopCastOfTo(LHS, Ty); 00786 } 00787 Value *RHS = expandCodeFor(S->getOperand(i), Ty); 00788 Value *ICmp = Builder.CreateICmpUGT(LHS, RHS, "tmp"); 00789 InsertedValues.insert(ICmp); 00790 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax"); 00791 InsertedValues.insert(Sel); 00792 LHS = Sel; 00793 } 00794 // In the case of mixed integer and pointer types, cast the 00795 // final result back to the pointer type. 00796 if (LHS->getType() != S->getType()) 00797 LHS = InsertNoopCastOfTo(LHS, S->getType()); 00798 return LHS; 00799 } 00800 00801 Value *SCEVExpander::visitFieldOffsetExpr(const SCEVFieldOffsetExpr *S) { 00802 return ConstantExpr::getOffsetOf(S->getStructType(), S->getFieldNo()); 00803 } 00804 00805 Value *SCEVExpander::visitAllocSizeExpr(const SCEVAllocSizeExpr *S) { 00806 return ConstantExpr::getSizeOf(S->getAllocType()); 00807 } 00808 00809 Value *SCEVExpander::expandCodeFor(const SCEV *SH, const Type *Ty) { 00810 // Expand the code for this SCEV. 00811 Value *V = expand(SH); 00812 if (Ty) { 00813 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 00814 "non-trivial casts should be done with the SCEVs directly!"); 00815 V = InsertNoopCastOfTo(V, Ty); 00816 } 00817 return V; 00818 } 00819 00820 Value *SCEVExpander::expand(const SCEV *S) { 00821 // Compute an insertion point for this SCEV object. Hoist the instructions 00822 // as far out in the loop nest as possible. 00823 Instruction *InsertPt = Builder.GetInsertPoint(); 00824 for (Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock()); ; 00825 L = L->getParentLoop()) 00826 if (S->isLoopInvariant(L)) { 00827 if (!L) break; 00828 if (BasicBlock *Preheader = L->getLoopPreheader()) 00829 InsertPt = Preheader->getTerminator(); 00830 } else { 00831 // If the SCEV is computable at this level, insert it into the header 00832 // after the PHIs (and after any other instructions that we've inserted 00833 // there) so that it is guaranteed to dominate any user inside the loop. 00834 if (L && S->hasComputableLoopEvolution(L)) 00835 InsertPt = L->getHeader()->getFirstNonPHI(); 00836 while (isInsertedInstruction(InsertPt)) 00837 InsertPt = next(BasicBlock::iterator(InsertPt)); 00838 break; 00839 } 00840 00841 // Check to see if we already expanded this here. 00842 std::map<std::pair<const SCEV *, Instruction *>, 00843 AssertingVH<Value> >::iterator I = 00844 InsertedExpressions.find(std::make_pair(S, InsertPt)); 00845 if (I != InsertedExpressions.end()) 00846 return I->second; 00847 00848 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 00849 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 00850 Builder.SetInsertPoint(InsertPt->getParent(), InsertPt); 00851 00852 // Expand the expression into instructions. 00853 Value *V = visit(S); 00854 00855 // Remember the expanded value for this SCEV at this location. 00856 InsertedExpressions[std::make_pair(S, InsertPt)] = V; 00857 00858 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 00859 return V; 00860 } 00861 00862 /// getOrInsertCanonicalInductionVariable - This method returns the 00863 /// canonical induction variable of the specified type for the specified 00864 /// loop (inserting one if there is none). A canonical induction variable 00865 /// starts at zero and steps by one on each iteration. 00866 Value * 00867 SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 00868 const Type *Ty) { 00869 assert(Ty->isInteger() && "Can only insert integer induction variables!"); 00870 const SCEV *H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), 00871 SE.getIntegerSCEV(1, Ty), L); 00872 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 00873 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 00874 Value *V = expandCodeFor(H, 0, L->getHeader()->begin()); 00875 if (SaveInsertBB) 00876 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 00877 return V; 00878 }