ScalarEvolutionExpander.cpp revision 6de29f8d960505421d61c80cdb738e16720b6c0e
1//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains the implementation of the scalar evolution expander, 11// which is used to generate the code corresponding to a given scalar evolution 12// expression. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/ScalarEvolutionExpander.h" 17#include "llvm/Analysis/LoopInfo.h" 18#include "llvm/Target/TargetData.h" 19#include "llvm/ADT/STLExtras.h" 20using namespace llvm; 21 22/// InsertCastOfTo - Insert a cast of V to the specified type, doing what 23/// we can to share the casts. 24Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 25 const Type *Ty) { 26 // Short-circuit unnecessary bitcasts. 27 if (opcode == Instruction::BitCast && V->getType() == Ty) 28 return V; 29 30 // Short-circuit unnecessary inttoptr<->ptrtoint casts. 31 if ((opcode == Instruction::PtrToInt || opcode == Instruction::IntToPtr) && 32 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 33 if (CastInst *CI = dyn_cast<CastInst>(V)) 34 if ((CI->getOpcode() == Instruction::PtrToInt || 35 CI->getOpcode() == Instruction::IntToPtr) && 36 SE.getTypeSizeInBits(CI->getType()) == 37 SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 38 return CI->getOperand(0); 39 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 40 if ((CE->getOpcode() == Instruction::PtrToInt || 41 CE->getOpcode() == Instruction::IntToPtr) && 42 SE.getTypeSizeInBits(CE->getType()) == 43 SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 44 return CE->getOperand(0); 45 } 46 47 // FIXME: keep track of the cast instruction. 48 if (Constant *C = dyn_cast<Constant>(V)) 49 return ConstantExpr::getCast(opcode, C, Ty); 50 51 if (Argument *A = dyn_cast<Argument>(V)) { 52 // Check to see if there is already a cast! 53 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 54 UI != E; ++UI) { 55 if ((*UI)->getType() == Ty) 56 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 57 if (CI->getOpcode() == opcode) { 58 // If the cast isn't the first instruction of the function, move it. 59 if (BasicBlock::iterator(CI) != 60 A->getParent()->getEntryBlock().begin()) { 61 // If the CastInst is the insert point, change the insert point. 62 if (CI == InsertPt) ++InsertPt; 63 // Splice the cast at the beginning of the entry block. 64 CI->moveBefore(A->getParent()->getEntryBlock().begin()); 65 } 66 return CI; 67 } 68 } 69 Instruction *I = CastInst::Create(opcode, V, Ty, V->getName(), 70 A->getParent()->getEntryBlock().begin()); 71 InsertedValues.insert(I); 72 return I; 73 } 74 75 Instruction *I = cast<Instruction>(V); 76 77 // Check to see if there is already a cast. If there is, use it. 78 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 79 UI != E; ++UI) { 80 if ((*UI)->getType() == Ty) 81 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 82 if (CI->getOpcode() == opcode) { 83 BasicBlock::iterator It = I; ++It; 84 if (isa<InvokeInst>(I)) 85 It = cast<InvokeInst>(I)->getNormalDest()->begin(); 86 while (isa<PHINode>(It)) ++It; 87 if (It != BasicBlock::iterator(CI)) { 88 // If the CastInst is the insert point, change the insert point. 89 if (CI == InsertPt) ++InsertPt; 90 // Splice the cast immediately after the operand in question. 91 CI->moveBefore(It); 92 } 93 return CI; 94 } 95 } 96 BasicBlock::iterator IP = I; ++IP; 97 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 98 IP = II->getNormalDest()->begin(); 99 while (isa<PHINode>(IP)) ++IP; 100 Instruction *CI = CastInst::Create(opcode, V, Ty, V->getName(), IP); 101 InsertedValues.insert(CI); 102 return CI; 103} 104 105/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 106/// which must be possible with a noop cast. 107Value *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 108 Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 109 assert((Op == Instruction::BitCast || 110 Op == Instruction::PtrToInt || 111 Op == Instruction::IntToPtr) && 112 "InsertNoopCastOfTo cannot perform non-noop casts!"); 113 assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 114 "InsertNoopCastOfTo cannot change sizes!"); 115 return InsertCastOfTo(Op, V, Ty); 116} 117 118/// InsertBinop - Insert the specified binary operator, doing a small amount 119/// of work to avoid inserting an obviously redundant operation. 120Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 121 Value *RHS, BasicBlock::iterator InsertPt) { 122 // Fold a binop with constant operands. 123 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 124 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 125 return ConstantExpr::get(Opcode, CLHS, CRHS); 126 127 // Do a quick scan to see if we have this binop nearby. If so, reuse it. 128 unsigned ScanLimit = 6; 129 BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 130 if (InsertPt != BlockBegin) { 131 // Scanning starts from the last instruction before InsertPt. 132 BasicBlock::iterator IP = InsertPt; 133 --IP; 134 for (; ScanLimit; --IP, --ScanLimit) { 135 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 136 IP->getOperand(1) == RHS) 137 return IP; 138 if (IP == BlockBegin) break; 139 } 140 } 141 142 // If we haven't found this binop, insert it. 143 Instruction *BO = BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); 144 InsertedValues.insert(BO); 145 return BO; 146} 147 148/// FactorOutConstant - Test if S is divisible by Factor, using signed 149/// division. If so, update S with Factor divided out and return true. 150/// S need not be evenly divisble if a reasonable remainder can be 151/// computed. 152/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 153/// unnecessary; in its place, just signed-divide Ops[i] by the scale and 154/// check to see if the divide was folded. 155static bool FactorOutConstant(SCEVHandle &S, 156 SCEVHandle &Remainder, 157 const APInt &Factor, 158 ScalarEvolution &SE) { 159 // Everything is divisible by one. 160 if (Factor == 1) 161 return true; 162 163 // For a Constant, check for a multiple of the given factor. 164 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 165 ConstantInt *CI = 166 ConstantInt::get(C->getValue()->getValue().sdiv(Factor)); 167 // If the quotient is zero and the remainder is non-zero, reject 168 // the value at this scale. It will be considered for subsequent 169 // smaller scales. 170 if (C->isZero() || !CI->isZero()) { 171 SCEVHandle Div = SE.getConstant(CI); 172 S = Div; 173 Remainder = 174 SE.getAddExpr(Remainder, 175 SE.getConstant(C->getValue()->getValue().srem(Factor))); 176 return true; 177 } 178 } 179 180 // In a Mul, check if there is a constant operand which is a multiple 181 // of the given factor. 182 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) 183 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 184 if (!C->getValue()->getValue().srem(Factor)) { 185 const SmallVectorImpl<SCEVHandle> &MOperands = M->getOperands(); 186 SmallVector<SCEVHandle, 4> NewMulOps(MOperands.begin(), MOperands.end()); 187 NewMulOps[0] = 188 SE.getConstant(C->getValue()->getValue().sdiv(Factor)); 189 S = SE.getMulExpr(NewMulOps); 190 return true; 191 } 192 193 // In an AddRec, check if both start and step are divisible. 194 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 195 SCEVHandle Step = A->getStepRecurrence(SE); 196 SCEVHandle StepRem = SE.getIntegerSCEV(0, Step->getType()); 197 if (!FactorOutConstant(Step, StepRem, Factor, SE)) 198 return false; 199 if (!StepRem->isZero()) 200 return false; 201 SCEVHandle Start = A->getStart(); 202 if (!FactorOutConstant(Start, Remainder, Factor, SE)) 203 return false; 204 S = SE.getAddRecExpr(Start, Step, A->getLoop()); 205 return true; 206 } 207 208 return false; 209} 210 211/// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 212/// instead of using ptrtoint+arithmetic+inttoptr. This helps 213/// BasicAliasAnalysis analyze the result. However, it suffers from the 214/// underlying bug described in PR2831. Addition in LLVM currently always 215/// has two's complement wrapping guaranteed. However, the semantics for 216/// getelementptr overflow are ambiguous. In the common case though, this 217/// expansion gets used when a GEP in the original code has been converted 218/// into integer arithmetic, in which case the resulting code will be no 219/// more undefined than it was originally. 220/// 221/// Design note: It might seem desirable for this function to be more 222/// loop-aware. If some of the indices are loop-invariant while others 223/// aren't, it might seem desirable to emit multiple GEPs, keeping the 224/// loop-invariant portions of the overall computation outside the loop. 225/// However, there are a few reasons this is not done here. Hoisting simple 226/// arithmetic is a low-level optimization that often isn't very 227/// important until late in the optimization process. In fact, passes 228/// like InstructionCombining will combine GEPs, even if it means 229/// pushing loop-invariant computation down into loops, so even if the 230/// GEPs were split here, the work would quickly be undone. The 231/// LoopStrengthReduction pass, which is usually run quite late (and 232/// after the last InstructionCombining pass), takes care of hoisting 233/// loop-invariant portions of expressions, after considering what 234/// can be folded using target addressing modes. 235/// 236Value *SCEVExpander::expandAddToGEP(const SCEVHandle *op_begin, 237 const SCEVHandle *op_end, 238 const PointerType *PTy, 239 const Type *Ty, 240 Value *V) { 241 const Type *ElTy = PTy->getElementType(); 242 SmallVector<Value *, 4> GepIndices; 243 SmallVector<SCEVHandle, 8> Ops(op_begin, op_end); 244 bool AnyNonZeroIndices = false; 245 246 // Decend down the pointer's type and attempt to convert the other 247 // operands into GEP indices, at each level. The first index in a GEP 248 // indexes into the array implied by the pointer operand; the rest of 249 // the indices index into the element or field type selected by the 250 // preceding index. 251 for (;;) { 252 APInt ElSize = APInt(SE.getTypeSizeInBits(Ty), 253 ElTy->isSized() ? SE.TD->getTypeAllocSize(ElTy) : 0); 254 SmallVector<SCEVHandle, 8> NewOps; 255 SmallVector<SCEVHandle, 8> ScaledOps; 256 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 257 // Split AddRecs up into parts as either of the parts may be usable 258 // without the other. 259 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) 260 if (!A->getStart()->isZero()) { 261 SCEVHandle Start = A->getStart(); 262 Ops.push_back(SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 263 A->getStepRecurrence(SE), 264 A->getLoop())); 265 Ops[i] = Start; 266 ++e; 267 } 268 // If the scale size is not 0, attempt to factor out a scale. 269 if (ElSize != 0) { 270 SCEVHandle Op = Ops[i]; 271 SCEVHandle Remainder = SE.getIntegerSCEV(0, Op->getType()); 272 if (FactorOutConstant(Op, Remainder, ElSize, SE)) { 273 ScaledOps.push_back(Op); // Op now has ElSize factored out. 274 NewOps.push_back(Remainder); 275 continue; 276 } 277 } 278 // If the operand was not divisible, add it to the list of operands 279 // we'll scan next iteration. 280 NewOps.push_back(Ops[i]); 281 } 282 Ops = NewOps; 283 AnyNonZeroIndices |= !ScaledOps.empty(); 284 Value *Scaled = ScaledOps.empty() ? 285 Constant::getNullValue(Ty) : 286 expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 287 GepIndices.push_back(Scaled); 288 289 // Collect struct field index operands. 290 if (!Ops.empty()) 291 while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 292 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 293 if (SE.getTypeSizeInBits(C->getType()) <= 64) { 294 const StructLayout &SL = *SE.TD->getStructLayout(STy); 295 uint64_t FullOffset = C->getValue()->getZExtValue(); 296 if (FullOffset < SL.getSizeInBytes()) { 297 unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 298 GepIndices.push_back(ConstantInt::get(Type::Int32Ty, ElIdx)); 299 ElTy = STy->getTypeAtIndex(ElIdx); 300 Ops[0] = 301 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 302 AnyNonZeroIndices = true; 303 continue; 304 } 305 } 306 break; 307 } 308 309 if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) { 310 ElTy = ATy->getElementType(); 311 continue; 312 } 313 break; 314 } 315 316 // If none of the operands were convertable to proper GEP indices, cast 317 // the base to i8* and do an ugly getelementptr with that. It's still 318 // better than ptrtoint+arithmetic+inttoptr at least. 319 if (!AnyNonZeroIndices) { 320 V = InsertNoopCastOfTo(V, 321 Type::Int8Ty->getPointerTo(PTy->getAddressSpace())); 322 Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 323 324 // Fold a GEP with constant operands. 325 if (Constant *CLHS = dyn_cast<Constant>(V)) 326 if (Constant *CRHS = dyn_cast<Constant>(Idx)) 327 return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 328 329 // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 330 unsigned ScanLimit = 6; 331 BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 332 if (InsertPt != BlockBegin) { 333 // Scanning starts from the last instruction before InsertPt. 334 BasicBlock::iterator IP = InsertPt; 335 --IP; 336 for (; ScanLimit; --IP, --ScanLimit) { 337 if (IP->getOpcode() == Instruction::GetElementPtr && 338 IP->getOperand(0) == V && IP->getOperand(1) == Idx) 339 return IP; 340 if (IP == BlockBegin) break; 341 } 342 } 343 344 Value *GEP = GetElementPtrInst::Create(V, Idx, "scevgep", InsertPt); 345 InsertedValues.insert(GEP); 346 return GEP; 347 } 348 349 // Insert a pretty getelementptr. 350 Value *GEP = GetElementPtrInst::Create(V, 351 GepIndices.begin(), 352 GepIndices.end(), 353 "scevgep", InsertPt); 354 Ops.push_back(SE.getUnknown(GEP)); 355 InsertedValues.insert(GEP); 356 return expand(SE.getAddExpr(Ops)); 357} 358 359Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 360 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 361 Value *V = expand(S->getOperand(S->getNumOperands()-1)); 362 363 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 364 // comments on expandAddToGEP for details. 365 if (SE.TD) 366 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 367 const SmallVectorImpl<SCEVHandle> &Ops = S->getOperands(); 368 return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], 369 PTy, Ty, V); 370 } 371 372 V = InsertNoopCastOfTo(V, Ty); 373 374 // Emit a bunch of add instructions 375 for (int i = S->getNumOperands()-2; i >= 0; --i) { 376 Value *W = expandCodeFor(S->getOperand(i), Ty); 377 V = InsertBinop(Instruction::Add, V, W, InsertPt); 378 } 379 return V; 380} 381 382Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 383 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 384 int FirstOp = 0; // Set if we should emit a subtract. 385 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 386 if (SC->getValue()->isAllOnesValue()) 387 FirstOp = 1; 388 389 int i = S->getNumOperands()-2; 390 Value *V = expandCodeFor(S->getOperand(i+1), Ty); 391 392 // Emit a bunch of multiply instructions 393 for (; i >= FirstOp; --i) { 394 Value *W = expandCodeFor(S->getOperand(i), Ty); 395 V = InsertBinop(Instruction::Mul, V, W, InsertPt); 396 } 397 398 // -1 * ... ---> 0 - ... 399 if (FirstOp == 1) 400 V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt); 401 return V; 402} 403 404Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 405 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 406 407 Value *LHS = expandCodeFor(S->getLHS(), Ty); 408 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 409 const APInt &RHS = SC->getValue()->getValue(); 410 if (RHS.isPowerOf2()) 411 return InsertBinop(Instruction::LShr, LHS, 412 ConstantInt::get(Ty, RHS.logBase2()), 413 InsertPt); 414 } 415 416 Value *RHS = expandCodeFor(S->getRHS(), Ty); 417 return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); 418} 419 420/// Move parts of Base into Rest to leave Base with the minimal 421/// expression that provides a pointer operand suitable for a 422/// GEP expansion. 423static void ExposePointerBase(SCEVHandle &Base, SCEVHandle &Rest, 424 ScalarEvolution &SE) { 425 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 426 Base = A->getStart(); 427 Rest = SE.getAddExpr(Rest, 428 SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 429 A->getStepRecurrence(SE), 430 A->getLoop())); 431 } 432 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 433 Base = A->getOperand(A->getNumOperands()-1); 434 SmallVector<SCEVHandle, 8> NewAddOps(A->op_begin(), A->op_end()); 435 NewAddOps.back() = Rest; 436 Rest = SE.getAddExpr(NewAddOps); 437 ExposePointerBase(Base, Rest, SE); 438 } 439} 440 441Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 442 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 443 const Loop *L = S->getLoop(); 444 445 // First check for an existing canonical IV in a suitable type. 446 PHINode *CanonicalIV = 0; 447 if (PHINode *PN = L->getCanonicalInductionVariable()) 448 if (SE.isSCEVable(PN->getType()) && 449 isa<IntegerType>(SE.getEffectiveSCEVType(PN->getType())) && 450 SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 451 CanonicalIV = PN; 452 453 // Rewrite an AddRec in terms of the canonical induction variable, if 454 // its type is more narrow. 455 if (CanonicalIV && 456 SE.getTypeSizeInBits(CanonicalIV->getType()) > 457 SE.getTypeSizeInBits(Ty)) { 458 SCEVHandle Start = SE.getAnyExtendExpr(S->getStart(), 459 CanonicalIV->getType()); 460 SCEVHandle Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE), 461 CanonicalIV->getType()); 462 Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop())); 463 BasicBlock::iterator SaveInsertPt = getInsertionPoint(); 464 BasicBlock::iterator NewInsertPt = 465 next(BasicBlock::iterator(cast<Instruction>(V))); 466 while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; 467 V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, 468 NewInsertPt); 469 setInsertionPoint(SaveInsertPt); 470 return V; 471 } 472 473 // {X,+,F} --> X + {0,+,F} 474 if (!S->getStart()->isZero()) { 475 const SmallVectorImpl<SCEVHandle> &SOperands = S->getOperands(); 476 SmallVector<SCEVHandle, 4> NewOps(SOperands.begin(), SOperands.end()); 477 NewOps[0] = SE.getIntegerSCEV(0, Ty); 478 SCEVHandle Rest = SE.getAddRecExpr(NewOps, L); 479 480 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 481 // comments on expandAddToGEP for details. 482 if (SE.TD) { 483 SCEVHandle Base = S->getStart(); 484 SCEVHandle RestArray[1] = { Rest }; 485 // Dig into the expression to find the pointer base for a GEP. 486 ExposePointerBase(Base, RestArray[0], SE); 487 // If we found a pointer, expand the AddRec with a GEP. 488 if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 489 // Make sure the Base isn't something exotic, such as a multiplied 490 // or divided pointer value. In those cases, the result type isn't 491 // actually a pointer type. 492 if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 493 Value *StartV = expand(Base); 494 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 495 return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 496 } 497 } 498 } 499 500 Value *RestV = expand(Rest); 501 return expand(SE.getAddExpr(S->getStart(), SE.getUnknown(RestV))); 502 } 503 504 // {0,+,1} --> Insert a canonical induction variable into the loop! 505 if (S->isAffine() && 506 S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 507 // If there's a canonical IV, just use it. 508 if (CanonicalIV) { 509 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 510 "IVs with types different from the canonical IV should " 511 "already have been handled!"); 512 return CanonicalIV; 513 } 514 515 // Create and insert the PHI node for the induction variable in the 516 // specified loop. 517 BasicBlock *Header = L->getHeader(); 518 PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 519 InsertedValues.insert(PN); 520 PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 521 522 pred_iterator HPI = pred_begin(Header); 523 assert(HPI != pred_end(Header) && "Loop with zero preds???"); 524 if (!L->contains(*HPI)) ++HPI; 525 assert(HPI != pred_end(Header) && L->contains(*HPI) && 526 "No backedge in loop?"); 527 528 // Insert a unit add instruction right before the terminator corresponding 529 // to the back-edge. 530 Constant *One = ConstantInt::get(Ty, 1); 531 Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 532 (*HPI)->getTerminator()); 533 InsertedValues.insert(Add); 534 535 pred_iterator PI = pred_begin(Header); 536 if (*PI == L->getLoopPreheader()) 537 ++PI; 538 PN->addIncoming(Add, *PI); 539 return PN; 540 } 541 542 // {0,+,F} --> {0,+,1} * F 543 // Get the canonical induction variable I for this loop. 544 Value *I = CanonicalIV ? 545 CanonicalIV : 546 getOrInsertCanonicalInductionVariable(L, Ty); 547 548 // If this is a simple linear addrec, emit it now as a special case. 549 if (S->isAffine()) { // {0,+,F} --> i*F 550 Value *F = expandCodeFor(S->getOperand(1), Ty); 551 552 // If the insert point is directly inside of the loop, emit the multiply at 553 // the insert point. Otherwise, L is a loop that is a parent of the insert 554 // point loop. If we can, move the multiply to the outer most loop that it 555 // is safe to be in. 556 BasicBlock::iterator MulInsertPt = getInsertionPoint(); 557 Loop *InsertPtLoop = SE.LI->getLoopFor(MulInsertPt->getParent()); 558 if (InsertPtLoop != L && InsertPtLoop && 559 L->contains(InsertPtLoop->getHeader())) { 560 do { 561 // If we cannot hoist the multiply out of this loop, don't. 562 if (!InsertPtLoop->isLoopInvariant(F)) break; 563 564 BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader(); 565 566 // If this loop hasn't got a preheader, we aren't able to hoist the 567 // multiply. 568 if (!InsertPtLoopPH) 569 break; 570 571 // Otherwise, move the insert point to the preheader. 572 MulInsertPt = InsertPtLoopPH->getTerminator(); 573 InsertPtLoop = InsertPtLoop->getParentLoop(); 574 } while (InsertPtLoop != L); 575 } 576 577 return InsertBinop(Instruction::Mul, I, F, MulInsertPt); 578 } 579 580 // If this is a chain of recurrences, turn it into a closed form, using the 581 // folders, then expandCodeFor the closed form. This allows the folders to 582 // simplify the expression without having to build a bunch of special code 583 // into this folder. 584 SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 585 586 // Promote S up to the canonical IV type, if the cast is foldable. 587 SCEVHandle NewS = S; 588 SCEVHandle Ext = SE.getNoopOrAnyExtend(S, I->getType()); 589 if (isa<SCEVAddRecExpr>(Ext)) 590 NewS = Ext; 591 592 SCEVHandle V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 593 //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 594 595 // Truncate the result down to the original type, if needed. 596 SCEVHandle T = SE.getTruncateOrNoop(V, Ty); 597 return expand(V); 598} 599 600Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 601 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 602 Value *V = expandCodeFor(S->getOperand(), 603 SE.getEffectiveSCEVType(S->getOperand()->getType())); 604 Instruction *I = new TruncInst(V, Ty, "tmp.", InsertPt); 605 InsertedValues.insert(I); 606 return I; 607} 608 609Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 610 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 611 Value *V = expandCodeFor(S->getOperand(), 612 SE.getEffectiveSCEVType(S->getOperand()->getType())); 613 Instruction *I = new ZExtInst(V, Ty, "tmp.", InsertPt); 614 InsertedValues.insert(I); 615 return I; 616} 617 618Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 619 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 620 Value *V = expandCodeFor(S->getOperand(), 621 SE.getEffectiveSCEVType(S->getOperand()->getType())); 622 Instruction *I = new SExtInst(V, Ty, "tmp.", InsertPt); 623 InsertedValues.insert(I); 624 return I; 625} 626 627Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 628 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 629 Value *LHS = expandCodeFor(S->getOperand(0), Ty); 630 for (unsigned i = 1; i < S->getNumOperands(); ++i) { 631 Value *RHS = expandCodeFor(S->getOperand(i), Ty); 632 Instruction *ICmp = 633 new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); 634 InsertedValues.insert(ICmp); 635 Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); 636 InsertedValues.insert(Sel); 637 LHS = Sel; 638 } 639 return LHS; 640} 641 642Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 643 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 644 Value *LHS = expandCodeFor(S->getOperand(0), Ty); 645 for (unsigned i = 1; i < S->getNumOperands(); ++i) { 646 Value *RHS = expandCodeFor(S->getOperand(i), Ty); 647 Instruction *ICmp = 648 new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); 649 InsertedValues.insert(ICmp); 650 Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); 651 InsertedValues.insert(Sel); 652 LHS = Sel; 653 } 654 return LHS; 655} 656 657Value *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty) { 658 // Expand the code for this SCEV. 659 Value *V = expand(SH); 660 if (Ty) { 661 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 662 "non-trivial casts should be done with the SCEVs directly!"); 663 V = InsertNoopCastOfTo(V, Ty); 664 } 665 return V; 666} 667 668Value *SCEVExpander::expand(const SCEV *S) { 669 // Check to see if we already expanded this. 670 std::map<SCEVHandle, AssertingVH<Value> >::iterator I = 671 InsertedExpressions.find(S); 672 if (I != InsertedExpressions.end()) 673 return I->second; 674 675 Value *V = visit(S); 676 InsertedExpressions[S] = V; 677 return V; 678} 679 680/// getOrInsertCanonicalInductionVariable - This method returns the 681/// canonical induction variable of the specified type for the specified 682/// loop (inserting one if there is none). A canonical induction variable 683/// starts at zero and steps by one on each iteration. 684Value * 685SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 686 const Type *Ty) { 687 assert(Ty->isInteger() && "Can only insert integer induction variables!"); 688 SCEVHandle H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), 689 SE.getIntegerSCEV(1, Ty), L); 690 return expand(H); 691} 692