ScalarEvolutionExpander.cpp revision 198090
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/LLVMContext.h" 19#include "llvm/Target/TargetData.h" 20#include "llvm/ADT/STLExtras.h" 21using namespace llvm; 22 23/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 24/// which must be possible with a noop cast, doing what we can to share 25/// the casts. 26Value *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 27 Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 28 assert((Op == Instruction::BitCast || 29 Op == Instruction::PtrToInt || 30 Op == Instruction::IntToPtr) && 31 "InsertNoopCastOfTo cannot perform non-noop casts!"); 32 assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 33 "InsertNoopCastOfTo cannot change sizes!"); 34 35 // Short-circuit unnecessary bitcasts. 36 if (Op == Instruction::BitCast && V->getType() == Ty) 37 return V; 38 39 // Short-circuit unnecessary inttoptr<->ptrtoint casts. 40 if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && 41 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 42 if (CastInst *CI = dyn_cast<CastInst>(V)) 43 if ((CI->getOpcode() == Instruction::PtrToInt || 44 CI->getOpcode() == Instruction::IntToPtr) && 45 SE.getTypeSizeInBits(CI->getType()) == 46 SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 47 return CI->getOperand(0); 48 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 49 if ((CE->getOpcode() == Instruction::PtrToInt || 50 CE->getOpcode() == Instruction::IntToPtr) && 51 SE.getTypeSizeInBits(CE->getType()) == 52 SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 53 return CE->getOperand(0); 54 } 55 56 if (Constant *C = dyn_cast<Constant>(V)) 57 return ConstantExpr::getCast(Op, C, Ty); 58 59 if (Argument *A = dyn_cast<Argument>(V)) { 60 // Check to see if there is already a cast! 61 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 62 UI != E; ++UI) 63 if ((*UI)->getType() == Ty) 64 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 65 if (CI->getOpcode() == Op) { 66 // If the cast isn't the first instruction of the function, move it. 67 if (BasicBlock::iterator(CI) != 68 A->getParent()->getEntryBlock().begin()) { 69 // Recreate the cast at the beginning of the entry block. 70 // The old cast is left in place in case it is being used 71 // as an insert point. 72 Instruction *NewCI = 73 CastInst::Create(Op, V, Ty, "", 74 A->getParent()->getEntryBlock().begin()); 75 NewCI->takeName(CI); 76 CI->replaceAllUsesWith(NewCI); 77 return NewCI; 78 } 79 return CI; 80 } 81 82 Instruction *I = CastInst::Create(Op, V, Ty, V->getName(), 83 A->getParent()->getEntryBlock().begin()); 84 InsertedValues.insert(I); 85 return I; 86 } 87 88 Instruction *I = cast<Instruction>(V); 89 90 // Check to see if there is already a cast. If there is, use it. 91 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 92 UI != E; ++UI) { 93 if ((*UI)->getType() == Ty) 94 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 95 if (CI->getOpcode() == Op) { 96 BasicBlock::iterator It = I; ++It; 97 if (isa<InvokeInst>(I)) 98 It = cast<InvokeInst>(I)->getNormalDest()->begin(); 99 while (isa<PHINode>(It)) ++It; 100 if (It != BasicBlock::iterator(CI)) { 101 // Recreate the cast at the beginning of the entry block. 102 // The old cast is left in place in case it is being used 103 // as an insert point. 104 Instruction *NewCI = CastInst::Create(Op, V, Ty, "", It); 105 NewCI->takeName(CI); 106 CI->replaceAllUsesWith(NewCI); 107 return NewCI; 108 } 109 return CI; 110 } 111 } 112 BasicBlock::iterator IP = I; ++IP; 113 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 114 IP = II->getNormalDest()->begin(); 115 while (isa<PHINode>(IP)) ++IP; 116 Instruction *CI = CastInst::Create(Op, V, Ty, V->getName(), IP); 117 InsertedValues.insert(CI); 118 return CI; 119} 120 121/// InsertBinop - Insert the specified binary operator, doing a small amount 122/// of work to avoid inserting an obviously redundant operation. 123Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, 124 Value *LHS, Value *RHS) { 125 // Fold a binop with constant operands. 126 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 127 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 128 return ConstantExpr::get(Opcode, CLHS, CRHS); 129 130 // Do a quick scan to see if we have this binop nearby. If so, reuse it. 131 unsigned ScanLimit = 6; 132 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 133 // Scanning starts from the last instruction before the insertion point. 134 BasicBlock::iterator IP = Builder.GetInsertPoint(); 135 if (IP != BlockBegin) { 136 --IP; 137 for (; ScanLimit; --IP, --ScanLimit) { 138 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 139 IP->getOperand(1) == RHS) 140 return IP; 141 if (IP == BlockBegin) break; 142 } 143 } 144 145 // If we haven't found this binop, insert it. 146 Value *BO = Builder.CreateBinOp(Opcode, LHS, RHS, "tmp"); 147 InsertedValues.insert(BO); 148 return BO; 149} 150 151/// FactorOutConstant - Test if S is divisible by Factor, using signed 152/// division. If so, update S with Factor divided out and return true. 153/// S need not be evenly divisble if a reasonable remainder can be 154/// computed. 155/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 156/// unnecessary; in its place, just signed-divide Ops[i] by the scale and 157/// check to see if the divide was folded. 158static bool FactorOutConstant(const SCEV *&S, 159 const SCEV *&Remainder, 160 const SCEV *Factor, 161 ScalarEvolution &SE, 162 const TargetData *TD) { 163 // Everything is divisible by one. 164 if (Factor->isOne()) 165 return true; 166 167 // x/x == 1. 168 if (S == Factor) { 169 S = SE.getIntegerSCEV(1, S->getType()); 170 return true; 171 } 172 173 // For a Constant, check for a multiple of the given factor. 174 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 175 // 0/x == 0. 176 if (C->isZero()) 177 return true; 178 // Check for divisibility. 179 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) { 180 ConstantInt *CI = 181 ConstantInt::get(SE.getContext(), 182 C->getValue()->getValue().sdiv( 183 FC->getValue()->getValue())); 184 // If the quotient is zero and the remainder is non-zero, reject 185 // the value at this scale. It will be considered for subsequent 186 // smaller scales. 187 if (!CI->isZero()) { 188 const SCEV *Div = SE.getConstant(CI); 189 S = Div; 190 Remainder = 191 SE.getAddExpr(Remainder, 192 SE.getConstant(C->getValue()->getValue().srem( 193 FC->getValue()->getValue()))); 194 return true; 195 } 196 } 197 } 198 199 // In a Mul, check if there is a constant operand which is a multiple 200 // of the given factor. 201 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 202 if (TD) { 203 // With TargetData, the size is known. Check if there is a constant 204 // operand which is a multiple of the given factor. If so, we can 205 // factor it. 206 const SCEVConstant *FC = cast<SCEVConstant>(Factor); 207 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 208 if (!C->getValue()->getValue().srem(FC->getValue()->getValue())) { 209 const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands(); 210 SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(), 211 MOperands.end()); 212 NewMulOps[0] = 213 SE.getConstant(C->getValue()->getValue().sdiv( 214 FC->getValue()->getValue())); 215 S = SE.getMulExpr(NewMulOps); 216 return true; 217 } 218 } else { 219 // Without TargetData, check if Factor can be factored out of any of the 220 // Mul's operands. If so, we can just remove it. 221 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { 222 const SCEV *SOp = M->getOperand(i); 223 const SCEV *Remainder = SE.getIntegerSCEV(0, SOp->getType()); 224 if (FactorOutConstant(SOp, Remainder, Factor, SE, TD) && 225 Remainder->isZero()) { 226 const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands(); 227 SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(), 228 MOperands.end()); 229 NewMulOps[i] = SOp; 230 S = SE.getMulExpr(NewMulOps); 231 return true; 232 } 233 } 234 } 235 } 236 237 // In an AddRec, check if both start and step are divisible. 238 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 239 const SCEV *Step = A->getStepRecurrence(SE); 240 const SCEV *StepRem = SE.getIntegerSCEV(0, Step->getType()); 241 if (!FactorOutConstant(Step, StepRem, Factor, SE, TD)) 242 return false; 243 if (!StepRem->isZero()) 244 return false; 245 const SCEV *Start = A->getStart(); 246 if (!FactorOutConstant(Start, Remainder, Factor, SE, TD)) 247 return false; 248 S = SE.getAddRecExpr(Start, Step, A->getLoop()); 249 return true; 250 } 251 252 return false; 253} 254 255/// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs 256/// is the number of SCEVAddRecExprs present, which are kept at the end of 257/// the list. 258/// 259static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops, 260 const Type *Ty, 261 ScalarEvolution &SE) { 262 unsigned NumAddRecs = 0; 263 for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i) 264 ++NumAddRecs; 265 // Group Ops into non-addrecs and addrecs. 266 SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs); 267 SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end()); 268 // Let ScalarEvolution sort and simplify the non-addrecs list. 269 const SCEV *Sum = NoAddRecs.empty() ? 270 SE.getIntegerSCEV(0, Ty) : 271 SE.getAddExpr(NoAddRecs); 272 // If it returned an add, use the operands. Otherwise it simplified 273 // the sum into a single value, so just use that. 274 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum)) 275 Ops = Add->getOperands(); 276 else { 277 Ops.clear(); 278 if (!Sum->isZero()) 279 Ops.push_back(Sum); 280 } 281 // Then append the addrecs. 282 Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); 283} 284 285/// SplitAddRecs - Flatten a list of add operands, moving addrec start values 286/// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}. 287/// This helps expose more opportunities for folding parts of the expressions 288/// into GEP indices. 289/// 290static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, 291 const Type *Ty, 292 ScalarEvolution &SE) { 293 // Find the addrecs. 294 SmallVector<const SCEV *, 8> AddRecs; 295 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 296 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) { 297 const SCEV *Start = A->getStart(); 298 if (Start->isZero()) break; 299 const SCEV *Zero = SE.getIntegerSCEV(0, Ty); 300 AddRecs.push_back(SE.getAddRecExpr(Zero, 301 A->getStepRecurrence(SE), 302 A->getLoop())); 303 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { 304 Ops[i] = Zero; 305 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 306 e += Add->getNumOperands(); 307 } else { 308 Ops[i] = Start; 309 } 310 } 311 if (!AddRecs.empty()) { 312 // Add the addrecs onto the end of the list. 313 Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); 314 // Resort the operand list, moving any constants to the front. 315 SimplifyAddOperands(Ops, Ty, SE); 316 } 317} 318 319/// expandAddToGEP - Expand an addition expression with a pointer type into 320/// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps 321/// BasicAliasAnalysis and other passes analyze the result. See the rules 322/// for getelementptr vs. inttoptr in 323/// http://llvm.org/docs/LangRef.html#pointeraliasing 324/// for details. 325/// 326/// Design note: The correctness of using getelmeentptr here depends on 327/// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as 328/// they may introduce pointer arithmetic which may not be safely converted 329/// into getelementptr. 330/// 331/// Design note: It might seem desirable for this function to be more 332/// loop-aware. If some of the indices are loop-invariant while others 333/// aren't, it might seem desirable to emit multiple GEPs, keeping the 334/// loop-invariant portions of the overall computation outside the loop. 335/// However, there are a few reasons this is not done here. Hoisting simple 336/// arithmetic is a low-level optimization that often isn't very 337/// important until late in the optimization process. In fact, passes 338/// like InstructionCombining will combine GEPs, even if it means 339/// pushing loop-invariant computation down into loops, so even if the 340/// GEPs were split here, the work would quickly be undone. The 341/// LoopStrengthReduction pass, which is usually run quite late (and 342/// after the last InstructionCombining pass), takes care of hoisting 343/// loop-invariant portions of expressions, after considering what 344/// can be folded using target addressing modes. 345/// 346Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, 347 const SCEV *const *op_end, 348 const PointerType *PTy, 349 const Type *Ty, 350 Value *V) { 351 const Type *ElTy = PTy->getElementType(); 352 SmallVector<Value *, 4> GepIndices; 353 SmallVector<const SCEV *, 8> Ops(op_begin, op_end); 354 bool AnyNonZeroIndices = false; 355 356 // Split AddRecs up into parts as either of the parts may be usable 357 // without the other. 358 SplitAddRecs(Ops, Ty, SE); 359 360 // Decend down the pointer's type and attempt to convert the other 361 // operands into GEP indices, at each level. The first index in a GEP 362 // indexes into the array implied by the pointer operand; the rest of 363 // the indices index into the element or field type selected by the 364 // preceding index. 365 for (;;) { 366 const SCEV *ElSize = SE.getAllocSizeExpr(ElTy); 367 // If the scale size is not 0, attempt to factor out a scale for 368 // array indexing. 369 SmallVector<const SCEV *, 8> ScaledOps; 370 if (ElTy->isSized() && !ElSize->isZero()) { 371 SmallVector<const SCEV *, 8> NewOps; 372 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 373 const SCEV *Op = Ops[i]; 374 const SCEV *Remainder = SE.getIntegerSCEV(0, Ty); 375 if (FactorOutConstant(Op, Remainder, ElSize, SE, SE.TD)) { 376 // Op now has ElSize factored out. 377 ScaledOps.push_back(Op); 378 if (!Remainder->isZero()) 379 NewOps.push_back(Remainder); 380 AnyNonZeroIndices = true; 381 } else { 382 // The operand was not divisible, so add it to the list of operands 383 // we'll scan next iteration. 384 NewOps.push_back(Ops[i]); 385 } 386 } 387 // If we made any changes, update Ops. 388 if (!ScaledOps.empty()) { 389 Ops = NewOps; 390 SimplifyAddOperands(Ops, Ty, SE); 391 } 392 } 393 394 // Record the scaled array index for this level of the type. If 395 // we didn't find any operands that could be factored, tentatively 396 // assume that element zero was selected (since the zero offset 397 // would obviously be folded away). 398 Value *Scaled = ScaledOps.empty() ? 399 Constant::getNullValue(Ty) : 400 expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 401 GepIndices.push_back(Scaled); 402 403 // Collect struct field index operands. 404 while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 405 bool FoundFieldNo = false; 406 // An empty struct has no fields. 407 if (STy->getNumElements() == 0) break; 408 if (SE.TD) { 409 // With TargetData, field offsets are known. See if a constant offset 410 // falls within any of the struct fields. 411 if (Ops.empty()) break; 412 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 413 if (SE.getTypeSizeInBits(C->getType()) <= 64) { 414 const StructLayout &SL = *SE.TD->getStructLayout(STy); 415 uint64_t FullOffset = C->getValue()->getZExtValue(); 416 if (FullOffset < SL.getSizeInBytes()) { 417 unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 418 GepIndices.push_back( 419 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx)); 420 ElTy = STy->getTypeAtIndex(ElIdx); 421 Ops[0] = 422 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 423 AnyNonZeroIndices = true; 424 FoundFieldNo = true; 425 } 426 } 427 } else { 428 // Without TargetData, just check for a SCEVFieldOffsetExpr of the 429 // appropriate struct type. 430 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 431 if (const SCEVFieldOffsetExpr *FO = 432 dyn_cast<SCEVFieldOffsetExpr>(Ops[i])) 433 if (FO->getStructType() == STy) { 434 unsigned FieldNo = FO->getFieldNo(); 435 GepIndices.push_back( 436 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), 437 FieldNo)); 438 ElTy = STy->getTypeAtIndex(FieldNo); 439 Ops[i] = SE.getConstant(Ty, 0); 440 AnyNonZeroIndices = true; 441 FoundFieldNo = true; 442 break; 443 } 444 } 445 // If no struct field offsets were found, tentatively assume that 446 // field zero was selected (since the zero offset would obviously 447 // be folded away). 448 if (!FoundFieldNo) { 449 ElTy = STy->getTypeAtIndex(0u); 450 GepIndices.push_back( 451 Constant::getNullValue(Type::getInt32Ty(Ty->getContext()))); 452 } 453 } 454 455 if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) 456 ElTy = ATy->getElementType(); 457 else 458 break; 459 } 460 461 // If none of the operands were convertable to proper GEP indices, cast 462 // the base to i8* and do an ugly getelementptr with that. It's still 463 // better than ptrtoint+arithmetic+inttoptr at least. 464 if (!AnyNonZeroIndices) { 465 // Cast the base to i8*. 466 V = InsertNoopCastOfTo(V, 467 Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace())); 468 469 // Expand the operands for a plain byte offset. 470 Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 471 472 // Fold a GEP with constant operands. 473 if (Constant *CLHS = dyn_cast<Constant>(V)) 474 if (Constant *CRHS = dyn_cast<Constant>(Idx)) 475 return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 476 477 // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 478 unsigned ScanLimit = 6; 479 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 480 // Scanning starts from the last instruction before the insertion point. 481 BasicBlock::iterator IP = Builder.GetInsertPoint(); 482 if (IP != BlockBegin) { 483 --IP; 484 for (; ScanLimit; --IP, --ScanLimit) { 485 if (IP->getOpcode() == Instruction::GetElementPtr && 486 IP->getOperand(0) == V && IP->getOperand(1) == Idx) 487 return IP; 488 if (IP == BlockBegin) break; 489 } 490 } 491 492 // Emit a GEP. 493 Value *GEP = Builder.CreateGEP(V, Idx, "uglygep"); 494 InsertedValues.insert(GEP); 495 return GEP; 496 } 497 498 // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, 499 // because ScalarEvolution may have changed the address arithmetic to 500 // compute a value which is beyond the end of the allocated object. 501 Value *GEP = Builder.CreateGEP(V, 502 GepIndices.begin(), 503 GepIndices.end(), 504 "scevgep"); 505 Ops.push_back(SE.getUnknown(GEP)); 506 InsertedValues.insert(GEP); 507 return expand(SE.getAddExpr(Ops)); 508} 509 510Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 511 int NumOperands = S->getNumOperands(); 512 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 513 514 // Find the index of an operand to start with. Choose the operand with 515 // pointer type, if there is one, or the last operand otherwise. 516 int PIdx = 0; 517 for (; PIdx != NumOperands - 1; ++PIdx) 518 if (isa<PointerType>(S->getOperand(PIdx)->getType())) break; 519 520 // Expand code for the operand that we chose. 521 Value *V = expand(S->getOperand(PIdx)); 522 523 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 524 // comments on expandAddToGEP for details. 525 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 526 // Take the operand at PIdx out of the list. 527 const SmallVectorImpl<const SCEV *> &Ops = S->getOperands(); 528 SmallVector<const SCEV *, 8> NewOps; 529 NewOps.insert(NewOps.end(), Ops.begin(), Ops.begin() + PIdx); 530 NewOps.insert(NewOps.end(), Ops.begin() + PIdx + 1, Ops.end()); 531 // Make a GEP. 532 return expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, V); 533 } 534 535 // Otherwise, we'll expand the rest of the SCEVAddExpr as plain integer 536 // arithmetic. 537 V = InsertNoopCastOfTo(V, Ty); 538 539 // Emit a bunch of add instructions 540 for (int i = NumOperands-1; i >= 0; --i) { 541 if (i == PIdx) continue; 542 Value *W = expandCodeFor(S->getOperand(i), Ty); 543 V = InsertBinop(Instruction::Add, V, W); 544 } 545 return V; 546} 547 548Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 549 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 550 int FirstOp = 0; // Set if we should emit a subtract. 551 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 552 if (SC->getValue()->isAllOnesValue()) 553 FirstOp = 1; 554 555 int i = S->getNumOperands()-2; 556 Value *V = expandCodeFor(S->getOperand(i+1), Ty); 557 558 // Emit a bunch of multiply instructions 559 for (; i >= FirstOp; --i) { 560 Value *W = expandCodeFor(S->getOperand(i), Ty); 561 V = InsertBinop(Instruction::Mul, V, W); 562 } 563 564 // -1 * ... ---> 0 - ... 565 if (FirstOp == 1) 566 V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V); 567 return V; 568} 569 570Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 571 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 572 573 Value *LHS = expandCodeFor(S->getLHS(), Ty); 574 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 575 const APInt &RHS = SC->getValue()->getValue(); 576 if (RHS.isPowerOf2()) 577 return InsertBinop(Instruction::LShr, LHS, 578 ConstantInt::get(Ty, RHS.logBase2())); 579 } 580 581 Value *RHS = expandCodeFor(S->getRHS(), Ty); 582 return InsertBinop(Instruction::UDiv, LHS, RHS); 583} 584 585/// Move parts of Base into Rest to leave Base with the minimal 586/// expression that provides a pointer operand suitable for a 587/// GEP expansion. 588static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, 589 ScalarEvolution &SE) { 590 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 591 Base = A->getStart(); 592 Rest = SE.getAddExpr(Rest, 593 SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 594 A->getStepRecurrence(SE), 595 A->getLoop())); 596 } 597 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 598 Base = A->getOperand(A->getNumOperands()-1); 599 SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end()); 600 NewAddOps.back() = Rest; 601 Rest = SE.getAddExpr(NewAddOps); 602 ExposePointerBase(Base, Rest, SE); 603 } 604} 605 606Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 607 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 608 const Loop *L = S->getLoop(); 609 610 // First check for an existing canonical IV in a suitable type. 611 PHINode *CanonicalIV = 0; 612 if (PHINode *PN = L->getCanonicalInductionVariable()) 613 if (SE.isSCEVable(PN->getType()) && 614 isa<IntegerType>(SE.getEffectiveSCEVType(PN->getType())) && 615 SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 616 CanonicalIV = PN; 617 618 // Rewrite an AddRec in terms of the canonical induction variable, if 619 // its type is more narrow. 620 if (CanonicalIV && 621 SE.getTypeSizeInBits(CanonicalIV->getType()) > 622 SE.getTypeSizeInBits(Ty)) { 623 const SmallVectorImpl<const SCEV *> &Ops = S->getOperands(); 624 SmallVector<const SCEV *, 4> NewOps(Ops.size()); 625 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 626 NewOps[i] = SE.getAnyExtendExpr(Ops[i], CanonicalIV->getType()); 627 Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop())); 628 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 629 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 630 BasicBlock::iterator NewInsertPt = 631 next(BasicBlock::iterator(cast<Instruction>(V))); 632 while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; 633 V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, 634 NewInsertPt); 635 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 636 return V; 637 } 638 639 // {X,+,F} --> X + {0,+,F} 640 if (!S->getStart()->isZero()) { 641 const SmallVectorImpl<const SCEV *> &SOperands = S->getOperands(); 642 SmallVector<const SCEV *, 4> NewOps(SOperands.begin(), SOperands.end()); 643 NewOps[0] = SE.getIntegerSCEV(0, Ty); 644 const SCEV *Rest = SE.getAddRecExpr(NewOps, L); 645 646 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 647 // comments on expandAddToGEP for details. 648 const SCEV *Base = S->getStart(); 649 const SCEV *RestArray[1] = { Rest }; 650 // Dig into the expression to find the pointer base for a GEP. 651 ExposePointerBase(Base, RestArray[0], SE); 652 // If we found a pointer, expand the AddRec with a GEP. 653 if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 654 // Make sure the Base isn't something exotic, such as a multiplied 655 // or divided pointer value. In those cases, the result type isn't 656 // actually a pointer type. 657 if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 658 Value *StartV = expand(Base); 659 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 660 return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 661 } 662 } 663 664 // Just do a normal add. Pre-expand the operands to suppress folding. 665 return expand(SE.getAddExpr(SE.getUnknown(expand(S->getStart())), 666 SE.getUnknown(expand(Rest)))); 667 } 668 669 // {0,+,1} --> Insert a canonical induction variable into the loop! 670 if (S->isAffine() && 671 S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 672 // If there's a canonical IV, just use it. 673 if (CanonicalIV) { 674 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 675 "IVs with types different from the canonical IV should " 676 "already have been handled!"); 677 return CanonicalIV; 678 } 679 680 // Create and insert the PHI node for the induction variable in the 681 // specified loop. 682 BasicBlock *Header = L->getHeader(); 683 PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 684 InsertedValues.insert(PN); 685 686 Constant *One = ConstantInt::get(Ty, 1); 687 for (pred_iterator HPI = pred_begin(Header), HPE = pred_end(Header); 688 HPI != HPE; ++HPI) 689 if (L->contains(*HPI)) { 690 // Insert a unit add instruction right before the terminator corresponding 691 // to the back-edge. 692 Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 693 (*HPI)->getTerminator()); 694 InsertedValues.insert(Add); 695 PN->addIncoming(Add, *HPI); 696 } else { 697 PN->addIncoming(Constant::getNullValue(Ty), *HPI); 698 } 699 } 700 701 // {0,+,F} --> {0,+,1} * F 702 // Get the canonical induction variable I for this loop. 703 Value *I = CanonicalIV ? 704 CanonicalIV : 705 getOrInsertCanonicalInductionVariable(L, Ty); 706 707 // If this is a simple linear addrec, emit it now as a special case. 708 if (S->isAffine()) // {0,+,F} --> i*F 709 return 710 expand(SE.getTruncateOrNoop( 711 SE.getMulExpr(SE.getUnknown(I), 712 SE.getNoopOrAnyExtend(S->getOperand(1), 713 I->getType())), 714 Ty)); 715 716 // If this is a chain of recurrences, turn it into a closed form, using the 717 // folders, then expandCodeFor the closed form. This allows the folders to 718 // simplify the expression without having to build a bunch of special code 719 // into this folder. 720 const SCEV *IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 721 722 // Promote S up to the canonical IV type, if the cast is foldable. 723 const SCEV *NewS = S; 724 const SCEV *Ext = SE.getNoopOrAnyExtend(S, I->getType()); 725 if (isa<SCEVAddRecExpr>(Ext)) 726 NewS = Ext; 727 728 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 729 //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 730 731 // Truncate the result down to the original type, if needed. 732 const SCEV *T = SE.getTruncateOrNoop(V, Ty); 733 return expand(T); 734} 735 736Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 737 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 738 Value *V = expandCodeFor(S->getOperand(), 739 SE.getEffectiveSCEVType(S->getOperand()->getType())); 740 Value *I = Builder.CreateTrunc(V, Ty, "tmp"); 741 InsertedValues.insert(I); 742 return I; 743} 744 745Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 746 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 747 Value *V = expandCodeFor(S->getOperand(), 748 SE.getEffectiveSCEVType(S->getOperand()->getType())); 749 Value *I = Builder.CreateZExt(V, Ty, "tmp"); 750 InsertedValues.insert(I); 751 return I; 752} 753 754Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 755 const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 756 Value *V = expandCodeFor(S->getOperand(), 757 SE.getEffectiveSCEVType(S->getOperand()->getType())); 758 Value *I = Builder.CreateSExt(V, Ty, "tmp"); 759 InsertedValues.insert(I); 760 return I; 761} 762 763Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 764 Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 765 const Type *Ty = LHS->getType(); 766 for (int i = S->getNumOperands()-2; i >= 0; --i) { 767 // In the case of mixed integer and pointer types, do the 768 // rest of the comparisons as integer. 769 if (S->getOperand(i)->getType() != Ty) { 770 Ty = SE.getEffectiveSCEVType(Ty); 771 LHS = InsertNoopCastOfTo(LHS, Ty); 772 } 773 Value *RHS = expandCodeFor(S->getOperand(i), Ty); 774 Value *ICmp = Builder.CreateICmpSGT(LHS, RHS, "tmp"); 775 InsertedValues.insert(ICmp); 776 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax"); 777 InsertedValues.insert(Sel); 778 LHS = Sel; 779 } 780 // In the case of mixed integer and pointer types, cast the 781 // final result back to the pointer type. 782 if (LHS->getType() != S->getType()) 783 LHS = InsertNoopCastOfTo(LHS, S->getType()); 784 return LHS; 785} 786 787Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 788 Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 789 const Type *Ty = LHS->getType(); 790 for (int i = S->getNumOperands()-2; i >= 0; --i) { 791 // In the case of mixed integer and pointer types, do the 792 // rest of the comparisons as integer. 793 if (S->getOperand(i)->getType() != Ty) { 794 Ty = SE.getEffectiveSCEVType(Ty); 795 LHS = InsertNoopCastOfTo(LHS, Ty); 796 } 797 Value *RHS = expandCodeFor(S->getOperand(i), Ty); 798 Value *ICmp = Builder.CreateICmpUGT(LHS, RHS, "tmp"); 799 InsertedValues.insert(ICmp); 800 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax"); 801 InsertedValues.insert(Sel); 802 LHS = Sel; 803 } 804 // In the case of mixed integer and pointer types, cast the 805 // final result back to the pointer type. 806 if (LHS->getType() != S->getType()) 807 LHS = InsertNoopCastOfTo(LHS, S->getType()); 808 return LHS; 809} 810 811Value *SCEVExpander::visitFieldOffsetExpr(const SCEVFieldOffsetExpr *S) { 812 return ConstantExpr::getOffsetOf(S->getStructType(), S->getFieldNo()); 813} 814 815Value *SCEVExpander::visitAllocSizeExpr(const SCEVAllocSizeExpr *S) { 816 return ConstantExpr::getSizeOf(S->getAllocType()); 817} 818 819Value *SCEVExpander::expandCodeFor(const SCEV *SH, const Type *Ty) { 820 // Expand the code for this SCEV. 821 Value *V = expand(SH); 822 if (Ty) { 823 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 824 "non-trivial casts should be done with the SCEVs directly!"); 825 V = InsertNoopCastOfTo(V, Ty); 826 } 827 return V; 828} 829 830Value *SCEVExpander::expand(const SCEV *S) { 831 // Compute an insertion point for this SCEV object. Hoist the instructions 832 // as far out in the loop nest as possible. 833 Instruction *InsertPt = Builder.GetInsertPoint(); 834 for (Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock()); ; 835 L = L->getParentLoop()) 836 if (S->isLoopInvariant(L)) { 837 if (!L) break; 838 if (BasicBlock *Preheader = L->getLoopPreheader()) 839 InsertPt = Preheader->getTerminator(); 840 } else { 841 // If the SCEV is computable at this level, insert it into the header 842 // after the PHIs (and after any other instructions that we've inserted 843 // there) so that it is guaranteed to dominate any user inside the loop. 844 if (L && S->hasComputableLoopEvolution(L)) 845 InsertPt = L->getHeader()->getFirstNonPHI(); 846 while (isInsertedInstruction(InsertPt)) 847 InsertPt = next(BasicBlock::iterator(InsertPt)); 848 break; 849 } 850 851 // Check to see if we already expanded this here. 852 std::map<std::pair<const SCEV *, Instruction *>, 853 AssertingVH<Value> >::iterator I = 854 InsertedExpressions.find(std::make_pair(S, InsertPt)); 855 if (I != InsertedExpressions.end()) 856 return I->second; 857 858 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 859 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 860 Builder.SetInsertPoint(InsertPt->getParent(), InsertPt); 861 862 // Expand the expression into instructions. 863 Value *V = visit(S); 864 865 // Remember the expanded value for this SCEV at this location. 866 InsertedExpressions[std::make_pair(S, InsertPt)] = V; 867 868 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 869 return V; 870} 871 872/// getOrInsertCanonicalInductionVariable - This method returns the 873/// canonical induction variable of the specified type for the specified 874/// loop (inserting one if there is none). A canonical induction variable 875/// starts at zero and steps by one on each iteration. 876Value * 877SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 878 const Type *Ty) { 879 assert(Ty->isInteger() && "Can only insert integer induction variables!"); 880 const SCEV *H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), 881 SE.getIntegerSCEV(1, Ty), L); 882 BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 883 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 884 Value *V = expandCodeFor(H, 0, L->getHeader()->begin()); 885 if (SaveInsertBB) 886 Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 887 return V; 888} 889