1 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains the implementation of the scalar evolution expander, 10 // which is used to generate the code corresponding to a given scalar evolution 11 // expression. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/ADT/SmallSet.h" 18 #include "llvm/Analysis/InstructionSimplify.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/TargetTransformInfo.h" 21 #include "llvm/IR/DataLayout.h" 22 #include "llvm/IR/Dominators.h" 23 #include "llvm/IR/IntrinsicInst.h" 24 #include "llvm/IR/LLVMContext.h" 25 #include "llvm/IR/Module.h" 26 #include "llvm/IR/PatternMatch.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include "llvm/Transforms/Utils/LoopUtils.h" 31 32 using namespace llvm; 33 34 cl::opt<unsigned> llvm::SCEVCheapExpansionBudget( 35 "scev-cheap-expansion-budget", cl::Hidden, cl::init(4), 36 cl::desc("When performing SCEV expansion only if it is cheap to do, this " 37 "controls the budget that is considered cheap (default = 4)")); 38 39 using namespace PatternMatch; 40 41 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP, 42 /// reusing an existing cast if a suitable one (= dominating IP) exists, or 43 /// creating a new one. 44 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, 45 Instruction::CastOps Op, 46 BasicBlock::iterator IP) { 47 // This function must be called with the builder having a valid insertion 48 // point. It doesn't need to be the actual IP where the uses of the returned 49 // cast will be added, but it must dominate such IP. 50 // We use this precondition to produce a cast that will dominate all its 51 // uses. In particular, this is crucial for the case where the builder's 52 // insertion point *is* the point where we were asked to put the cast. 53 // Since we don't know the builder's insertion point is actually 54 // where the uses will be added (only that it dominates it), we are 55 // not allowed to move it. 56 BasicBlock::iterator BIP = Builder.GetInsertPoint(); 57 58 Instruction *Ret = nullptr; 59 60 // Check to see if there is already a cast! 61 for (User *U : V->users()) { 62 if (U->getType() != Ty) 63 continue; 64 CastInst *CI = dyn_cast<CastInst>(U); 65 if (!CI || CI->getOpcode() != Op) 66 continue; 67 68 // Found a suitable cast that is at IP or comes before IP. Use it. Note that 69 // the cast must also properly dominate the Builder's insertion point. 70 if (IP->getParent() == CI->getParent() && &*BIP != CI && 71 (&*IP == CI || CI->comesBefore(&*IP))) { 72 Ret = CI; 73 break; 74 } 75 } 76 77 // Create a new cast. 78 if (!Ret) { 79 Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP); 80 rememberInstruction(Ret); 81 } 82 83 // We assert at the end of the function since IP might point to an 84 // instruction with different dominance properties than a cast 85 // (an invoke for example) and not dominate BIP (but the cast does). 86 assert(SE.DT.dominates(Ret, &*BIP)); 87 88 return Ret; 89 } 90 91 BasicBlock::iterator 92 SCEVExpander::findInsertPointAfter(Instruction *I, Instruction *MustDominate) { 93 BasicBlock::iterator IP = ++I->getIterator(); 94 if (auto *II = dyn_cast<InvokeInst>(I)) 95 IP = II->getNormalDest()->begin(); 96 97 while (isa<PHINode>(IP)) 98 ++IP; 99 100 if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) { 101 ++IP; 102 } else if (isa<CatchSwitchInst>(IP)) { 103 IP = MustDominate->getParent()->getFirstInsertionPt(); 104 } else { 105 assert(!IP->isEHPad() && "unexpected eh pad!"); 106 } 107 108 // Adjust insert point to be after instructions inserted by the expander, so 109 // we can re-use already inserted instructions. Avoid skipping past the 110 // original \p MustDominate, in case it is an inserted instruction. 111 while (isInsertedInstruction(&*IP) && &*IP != MustDominate) 112 ++IP; 113 114 return IP; 115 } 116 117 /// InsertNoopCastOfTo - Insert a cast of V to the specified type, 118 /// which must be possible with a noop cast, doing what we can to share 119 /// the casts. 120 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) { 121 Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 122 assert((Op == Instruction::BitCast || 123 Op == Instruction::PtrToInt || 124 Op == Instruction::IntToPtr) && 125 "InsertNoopCastOfTo cannot perform non-noop casts!"); 126 assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 127 "InsertNoopCastOfTo cannot change sizes!"); 128 129 // inttoptr only works for integral pointers. For non-integral pointers, we 130 // can create a GEP on i8* null with the integral value as index. Note that 131 // it is safe to use GEP of null instead of inttoptr here, because only 132 // expressions already based on a GEP of null should be converted to pointers 133 // during expansion. 134 if (Op == Instruction::IntToPtr) { 135 auto *PtrTy = cast<PointerType>(Ty); 136 if (DL.isNonIntegralPointerType(PtrTy)) { 137 auto *Int8PtrTy = Builder.getInt8PtrTy(PtrTy->getAddressSpace()); 138 assert(DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && 139 "alloc size of i8 must by 1 byte for the GEP to be correct"); 140 auto *GEP = Builder.CreateGEP( 141 Builder.getInt8Ty(), Constant::getNullValue(Int8PtrTy), V, "uglygep"); 142 return Builder.CreateBitCast(GEP, Ty); 143 } 144 } 145 // Short-circuit unnecessary bitcasts. 146 if (Op == Instruction::BitCast) { 147 if (V->getType() == Ty) 148 return V; 149 if (CastInst *CI = dyn_cast<CastInst>(V)) { 150 if (CI->getOperand(0)->getType() == Ty) 151 return CI->getOperand(0); 152 } 153 } 154 // Short-circuit unnecessary inttoptr<->ptrtoint casts. 155 if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && 156 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 157 if (CastInst *CI = dyn_cast<CastInst>(V)) 158 if ((CI->getOpcode() == Instruction::PtrToInt || 159 CI->getOpcode() == Instruction::IntToPtr) && 160 SE.getTypeSizeInBits(CI->getType()) == 161 SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 162 return CI->getOperand(0); 163 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 164 if ((CE->getOpcode() == Instruction::PtrToInt || 165 CE->getOpcode() == Instruction::IntToPtr) && 166 SE.getTypeSizeInBits(CE->getType()) == 167 SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 168 return CE->getOperand(0); 169 } 170 171 // Fold a cast of a constant. 172 if (Constant *C = dyn_cast<Constant>(V)) 173 return ConstantExpr::getCast(Op, C, Ty); 174 175 // Cast the argument at the beginning of the entry block, after 176 // any bitcasts of other arguments. 177 if (Argument *A = dyn_cast<Argument>(V)) { 178 BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin(); 179 while ((isa<BitCastInst>(IP) && 180 isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) && 181 cast<BitCastInst>(IP)->getOperand(0) != A) || 182 isa<DbgInfoIntrinsic>(IP)) 183 ++IP; 184 return ReuseOrCreateCast(A, Ty, Op, IP); 185 } 186 187 // Cast the instruction immediately after the instruction. 188 Instruction *I = cast<Instruction>(V); 189 BasicBlock::iterator IP = findInsertPointAfter(I, &*Builder.GetInsertPoint()); 190 return ReuseOrCreateCast(I, Ty, Op, IP); 191 } 192 193 /// InsertBinop - Insert the specified binary operator, doing a small amount 194 /// of work to avoid inserting an obviously redundant operation, and hoisting 195 /// to an outer loop when the opportunity is there and it is safe. 196 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, 197 Value *LHS, Value *RHS, 198 SCEV::NoWrapFlags Flags, bool IsSafeToHoist) { 199 // Fold a binop with constant operands. 200 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 201 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 202 return ConstantExpr::get(Opcode, CLHS, CRHS); 203 204 // Do a quick scan to see if we have this binop nearby. If so, reuse it. 205 unsigned ScanLimit = 6; 206 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 207 // Scanning starts from the last instruction before the insertion point. 208 BasicBlock::iterator IP = Builder.GetInsertPoint(); 209 if (IP != BlockBegin) { 210 --IP; 211 for (; ScanLimit; --IP, --ScanLimit) { 212 // Don't count dbg.value against the ScanLimit, to avoid perturbing the 213 // generated code. 214 if (isa<DbgInfoIntrinsic>(IP)) 215 ScanLimit++; 216 217 auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) { 218 // Ensure that no-wrap flags match. 219 if (isa<OverflowingBinaryOperator>(I)) { 220 if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW)) 221 return true; 222 if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW)) 223 return true; 224 } 225 // Conservatively, do not use any instruction which has any of exact 226 // flags installed. 227 if (isa<PossiblyExactOperator>(I) && I->isExact()) 228 return true; 229 return false; 230 }; 231 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 232 IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP)) 233 return &*IP; 234 if (IP == BlockBegin) break; 235 } 236 } 237 238 // Save the original insertion point so we can restore it when we're done. 239 DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc(); 240 SCEVInsertPointGuard Guard(Builder, this); 241 242 if (IsSafeToHoist) { 243 // Move the insertion point out of as many loops as we can. 244 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { 245 if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break; 246 BasicBlock *Preheader = L->getLoopPreheader(); 247 if (!Preheader) break; 248 249 // Ok, move up a level. 250 Builder.SetInsertPoint(Preheader->getTerminator()); 251 } 252 } 253 254 // If we haven't found this binop, insert it. 255 Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS)); 256 BO->setDebugLoc(Loc); 257 if (Flags & SCEV::FlagNUW) 258 BO->setHasNoUnsignedWrap(); 259 if (Flags & SCEV::FlagNSW) 260 BO->setHasNoSignedWrap(); 261 262 return BO; 263 } 264 265 /// FactorOutConstant - Test if S is divisible by Factor, using signed 266 /// division. If so, update S with Factor divided out and return true. 267 /// S need not be evenly divisible if a reasonable remainder can be 268 /// computed. 269 static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder, 270 const SCEV *Factor, ScalarEvolution &SE, 271 const DataLayout &DL) { 272 // Everything is divisible by one. 273 if (Factor->isOne()) 274 return true; 275 276 // x/x == 1. 277 if (S == Factor) { 278 S = SE.getConstant(S->getType(), 1); 279 return true; 280 } 281 282 // For a Constant, check for a multiple of the given factor. 283 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 284 // 0/x == 0. 285 if (C->isZero()) 286 return true; 287 // Check for divisibility. 288 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) { 289 ConstantInt *CI = 290 ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt())); 291 // If the quotient is zero and the remainder is non-zero, reject 292 // the value at this scale. It will be considered for subsequent 293 // smaller scales. 294 if (!CI->isZero()) { 295 const SCEV *Div = SE.getConstant(CI); 296 S = Div; 297 Remainder = SE.getAddExpr( 298 Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt()))); 299 return true; 300 } 301 } 302 } 303 304 // In a Mul, check if there is a constant operand which is a multiple 305 // of the given factor. 306 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 307 // Size is known, check if there is a constant operand which is a multiple 308 // of the given factor. If so, we can factor it. 309 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) 310 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 311 if (!C->getAPInt().srem(FC->getAPInt())) { 312 SmallVector<const SCEV *, 4> NewMulOps(M->operands()); 313 NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt())); 314 S = SE.getMulExpr(NewMulOps); 315 return true; 316 } 317 } 318 319 // In an AddRec, check if both start and step are divisible. 320 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 321 const SCEV *Step = A->getStepRecurrence(SE); 322 const SCEV *StepRem = SE.getConstant(Step->getType(), 0); 323 if (!FactorOutConstant(Step, StepRem, Factor, SE, DL)) 324 return false; 325 if (!StepRem->isZero()) 326 return false; 327 const SCEV *Start = A->getStart(); 328 if (!FactorOutConstant(Start, Remainder, Factor, SE, DL)) 329 return false; 330 S = SE.getAddRecExpr(Start, Step, A->getLoop(), 331 A->getNoWrapFlags(SCEV::FlagNW)); 332 return true; 333 } 334 335 return false; 336 } 337 338 /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs 339 /// is the number of SCEVAddRecExprs present, which are kept at the end of 340 /// the list. 341 /// 342 static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops, 343 Type *Ty, 344 ScalarEvolution &SE) { 345 unsigned NumAddRecs = 0; 346 for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i) 347 ++NumAddRecs; 348 // Group Ops into non-addrecs and addrecs. 349 SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs); 350 SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end()); 351 // Let ScalarEvolution sort and simplify the non-addrecs list. 352 const SCEV *Sum = NoAddRecs.empty() ? 353 SE.getConstant(Ty, 0) : 354 SE.getAddExpr(NoAddRecs); 355 // If it returned an add, use the operands. Otherwise it simplified 356 // the sum into a single value, so just use that. 357 Ops.clear(); 358 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum)) 359 Ops.append(Add->op_begin(), Add->op_end()); 360 else if (!Sum->isZero()) 361 Ops.push_back(Sum); 362 // Then append the addrecs. 363 Ops.append(AddRecs.begin(), AddRecs.end()); 364 } 365 366 /// SplitAddRecs - Flatten a list of add operands, moving addrec start values 367 /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}. 368 /// This helps expose more opportunities for folding parts of the expressions 369 /// into GEP indices. 370 /// 371 static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, 372 Type *Ty, 373 ScalarEvolution &SE) { 374 // Find the addrecs. 375 SmallVector<const SCEV *, 8> AddRecs; 376 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 377 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) { 378 const SCEV *Start = A->getStart(); 379 if (Start->isZero()) break; 380 const SCEV *Zero = SE.getConstant(Ty, 0); 381 AddRecs.push_back(SE.getAddRecExpr(Zero, 382 A->getStepRecurrence(SE), 383 A->getLoop(), 384 A->getNoWrapFlags(SCEV::FlagNW))); 385 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { 386 Ops[i] = Zero; 387 Ops.append(Add->op_begin(), Add->op_end()); 388 e += Add->getNumOperands(); 389 } else { 390 Ops[i] = Start; 391 } 392 } 393 if (!AddRecs.empty()) { 394 // Add the addrecs onto the end of the list. 395 Ops.append(AddRecs.begin(), AddRecs.end()); 396 // Resort the operand list, moving any constants to the front. 397 SimplifyAddOperands(Ops, Ty, SE); 398 } 399 } 400 401 /// expandAddToGEP - Expand an addition expression with a pointer type into 402 /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps 403 /// BasicAliasAnalysis and other passes analyze the result. See the rules 404 /// for getelementptr vs. inttoptr in 405 /// http://llvm.org/docs/LangRef.html#pointeraliasing 406 /// for details. 407 /// 408 /// Design note: The correctness of using getelementptr here depends on 409 /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as 410 /// they may introduce pointer arithmetic which may not be safely converted 411 /// into getelementptr. 412 /// 413 /// Design note: It might seem desirable for this function to be more 414 /// loop-aware. If some of the indices are loop-invariant while others 415 /// aren't, it might seem desirable to emit multiple GEPs, keeping the 416 /// loop-invariant portions of the overall computation outside the loop. 417 /// However, there are a few reasons this is not done here. Hoisting simple 418 /// arithmetic is a low-level optimization that often isn't very 419 /// important until late in the optimization process. In fact, passes 420 /// like InstructionCombining will combine GEPs, even if it means 421 /// pushing loop-invariant computation down into loops, so even if the 422 /// GEPs were split here, the work would quickly be undone. The 423 /// LoopStrengthReduction pass, which is usually run quite late (and 424 /// after the last InstructionCombining pass), takes care of hoisting 425 /// loop-invariant portions of expressions, after considering what 426 /// can be folded using target addressing modes. 427 /// 428 Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, 429 const SCEV *const *op_end, 430 PointerType *PTy, 431 Type *Ty, 432 Value *V) { 433 Type *OriginalElTy = PTy->getElementType(); 434 Type *ElTy = OriginalElTy; 435 SmallVector<Value *, 4> GepIndices; 436 SmallVector<const SCEV *, 8> Ops(op_begin, op_end); 437 bool AnyNonZeroIndices = false; 438 439 // Split AddRecs up into parts as either of the parts may be usable 440 // without the other. 441 SplitAddRecs(Ops, Ty, SE); 442 443 Type *IntIdxTy = DL.getIndexType(PTy); 444 445 // Descend down the pointer's type and attempt to convert the other 446 // operands into GEP indices, at each level. The first index in a GEP 447 // indexes into the array implied by the pointer operand; the rest of 448 // the indices index into the element or field type selected by the 449 // preceding index. 450 for (;;) { 451 // If the scale size is not 0, attempt to factor out a scale for 452 // array indexing. 453 SmallVector<const SCEV *, 8> ScaledOps; 454 if (ElTy->isSized()) { 455 const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy); 456 if (!ElSize->isZero()) { 457 SmallVector<const SCEV *, 8> NewOps; 458 for (const SCEV *Op : Ops) { 459 const SCEV *Remainder = SE.getConstant(Ty, 0); 460 if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) { 461 // Op now has ElSize factored out. 462 ScaledOps.push_back(Op); 463 if (!Remainder->isZero()) 464 NewOps.push_back(Remainder); 465 AnyNonZeroIndices = true; 466 } else { 467 // The operand was not divisible, so add it to the list of operands 468 // we'll scan next iteration. 469 NewOps.push_back(Op); 470 } 471 } 472 // If we made any changes, update Ops. 473 if (!ScaledOps.empty()) { 474 Ops = NewOps; 475 SimplifyAddOperands(Ops, Ty, SE); 476 } 477 } 478 } 479 480 // Record the scaled array index for this level of the type. If 481 // we didn't find any operands that could be factored, tentatively 482 // assume that element zero was selected (since the zero offset 483 // would obviously be folded away). 484 Value *Scaled = 485 ScaledOps.empty() 486 ? Constant::getNullValue(Ty) 487 : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty, false); 488 GepIndices.push_back(Scaled); 489 490 // Collect struct field index operands. 491 while (StructType *STy = dyn_cast<StructType>(ElTy)) { 492 bool FoundFieldNo = false; 493 // An empty struct has no fields. 494 if (STy->getNumElements() == 0) break; 495 // Field offsets are known. See if a constant offset falls within any of 496 // the struct fields. 497 if (Ops.empty()) 498 break; 499 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 500 if (SE.getTypeSizeInBits(C->getType()) <= 64) { 501 const StructLayout &SL = *DL.getStructLayout(STy); 502 uint64_t FullOffset = C->getValue()->getZExtValue(); 503 if (FullOffset < SL.getSizeInBytes()) { 504 unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 505 GepIndices.push_back( 506 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx)); 507 ElTy = STy->getTypeAtIndex(ElIdx); 508 Ops[0] = 509 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 510 AnyNonZeroIndices = true; 511 FoundFieldNo = true; 512 } 513 } 514 // If no struct field offsets were found, tentatively assume that 515 // field zero was selected (since the zero offset would obviously 516 // be folded away). 517 if (!FoundFieldNo) { 518 ElTy = STy->getTypeAtIndex(0u); 519 GepIndices.push_back( 520 Constant::getNullValue(Type::getInt32Ty(Ty->getContext()))); 521 } 522 } 523 524 if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) 525 ElTy = ATy->getElementType(); 526 else 527 // FIXME: Handle VectorType. 528 // E.g., If ElTy is scalable vector, then ElSize is not a compile-time 529 // constant, therefore can not be factored out. The generated IR is less 530 // ideal with base 'V' cast to i8* and do ugly getelementptr over that. 531 break; 532 } 533 534 // If none of the operands were convertible to proper GEP indices, cast 535 // the base to i8* and do an ugly getelementptr with that. It's still 536 // better than ptrtoint+arithmetic+inttoptr at least. 537 if (!AnyNonZeroIndices) { 538 // Cast the base to i8*. 539 V = InsertNoopCastOfTo(V, 540 Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace())); 541 542 assert(!isa<Instruction>(V) || 543 SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint())); 544 545 // Expand the operands for a plain byte offset. 546 Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty, false); 547 548 // Fold a GEP with constant operands. 549 if (Constant *CLHS = dyn_cast<Constant>(V)) 550 if (Constant *CRHS = dyn_cast<Constant>(Idx)) 551 return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()), 552 CLHS, CRHS); 553 554 // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 555 unsigned ScanLimit = 6; 556 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 557 // Scanning starts from the last instruction before the insertion point. 558 BasicBlock::iterator IP = Builder.GetInsertPoint(); 559 if (IP != BlockBegin) { 560 --IP; 561 for (; ScanLimit; --IP, --ScanLimit) { 562 // Don't count dbg.value against the ScanLimit, to avoid perturbing the 563 // generated code. 564 if (isa<DbgInfoIntrinsic>(IP)) 565 ScanLimit++; 566 if (IP->getOpcode() == Instruction::GetElementPtr && 567 IP->getOperand(0) == V && IP->getOperand(1) == Idx) 568 return &*IP; 569 if (IP == BlockBegin) break; 570 } 571 } 572 573 // Save the original insertion point so we can restore it when we're done. 574 SCEVInsertPointGuard Guard(Builder, this); 575 576 // Move the insertion point out of as many loops as we can. 577 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { 578 if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break; 579 BasicBlock *Preheader = L->getLoopPreheader(); 580 if (!Preheader) break; 581 582 // Ok, move up a level. 583 Builder.SetInsertPoint(Preheader->getTerminator()); 584 } 585 586 // Emit a GEP. 587 return Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep"); 588 } 589 590 { 591 SCEVInsertPointGuard Guard(Builder, this); 592 593 // Move the insertion point out of as many loops as we can. 594 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { 595 if (!L->isLoopInvariant(V)) break; 596 597 bool AnyIndexNotLoopInvariant = any_of( 598 GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); }); 599 600 if (AnyIndexNotLoopInvariant) 601 break; 602 603 BasicBlock *Preheader = L->getLoopPreheader(); 604 if (!Preheader) break; 605 606 // Ok, move up a level. 607 Builder.SetInsertPoint(Preheader->getTerminator()); 608 } 609 610 // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, 611 // because ScalarEvolution may have changed the address arithmetic to 612 // compute a value which is beyond the end of the allocated object. 613 Value *Casted = V; 614 if (V->getType() != PTy) 615 Casted = InsertNoopCastOfTo(Casted, PTy); 616 Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep"); 617 Ops.push_back(SE.getUnknown(GEP)); 618 } 619 620 return expand(SE.getAddExpr(Ops)); 621 } 622 623 Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, 624 Value *V) { 625 const SCEV *const Ops[1] = {Op}; 626 return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V); 627 } 628 629 /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for 630 /// SCEV expansion. If they are nested, this is the most nested. If they are 631 /// neighboring, pick the later. 632 static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B, 633 DominatorTree &DT) { 634 if (!A) return B; 635 if (!B) return A; 636 if (A->contains(B)) return B; 637 if (B->contains(A)) return A; 638 if (DT.dominates(A->getHeader(), B->getHeader())) return B; 639 if (DT.dominates(B->getHeader(), A->getHeader())) return A; 640 return A; // Arbitrarily break the tie. 641 } 642 643 /// getRelevantLoop - Get the most relevant loop associated with the given 644 /// expression, according to PickMostRelevantLoop. 645 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) { 646 // Test whether we've already computed the most relevant loop for this SCEV. 647 auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr)); 648 if (!Pair.second) 649 return Pair.first->second; 650 651 if (isa<SCEVConstant>(S)) 652 // A constant has no relevant loops. 653 return nullptr; 654 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 655 if (const Instruction *I = dyn_cast<Instruction>(U->getValue())) 656 return Pair.first->second = SE.LI.getLoopFor(I->getParent()); 657 // A non-instruction has no relevant loops. 658 return nullptr; 659 } 660 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) { 661 const Loop *L = nullptr; 662 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 663 L = AR->getLoop(); 664 for (const SCEV *Op : N->operands()) 665 L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT); 666 return RelevantLoops[N] = L; 667 } 668 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) { 669 const Loop *Result = getRelevantLoop(C->getOperand()); 670 return RelevantLoops[C] = Result; 671 } 672 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 673 const Loop *Result = PickMostRelevantLoop( 674 getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT); 675 return RelevantLoops[D] = Result; 676 } 677 llvm_unreachable("Unexpected SCEV type!"); 678 } 679 680 namespace { 681 682 /// LoopCompare - Compare loops by PickMostRelevantLoop. 683 class LoopCompare { 684 DominatorTree &DT; 685 public: 686 explicit LoopCompare(DominatorTree &dt) : DT(dt) {} 687 688 bool operator()(std::pair<const Loop *, const SCEV *> LHS, 689 std::pair<const Loop *, const SCEV *> RHS) const { 690 // Keep pointer operands sorted at the end. 691 if (LHS.second->getType()->isPointerTy() != 692 RHS.second->getType()->isPointerTy()) 693 return LHS.second->getType()->isPointerTy(); 694 695 // Compare loops with PickMostRelevantLoop. 696 if (LHS.first != RHS.first) 697 return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first; 698 699 // If one operand is a non-constant negative and the other is not, 700 // put the non-constant negative on the right so that a sub can 701 // be used instead of a negate and add. 702 if (LHS.second->isNonConstantNegative()) { 703 if (!RHS.second->isNonConstantNegative()) 704 return false; 705 } else if (RHS.second->isNonConstantNegative()) 706 return true; 707 708 // Otherwise they are equivalent according to this comparison. 709 return false; 710 } 711 }; 712 713 } 714 715 Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 716 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 717 718 // Collect all the add operands in a loop, along with their associated loops. 719 // Iterate in reverse so that constants are emitted last, all else equal, and 720 // so that pointer operands are inserted first, which the code below relies on 721 // to form more involved GEPs. 722 SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops; 723 for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()), 724 E(S->op_begin()); I != E; ++I) 725 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); 726 727 // Sort by loop. Use a stable sort so that constants follow non-constants and 728 // pointer operands precede non-pointer operands. 729 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); 730 731 // Emit instructions to add all the operands. Hoist as much as possible 732 // out of loops, and form meaningful getelementptrs where possible. 733 Value *Sum = nullptr; 734 for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) { 735 const Loop *CurLoop = I->first; 736 const SCEV *Op = I->second; 737 if (!Sum) { 738 // This is the first operand. Just expand it. 739 Sum = expand(Op); 740 ++I; 741 } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) { 742 // The running sum expression is a pointer. Try to form a getelementptr 743 // at this level with that as the base. 744 SmallVector<const SCEV *, 4> NewOps; 745 for (; I != E && I->first == CurLoop; ++I) { 746 // If the operand is SCEVUnknown and not instructions, peek through 747 // it, to enable more of it to be folded into the GEP. 748 const SCEV *X = I->second; 749 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X)) 750 if (!isa<Instruction>(U->getValue())) 751 X = SE.getSCEV(U->getValue()); 752 NewOps.push_back(X); 753 } 754 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum); 755 } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) { 756 // The running sum is an integer, and there's a pointer at this level. 757 // Try to form a getelementptr. If the running sum is instructions, 758 // use a SCEVUnknown to avoid re-analyzing them. 759 SmallVector<const SCEV *, 4> NewOps; 760 NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) : 761 SE.getSCEV(Sum)); 762 for (++I; I != E && I->first == CurLoop; ++I) 763 NewOps.push_back(I->second); 764 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op)); 765 } else if (Op->isNonConstantNegative()) { 766 // Instead of doing a negate and add, just do a subtract. 767 Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false); 768 Sum = InsertNoopCastOfTo(Sum, Ty); 769 Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap, 770 /*IsSafeToHoist*/ true); 771 ++I; 772 } else { 773 // A simple add. 774 Value *W = expandCodeForImpl(Op, Ty, false); 775 Sum = InsertNoopCastOfTo(Sum, Ty); 776 // Canonicalize a constant to the RHS. 777 if (isa<Constant>(Sum)) std::swap(Sum, W); 778 Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(), 779 /*IsSafeToHoist*/ true); 780 ++I; 781 } 782 } 783 784 return Sum; 785 } 786 787 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 788 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 789 790 // Collect all the mul operands in a loop, along with their associated loops. 791 // Iterate in reverse so that constants are emitted last, all else equal. 792 SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops; 793 for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()), 794 E(S->op_begin()); I != E; ++I) 795 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); 796 797 // Sort by loop. Use a stable sort so that constants follow non-constants. 798 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); 799 800 // Emit instructions to mul all the operands. Hoist as much as possible 801 // out of loops. 802 Value *Prod = nullptr; 803 auto I = OpsAndLoops.begin(); 804 805 // Expand the calculation of X pow N in the following manner: 806 // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then: 807 // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK). 808 const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() { 809 auto E = I; 810 // Calculate how many times the same operand from the same loop is included 811 // into this power. 812 uint64_t Exponent = 0; 813 const uint64_t MaxExponent = UINT64_MAX >> 1; 814 // No one sane will ever try to calculate such huge exponents, but if we 815 // need this, we stop on UINT64_MAX / 2 because we need to exit the loop 816 // below when the power of 2 exceeds our Exponent, and we want it to be 817 // 1u << 31 at most to not deal with unsigned overflow. 818 while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) { 819 ++Exponent; 820 ++E; 821 } 822 assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?"); 823 824 // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them 825 // that are needed into the result. 826 Value *P = expandCodeForImpl(I->second, Ty, false); 827 Value *Result = nullptr; 828 if (Exponent & 1) 829 Result = P; 830 for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) { 831 P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap, 832 /*IsSafeToHoist*/ true); 833 if (Exponent & BinExp) 834 Result = Result ? InsertBinop(Instruction::Mul, Result, P, 835 SCEV::FlagAnyWrap, 836 /*IsSafeToHoist*/ true) 837 : P; 838 } 839 840 I = E; 841 assert(Result && "Nothing was expanded?"); 842 return Result; 843 }; 844 845 while (I != OpsAndLoops.end()) { 846 if (!Prod) { 847 // This is the first operand. Just expand it. 848 Prod = ExpandOpBinPowN(); 849 } else if (I->second->isAllOnesValue()) { 850 // Instead of doing a multiply by negative one, just do a negate. 851 Prod = InsertNoopCastOfTo(Prod, Ty); 852 Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod, 853 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); 854 ++I; 855 } else { 856 // A simple mul. 857 Value *W = ExpandOpBinPowN(); 858 Prod = InsertNoopCastOfTo(Prod, Ty); 859 // Canonicalize a constant to the RHS. 860 if (isa<Constant>(Prod)) std::swap(Prod, W); 861 const APInt *RHS; 862 if (match(W, m_Power2(RHS))) { 863 // Canonicalize Prod*(1<<C) to Prod<<C. 864 assert(!Ty->isVectorTy() && "vector types are not SCEVable"); 865 auto NWFlags = S->getNoWrapFlags(); 866 // clear nsw flag if shl will produce poison value. 867 if (RHS->logBase2() == RHS->getBitWidth() - 1) 868 NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW); 869 Prod = InsertBinop(Instruction::Shl, Prod, 870 ConstantInt::get(Ty, RHS->logBase2()), NWFlags, 871 /*IsSafeToHoist*/ true); 872 } else { 873 Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(), 874 /*IsSafeToHoist*/ true); 875 } 876 } 877 } 878 879 return Prod; 880 } 881 882 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 883 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 884 885 Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false); 886 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 887 const APInt &RHS = SC->getAPInt(); 888 if (RHS.isPowerOf2()) 889 return InsertBinop(Instruction::LShr, LHS, 890 ConstantInt::get(Ty, RHS.logBase2()), 891 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); 892 } 893 894 Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false); 895 return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap, 896 /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS())); 897 } 898 899 /// Move parts of Base into Rest to leave Base with the minimal 900 /// expression that provides a pointer operand suitable for a 901 /// GEP expansion. 902 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, 903 ScalarEvolution &SE) { 904 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 905 Base = A->getStart(); 906 Rest = SE.getAddExpr(Rest, 907 SE.getAddRecExpr(SE.getConstant(A->getType(), 0), 908 A->getStepRecurrence(SE), 909 A->getLoop(), 910 A->getNoWrapFlags(SCEV::FlagNW))); 911 } 912 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 913 Base = A->getOperand(A->getNumOperands()-1); 914 SmallVector<const SCEV *, 8> NewAddOps(A->operands()); 915 NewAddOps.back() = Rest; 916 Rest = SE.getAddExpr(NewAddOps); 917 ExposePointerBase(Base, Rest, SE); 918 } 919 } 920 921 /// Determine if this is a well-behaved chain of instructions leading back to 922 /// the PHI. If so, it may be reused by expanded expressions. 923 bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, 924 const Loop *L) { 925 if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) || 926 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV))) 927 return false; 928 // If any of the operands don't dominate the insert position, bail. 929 // Addrec operands are always loop-invariant, so this can only happen 930 // if there are instructions which haven't been hoisted. 931 if (L == IVIncInsertLoop) { 932 for (Use &Op : llvm::drop_begin(IncV->operands())) 933 if (Instruction *OInst = dyn_cast<Instruction>(Op)) 934 if (!SE.DT.dominates(OInst, IVIncInsertPos)) 935 return false; 936 } 937 // Advance to the next instruction. 938 IncV = dyn_cast<Instruction>(IncV->getOperand(0)); 939 if (!IncV) 940 return false; 941 942 if (IncV->mayHaveSideEffects()) 943 return false; 944 945 if (IncV == PN) 946 return true; 947 948 return isNormalAddRecExprPHI(PN, IncV, L); 949 } 950 951 /// getIVIncOperand returns an induction variable increment's induction 952 /// variable operand. 953 /// 954 /// If allowScale is set, any type of GEP is allowed as long as the nonIV 955 /// operands dominate InsertPos. 956 /// 957 /// If allowScale is not set, ensure that a GEP increment conforms to one of the 958 /// simple patterns generated by getAddRecExprPHILiterally and 959 /// expandAddtoGEP. If the pattern isn't recognized, return NULL. 960 Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, 961 Instruction *InsertPos, 962 bool allowScale) { 963 if (IncV == InsertPos) 964 return nullptr; 965 966 switch (IncV->getOpcode()) { 967 default: 968 return nullptr; 969 // Check for a simple Add/Sub or GEP of a loop invariant step. 970 case Instruction::Add: 971 case Instruction::Sub: { 972 Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1)); 973 if (!OInst || SE.DT.dominates(OInst, InsertPos)) 974 return dyn_cast<Instruction>(IncV->getOperand(0)); 975 return nullptr; 976 } 977 case Instruction::BitCast: 978 return dyn_cast<Instruction>(IncV->getOperand(0)); 979 case Instruction::GetElementPtr: 980 for (Use &U : llvm::drop_begin(IncV->operands())) { 981 if (isa<Constant>(U)) 982 continue; 983 if (Instruction *OInst = dyn_cast<Instruction>(U)) { 984 if (!SE.DT.dominates(OInst, InsertPos)) 985 return nullptr; 986 } 987 if (allowScale) { 988 // allow any kind of GEP as long as it can be hoisted. 989 continue; 990 } 991 // This must be a pointer addition of constants (pretty), which is already 992 // handled, or some number of address-size elements (ugly). Ugly geps 993 // have 2 operands. i1* is used by the expander to represent an 994 // address-size element. 995 if (IncV->getNumOperands() != 2) 996 return nullptr; 997 unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace(); 998 if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS) 999 && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS)) 1000 return nullptr; 1001 break; 1002 } 1003 return dyn_cast<Instruction>(IncV->getOperand(0)); 1004 } 1005 } 1006 1007 /// If the insert point of the current builder or any of the builders on the 1008 /// stack of saved builders has 'I' as its insert point, update it to point to 1009 /// the instruction after 'I'. This is intended to be used when the instruction 1010 /// 'I' is being moved. If this fixup is not done and 'I' is moved to a 1011 /// different block, the inconsistent insert point (with a mismatched 1012 /// Instruction and Block) can lead to an instruction being inserted in a block 1013 /// other than its parent. 1014 void SCEVExpander::fixupInsertPoints(Instruction *I) { 1015 BasicBlock::iterator It(*I); 1016 BasicBlock::iterator NewInsertPt = std::next(It); 1017 if (Builder.GetInsertPoint() == It) 1018 Builder.SetInsertPoint(&*NewInsertPt); 1019 for (auto *InsertPtGuard : InsertPointGuards) 1020 if (InsertPtGuard->GetInsertPoint() == It) 1021 InsertPtGuard->SetInsertPoint(NewInsertPt); 1022 } 1023 1024 /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make 1025 /// it available to other uses in this loop. Recursively hoist any operands, 1026 /// until we reach a value that dominates InsertPos. 1027 bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { 1028 if (SE.DT.dominates(IncV, InsertPos)) 1029 return true; 1030 1031 // InsertPos must itself dominate IncV so that IncV's new position satisfies 1032 // its existing users. 1033 if (isa<PHINode>(InsertPos) || 1034 !SE.DT.dominates(InsertPos->getParent(), IncV->getParent())) 1035 return false; 1036 1037 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos)) 1038 return false; 1039 1040 // Check that the chain of IV operands leading back to Phi can be hoisted. 1041 SmallVector<Instruction*, 4> IVIncs; 1042 for(;;) { 1043 Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true); 1044 if (!Oper) 1045 return false; 1046 // IncV is safe to hoist. 1047 IVIncs.push_back(IncV); 1048 IncV = Oper; 1049 if (SE.DT.dominates(IncV, InsertPos)) 1050 break; 1051 } 1052 for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) { 1053 fixupInsertPoints(*I); 1054 (*I)->moveBefore(InsertPos); 1055 } 1056 return true; 1057 } 1058 1059 /// Determine if this cyclic phi is in a form that would have been generated by 1060 /// LSR. We don't care if the phi was actually expanded in this pass, as long 1061 /// as it is in a low-cost form, for example, no implied multiplication. This 1062 /// should match any patterns generated by getAddRecExprPHILiterally and 1063 /// expandAddtoGEP. 1064 bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, 1065 const Loop *L) { 1066 for(Instruction *IVOper = IncV; 1067 (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(), 1068 /*allowScale=*/false));) { 1069 if (IVOper == PN) 1070 return true; 1071 } 1072 return false; 1073 } 1074 1075 /// expandIVInc - Expand an IV increment at Builder's current InsertPos. 1076 /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may 1077 /// need to materialize IV increments elsewhere to handle difficult situations. 1078 Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L, 1079 Type *ExpandTy, Type *IntTy, 1080 bool useSubtract) { 1081 Value *IncV; 1082 // If the PHI is a pointer, use a GEP, otherwise use an add or sub. 1083 if (ExpandTy->isPointerTy()) { 1084 PointerType *GEPPtrTy = cast<PointerType>(ExpandTy); 1085 // If the step isn't constant, don't use an implicitly scaled GEP, because 1086 // that would require a multiply inside the loop. 1087 if (!isa<ConstantInt>(StepV)) 1088 GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()), 1089 GEPPtrTy->getAddressSpace()); 1090 IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN); 1091 if (IncV->getType() != PN->getType()) 1092 IncV = Builder.CreateBitCast(IncV, PN->getType()); 1093 } else { 1094 IncV = useSubtract ? 1095 Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") : 1096 Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next"); 1097 } 1098 return IncV; 1099 } 1100 1101 /// Hoist the addrec instruction chain rooted in the loop phi above the 1102 /// position. This routine assumes that this is possible (has been checked). 1103 void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, 1104 Instruction *Pos, PHINode *LoopPhi) { 1105 do { 1106 if (DT->dominates(InstToHoist, Pos)) 1107 break; 1108 // Make sure the increment is where we want it. But don't move it 1109 // down past a potential existing post-inc user. 1110 fixupInsertPoints(InstToHoist); 1111 InstToHoist->moveBefore(Pos); 1112 Pos = InstToHoist; 1113 InstToHoist = cast<Instruction>(InstToHoist->getOperand(0)); 1114 } while (InstToHoist != LoopPhi); 1115 } 1116 1117 /// Check whether we can cheaply express the requested SCEV in terms of 1118 /// the available PHI SCEV by truncation and/or inversion of the step. 1119 static bool canBeCheaplyTransformed(ScalarEvolution &SE, 1120 const SCEVAddRecExpr *Phi, 1121 const SCEVAddRecExpr *Requested, 1122 bool &InvertStep) { 1123 Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType()); 1124 Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType()); 1125 1126 if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth()) 1127 return false; 1128 1129 // Try truncate it if necessary. 1130 Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy)); 1131 if (!Phi) 1132 return false; 1133 1134 // Check whether truncation will help. 1135 if (Phi == Requested) { 1136 InvertStep = false; 1137 return true; 1138 } 1139 1140 // Check whether inverting will help: {R,+,-1} == R - {0,+,1}. 1141 if (SE.getAddExpr(Requested->getStart(), 1142 SE.getNegativeSCEV(Requested)) == Phi) { 1143 InvertStep = true; 1144 return true; 1145 } 1146 1147 return false; 1148 } 1149 1150 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) { 1151 if (!isa<IntegerType>(AR->getType())) 1152 return false; 1153 1154 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth(); 1155 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2); 1156 const SCEV *Step = AR->getStepRecurrence(SE); 1157 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy), 1158 SE.getSignExtendExpr(AR, WideTy)); 1159 const SCEV *ExtendAfterOp = 1160 SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy); 1161 return ExtendAfterOp == OpAfterExtend; 1162 } 1163 1164 static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) { 1165 if (!isa<IntegerType>(AR->getType())) 1166 return false; 1167 1168 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth(); 1169 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2); 1170 const SCEV *Step = AR->getStepRecurrence(SE); 1171 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy), 1172 SE.getZeroExtendExpr(AR, WideTy)); 1173 const SCEV *ExtendAfterOp = 1174 SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy); 1175 return ExtendAfterOp == OpAfterExtend; 1176 } 1177 1178 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand 1179 /// the base addrec, which is the addrec without any non-loop-dominating 1180 /// values, and return the PHI. 1181 PHINode * 1182 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, 1183 const Loop *L, 1184 Type *ExpandTy, 1185 Type *IntTy, 1186 Type *&TruncTy, 1187 bool &InvertStep) { 1188 assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position"); 1189 1190 // Reuse a previously-inserted PHI, if present. 1191 BasicBlock *LatchBlock = L->getLoopLatch(); 1192 if (LatchBlock) { 1193 PHINode *AddRecPhiMatch = nullptr; 1194 Instruction *IncV = nullptr; 1195 TruncTy = nullptr; 1196 InvertStep = false; 1197 1198 // Only try partially matching scevs that need truncation and/or 1199 // step-inversion if we know this loop is outside the current loop. 1200 bool TryNonMatchingSCEV = 1201 IVIncInsertLoop && 1202 SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader()); 1203 1204 for (PHINode &PN : L->getHeader()->phis()) { 1205 if (!SE.isSCEVable(PN.getType())) 1206 continue; 1207 1208 // We should not look for a incomplete PHI. Getting SCEV for a incomplete 1209 // PHI has no meaning at all. 1210 if (!PN.isComplete()) { 1211 DEBUG_WITH_TYPE( 1212 DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n"); 1213 continue; 1214 } 1215 1216 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN)); 1217 if (!PhiSCEV) 1218 continue; 1219 1220 bool IsMatchingSCEV = PhiSCEV == Normalized; 1221 // We only handle truncation and inversion of phi recurrences for the 1222 // expanded expression if the expanded expression's loop dominates the 1223 // loop we insert to. Check now, so we can bail out early. 1224 if (!IsMatchingSCEV && !TryNonMatchingSCEV) 1225 continue; 1226 1227 // TODO: this possibly can be reworked to avoid this cast at all. 1228 Instruction *TempIncV = 1229 dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock)); 1230 if (!TempIncV) 1231 continue; 1232 1233 // Check whether we can reuse this PHI node. 1234 if (LSRMode) { 1235 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L)) 1236 continue; 1237 if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos)) 1238 continue; 1239 } else { 1240 if (!isNormalAddRecExprPHI(&PN, TempIncV, L)) 1241 continue; 1242 } 1243 1244 // Stop if we have found an exact match SCEV. 1245 if (IsMatchingSCEV) { 1246 IncV = TempIncV; 1247 TruncTy = nullptr; 1248 InvertStep = false; 1249 AddRecPhiMatch = &PN; 1250 break; 1251 } 1252 1253 // Try whether the phi can be translated into the requested form 1254 // (truncated and/or offset by a constant). 1255 if ((!TruncTy || InvertStep) && 1256 canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) { 1257 // Record the phi node. But don't stop we might find an exact match 1258 // later. 1259 AddRecPhiMatch = &PN; 1260 IncV = TempIncV; 1261 TruncTy = SE.getEffectiveSCEVType(Normalized->getType()); 1262 } 1263 } 1264 1265 if (AddRecPhiMatch) { 1266 // Potentially, move the increment. We have made sure in 1267 // isExpandedAddRecExprPHI or hoistIVInc that this is possible. 1268 if (L == IVIncInsertLoop) 1269 hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch); 1270 1271 // Ok, the add recurrence looks usable. 1272 // Remember this PHI, even in post-inc mode. 1273 InsertedValues.insert(AddRecPhiMatch); 1274 // Remember the increment. 1275 rememberInstruction(IncV); 1276 // Those values were not actually inserted but re-used. 1277 ReusedValues.insert(AddRecPhiMatch); 1278 ReusedValues.insert(IncV); 1279 return AddRecPhiMatch; 1280 } 1281 } 1282 1283 // Save the original insertion point so we can restore it when we're done. 1284 SCEVInsertPointGuard Guard(Builder, this); 1285 1286 // Another AddRec may need to be recursively expanded below. For example, if 1287 // this AddRec is quadratic, the StepV may itself be an AddRec in this 1288 // loop. Remove this loop from the PostIncLoops set before expanding such 1289 // AddRecs. Otherwise, we cannot find a valid position for the step 1290 // (i.e. StepV can never dominate its loop header). Ideally, we could do 1291 // SavedIncLoops.swap(PostIncLoops), but we generally have a single element, 1292 // so it's not worth implementing SmallPtrSet::swap. 1293 PostIncLoopSet SavedPostIncLoops = PostIncLoops; 1294 PostIncLoops.clear(); 1295 1296 // Expand code for the start value into the loop preheader. 1297 assert(L->getLoopPreheader() && 1298 "Can't expand add recurrences without a loop preheader!"); 1299 Value *StartV = 1300 expandCodeForImpl(Normalized->getStart(), ExpandTy, 1301 L->getLoopPreheader()->getTerminator(), false); 1302 1303 // StartV must have been be inserted into L's preheader to dominate the new 1304 // phi. 1305 assert(!isa<Instruction>(StartV) || 1306 SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), 1307 L->getHeader())); 1308 1309 // Expand code for the step value. Do this before creating the PHI so that PHI 1310 // reuse code doesn't see an incomplete PHI. 1311 const SCEV *Step = Normalized->getStepRecurrence(SE); 1312 // If the stride is negative, insert a sub instead of an add for the increment 1313 // (unless it's a constant, because subtracts of constants are canonicalized 1314 // to adds). 1315 bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative(); 1316 if (useSubtract) 1317 Step = SE.getNegativeSCEV(Step); 1318 // Expand the step somewhere that dominates the loop header. 1319 Value *StepV = expandCodeForImpl( 1320 Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false); 1321 1322 // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if 1323 // we actually do emit an addition. It does not apply if we emit a 1324 // subtraction. 1325 bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized); 1326 bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized); 1327 1328 // Create the PHI. 1329 BasicBlock *Header = L->getHeader(); 1330 Builder.SetInsertPoint(Header, Header->begin()); 1331 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); 1332 PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE), 1333 Twine(IVName) + ".iv"); 1334 1335 // Create the step instructions and populate the PHI. 1336 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { 1337 BasicBlock *Pred = *HPI; 1338 1339 // Add a start value. 1340 if (!L->contains(Pred)) { 1341 PN->addIncoming(StartV, Pred); 1342 continue; 1343 } 1344 1345 // Create a step value and add it to the PHI. 1346 // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the 1347 // instructions at IVIncInsertPos. 1348 Instruction *InsertPos = L == IVIncInsertLoop ? 1349 IVIncInsertPos : Pred->getTerminator(); 1350 Builder.SetInsertPoint(InsertPos); 1351 Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); 1352 1353 if (isa<OverflowingBinaryOperator>(IncV)) { 1354 if (IncrementIsNUW) 1355 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap(); 1356 if (IncrementIsNSW) 1357 cast<BinaryOperator>(IncV)->setHasNoSignedWrap(); 1358 } 1359 PN->addIncoming(IncV, Pred); 1360 } 1361 1362 // After expanding subexpressions, restore the PostIncLoops set so the caller 1363 // can ensure that IVIncrement dominates the current uses. 1364 PostIncLoops = SavedPostIncLoops; 1365 1366 // Remember this PHI, even in post-inc mode. 1367 InsertedValues.insert(PN); 1368 1369 return PN; 1370 } 1371 1372 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { 1373 Type *STy = S->getType(); 1374 Type *IntTy = SE.getEffectiveSCEVType(STy); 1375 const Loop *L = S->getLoop(); 1376 1377 // Determine a normalized form of this expression, which is the expression 1378 // before any post-inc adjustment is made. 1379 const SCEVAddRecExpr *Normalized = S; 1380 if (PostIncLoops.count(L)) { 1381 PostIncLoopSet Loops; 1382 Loops.insert(L); 1383 Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE)); 1384 } 1385 1386 // Strip off any non-loop-dominating component from the addrec start. 1387 const SCEV *Start = Normalized->getStart(); 1388 const SCEV *PostLoopOffset = nullptr; 1389 if (!SE.properlyDominates(Start, L->getHeader())) { 1390 PostLoopOffset = Start; 1391 Start = SE.getConstant(Normalized->getType(), 0); 1392 Normalized = cast<SCEVAddRecExpr>( 1393 SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE), 1394 Normalized->getLoop(), 1395 Normalized->getNoWrapFlags(SCEV::FlagNW))); 1396 } 1397 1398 // Strip off any non-loop-dominating component from the addrec step. 1399 const SCEV *Step = Normalized->getStepRecurrence(SE); 1400 const SCEV *PostLoopScale = nullptr; 1401 if (!SE.dominates(Step, L->getHeader())) { 1402 PostLoopScale = Step; 1403 Step = SE.getConstant(Normalized->getType(), 1); 1404 if (!Start->isZero()) { 1405 // The normalization below assumes that Start is constant zero, so if 1406 // it isn't re-associate Start to PostLoopOffset. 1407 assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?"); 1408 PostLoopOffset = Start; 1409 Start = SE.getConstant(Normalized->getType(), 0); 1410 } 1411 Normalized = 1412 cast<SCEVAddRecExpr>(SE.getAddRecExpr( 1413 Start, Step, Normalized->getLoop(), 1414 Normalized->getNoWrapFlags(SCEV::FlagNW))); 1415 } 1416 1417 // Expand the core addrec. If we need post-loop scaling, force it to 1418 // expand to an integer type to avoid the need for additional casting. 1419 Type *ExpandTy = PostLoopScale ? IntTy : STy; 1420 // We can't use a pointer type for the addrec if the pointer type is 1421 // non-integral. 1422 Type *AddRecPHIExpandTy = 1423 DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy; 1424 1425 // In some cases, we decide to reuse an existing phi node but need to truncate 1426 // it and/or invert the step. 1427 Type *TruncTy = nullptr; 1428 bool InvertStep = false; 1429 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy, 1430 IntTy, TruncTy, InvertStep); 1431 1432 // Accommodate post-inc mode, if necessary. 1433 Value *Result; 1434 if (!PostIncLoops.count(L)) 1435 Result = PN; 1436 else { 1437 // In PostInc mode, use the post-incremented value. 1438 BasicBlock *LatchBlock = L->getLoopLatch(); 1439 assert(LatchBlock && "PostInc mode requires a unique loop latch!"); 1440 Result = PN->getIncomingValueForBlock(LatchBlock); 1441 1442 // We might be introducing a new use of the post-inc IV that is not poison 1443 // safe, in which case we should drop poison generating flags. Only keep 1444 // those flags for which SCEV has proven that they always hold. 1445 if (isa<OverflowingBinaryOperator>(Result)) { 1446 auto *I = cast<Instruction>(Result); 1447 if (!S->hasNoUnsignedWrap()) 1448 I->setHasNoUnsignedWrap(false); 1449 if (!S->hasNoSignedWrap()) 1450 I->setHasNoSignedWrap(false); 1451 } 1452 1453 // For an expansion to use the postinc form, the client must call 1454 // expandCodeFor with an InsertPoint that is either outside the PostIncLoop 1455 // or dominated by IVIncInsertPos. 1456 if (isa<Instruction>(Result) && 1457 !SE.DT.dominates(cast<Instruction>(Result), 1458 &*Builder.GetInsertPoint())) { 1459 // The induction variable's postinc expansion does not dominate this use. 1460 // IVUsers tries to prevent this case, so it is rare. However, it can 1461 // happen when an IVUser outside the loop is not dominated by the latch 1462 // block. Adjusting IVIncInsertPos before expansion begins cannot handle 1463 // all cases. Consider a phi outside whose operand is replaced during 1464 // expansion with the value of the postinc user. Without fundamentally 1465 // changing the way postinc users are tracked, the only remedy is 1466 // inserting an extra IV increment. StepV might fold into PostLoopOffset, 1467 // but hopefully expandCodeFor handles that. 1468 bool useSubtract = 1469 !ExpandTy->isPointerTy() && Step->isNonConstantNegative(); 1470 if (useSubtract) 1471 Step = SE.getNegativeSCEV(Step); 1472 Value *StepV; 1473 { 1474 // Expand the step somewhere that dominates the loop header. 1475 SCEVInsertPointGuard Guard(Builder, this); 1476 StepV = expandCodeForImpl( 1477 Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false); 1478 } 1479 Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); 1480 } 1481 } 1482 1483 // We have decided to reuse an induction variable of a dominating loop. Apply 1484 // truncation and/or inversion of the step. 1485 if (TruncTy) { 1486 Type *ResTy = Result->getType(); 1487 // Normalize the result type. 1488 if (ResTy != SE.getEffectiveSCEVType(ResTy)) 1489 Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy)); 1490 // Truncate the result. 1491 if (TruncTy != Result->getType()) 1492 Result = Builder.CreateTrunc(Result, TruncTy); 1493 1494 // Invert the result. 1495 if (InvertStep) 1496 Result = Builder.CreateSub( 1497 expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result); 1498 } 1499 1500 // Re-apply any non-loop-dominating scale. 1501 if (PostLoopScale) { 1502 assert(S->isAffine() && "Can't linearly scale non-affine recurrences."); 1503 Result = InsertNoopCastOfTo(Result, IntTy); 1504 Result = Builder.CreateMul(Result, 1505 expandCodeForImpl(PostLoopScale, IntTy, false)); 1506 } 1507 1508 // Re-apply any non-loop-dominating offset. 1509 if (PostLoopOffset) { 1510 if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) { 1511 if (Result->getType()->isIntegerTy()) { 1512 Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false); 1513 Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base); 1514 } else { 1515 Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result); 1516 } 1517 } else { 1518 Result = InsertNoopCastOfTo(Result, IntTy); 1519 Result = Builder.CreateAdd( 1520 Result, expandCodeForImpl(PostLoopOffset, IntTy, false)); 1521 } 1522 } 1523 1524 return Result; 1525 } 1526 1527 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 1528 // In canonical mode we compute the addrec as an expression of a canonical IV 1529 // using evaluateAtIteration and expand the resulting SCEV expression. This 1530 // way we avoid introducing new IVs to carry on the comutation of the addrec 1531 // throughout the loop. 1532 // 1533 // For nested addrecs evaluateAtIteration might need a canonical IV of a 1534 // type wider than the addrec itself. Emitting a canonical IV of the 1535 // proper type might produce non-legal types, for example expanding an i64 1536 // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall 1537 // back to non-canonical mode for nested addrecs. 1538 if (!CanonicalMode || (S->getNumOperands() > 2)) 1539 return expandAddRecExprLiterally(S); 1540 1541 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1542 const Loop *L = S->getLoop(); 1543 1544 // First check for an existing canonical IV in a suitable type. 1545 PHINode *CanonicalIV = nullptr; 1546 if (PHINode *PN = L->getCanonicalInductionVariable()) 1547 if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 1548 CanonicalIV = PN; 1549 1550 // Rewrite an AddRec in terms of the canonical induction variable, if 1551 // its type is more narrow. 1552 if (CanonicalIV && 1553 SE.getTypeSizeInBits(CanonicalIV->getType()) > 1554 SE.getTypeSizeInBits(Ty)) { 1555 SmallVector<const SCEV *, 4> NewOps(S->getNumOperands()); 1556 for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i) 1557 NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType()); 1558 Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(), 1559 S->getNoWrapFlags(SCEV::FlagNW))); 1560 BasicBlock::iterator NewInsertPt = 1561 findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint()); 1562 V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr, 1563 &*NewInsertPt, false); 1564 return V; 1565 } 1566 1567 // {X,+,F} --> X + {0,+,F} 1568 if (!S->getStart()->isZero()) { 1569 SmallVector<const SCEV *, 4> NewOps(S->operands()); 1570 NewOps[0] = SE.getConstant(Ty, 0); 1571 const SCEV *Rest = SE.getAddRecExpr(NewOps, L, 1572 S->getNoWrapFlags(SCEV::FlagNW)); 1573 1574 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 1575 // comments on expandAddToGEP for details. 1576 const SCEV *Base = S->getStart(); 1577 // Dig into the expression to find the pointer base for a GEP. 1578 const SCEV *ExposedRest = Rest; 1579 ExposePointerBase(Base, ExposedRest, SE); 1580 // If we found a pointer, expand the AddRec with a GEP. 1581 if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 1582 // Make sure the Base isn't something exotic, such as a multiplied 1583 // or divided pointer value. In those cases, the result type isn't 1584 // actually a pointer type. 1585 if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 1586 Value *StartV = expand(Base); 1587 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 1588 return expandAddToGEP(ExposedRest, PTy, Ty, StartV); 1589 } 1590 } 1591 1592 // Just do a normal add. Pre-expand the operands to suppress folding. 1593 // 1594 // The LHS and RHS values are factored out of the expand call to make the 1595 // output independent of the argument evaluation order. 1596 const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart())); 1597 const SCEV *AddExprRHS = SE.getUnknown(expand(Rest)); 1598 return expand(SE.getAddExpr(AddExprLHS, AddExprRHS)); 1599 } 1600 1601 // If we don't yet have a canonical IV, create one. 1602 if (!CanonicalIV) { 1603 // Create and insert the PHI node for the induction variable in the 1604 // specified loop. 1605 BasicBlock *Header = L->getHeader(); 1606 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); 1607 CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar", 1608 &Header->front()); 1609 rememberInstruction(CanonicalIV); 1610 1611 SmallSet<BasicBlock *, 4> PredSeen; 1612 Constant *One = ConstantInt::get(Ty, 1); 1613 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { 1614 BasicBlock *HP = *HPI; 1615 if (!PredSeen.insert(HP).second) { 1616 // There must be an incoming value for each predecessor, even the 1617 // duplicates! 1618 CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP); 1619 continue; 1620 } 1621 1622 if (L->contains(HP)) { 1623 // Insert a unit add instruction right before the terminator 1624 // corresponding to the back-edge. 1625 Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One, 1626 "indvar.next", 1627 HP->getTerminator()); 1628 Add->setDebugLoc(HP->getTerminator()->getDebugLoc()); 1629 rememberInstruction(Add); 1630 CanonicalIV->addIncoming(Add, HP); 1631 } else { 1632 CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP); 1633 } 1634 } 1635 } 1636 1637 // {0,+,1} --> Insert a canonical induction variable into the loop! 1638 if (S->isAffine() && S->getOperand(1)->isOne()) { 1639 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 1640 "IVs with types different from the canonical IV should " 1641 "already have been handled!"); 1642 return CanonicalIV; 1643 } 1644 1645 // {0,+,F} --> {0,+,1} * F 1646 1647 // If this is a simple linear addrec, emit it now as a special case. 1648 if (S->isAffine()) // {0,+,F} --> i*F 1649 return 1650 expand(SE.getTruncateOrNoop( 1651 SE.getMulExpr(SE.getUnknown(CanonicalIV), 1652 SE.getNoopOrAnyExtend(S->getOperand(1), 1653 CanonicalIV->getType())), 1654 Ty)); 1655 1656 // If this is a chain of recurrences, turn it into a closed form, using the 1657 // folders, then expandCodeFor the closed form. This allows the folders to 1658 // simplify the expression without having to build a bunch of special code 1659 // into this folder. 1660 const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV. 1661 1662 // Promote S up to the canonical IV type, if the cast is foldable. 1663 const SCEV *NewS = S; 1664 const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType()); 1665 if (isa<SCEVAddRecExpr>(Ext)) 1666 NewS = Ext; 1667 1668 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 1669 //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 1670 1671 // Truncate the result down to the original type, if needed. 1672 const SCEV *T = SE.getTruncateOrNoop(V, Ty); 1673 return expand(T); 1674 } 1675 1676 Value *SCEVExpander::visitPtrToIntExpr(const SCEVPtrToIntExpr *S) { 1677 Value *V = 1678 expandCodeForImpl(S->getOperand(), S->getOperand()->getType(), false); 1679 return Builder.CreatePtrToInt(V, S->getType()); 1680 } 1681 1682 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 1683 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1684 Value *V = expandCodeForImpl( 1685 S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()), 1686 false); 1687 return Builder.CreateTrunc(V, Ty); 1688 } 1689 1690 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 1691 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1692 Value *V = expandCodeForImpl( 1693 S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()), 1694 false); 1695 return Builder.CreateZExt(V, Ty); 1696 } 1697 1698 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 1699 Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1700 Value *V = expandCodeForImpl( 1701 S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()), 1702 false); 1703 return Builder.CreateSExt(V, Ty); 1704 } 1705 1706 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 1707 Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 1708 Type *Ty = LHS->getType(); 1709 for (int i = S->getNumOperands()-2; i >= 0; --i) { 1710 // In the case of mixed integer and pointer types, do the 1711 // rest of the comparisons as integer. 1712 Type *OpTy = S->getOperand(i)->getType(); 1713 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1714 Ty = SE.getEffectiveSCEVType(Ty); 1715 LHS = InsertNoopCastOfTo(LHS, Ty); 1716 } 1717 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); 1718 Value *Sel; 1719 if (Ty->isIntegerTy()) 1720 Sel = Builder.CreateIntrinsic(Intrinsic::smax, {Ty}, {LHS, RHS}, 1721 /*FMFSource=*/nullptr, "smax"); 1722 else { 1723 Value *ICmp = Builder.CreateICmpSGT(LHS, RHS); 1724 Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax"); 1725 } 1726 LHS = Sel; 1727 } 1728 // In the case of mixed integer and pointer types, cast the 1729 // final result back to the pointer type. 1730 if (LHS->getType() != S->getType()) 1731 LHS = InsertNoopCastOfTo(LHS, S->getType()); 1732 return LHS; 1733 } 1734 1735 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 1736 Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 1737 Type *Ty = LHS->getType(); 1738 for (int i = S->getNumOperands()-2; i >= 0; --i) { 1739 // In the case of mixed integer and pointer types, do the 1740 // rest of the comparisons as integer. 1741 Type *OpTy = S->getOperand(i)->getType(); 1742 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1743 Ty = SE.getEffectiveSCEVType(Ty); 1744 LHS = InsertNoopCastOfTo(LHS, Ty); 1745 } 1746 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); 1747 Value *Sel; 1748 if (Ty->isIntegerTy()) 1749 Sel = Builder.CreateIntrinsic(Intrinsic::umax, {Ty}, {LHS, RHS}, 1750 /*FMFSource=*/nullptr, "umax"); 1751 else { 1752 Value *ICmp = Builder.CreateICmpUGT(LHS, RHS); 1753 Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax"); 1754 } 1755 LHS = Sel; 1756 } 1757 // In the case of mixed integer and pointer types, cast the 1758 // final result back to the pointer type. 1759 if (LHS->getType() != S->getType()) 1760 LHS = InsertNoopCastOfTo(LHS, S->getType()); 1761 return LHS; 1762 } 1763 1764 Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) { 1765 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); 1766 Type *Ty = LHS->getType(); 1767 for (int i = S->getNumOperands() - 2; i >= 0; --i) { 1768 // In the case of mixed integer and pointer types, do the 1769 // rest of the comparisons as integer. 1770 Type *OpTy = S->getOperand(i)->getType(); 1771 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1772 Ty = SE.getEffectiveSCEVType(Ty); 1773 LHS = InsertNoopCastOfTo(LHS, Ty); 1774 } 1775 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); 1776 Value *Sel; 1777 if (Ty->isIntegerTy()) 1778 Sel = Builder.CreateIntrinsic(Intrinsic::smin, {Ty}, {LHS, RHS}, 1779 /*FMFSource=*/nullptr, "smin"); 1780 else { 1781 Value *ICmp = Builder.CreateICmpSLT(LHS, RHS); 1782 Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin"); 1783 } 1784 LHS = Sel; 1785 } 1786 // In the case of mixed integer and pointer types, cast the 1787 // final result back to the pointer type. 1788 if (LHS->getType() != S->getType()) 1789 LHS = InsertNoopCastOfTo(LHS, S->getType()); 1790 return LHS; 1791 } 1792 1793 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) { 1794 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); 1795 Type *Ty = LHS->getType(); 1796 for (int i = S->getNumOperands() - 2; i >= 0; --i) { 1797 // In the case of mixed integer and pointer types, do the 1798 // rest of the comparisons as integer. 1799 Type *OpTy = S->getOperand(i)->getType(); 1800 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1801 Ty = SE.getEffectiveSCEVType(Ty); 1802 LHS = InsertNoopCastOfTo(LHS, Ty); 1803 } 1804 Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); 1805 Value *Sel; 1806 if (Ty->isIntegerTy()) 1807 Sel = Builder.CreateIntrinsic(Intrinsic::umin, {Ty}, {LHS, RHS}, 1808 /*FMFSource=*/nullptr, "umin"); 1809 else { 1810 Value *ICmp = Builder.CreateICmpULT(LHS, RHS); 1811 Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin"); 1812 } 1813 LHS = Sel; 1814 } 1815 // In the case of mixed integer and pointer types, cast the 1816 // final result back to the pointer type. 1817 if (LHS->getType() != S->getType()) 1818 LHS = InsertNoopCastOfTo(LHS, S->getType()); 1819 return LHS; 1820 } 1821 1822 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, 1823 Instruction *IP, bool Root) { 1824 setInsertPoint(IP); 1825 Value *V = expandCodeForImpl(SH, Ty, Root); 1826 return V; 1827 } 1828 1829 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) { 1830 // Expand the code for this SCEV. 1831 Value *V = expand(SH); 1832 1833 if (PreserveLCSSA) { 1834 if (auto *Inst = dyn_cast<Instruction>(V)) { 1835 // Create a temporary instruction to at the current insertion point, so we 1836 // can hand it off to the helper to create LCSSA PHIs if required for the 1837 // new use. 1838 // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor) 1839 // would accept a insertion point and return an LCSSA phi for that 1840 // insertion point, so there is no need to insert & remove the temporary 1841 // instruction. 1842 Instruction *Tmp; 1843 if (Inst->getType()->isIntegerTy()) 1844 Tmp = 1845 cast<Instruction>(Builder.CreateAdd(Inst, Inst, "tmp.lcssa.user")); 1846 else { 1847 assert(Inst->getType()->isPointerTy()); 1848 Tmp = cast<Instruction>( 1849 Builder.CreateGEP(Inst, Builder.getInt32(1), "tmp.lcssa.user")); 1850 } 1851 V = fixupLCSSAFormFor(Tmp, 0); 1852 1853 // Clean up temporary instruction. 1854 InsertedValues.erase(Tmp); 1855 InsertedPostIncValues.erase(Tmp); 1856 Tmp->eraseFromParent(); 1857 } 1858 } 1859 1860 InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V; 1861 if (Ty) { 1862 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 1863 "non-trivial casts should be done with the SCEVs directly!"); 1864 V = InsertNoopCastOfTo(V, Ty); 1865 } 1866 return V; 1867 } 1868 1869 ScalarEvolution::ValueOffsetPair 1870 SCEVExpander::FindValueInExprValueMap(const SCEV *S, 1871 const Instruction *InsertPt) { 1872 SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S); 1873 // If the expansion is not in CanonicalMode, and the SCEV contains any 1874 // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally. 1875 if (CanonicalMode || !SE.containsAddRecurrence(S)) { 1876 // If S is scConstant, it may be worse to reuse an existing Value. 1877 if (S->getSCEVType() != scConstant && Set) { 1878 // Choose a Value from the set which dominates the insertPt. 1879 // insertPt should be inside the Value's parent loop so as not to break 1880 // the LCSSA form. 1881 for (auto const &VOPair : *Set) { 1882 Value *V = VOPair.first; 1883 ConstantInt *Offset = VOPair.second; 1884 Instruction *EntInst = nullptr; 1885 if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) && 1886 S->getType() == V->getType() && 1887 EntInst->getFunction() == InsertPt->getFunction() && 1888 SE.DT.dominates(EntInst, InsertPt) && 1889 (SE.LI.getLoopFor(EntInst->getParent()) == nullptr || 1890 SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt))) 1891 return {V, Offset}; 1892 } 1893 } 1894 } 1895 return {nullptr, nullptr}; 1896 } 1897 1898 // The expansion of SCEV will either reuse a previous Value in ExprValueMap, 1899 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode, 1900 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded 1901 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise, 1902 // the expansion will try to reuse Value from ExprValueMap, and only when it 1903 // fails, expand the SCEV literally. 1904 Value *SCEVExpander::expand(const SCEV *S) { 1905 // Compute an insertion point for this SCEV object. Hoist the instructions 1906 // as far out in the loop nest as possible. 1907 Instruction *InsertPt = &*Builder.GetInsertPoint(); 1908 1909 // We can move insertion point only if there is no div or rem operations 1910 // otherwise we are risky to move it over the check for zero denominator. 1911 auto SafeToHoist = [](const SCEV *S) { 1912 return !SCEVExprContains(S, [](const SCEV *S) { 1913 if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) { 1914 if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS())) 1915 // Division by non-zero constants can be hoisted. 1916 return SC->getValue()->isZero(); 1917 // All other divisions should not be moved as they may be 1918 // divisions by zero and should be kept within the 1919 // conditions of the surrounding loops that guard their 1920 // execution (see PR35406). 1921 return true; 1922 } 1923 return false; 1924 }); 1925 }; 1926 if (SafeToHoist(S)) { 1927 for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; 1928 L = L->getParentLoop()) { 1929 if (SE.isLoopInvariant(S, L)) { 1930 if (!L) break; 1931 if (BasicBlock *Preheader = L->getLoopPreheader()) 1932 InsertPt = Preheader->getTerminator(); 1933 else 1934 // LSR sets the insertion point for AddRec start/step values to the 1935 // block start to simplify value reuse, even though it's an invalid 1936 // position. SCEVExpander must correct for this in all cases. 1937 InsertPt = &*L->getHeader()->getFirstInsertionPt(); 1938 } else { 1939 // If the SCEV is computable at this level, insert it into the header 1940 // after the PHIs (and after any other instructions that we've inserted 1941 // there) so that it is guaranteed to dominate any user inside the loop. 1942 if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L)) 1943 InsertPt = &*L->getHeader()->getFirstInsertionPt(); 1944 1945 while (InsertPt->getIterator() != Builder.GetInsertPoint() && 1946 (isInsertedInstruction(InsertPt) || 1947 isa<DbgInfoIntrinsic>(InsertPt))) { 1948 InsertPt = &*std::next(InsertPt->getIterator()); 1949 } 1950 break; 1951 } 1952 } 1953 } 1954 1955 // Check to see if we already expanded this here. 1956 auto I = InsertedExpressions.find(std::make_pair(S, InsertPt)); 1957 if (I != InsertedExpressions.end()) 1958 return I->second; 1959 1960 SCEVInsertPointGuard Guard(Builder, this); 1961 Builder.SetInsertPoint(InsertPt); 1962 1963 // Expand the expression into instructions. 1964 ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt); 1965 Value *V = VO.first; 1966 1967 if (!V) 1968 V = visit(S); 1969 else if (VO.second) { 1970 if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) { 1971 Type *Ety = Vty->getPointerElementType(); 1972 int64_t Offset = VO.second->getSExtValue(); 1973 int64_t ESize = SE.getTypeSizeInBits(Ety); 1974 if ((Offset * 8) % ESize == 0) { 1975 ConstantInt *Idx = 1976 ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize); 1977 V = Builder.CreateGEP(Ety, V, Idx, "scevgep"); 1978 } else { 1979 ConstantInt *Idx = 1980 ConstantInt::getSigned(VO.second->getType(), -Offset); 1981 unsigned AS = Vty->getAddressSpace(); 1982 V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS)); 1983 V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx, 1984 "uglygep"); 1985 V = Builder.CreateBitCast(V, Vty); 1986 } 1987 } else { 1988 V = Builder.CreateSub(V, VO.second); 1989 } 1990 } 1991 // Remember the expanded value for this SCEV at this location. 1992 // 1993 // This is independent of PostIncLoops. The mapped value simply materializes 1994 // the expression at this insertion point. If the mapped value happened to be 1995 // a postinc expansion, it could be reused by a non-postinc user, but only if 1996 // its insertion point was already at the head of the loop. 1997 InsertedExpressions[std::make_pair(S, InsertPt)] = V; 1998 return V; 1999 } 2000 2001 void SCEVExpander::rememberInstruction(Value *I) { 2002 auto DoInsert = [this](Value *V) { 2003 if (!PostIncLoops.empty()) 2004 InsertedPostIncValues.insert(V); 2005 else 2006 InsertedValues.insert(V); 2007 }; 2008 DoInsert(I); 2009 2010 if (!PreserveLCSSA) 2011 return; 2012 2013 if (auto *Inst = dyn_cast<Instruction>(I)) { 2014 // A new instruction has been added, which might introduce new uses outside 2015 // a defining loop. Fix LCSSA from for each operand of the new instruction, 2016 // if required. 2017 for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd; 2018 OpIdx++) 2019 fixupLCSSAFormFor(Inst, OpIdx); 2020 } 2021 } 2022 2023 /// replaceCongruentIVs - Check for congruent phis in this loop header and 2024 /// replace them with their most canonical representative. Return the number of 2025 /// phis eliminated. 2026 /// 2027 /// This does not depend on any SCEVExpander state but should be used in 2028 /// the same context that SCEVExpander is used. 2029 unsigned 2030 SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, 2031 SmallVectorImpl<WeakTrackingVH> &DeadInsts, 2032 const TargetTransformInfo *TTI) { 2033 // Find integer phis in order of increasing width. 2034 SmallVector<PHINode*, 8> Phis; 2035 for (PHINode &PN : L->getHeader()->phis()) 2036 Phis.push_back(&PN); 2037 2038 if (TTI) 2039 llvm::sort(Phis, [](Value *LHS, Value *RHS) { 2040 // Put pointers at the back and make sure pointer < pointer = false. 2041 if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) 2042 return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy(); 2043 return RHS->getType()->getPrimitiveSizeInBits().getFixedSize() < 2044 LHS->getType()->getPrimitiveSizeInBits().getFixedSize(); 2045 }); 2046 2047 unsigned NumElim = 0; 2048 DenseMap<const SCEV *, PHINode *> ExprToIVMap; 2049 // Process phis from wide to narrow. Map wide phis to their truncation 2050 // so narrow phis can reuse them. 2051 for (PHINode *Phi : Phis) { 2052 auto SimplifyPHINode = [&](PHINode *PN) -> Value * { 2053 if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC})) 2054 return V; 2055 if (!SE.isSCEVable(PN->getType())) 2056 return nullptr; 2057 auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN)); 2058 if (!Const) 2059 return nullptr; 2060 return Const->getValue(); 2061 }; 2062 2063 // Fold constant phis. They may be congruent to other constant phis and 2064 // would confuse the logic below that expects proper IVs. 2065 if (Value *V = SimplifyPHINode(Phi)) { 2066 if (V->getType() != Phi->getType()) 2067 continue; 2068 Phi->replaceAllUsesWith(V); 2069 DeadInsts.emplace_back(Phi); 2070 ++NumElim; 2071 DEBUG_WITH_TYPE(DebugType, dbgs() 2072 << "INDVARS: Eliminated constant iv: " << *Phi << '\n'); 2073 continue; 2074 } 2075 2076 if (!SE.isSCEVable(Phi->getType())) 2077 continue; 2078 2079 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)]; 2080 if (!OrigPhiRef) { 2081 OrigPhiRef = Phi; 2082 if (Phi->getType()->isIntegerTy() && TTI && 2083 TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) { 2084 // This phi can be freely truncated to the narrowest phi type. Map the 2085 // truncated expression to it so it will be reused for narrow types. 2086 const SCEV *TruncExpr = 2087 SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType()); 2088 ExprToIVMap[TruncExpr] = Phi; 2089 } 2090 continue; 2091 } 2092 2093 // Replacing a pointer phi with an integer phi or vice-versa doesn't make 2094 // sense. 2095 if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy()) 2096 continue; 2097 2098 if (BasicBlock *LatchBlock = L->getLoopLatch()) { 2099 Instruction *OrigInc = dyn_cast<Instruction>( 2100 OrigPhiRef->getIncomingValueForBlock(LatchBlock)); 2101 Instruction *IsomorphicInc = 2102 dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock)); 2103 2104 if (OrigInc && IsomorphicInc) { 2105 // If this phi has the same width but is more canonical, replace the 2106 // original with it. As part of the "more canonical" determination, 2107 // respect a prior decision to use an IV chain. 2108 if (OrigPhiRef->getType() == Phi->getType() && 2109 !(ChainedPhis.count(Phi) || 2110 isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) && 2111 (ChainedPhis.count(Phi) || 2112 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) { 2113 std::swap(OrigPhiRef, Phi); 2114 std::swap(OrigInc, IsomorphicInc); 2115 } 2116 // Replacing the congruent phi is sufficient because acyclic 2117 // redundancy elimination, CSE/GVN, should handle the 2118 // rest. However, once SCEV proves that a phi is congruent, 2119 // it's often the head of an IV user cycle that is isomorphic 2120 // with the original phi. It's worth eagerly cleaning up the 2121 // common case of a single IV increment so that DeleteDeadPHIs 2122 // can remove cycles that had postinc uses. 2123 const SCEV *TruncExpr = 2124 SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType()); 2125 if (OrigInc != IsomorphicInc && 2126 TruncExpr == SE.getSCEV(IsomorphicInc) && 2127 SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) && 2128 hoistIVInc(OrigInc, IsomorphicInc)) { 2129 DEBUG_WITH_TYPE(DebugType, 2130 dbgs() << "INDVARS: Eliminated congruent iv.inc: " 2131 << *IsomorphicInc << '\n'); 2132 Value *NewInc = OrigInc; 2133 if (OrigInc->getType() != IsomorphicInc->getType()) { 2134 Instruction *IP = nullptr; 2135 if (PHINode *PN = dyn_cast<PHINode>(OrigInc)) 2136 IP = &*PN->getParent()->getFirstInsertionPt(); 2137 else 2138 IP = OrigInc->getNextNode(); 2139 2140 IRBuilder<> Builder(IP); 2141 Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc()); 2142 NewInc = Builder.CreateTruncOrBitCast( 2143 OrigInc, IsomorphicInc->getType(), IVName); 2144 } 2145 IsomorphicInc->replaceAllUsesWith(NewInc); 2146 DeadInsts.emplace_back(IsomorphicInc); 2147 } 2148 } 2149 } 2150 DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: " 2151 << *Phi << '\n'); 2152 DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Original iv: " 2153 << *OrigPhiRef << '\n'); 2154 ++NumElim; 2155 Value *NewIV = OrigPhiRef; 2156 if (OrigPhiRef->getType() != Phi->getType()) { 2157 IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt()); 2158 Builder.SetCurrentDebugLocation(Phi->getDebugLoc()); 2159 NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName); 2160 } 2161 Phi->replaceAllUsesWith(NewIV); 2162 DeadInsts.emplace_back(Phi); 2163 } 2164 return NumElim; 2165 } 2166 2167 Optional<ScalarEvolution::ValueOffsetPair> 2168 SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At, 2169 Loop *L) { 2170 using namespace llvm::PatternMatch; 2171 2172 SmallVector<BasicBlock *, 4> ExitingBlocks; 2173 L->getExitingBlocks(ExitingBlocks); 2174 2175 // Look for suitable value in simple conditions at the loop exits. 2176 for (BasicBlock *BB : ExitingBlocks) { 2177 ICmpInst::Predicate Pred; 2178 Instruction *LHS, *RHS; 2179 2180 if (!match(BB->getTerminator(), 2181 m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)), 2182 m_BasicBlock(), m_BasicBlock()))) 2183 continue; 2184 2185 if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At)) 2186 return ScalarEvolution::ValueOffsetPair(LHS, nullptr); 2187 2188 if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At)) 2189 return ScalarEvolution::ValueOffsetPair(RHS, nullptr); 2190 } 2191 2192 // Use expand's logic which is used for reusing a previous Value in 2193 // ExprValueMap. 2194 ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At); 2195 if (VO.first) 2196 return VO; 2197 2198 // There is potential to make this significantly smarter, but this simple 2199 // heuristic already gets some interesting cases. 2200 2201 // Can not find suitable value. 2202 return None; 2203 } 2204 2205 template<typename T> static InstructionCost costAndCollectOperands( 2206 const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, 2207 TargetTransformInfo::TargetCostKind CostKind, 2208 SmallVectorImpl<SCEVOperand> &Worklist) { 2209 2210 const T *S = cast<T>(WorkItem.S); 2211 InstructionCost Cost = 0; 2212 // Object to help map SCEV operands to expanded IR instructions. 2213 struct OperationIndices { 2214 OperationIndices(unsigned Opc, size_t min, size_t max) : 2215 Opcode(Opc), MinIdx(min), MaxIdx(max) { } 2216 unsigned Opcode; 2217 size_t MinIdx; 2218 size_t MaxIdx; 2219 }; 2220 2221 // Collect the operations of all the instructions that will be needed to 2222 // expand the SCEVExpr. This is so that when we come to cost the operands, 2223 // we know what the generated user(s) will be. 2224 SmallVector<OperationIndices, 2> Operations; 2225 2226 auto CastCost = [&](unsigned Opcode) -> InstructionCost { 2227 Operations.emplace_back(Opcode, 0, 0); 2228 return TTI.getCastInstrCost(Opcode, S->getType(), 2229 S->getOperand(0)->getType(), 2230 TTI::CastContextHint::None, CostKind); 2231 }; 2232 2233 auto ArithCost = [&](unsigned Opcode, unsigned NumRequired, 2234 unsigned MinIdx = 0, 2235 unsigned MaxIdx = 1) -> InstructionCost { 2236 Operations.emplace_back(Opcode, MinIdx, MaxIdx); 2237 return NumRequired * 2238 TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind); 2239 }; 2240 2241 auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, unsigned MinIdx, 2242 unsigned MaxIdx) -> InstructionCost { 2243 Operations.emplace_back(Opcode, MinIdx, MaxIdx); 2244 Type *OpType = S->getOperand(0)->getType(); 2245 return NumRequired * TTI.getCmpSelInstrCost( 2246 Opcode, OpType, CmpInst::makeCmpResultType(OpType), 2247 CmpInst::BAD_ICMP_PREDICATE, CostKind); 2248 }; 2249 2250 switch (S->getSCEVType()) { 2251 case scCouldNotCompute: 2252 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 2253 case scUnknown: 2254 case scConstant: 2255 return 0; 2256 case scPtrToInt: 2257 Cost = CastCost(Instruction::PtrToInt); 2258 break; 2259 case scTruncate: 2260 Cost = CastCost(Instruction::Trunc); 2261 break; 2262 case scZeroExtend: 2263 Cost = CastCost(Instruction::ZExt); 2264 break; 2265 case scSignExtend: 2266 Cost = CastCost(Instruction::SExt); 2267 break; 2268 case scUDivExpr: { 2269 unsigned Opcode = Instruction::UDiv; 2270 if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1))) 2271 if (SC->getAPInt().isPowerOf2()) 2272 Opcode = Instruction::LShr; 2273 Cost = ArithCost(Opcode, 1); 2274 break; 2275 } 2276 case scAddExpr: 2277 Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1); 2278 break; 2279 case scMulExpr: 2280 // TODO: this is a very pessimistic cost modelling for Mul, 2281 // because of Bin Pow algorithm actually used by the expander, 2282 // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN(). 2283 Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1); 2284 break; 2285 case scSMaxExpr: 2286 case scUMaxExpr: 2287 case scSMinExpr: 2288 case scUMinExpr: { 2289 // FIXME: should this ask the cost for Intrinsic's? 2290 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1); 2291 Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2); 2292 break; 2293 } 2294 case scAddRecExpr: { 2295 // In this polynominal, we may have some zero operands, and we shouldn't 2296 // really charge for those. So how many non-zero coeffients are there? 2297 int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) { 2298 return !Op->isZero(); 2299 }); 2300 2301 assert(NumTerms >= 1 && "Polynominal should have at least one term."); 2302 assert(!(*std::prev(S->operands().end()))->isZero() && 2303 "Last operand should not be zero"); 2304 2305 // Ignoring constant term (operand 0), how many of the coeffients are u> 1? 2306 int NumNonZeroDegreeNonOneTerms = 2307 llvm::count_if(S->operands(), [](const SCEV *Op) { 2308 auto *SConst = dyn_cast<SCEVConstant>(Op); 2309 return !SConst || SConst->getAPInt().ugt(1); 2310 }); 2311 2312 // Much like with normal add expr, the polynominal will require 2313 // one less addition than the number of it's terms. 2314 InstructionCost AddCost = ArithCost(Instruction::Add, NumTerms - 1, 2315 /*MinIdx*/ 1, /*MaxIdx*/ 1); 2316 // Here, *each* one of those will require a multiplication. 2317 InstructionCost MulCost = 2318 ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms); 2319 Cost = AddCost + MulCost; 2320 2321 // What is the degree of this polynominal? 2322 int PolyDegree = S->getNumOperands() - 1; 2323 assert(PolyDegree >= 1 && "Should be at least affine."); 2324 2325 // The final term will be: 2326 // Op_{PolyDegree} * x ^ {PolyDegree} 2327 // Where x ^ {PolyDegree} will again require PolyDegree-1 mul operations. 2328 // Note that x ^ {PolyDegree} = x * x ^ {PolyDegree-1} so charging for 2329 // x ^ {PolyDegree} will give us x ^ {2} .. x ^ {PolyDegree-1} for free. 2330 // FIXME: this is conservatively correct, but might be overly pessimistic. 2331 Cost += MulCost * (PolyDegree - 1); 2332 break; 2333 } 2334 } 2335 2336 for (auto &CostOp : Operations) { 2337 for (auto SCEVOp : enumerate(S->operands())) { 2338 // Clamp the index to account for multiple IR operations being chained. 2339 size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx); 2340 size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx); 2341 Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value()); 2342 } 2343 } 2344 return Cost; 2345 } 2346 2347 bool SCEVExpander::isHighCostExpansionHelper( 2348 const SCEVOperand &WorkItem, Loop *L, const Instruction &At, 2349 InstructionCost &Cost, unsigned Budget, const TargetTransformInfo &TTI, 2350 SmallPtrSetImpl<const SCEV *> &Processed, 2351 SmallVectorImpl<SCEVOperand> &Worklist) { 2352 if (Cost > Budget) 2353 return true; // Already run out of budget, give up. 2354 2355 const SCEV *S = WorkItem.S; 2356 // Was the cost of expansion of this expression already accounted for? 2357 if (!isa<SCEVConstant>(S) && !Processed.insert(S).second) 2358 return false; // We have already accounted for this expression. 2359 2360 // If we can find an existing value for this scev available at the point "At" 2361 // then consider the expression cheap. 2362 if (getRelatedExistingExpansion(S, &At, L)) 2363 return false; // Consider the expression to be free. 2364 2365 TargetTransformInfo::TargetCostKind CostKind = 2366 L->getHeader()->getParent()->hasMinSize() 2367 ? TargetTransformInfo::TCK_CodeSize 2368 : TargetTransformInfo::TCK_RecipThroughput; 2369 2370 switch (S->getSCEVType()) { 2371 case scCouldNotCompute: 2372 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 2373 case scUnknown: 2374 // Assume to be zero-cost. 2375 return false; 2376 case scConstant: { 2377 // Only evalulate the costs of constants when optimizing for size. 2378 if (CostKind != TargetTransformInfo::TCK_CodeSize) 2379 return 0; 2380 const APInt &Imm = cast<SCEVConstant>(S)->getAPInt(); 2381 Type *Ty = S->getType(); 2382 Cost += TTI.getIntImmCostInst( 2383 WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind); 2384 return Cost > Budget; 2385 } 2386 case scTruncate: 2387 case scPtrToInt: 2388 case scZeroExtend: 2389 case scSignExtend: { 2390 Cost += 2391 costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist); 2392 return false; // Will answer upon next entry into this function. 2393 } 2394 case scUDivExpr: { 2395 // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or 2396 // HowManyLessThans produced to compute a precise expression, rather than a 2397 // UDiv from the user's code. If we can't find a UDiv in the code with some 2398 // simple searching, we need to account for it's cost. 2399 2400 // At the beginning of this function we already tried to find existing 2401 // value for plain 'S'. Now try to lookup 'S + 1' since it is common 2402 // pattern involving division. This is just a simple search heuristic. 2403 if (getRelatedExistingExpansion( 2404 SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L)) 2405 return false; // Consider it to be free. 2406 2407 Cost += 2408 costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist); 2409 return false; // Will answer upon next entry into this function. 2410 } 2411 case scAddExpr: 2412 case scMulExpr: 2413 case scUMaxExpr: 2414 case scSMaxExpr: 2415 case scUMinExpr: 2416 case scSMinExpr: { 2417 assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 && 2418 "Nary expr should have more than 1 operand."); 2419 // The simple nary expr will require one less op (or pair of ops) 2420 // than the number of it's terms. 2421 Cost += 2422 costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist); 2423 return Cost > Budget; 2424 } 2425 case scAddRecExpr: { 2426 assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && 2427 "Polynomial should be at least linear"); 2428 Cost += costAndCollectOperands<SCEVAddRecExpr>( 2429 WorkItem, TTI, CostKind, Worklist); 2430 return Cost > Budget; 2431 } 2432 } 2433 llvm_unreachable("Unknown SCEV kind!"); 2434 } 2435 2436 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred, 2437 Instruction *IP) { 2438 assert(IP); 2439 switch (Pred->getKind()) { 2440 case SCEVPredicate::P_Union: 2441 return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP); 2442 case SCEVPredicate::P_Equal: 2443 return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP); 2444 case SCEVPredicate::P_Wrap: { 2445 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred); 2446 return expandWrapPredicate(AddRecPred, IP); 2447 } 2448 } 2449 llvm_unreachable("Unknown SCEV predicate type"); 2450 } 2451 2452 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred, 2453 Instruction *IP) { 2454 Value *Expr0 = 2455 expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false); 2456 Value *Expr1 = 2457 expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false); 2458 2459 Builder.SetInsertPoint(IP); 2460 auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check"); 2461 return I; 2462 } 2463 2464 Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR, 2465 Instruction *Loc, bool Signed) { 2466 assert(AR->isAffine() && "Cannot generate RT check for " 2467 "non-affine expression"); 2468 2469 SCEVUnionPredicate Pred; 2470 const SCEV *ExitCount = 2471 SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred); 2472 2473 assert(!isa<SCEVCouldNotCompute>(ExitCount) && "Invalid loop count"); 2474 2475 const SCEV *Step = AR->getStepRecurrence(SE); 2476 const SCEV *Start = AR->getStart(); 2477 2478 Type *ARTy = AR->getType(); 2479 unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType()); 2480 unsigned DstBits = SE.getTypeSizeInBits(ARTy); 2481 2482 // The expression {Start,+,Step} has nusw/nssw if 2483 // Step < 0, Start - |Step| * Backedge <= Start 2484 // Step >= 0, Start + |Step| * Backedge > Start 2485 // and |Step| * Backedge doesn't unsigned overflow. 2486 2487 IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits); 2488 Builder.SetInsertPoint(Loc); 2489 Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false); 2490 2491 IntegerType *Ty = 2492 IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy)); 2493 Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty; 2494 2495 Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false); 2496 Value *NegStepValue = 2497 expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false); 2498 Value *StartValue = expandCodeForImpl(Start, ARExpandTy, Loc, false); 2499 2500 ConstantInt *Zero = 2501 ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits)); 2502 2503 Builder.SetInsertPoint(Loc); 2504 // Compute |Step| 2505 Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero); 2506 Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue); 2507 2508 // Get the backedge taken count and truncate or extended to the AR type. 2509 Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty); 2510 auto *MulF = Intrinsic::getDeclaration(Loc->getModule(), 2511 Intrinsic::umul_with_overflow, Ty); 2512 2513 // Compute |Step| * Backedge 2514 CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul"); 2515 Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result"); 2516 Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow"); 2517 2518 // Compute: 2519 // Start + |Step| * Backedge < Start 2520 // Start - |Step| * Backedge > Start 2521 Value *Add = nullptr, *Sub = nullptr; 2522 if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) { 2523 const SCEV *MulS = SE.getSCEV(MulV); 2524 const SCEV *NegMulS = SE.getNegativeSCEV(MulS); 2525 Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue), 2526 ARPtrTy); 2527 Sub = Builder.CreateBitCast( 2528 expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy); 2529 } else { 2530 Add = Builder.CreateAdd(StartValue, MulV); 2531 Sub = Builder.CreateSub(StartValue, MulV); 2532 } 2533 2534 Value *EndCompareGT = Builder.CreateICmp( 2535 Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue); 2536 2537 Value *EndCompareLT = Builder.CreateICmp( 2538 Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue); 2539 2540 // Select the answer based on the sign of Step. 2541 Value *EndCheck = 2542 Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT); 2543 2544 // If the backedge taken count type is larger than the AR type, 2545 // check that we don't drop any bits by truncating it. If we are 2546 // dropping bits, then we have overflow (unless the step is zero). 2547 if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) { 2548 auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits); 2549 auto *BackedgeCheck = 2550 Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal, 2551 ConstantInt::get(Loc->getContext(), MaxVal)); 2552 BackedgeCheck = Builder.CreateAnd( 2553 BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero)); 2554 2555 EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck); 2556 } 2557 2558 return Builder.CreateOr(EndCheck, OfMul); 2559 } 2560 2561 Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred, 2562 Instruction *IP) { 2563 const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr()); 2564 Value *NSSWCheck = nullptr, *NUSWCheck = nullptr; 2565 2566 // Add a check for NUSW 2567 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW) 2568 NUSWCheck = generateOverflowCheck(A, IP, false); 2569 2570 // Add a check for NSSW 2571 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW) 2572 NSSWCheck = generateOverflowCheck(A, IP, true); 2573 2574 if (NUSWCheck && NSSWCheck) 2575 return Builder.CreateOr(NUSWCheck, NSSWCheck); 2576 2577 if (NUSWCheck) 2578 return NUSWCheck; 2579 2580 if (NSSWCheck) 2581 return NSSWCheck; 2582 2583 return ConstantInt::getFalse(IP->getContext()); 2584 } 2585 2586 Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union, 2587 Instruction *IP) { 2588 auto *BoolType = IntegerType::get(IP->getContext(), 1); 2589 Value *Check = ConstantInt::getNullValue(BoolType); 2590 2591 // Loop over all checks in this set. 2592 for (auto Pred : Union->getPredicates()) { 2593 auto *NextCheck = expandCodeForPredicate(Pred, IP); 2594 Builder.SetInsertPoint(IP); 2595 Check = Builder.CreateOr(Check, NextCheck); 2596 } 2597 2598 return Check; 2599 } 2600 2601 Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) { 2602 assert(PreserveLCSSA); 2603 SmallVector<Instruction *, 1> ToUpdate; 2604 2605 auto *OpV = User->getOperand(OpIdx); 2606 auto *OpI = dyn_cast<Instruction>(OpV); 2607 if (!OpI) 2608 return OpV; 2609 2610 Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent()); 2611 Loop *UseLoop = SE.LI.getLoopFor(User->getParent()); 2612 if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop)) 2613 return OpV; 2614 2615 ToUpdate.push_back(OpI); 2616 SmallVector<PHINode *, 16> PHIsToRemove; 2617 formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove); 2618 for (PHINode *PN : PHIsToRemove) { 2619 if (!PN->use_empty()) 2620 continue; 2621 InsertedValues.erase(PN); 2622 InsertedPostIncValues.erase(PN); 2623 PN->eraseFromParent(); 2624 } 2625 2626 return User->getOperand(OpIdx); 2627 } 2628 2629 namespace { 2630 // Search for a SCEV subexpression that is not safe to expand. Any expression 2631 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely 2632 // UDiv expressions. We don't know if the UDiv is derived from an IR divide 2633 // instruction, but the important thing is that we prove the denominator is 2634 // nonzero before expansion. 2635 // 2636 // IVUsers already checks that IV-derived expressions are safe. So this check is 2637 // only needed when the expression includes some subexpression that is not IV 2638 // derived. 2639 // 2640 // Currently, we only allow division by a nonzero constant here. If this is 2641 // inadequate, we could easily allow division by SCEVUnknown by using 2642 // ValueTracking to check isKnownNonZero(). 2643 // 2644 // We cannot generally expand recurrences unless the step dominates the loop 2645 // header. The expander handles the special case of affine recurrences by 2646 // scaling the recurrence outside the loop, but this technique isn't generally 2647 // applicable. Expanding a nested recurrence outside a loop requires computing 2648 // binomial coefficients. This could be done, but the recurrence has to be in a 2649 // perfectly reduced form, which can't be guaranteed. 2650 struct SCEVFindUnsafe { 2651 ScalarEvolution &SE; 2652 bool IsUnsafe; 2653 2654 SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {} 2655 2656 bool follow(const SCEV *S) { 2657 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 2658 const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS()); 2659 if (!SC || SC->getValue()->isZero()) { 2660 IsUnsafe = true; 2661 return false; 2662 } 2663 } 2664 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 2665 const SCEV *Step = AR->getStepRecurrence(SE); 2666 if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) { 2667 IsUnsafe = true; 2668 return false; 2669 } 2670 } 2671 return true; 2672 } 2673 bool isDone() const { return IsUnsafe; } 2674 }; 2675 } 2676 2677 namespace llvm { 2678 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) { 2679 SCEVFindUnsafe Search(SE); 2680 visitAll(S, Search); 2681 return !Search.IsUnsafe; 2682 } 2683 2684 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, 2685 ScalarEvolution &SE) { 2686 if (!isSafeToExpand(S, SE)) 2687 return false; 2688 // We have to prove that the expanded site of S dominates InsertionPoint. 2689 // This is easy when not in the same block, but hard when S is an instruction 2690 // to be expanded somewhere inside the same block as our insertion point. 2691 // What we really need here is something analogous to an OrderedBasicBlock, 2692 // but for the moment, we paper over the problem by handling two common and 2693 // cheap to check cases. 2694 if (SE.properlyDominates(S, InsertionPoint->getParent())) 2695 return true; 2696 if (SE.dominates(S, InsertionPoint->getParent())) { 2697 if (InsertionPoint->getParent()->getTerminator() == InsertionPoint) 2698 return true; 2699 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) 2700 if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue())) 2701 return true; 2702 } 2703 return false; 2704 } 2705 2706 void SCEVExpanderCleaner::cleanup() { 2707 // Result is used, nothing to remove. 2708 if (ResultUsed) 2709 return; 2710 2711 auto InsertedInstructions = Expander.getAllInsertedInstructions(); 2712 #ifndef NDEBUG 2713 SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(), 2714 InsertedInstructions.end()); 2715 (void)InsertedSet; 2716 #endif 2717 // Remove sets with value handles. 2718 Expander.clear(); 2719 2720 // Sort so that earlier instructions do not dominate later instructions. 2721 stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) { 2722 return DT.dominates(B, A); 2723 }); 2724 // Remove all inserted instructions. 2725 for (Instruction *I : InsertedInstructions) { 2726 2727 #ifndef NDEBUG 2728 assert(all_of(I->users(), 2729 [&InsertedSet](Value *U) { 2730 return InsertedSet.contains(cast<Instruction>(U)); 2731 }) && 2732 "removed instruction should only be used by instructions inserted " 2733 "during expansion"); 2734 #endif 2735 assert(!I->getType()->isVoidTy() && 2736 "inserted instruction should have non-void types"); 2737 I->replaceAllUsesWith(UndefValue::get(I->getType())); 2738 I->eraseFromParent(); 2739 } 2740 } 2741 } 2742