1309124Sdim//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file contains the implementation of the scalar evolution expander, 10193323Sed// which is used to generate the code corresponding to a given scalar evolution 11193323Sed// expression. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/Analysis/ScalarEvolutionExpander.h" 16276479Sdim#include "llvm/ADT/STLExtras.h" 17261991Sdim#include "llvm/ADT/SmallSet.h" 18276479Sdim#include "llvm/Analysis/InstructionSimplify.h" 19193323Sed#include "llvm/Analysis/LoopInfo.h" 20249423Sdim#include "llvm/Analysis/TargetTransformInfo.h" 21249423Sdim#include "llvm/IR/DataLayout.h" 22276479Sdim#include "llvm/IR/Dominators.h" 23249423Sdim#include "llvm/IR/IntrinsicInst.h" 24249423Sdim#include "llvm/IR/LLVMContext.h" 25288943Sdim#include "llvm/IR/Module.h" 26288943Sdim#include "llvm/IR/PatternMatch.h" 27226633Sdim#include "llvm/Support/Debug.h" 28288943Sdim#include "llvm/Support/raw_ostream.h" 29224145Sdim 30193323Sedusing namespace llvm; 31288943Sdimusing namespace PatternMatch; 32193323Sed 33210299Sed/// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP, 34210299Sed/// reusing an existing cast if a suitable one exists, moving an existing 35210299Sed/// cast if a suitable one exists but isn't in the right place, or 36210299Sed/// creating a new one. 37226633SdimValue *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, 38210299Sed Instruction::CastOps Op, 39210299Sed BasicBlock::iterator IP) { 40234353Sdim // This function must be called with the builder having a valid insertion 41234353Sdim // point. It doesn't need to be the actual IP where the uses of the returned 42234353Sdim // cast will be added, but it must dominate such IP. 43234353Sdim // We use this precondition to produce a cast that will dominate all its 44234353Sdim // uses. In particular, this is crucial for the case where the builder's 45234353Sdim // insertion point *is* the point where we were asked to put the cast. 46239462Sdim // Since we don't know the builder's insertion point is actually 47234353Sdim // where the uses will be added (only that it dominates it), we are 48234353Sdim // not allowed to move it. 49234353Sdim BasicBlock::iterator BIP = Builder.GetInsertPoint(); 50234353Sdim 51276479Sdim Instruction *Ret = nullptr; 52234353Sdim 53210299Sed // Check to see if there is already a cast! 54276479Sdim for (User *U : V->users()) 55210299Sed if (U->getType() == Ty) 56210299Sed if (CastInst *CI = dyn_cast<CastInst>(U)) 57210299Sed if (CI->getOpcode() == Op) { 58234353Sdim // If the cast isn't where we want it, create a new cast at IP. 59234353Sdim // Likewise, do not reuse a cast at BIP because it must dominate 60234353Sdim // instructions that might be inserted before BIP. 61234353Sdim if (BasicBlock::iterator(CI) != IP || BIP == IP) { 62210299Sed // Create a new cast, and leave the old cast in place in case 63353358Sdim // it is being used as an insert point. 64296417Sdim Ret = CastInst::Create(Op, V, Ty, "", &*IP); 65234353Sdim Ret->takeName(CI); 66234353Sdim CI->replaceAllUsesWith(Ret); 67234353Sdim break; 68210299Sed } 69234353Sdim Ret = CI; 70234353Sdim break; 71210299Sed } 72210299Sed 73210299Sed // Create a new cast. 74234353Sdim if (!Ret) 75296417Sdim Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP); 76234353Sdim 77234353Sdim // We assert at the end of the function since IP might point to an 78234353Sdim // instruction with different dominance properties than a cast 79234353Sdim // (an invoke for example) and not dominate BIP (but the cast does). 80296417Sdim assert(SE.DT.dominates(Ret, &*BIP)); 81234353Sdim 82234353Sdim rememberInstruction(Ret); 83234353Sdim return Ret; 84210299Sed} 85210299Sed 86296417Sdimstatic BasicBlock::iterator findInsertPointAfter(Instruction *I, 87296417Sdim BasicBlock *MustDominate) { 88296417Sdim BasicBlock::iterator IP = ++I->getIterator(); 89296417Sdim if (auto *II = dyn_cast<InvokeInst>(I)) 90296417Sdim IP = II->getNormalDest()->begin(); 91296417Sdim 92296417Sdim while (isa<PHINode>(IP)) 93296417Sdim ++IP; 94296417Sdim 95309124Sdim if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) { 96309124Sdim ++IP; 97309124Sdim } else if (isa<CatchSwitchInst>(IP)) { 98309124Sdim IP = MustDominate->getFirstInsertionPt(); 99309124Sdim } else { 100309124Sdim assert(!IP->isEHPad() && "unexpected eh pad!"); 101296417Sdim } 102296417Sdim 103296417Sdim return IP; 104296417Sdim} 105296417Sdim 106195340Sed/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 107195340Sed/// which must be possible with a noop cast, doing what we can to share 108195340Sed/// the casts. 109226633SdimValue *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) { 110195340Sed Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 111195340Sed assert((Op == Instruction::BitCast || 112195340Sed Op == Instruction::PtrToInt || 113195340Sed Op == Instruction::IntToPtr) && 114195340Sed "InsertNoopCastOfTo cannot perform non-noop casts!"); 115195340Sed assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 116195340Sed "InsertNoopCastOfTo cannot change sizes!"); 117195340Sed 118193323Sed // Short-circuit unnecessary bitcasts. 119234353Sdim if (Op == Instruction::BitCast) { 120234353Sdim if (V->getType() == Ty) 121234353Sdim return V; 122234353Sdim if (CastInst *CI = dyn_cast<CastInst>(V)) { 123234353Sdim if (CI->getOperand(0)->getType() == Ty) 124234353Sdim return CI->getOperand(0); 125234353Sdim } 126234353Sdim } 127193323Sed // Short-circuit unnecessary inttoptr<->ptrtoint casts. 128195340Sed if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && 129193323Sed SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 130193323Sed if (CastInst *CI = dyn_cast<CastInst>(V)) 131193323Sed if ((CI->getOpcode() == Instruction::PtrToInt || 132193323Sed CI->getOpcode() == Instruction::IntToPtr) && 133193323Sed SE.getTypeSizeInBits(CI->getType()) == 134193323Sed SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 135193323Sed return CI->getOperand(0); 136193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 137193323Sed if ((CE->getOpcode() == Instruction::PtrToInt || 138193323Sed CE->getOpcode() == Instruction::IntToPtr) && 139193323Sed SE.getTypeSizeInBits(CE->getType()) == 140193323Sed SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 141193323Sed return CE->getOperand(0); 142193323Sed } 143193323Sed 144210299Sed // Fold a cast of a constant. 145193323Sed if (Constant *C = dyn_cast<Constant>(V)) 146195340Sed return ConstantExpr::getCast(Op, C, Ty); 147198090Srdivacky 148210299Sed // Cast the argument at the beginning of the entry block, after 149210299Sed // any bitcasts of other arguments. 150193323Sed if (Argument *A = dyn_cast<Argument>(V)) { 151210299Sed BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin(); 152210299Sed while ((isa<BitCastInst>(IP) && 153210299Sed isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) && 154210299Sed cast<BitCastInst>(IP)->getOperand(0) != A) || 155296417Sdim isa<DbgInfoIntrinsic>(IP)) 156210299Sed ++IP; 157210299Sed return ReuseOrCreateCast(A, Ty, Op, IP); 158193323Sed } 159193323Sed 160210299Sed // Cast the instruction immediately after the instruction. 161193323Sed Instruction *I = cast<Instruction>(V); 162296417Sdim BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock()); 163210299Sed return ReuseOrCreateCast(I, Ty, Op, IP); 164193323Sed} 165193323Sed 166193323Sed/// InsertBinop - Insert the specified binary operator, doing a small amount 167353358Sdim/// of work to avoid inserting an obviously redundant operation, and hoisting 168353358Sdim/// to an outer loop when the opportunity is there and it is safe. 169195340SedValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, 170353358Sdim Value *LHS, Value *RHS, 171353358Sdim SCEV::NoWrapFlags Flags, bool IsSafeToHoist) { 172193323Sed // Fold a binop with constant operands. 173193323Sed if (Constant *CLHS = dyn_cast<Constant>(LHS)) 174193323Sed if (Constant *CRHS = dyn_cast<Constant>(RHS)) 175193323Sed return ConstantExpr::get(Opcode, CLHS, CRHS); 176193323Sed 177193323Sed // Do a quick scan to see if we have this binop nearby. If so, reuse it. 178193323Sed unsigned ScanLimit = 6; 179195340Sed BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 180195340Sed // Scanning starts from the last instruction before the insertion point. 181195340Sed BasicBlock::iterator IP = Builder.GetInsertPoint(); 182195340Sed if (IP != BlockBegin) { 183193323Sed --IP; 184193323Sed for (; ScanLimit; --IP, --ScanLimit) { 185204792Srdivacky // Don't count dbg.value against the ScanLimit, to avoid perturbing the 186204792Srdivacky // generated code. 187204792Srdivacky if (isa<DbgInfoIntrinsic>(IP)) 188204792Srdivacky ScanLimit++; 189327952Sdim 190353358Sdim auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) { 191353358Sdim // Ensure that no-wrap flags match. 192353358Sdim if (isa<OverflowingBinaryOperator>(I)) { 193353358Sdim if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW)) 194353358Sdim return true; 195353358Sdim if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW)) 196353358Sdim return true; 197353358Sdim } 198353358Sdim // Conservatively, do not use any instruction which has any of exact 199353358Sdim // flags installed. 200327952Sdim if (isa<PossiblyExactOperator>(I) && I->isExact()) 201327952Sdim return true; 202327952Sdim return false; 203327952Sdim }; 204193323Sed if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 205353358Sdim IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP)) 206296417Sdim return &*IP; 207193323Sed if (IP == BlockBegin) break; 208193323Sed } 209193323Sed } 210195340Sed 211204642Srdivacky // Save the original insertion point so we can restore it when we're done. 212261991Sdim DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc(); 213309124Sdim SCEVInsertPointGuard Guard(Builder, this); 214204642Srdivacky 215353358Sdim if (IsSafeToHoist) { 216353358Sdim // Move the insertion point out of as many loops as we can. 217353358Sdim while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { 218353358Sdim if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break; 219353358Sdim BasicBlock *Preheader = L->getLoopPreheader(); 220353358Sdim if (!Preheader) break; 221204642Srdivacky 222353358Sdim // Ok, move up a level. 223353358Sdim Builder.SetInsertPoint(Preheader->getTerminator()); 224353358Sdim } 225204642Srdivacky } 226204642Srdivacky 227193323Sed // If we haven't found this binop, insert it. 228226633Sdim Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS)); 229261991Sdim BO->setDebugLoc(Loc); 230353358Sdim if (Flags & SCEV::FlagNUW) 231353358Sdim BO->setHasNoUnsignedWrap(); 232353358Sdim if (Flags & SCEV::FlagNSW) 233353358Sdim BO->setHasNoSignedWrap(); 234202878Srdivacky rememberInstruction(BO); 235204642Srdivacky 236193323Sed return BO; 237193323Sed} 238193323Sed 239193323Sed/// FactorOutConstant - Test if S is divisible by Factor, using signed 240193323Sed/// division. If so, update S with Factor divided out and return true. 241204642Srdivacky/// S need not be evenly divisible if a reasonable remainder can be 242193323Sed/// computed. 243288943Sdimstatic bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder, 244288943Sdim const SCEV *Factor, ScalarEvolution &SE, 245288943Sdim const DataLayout &DL) { 246193323Sed // Everything is divisible by one. 247198090Srdivacky if (Factor->isOne()) 248193323Sed return true; 249193323Sed 250198090Srdivacky // x/x == 1. 251198090Srdivacky if (S == Factor) { 252207618Srdivacky S = SE.getConstant(S->getType(), 1); 253198090Srdivacky return true; 254198090Srdivacky } 255198090Srdivacky 256193323Sed // For a Constant, check for a multiple of the given factor. 257193323Sed if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 258198090Srdivacky // 0/x == 0. 259198090Srdivacky if (C->isZero()) 260193323Sed return true; 261198090Srdivacky // Check for divisibility. 262198090Srdivacky if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) { 263198090Srdivacky ConstantInt *CI = 264296417Sdim ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt())); 265198090Srdivacky // If the quotient is zero and the remainder is non-zero, reject 266198090Srdivacky // the value at this scale. It will be considered for subsequent 267198090Srdivacky // smaller scales. 268198090Srdivacky if (!CI->isZero()) { 269198090Srdivacky const SCEV *Div = SE.getConstant(CI); 270198090Srdivacky S = Div; 271296417Sdim Remainder = SE.getAddExpr( 272296417Sdim Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt()))); 273198090Srdivacky return true; 274198090Srdivacky } 275193323Sed } 276193323Sed } 277193323Sed 278193323Sed // In a Mul, check if there is a constant operand which is a multiple 279193323Sed // of the given factor. 280198090Srdivacky if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 281288943Sdim // Size is known, check if there is a constant operand which is a multiple 282288943Sdim // of the given factor. If so, we can factor it. 283288943Sdim const SCEVConstant *FC = cast<SCEVConstant>(Factor); 284288943Sdim if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 285296417Sdim if (!C->getAPInt().srem(FC->getAPInt())) { 286288943Sdim SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end()); 287296417Sdim NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt())); 288288943Sdim S = SE.getMulExpr(NewMulOps); 289288943Sdim return true; 290193323Sed } 291198090Srdivacky } 292193323Sed 293193323Sed // In an AddRec, check if both start and step are divisible. 294193323Sed if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 295198090Srdivacky const SCEV *Step = A->getStepRecurrence(SE); 296207618Srdivacky const SCEV *StepRem = SE.getConstant(Step->getType(), 0); 297276479Sdim if (!FactorOutConstant(Step, StepRem, Factor, SE, DL)) 298193323Sed return false; 299193323Sed if (!StepRem->isZero()) 300193323Sed return false; 301198090Srdivacky const SCEV *Start = A->getStart(); 302276479Sdim if (!FactorOutConstant(Start, Remainder, Factor, SE, DL)) 303193323Sed return false; 304261991Sdim S = SE.getAddRecExpr(Start, Step, A->getLoop(), 305261991Sdim A->getNoWrapFlags(SCEV::FlagNW)); 306193323Sed return true; 307193323Sed } 308193323Sed 309193323Sed return false; 310193323Sed} 311193323Sed 312198090Srdivacky/// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs 313198090Srdivacky/// is the number of SCEVAddRecExprs present, which are kept at the end of 314198090Srdivacky/// the list. 315193323Sed/// 316198090Srdivackystatic void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops, 317226633Sdim Type *Ty, 318198090Srdivacky ScalarEvolution &SE) { 319198090Srdivacky unsigned NumAddRecs = 0; 320198090Srdivacky for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i) 321198090Srdivacky ++NumAddRecs; 322198090Srdivacky // Group Ops into non-addrecs and addrecs. 323198090Srdivacky SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs); 324198090Srdivacky SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end()); 325198090Srdivacky // Let ScalarEvolution sort and simplify the non-addrecs list. 326198090Srdivacky const SCEV *Sum = NoAddRecs.empty() ? 327207618Srdivacky SE.getConstant(Ty, 0) : 328198090Srdivacky SE.getAddExpr(NoAddRecs); 329198090Srdivacky // If it returned an add, use the operands. Otherwise it simplified 330198090Srdivacky // the sum into a single value, so just use that. 331205407Srdivacky Ops.clear(); 332198090Srdivacky if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum)) 333210299Sed Ops.append(Add->op_begin(), Add->op_end()); 334205407Srdivacky else if (!Sum->isZero()) 335205407Srdivacky Ops.push_back(Sum); 336198090Srdivacky // Then append the addrecs. 337210299Sed Ops.append(AddRecs.begin(), AddRecs.end()); 338198090Srdivacky} 339198090Srdivacky 340198090Srdivacky/// SplitAddRecs - Flatten a list of add operands, moving addrec start values 341198090Srdivacky/// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}. 342198090Srdivacky/// This helps expose more opportunities for folding parts of the expressions 343198090Srdivacky/// into GEP indices. 344198090Srdivacky/// 345198090Srdivackystatic void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, 346226633Sdim Type *Ty, 347198090Srdivacky ScalarEvolution &SE) { 348198090Srdivacky // Find the addrecs. 349198090Srdivacky SmallVector<const SCEV *, 8> AddRecs; 350198090Srdivacky for (unsigned i = 0, e = Ops.size(); i != e; ++i) 351198090Srdivacky while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) { 352198090Srdivacky const SCEV *Start = A->getStart(); 353198090Srdivacky if (Start->isZero()) break; 354207618Srdivacky const SCEV *Zero = SE.getConstant(Ty, 0); 355198090Srdivacky AddRecs.push_back(SE.getAddRecExpr(Zero, 356198090Srdivacky A->getStepRecurrence(SE), 357221345Sdim A->getLoop(), 358261991Sdim A->getNoWrapFlags(SCEV::FlagNW))); 359198090Srdivacky if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { 360198090Srdivacky Ops[i] = Zero; 361210299Sed Ops.append(Add->op_begin(), Add->op_end()); 362198090Srdivacky e += Add->getNumOperands(); 363198090Srdivacky } else { 364198090Srdivacky Ops[i] = Start; 365198090Srdivacky } 366198090Srdivacky } 367198090Srdivacky if (!AddRecs.empty()) { 368198090Srdivacky // Add the addrecs onto the end of the list. 369210299Sed Ops.append(AddRecs.begin(), AddRecs.end()); 370198090Srdivacky // Resort the operand list, moving any constants to the front. 371198090Srdivacky SimplifyAddOperands(Ops, Ty, SE); 372198090Srdivacky } 373198090Srdivacky} 374198090Srdivacky 375198090Srdivacky/// expandAddToGEP - Expand an addition expression with a pointer type into 376198090Srdivacky/// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps 377198090Srdivacky/// BasicAliasAnalysis and other passes analyze the result. See the rules 378198090Srdivacky/// for getelementptr vs. inttoptr in 379198090Srdivacky/// http://llvm.org/docs/LangRef.html#pointeraliasing 380198090Srdivacky/// for details. 381198090Srdivacky/// 382202878Srdivacky/// Design note: The correctness of using getelementptr here depends on 383198090Srdivacky/// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as 384198090Srdivacky/// they may introduce pointer arithmetic which may not be safely converted 385198090Srdivacky/// into getelementptr. 386198090Srdivacky/// 387193323Sed/// Design note: It might seem desirable for this function to be more 388193323Sed/// loop-aware. If some of the indices are loop-invariant while others 389193323Sed/// aren't, it might seem desirable to emit multiple GEPs, keeping the 390193323Sed/// loop-invariant portions of the overall computation outside the loop. 391193323Sed/// However, there are a few reasons this is not done here. Hoisting simple 392193323Sed/// arithmetic is a low-level optimization that often isn't very 393193323Sed/// important until late in the optimization process. In fact, passes 394193323Sed/// like InstructionCombining will combine GEPs, even if it means 395193323Sed/// pushing loop-invariant computation down into loops, so even if the 396193323Sed/// GEPs were split here, the work would quickly be undone. The 397193323Sed/// LoopStrengthReduction pass, which is usually run quite late (and 398193323Sed/// after the last InstructionCombining pass), takes care of hoisting 399193323Sed/// loop-invariant portions of expressions, after considering what 400193323Sed/// can be folded using target addressing modes. 401193323Sed/// 402198090SrdivackyValue *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, 403198090Srdivacky const SCEV *const *op_end, 404226633Sdim PointerType *PTy, 405226633Sdim Type *Ty, 406193323Sed Value *V) { 407288943Sdim Type *OriginalElTy = PTy->getElementType(); 408288943Sdim Type *ElTy = OriginalElTy; 409193323Sed SmallVector<Value *, 4> GepIndices; 410198090Srdivacky SmallVector<const SCEV *, 8> Ops(op_begin, op_end); 411193323Sed bool AnyNonZeroIndices = false; 412193323Sed 413198090Srdivacky // Split AddRecs up into parts as either of the parts may be usable 414198090Srdivacky // without the other. 415198090Srdivacky SplitAddRecs(Ops, Ty, SE); 416198090Srdivacky 417360784Sdim Type *IntIdxTy = DL.getIndexType(PTy); 418261991Sdim 419200581Srdivacky // Descend down the pointer's type and attempt to convert the other 420193323Sed // operands into GEP indices, at each level. The first index in a GEP 421193323Sed // indexes into the array implied by the pointer operand; the rest of 422193323Sed // the indices index into the element or field type selected by the 423193323Sed // preceding index. 424193323Sed for (;;) { 425198090Srdivacky // If the scale size is not 0, attempt to factor out a scale for 426198090Srdivacky // array indexing. 427198090Srdivacky SmallVector<const SCEV *, 8> ScaledOps; 428203954Srdivacky if (ElTy->isSized()) { 429360784Sdim const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy); 430203954Srdivacky if (!ElSize->isZero()) { 431203954Srdivacky SmallVector<const SCEV *, 8> NewOps; 432296417Sdim for (const SCEV *Op : Ops) { 433207618Srdivacky const SCEV *Remainder = SE.getConstant(Ty, 0); 434288943Sdim if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) { 435203954Srdivacky // Op now has ElSize factored out. 436203954Srdivacky ScaledOps.push_back(Op); 437203954Srdivacky if (!Remainder->isZero()) 438203954Srdivacky NewOps.push_back(Remainder); 439203954Srdivacky AnyNonZeroIndices = true; 440203954Srdivacky } else { 441203954Srdivacky // The operand was not divisible, so add it to the list of operands 442203954Srdivacky // we'll scan next iteration. 443296417Sdim NewOps.push_back(Op); 444203954Srdivacky } 445193323Sed } 446203954Srdivacky // If we made any changes, update Ops. 447203954Srdivacky if (!ScaledOps.empty()) { 448203954Srdivacky Ops = NewOps; 449203954Srdivacky SimplifyAddOperands(Ops, Ty, SE); 450203954Srdivacky } 451193323Sed } 452193323Sed } 453198090Srdivacky 454198090Srdivacky // Record the scaled array index for this level of the type. If 455198090Srdivacky // we didn't find any operands that could be factored, tentatively 456198090Srdivacky // assume that element zero was selected (since the zero offset 457198090Srdivacky // would obviously be folded away). 458193323Sed Value *Scaled = ScaledOps.empty() ? 459193323Sed Constant::getNullValue(Ty) : 460193323Sed expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 461193323Sed GepIndices.push_back(Scaled); 462193323Sed 463193323Sed // Collect struct field index operands. 464226633Sdim while (StructType *STy = dyn_cast<StructType>(ElTy)) { 465198090Srdivacky bool FoundFieldNo = false; 466198090Srdivacky // An empty struct has no fields. 467198090Srdivacky if (STy->getNumElements() == 0) break; 468288943Sdim // Field offsets are known. See if a constant offset falls within any of 469288943Sdim // the struct fields. 470288943Sdim if (Ops.empty()) 471288943Sdim break; 472288943Sdim if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 473288943Sdim if (SE.getTypeSizeInBits(C->getType()) <= 64) { 474288943Sdim const StructLayout &SL = *DL.getStructLayout(STy); 475288943Sdim uint64_t FullOffset = C->getValue()->getZExtValue(); 476288943Sdim if (FullOffset < SL.getSizeInBytes()) { 477288943Sdim unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 478288943Sdim GepIndices.push_back( 479288943Sdim ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx)); 480288943Sdim ElTy = STy->getTypeAtIndex(ElIdx); 481288943Sdim Ops[0] = 482194612Sed SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 483288943Sdim AnyNonZeroIndices = true; 484288943Sdim FoundFieldNo = true; 485193323Sed } 486288943Sdim } 487198090Srdivacky // If no struct field offsets were found, tentatively assume that 488198090Srdivacky // field zero was selected (since the zero offset would obviously 489198090Srdivacky // be folded away). 490198090Srdivacky if (!FoundFieldNo) { 491198090Srdivacky ElTy = STy->getTypeAtIndex(0u); 492198090Srdivacky GepIndices.push_back( 493198090Srdivacky Constant::getNullValue(Type::getInt32Ty(Ty->getContext()))); 494198090Srdivacky } 495198090Srdivacky } 496193323Sed 497226633Sdim if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) 498193323Sed ElTy = ATy->getElementType(); 499198090Srdivacky else 500198090Srdivacky break; 501193323Sed } 502193323Sed 503204642Srdivacky // If none of the operands were convertible to proper GEP indices, cast 504193323Sed // the base to i8* and do an ugly getelementptr with that. It's still 505193323Sed // better than ptrtoint+arithmetic+inttoptr at least. 506193323Sed if (!AnyNonZeroIndices) { 507198090Srdivacky // Cast the base to i8*. 508193323Sed V = InsertNoopCastOfTo(V, 509198090Srdivacky Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace())); 510198090Srdivacky 511234353Sdim assert(!isa<Instruction>(V) || 512296417Sdim SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint())); 513234353Sdim 514198090Srdivacky // Expand the operands for a plain byte offset. 515194178Sed Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 516193323Sed 517193323Sed // Fold a GEP with constant operands. 518193323Sed if (Constant *CLHS = dyn_cast<Constant>(V)) 519193323Sed if (Constant *CRHS = dyn_cast<Constant>(Idx)) 520288943Sdim return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()), 521288943Sdim CLHS, CRHS); 522193323Sed 523193323Sed // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 524193323Sed unsigned ScanLimit = 6; 525195340Sed BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 526195340Sed // Scanning starts from the last instruction before the insertion point. 527195340Sed BasicBlock::iterator IP = Builder.GetInsertPoint(); 528195340Sed if (IP != BlockBegin) { 529193323Sed --IP; 530193323Sed for (; ScanLimit; --IP, --ScanLimit) { 531204792Srdivacky // Don't count dbg.value against the ScanLimit, to avoid perturbing the 532204792Srdivacky // generated code. 533204792Srdivacky if (isa<DbgInfoIntrinsic>(IP)) 534204792Srdivacky ScanLimit++; 535193323Sed if (IP->getOpcode() == Instruction::GetElementPtr && 536193323Sed IP->getOperand(0) == V && IP->getOperand(1) == Idx) 537296417Sdim return &*IP; 538193323Sed if (IP == BlockBegin) break; 539193323Sed } 540193323Sed } 541193323Sed 542204642Srdivacky // Save the original insertion point so we can restore it when we're done. 543309124Sdim SCEVInsertPointGuard Guard(Builder, this); 544204642Srdivacky 545204642Srdivacky // Move the insertion point out of as many loops as we can. 546296417Sdim while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { 547204642Srdivacky if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break; 548204642Srdivacky BasicBlock *Preheader = L->getLoopPreheader(); 549204642Srdivacky if (!Preheader) break; 550204642Srdivacky 551204642Srdivacky // Ok, move up a level. 552296417Sdim Builder.SetInsertPoint(Preheader->getTerminator()); 553204642Srdivacky } 554204642Srdivacky 555198090Srdivacky // Emit a GEP. 556288943Sdim Value *GEP = Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep"); 557202878Srdivacky rememberInstruction(GEP); 558204642Srdivacky 559193323Sed return GEP; 560193323Sed } 561193323Sed 562309124Sdim { 563309124Sdim SCEVInsertPointGuard Guard(Builder, this); 564204642Srdivacky 565309124Sdim // Move the insertion point out of as many loops as we can. 566309124Sdim while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { 567309124Sdim if (!L->isLoopInvariant(V)) break; 568204642Srdivacky 569314564Sdim bool AnyIndexNotLoopInvariant = any_of( 570314564Sdim GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); }); 571296417Sdim 572309124Sdim if (AnyIndexNotLoopInvariant) 573309124Sdim break; 574204642Srdivacky 575309124Sdim BasicBlock *Preheader = L->getLoopPreheader(); 576309124Sdim if (!Preheader) break; 577204642Srdivacky 578309124Sdim // Ok, move up a level. 579309124Sdim Builder.SetInsertPoint(Preheader->getTerminator()); 580309124Sdim } 581309124Sdim 582309124Sdim // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, 583309124Sdim // because ScalarEvolution may have changed the address arithmetic to 584309124Sdim // compute a value which is beyond the end of the allocated object. 585309124Sdim Value *Casted = V; 586309124Sdim if (V->getType() != PTy) 587309124Sdim Casted = InsertNoopCastOfTo(Casted, PTy); 588309124Sdim Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep"); 589309124Sdim Ops.push_back(SE.getUnknown(GEP)); 590309124Sdim rememberInstruction(GEP); 591204642Srdivacky } 592204642Srdivacky 593193323Sed return expand(SE.getAddExpr(Ops)); 594193323Sed} 595193323Sed 596341825SdimValue *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, 597341825Sdim Value *V) { 598341825Sdim const SCEV *const Ops[1] = {Op}; 599341825Sdim return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V); 600341825Sdim} 601341825Sdim 602204642Srdivacky/// PickMostRelevantLoop - Given two loops pick the one that's most relevant for 603204642Srdivacky/// SCEV expansion. If they are nested, this is the most nested. If they are 604204642Srdivacky/// neighboring, pick the later. 605204642Srdivackystatic const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B, 606204642Srdivacky DominatorTree &DT) { 607204642Srdivacky if (!A) return B; 608204642Srdivacky if (!B) return A; 609204642Srdivacky if (A->contains(B)) return B; 610204642Srdivacky if (B->contains(A)) return A; 611204642Srdivacky if (DT.dominates(A->getHeader(), B->getHeader())) return B; 612204642Srdivacky if (DT.dominates(B->getHeader(), A->getHeader())) return A; 613204642Srdivacky return A; // Arbitrarily break the tie. 614204642Srdivacky} 615193323Sed 616218893Sdim/// getRelevantLoop - Get the most relevant loop associated with the given 617204642Srdivacky/// expression, according to PickMostRelevantLoop. 618218893Sdimconst Loop *SCEVExpander::getRelevantLoop(const SCEV *S) { 619218893Sdim // Test whether we've already computed the most relevant loop for this SCEV. 620296417Sdim auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr)); 621218893Sdim if (!Pair.second) 622218893Sdim return Pair.first->second; 623218893Sdim 624204642Srdivacky if (isa<SCEVConstant>(S)) 625218893Sdim // A constant has no relevant loops. 626276479Sdim return nullptr; 627204642Srdivacky if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 628204642Srdivacky if (const Instruction *I = dyn_cast<Instruction>(U->getValue())) 629296417Sdim return Pair.first->second = SE.LI.getLoopFor(I->getParent()); 630218893Sdim // A non-instruction has no relevant loops. 631276479Sdim return nullptr; 632204642Srdivacky } 633204642Srdivacky if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) { 634276479Sdim const Loop *L = nullptr; 635204642Srdivacky if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 636204642Srdivacky L = AR->getLoop(); 637296417Sdim for (const SCEV *Op : N->operands()) 638296417Sdim L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT); 639218893Sdim return RelevantLoops[N] = L; 640204642Srdivacky } 641218893Sdim if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) { 642218893Sdim const Loop *Result = getRelevantLoop(C->getOperand()); 643218893Sdim return RelevantLoops[C] = Result; 644218893Sdim } 645218893Sdim if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 646296417Sdim const Loop *Result = PickMostRelevantLoop( 647296417Sdim getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT); 648218893Sdim return RelevantLoops[D] = Result; 649218893Sdim } 650204642Srdivacky llvm_unreachable("Unexpected SCEV type!"); 651204642Srdivacky} 652198090Srdivacky 653207618Srdivackynamespace { 654207618Srdivacky 655204642Srdivacky/// LoopCompare - Compare loops by PickMostRelevantLoop. 656204642Srdivackyclass LoopCompare { 657204642Srdivacky DominatorTree &DT; 658204642Srdivackypublic: 659204642Srdivacky explicit LoopCompare(DominatorTree &dt) : DT(dt) {} 660198090Srdivacky 661204642Srdivacky bool operator()(std::pair<const Loop *, const SCEV *> LHS, 662204642Srdivacky std::pair<const Loop *, const SCEV *> RHS) const { 663212904Sdim // Keep pointer operands sorted at the end. 664212904Sdim if (LHS.second->getType()->isPointerTy() != 665212904Sdim RHS.second->getType()->isPointerTy()) 666212904Sdim return LHS.second->getType()->isPointerTy(); 667212904Sdim 668204642Srdivacky // Compare loops with PickMostRelevantLoop. 669204642Srdivacky if (LHS.first != RHS.first) 670204642Srdivacky return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first; 671204642Srdivacky 672204642Srdivacky // If one operand is a non-constant negative and the other is not, 673204642Srdivacky // put the non-constant negative on the right so that a sub can 674204642Srdivacky // be used instead of a negate and add. 675234353Sdim if (LHS.second->isNonConstantNegative()) { 676234353Sdim if (!RHS.second->isNonConstantNegative()) 677204642Srdivacky return false; 678234353Sdim } else if (RHS.second->isNonConstantNegative()) 679204642Srdivacky return true; 680204642Srdivacky 681204642Srdivacky // Otherwise they are equivalent according to this comparison. 682204642Srdivacky return false; 683198090Srdivacky } 684204642Srdivacky}; 685193323Sed 686207618Srdivacky} 687207618Srdivacky 688204642SrdivackyValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 689226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 690193323Sed 691204642Srdivacky // Collect all the add operands in a loop, along with their associated loops. 692204642Srdivacky // Iterate in reverse so that constants are emitted last, all else equal, and 693204642Srdivacky // so that pointer operands are inserted first, which the code below relies on 694204642Srdivacky // to form more involved GEPs. 695204642Srdivacky SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops; 696204642Srdivacky for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()), 697204642Srdivacky E(S->op_begin()); I != E; ++I) 698218893Sdim OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); 699204642Srdivacky 700204642Srdivacky // Sort by loop. Use a stable sort so that constants follow non-constants and 701204642Srdivacky // pointer operands precede non-pointer operands. 702353358Sdim llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); 703204642Srdivacky 704204642Srdivacky // Emit instructions to add all the operands. Hoist as much as possible 705204642Srdivacky // out of loops, and form meaningful getelementptrs where possible. 706276479Sdim Value *Sum = nullptr; 707296417Sdim for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) { 708204642Srdivacky const Loop *CurLoop = I->first; 709204642Srdivacky const SCEV *Op = I->second; 710204642Srdivacky if (!Sum) { 711204642Srdivacky // This is the first operand. Just expand it. 712204642Srdivacky Sum = expand(Op); 713204642Srdivacky ++I; 714226633Sdim } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) { 715204642Srdivacky // The running sum expression is a pointer. Try to form a getelementptr 716204642Srdivacky // at this level with that as the base. 717204642Srdivacky SmallVector<const SCEV *, 4> NewOps; 718212904Sdim for (; I != E && I->first == CurLoop; ++I) { 719212904Sdim // If the operand is SCEVUnknown and not instructions, peek through 720212904Sdim // it, to enable more of it to be folded into the GEP. 721212904Sdim const SCEV *X = I->second; 722212904Sdim if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X)) 723212904Sdim if (!isa<Instruction>(U->getValue())) 724212904Sdim X = SE.getSCEV(U->getValue()); 725212904Sdim NewOps.push_back(X); 726212904Sdim } 727204642Srdivacky Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum); 728226633Sdim } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) { 729204642Srdivacky // The running sum is an integer, and there's a pointer at this level. 730207618Srdivacky // Try to form a getelementptr. If the running sum is instructions, 731207618Srdivacky // use a SCEVUnknown to avoid re-analyzing them. 732204642Srdivacky SmallVector<const SCEV *, 4> NewOps; 733207618Srdivacky NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) : 734207618Srdivacky SE.getSCEV(Sum)); 735204642Srdivacky for (++I; I != E && I->first == CurLoop; ++I) 736204642Srdivacky NewOps.push_back(I->second); 737204642Srdivacky Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op)); 738234353Sdim } else if (Op->isNonConstantNegative()) { 739204642Srdivacky // Instead of doing a negate and add, just do a subtract. 740202878Srdivacky Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty); 741204642Srdivacky Sum = InsertNoopCastOfTo(Sum, Ty); 742353358Sdim Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap, 743353358Sdim /*IsSafeToHoist*/ true); 744204642Srdivacky ++I; 745202878Srdivacky } else { 746204642Srdivacky // A simple add. 747202878Srdivacky Value *W = expandCodeFor(Op, Ty); 748204642Srdivacky Sum = InsertNoopCastOfTo(Sum, Ty); 749204642Srdivacky // Canonicalize a constant to the RHS. 750204642Srdivacky if (isa<Constant>(Sum)) std::swap(Sum, W); 751353358Sdim Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(), 752353358Sdim /*IsSafeToHoist*/ true); 753204642Srdivacky ++I; 754202878Srdivacky } 755193323Sed } 756204642Srdivacky 757204642Srdivacky return Sum; 758193323Sed} 759193323Sed 760193323SedValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 761226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 762193323Sed 763204642Srdivacky // Collect all the mul operands in a loop, along with their associated loops. 764204642Srdivacky // Iterate in reverse so that constants are emitted last, all else equal. 765204642Srdivacky SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops; 766204642Srdivacky for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()), 767204642Srdivacky E(S->op_begin()); I != E; ++I) 768218893Sdim OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); 769193323Sed 770204642Srdivacky // Sort by loop. Use a stable sort so that constants follow non-constants. 771353358Sdim llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); 772204642Srdivacky 773204642Srdivacky // Emit instructions to mul all the operands. Hoist as much as possible 774204642Srdivacky // out of loops. 775276479Sdim Value *Prod = nullptr; 776321369Sdim auto I = OpsAndLoops.begin(); 777321369Sdim 778321369Sdim // Expand the calculation of X pow N in the following manner: 779321369Sdim // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then: 780321369Sdim // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK). 781321369Sdim const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() { 782321369Sdim auto E = I; 783321369Sdim // Calculate how many times the same operand from the same loop is included 784321369Sdim // into this power. 785321369Sdim uint64_t Exponent = 0; 786321369Sdim const uint64_t MaxExponent = UINT64_MAX >> 1; 787321369Sdim // No one sane will ever try to calculate such huge exponents, but if we 788321369Sdim // need this, we stop on UINT64_MAX / 2 because we need to exit the loop 789321369Sdim // below when the power of 2 exceeds our Exponent, and we want it to be 790321369Sdim // 1u << 31 at most to not deal with unsigned overflow. 791321369Sdim while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) { 792321369Sdim ++Exponent; 793321369Sdim ++E; 794321369Sdim } 795321369Sdim assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?"); 796321369Sdim 797321369Sdim // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them 798321369Sdim // that are needed into the result. 799321369Sdim Value *P = expandCodeFor(I->second, Ty); 800321369Sdim Value *Result = nullptr; 801321369Sdim if (Exponent & 1) 802321369Sdim Result = P; 803321369Sdim for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) { 804353358Sdim P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap, 805353358Sdim /*IsSafeToHoist*/ true); 806321369Sdim if (Exponent & BinExp) 807353358Sdim Result = Result ? InsertBinop(Instruction::Mul, Result, P, 808353358Sdim SCEV::FlagAnyWrap, 809353358Sdim /*IsSafeToHoist*/ true) 810353358Sdim : P; 811321369Sdim } 812321369Sdim 813321369Sdim I = E; 814321369Sdim assert(Result && "Nothing was expanded?"); 815321369Sdim return Result; 816321369Sdim }; 817321369Sdim 818321369Sdim while (I != OpsAndLoops.end()) { 819204642Srdivacky if (!Prod) { 820204642Srdivacky // This is the first operand. Just expand it. 821321369Sdim Prod = ExpandOpBinPowN(); 822321369Sdim } else if (I->second->isAllOnesValue()) { 823204642Srdivacky // Instead of doing a multiply by negative one, just do a negate. 824204642Srdivacky Prod = InsertNoopCastOfTo(Prod, Ty); 825353358Sdim Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod, 826353358Sdim SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); 827321369Sdim ++I; 828204642Srdivacky } else { 829204642Srdivacky // A simple mul. 830321369Sdim Value *W = ExpandOpBinPowN(); 831204642Srdivacky Prod = InsertNoopCastOfTo(Prod, Ty); 832204642Srdivacky // Canonicalize a constant to the RHS. 833204642Srdivacky if (isa<Constant>(Prod)) std::swap(Prod, W); 834288943Sdim const APInt *RHS; 835288943Sdim if (match(W, m_Power2(RHS))) { 836288943Sdim // Canonicalize Prod*(1<<C) to Prod<<C. 837288943Sdim assert(!Ty->isVectorTy() && "vector types are not SCEVable"); 838353358Sdim auto NWFlags = S->getNoWrapFlags(); 839353358Sdim // clear nsw flag if shl will produce poison value. 840353358Sdim if (RHS->logBase2() == RHS->getBitWidth() - 1) 841353358Sdim NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW); 842288943Sdim Prod = InsertBinop(Instruction::Shl, Prod, 843353358Sdim ConstantInt::get(Ty, RHS->logBase2()), NWFlags, 844353358Sdim /*IsSafeToHoist*/ true); 845288943Sdim } else { 846353358Sdim Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(), 847353358Sdim /*IsSafeToHoist*/ true); 848288943Sdim } 849204642Srdivacky } 850193323Sed } 851193323Sed 852204642Srdivacky return Prod; 853193323Sed} 854193323Sed 855193323SedValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 856226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 857193323Sed 858194178Sed Value *LHS = expandCodeFor(S->getLHS(), Ty); 859193323Sed if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 860296417Sdim const APInt &RHS = SC->getAPInt(); 861193323Sed if (RHS.isPowerOf2()) 862193323Sed return InsertBinop(Instruction::LShr, LHS, 863353358Sdim ConstantInt::get(Ty, RHS.logBase2()), 864353358Sdim SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); 865193323Sed } 866193323Sed 867194178Sed Value *RHS = expandCodeFor(S->getRHS(), Ty); 868353358Sdim return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap, 869353358Sdim /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS())); 870193323Sed} 871193323Sed 872193323Sed/// Move parts of Base into Rest to leave Base with the minimal 873193323Sed/// expression that provides a pointer operand suitable for a 874193323Sed/// GEP expansion. 875198090Srdivackystatic void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, 876193323Sed ScalarEvolution &SE) { 877193323Sed while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 878193323Sed Base = A->getStart(); 879193323Sed Rest = SE.getAddExpr(Rest, 880207618Srdivacky SE.getAddRecExpr(SE.getConstant(A->getType(), 0), 881193323Sed A->getStepRecurrence(SE), 882221345Sdim A->getLoop(), 883261991Sdim A->getNoWrapFlags(SCEV::FlagNW))); 884193323Sed } 885193323Sed if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 886193323Sed Base = A->getOperand(A->getNumOperands()-1); 887198090Srdivacky SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end()); 888193323Sed NewAddOps.back() = Rest; 889193323Sed Rest = SE.getAddExpr(NewAddOps); 890193323Sed ExposePointerBase(Base, Rest, SE); 891193323Sed } 892193323Sed} 893193323Sed 894226633Sdim/// Determine if this is a well-behaved chain of instructions leading back to 895226633Sdim/// the PHI. If so, it may be reused by expanded expressions. 896226633Sdimbool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, 897226633Sdim const Loop *L) { 898226633Sdim if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) || 899226633Sdim (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV))) 900226633Sdim return false; 901226633Sdim // If any of the operands don't dominate the insert position, bail. 902226633Sdim // Addrec operands are always loop-invariant, so this can only happen 903226633Sdim // if there are instructions which haven't been hoisted. 904226633Sdim if (L == IVIncInsertLoop) { 905226633Sdim for (User::op_iterator OI = IncV->op_begin()+1, 906226633Sdim OE = IncV->op_end(); OI != OE; ++OI) 907226633Sdim if (Instruction *OInst = dyn_cast<Instruction>(OI)) 908296417Sdim if (!SE.DT.dominates(OInst, IVIncInsertPos)) 909226633Sdim return false; 910226633Sdim } 911226633Sdim // Advance to the next instruction. 912226633Sdim IncV = dyn_cast<Instruction>(IncV->getOperand(0)); 913226633Sdim if (!IncV) 914226633Sdim return false; 915226633Sdim 916226633Sdim if (IncV->mayHaveSideEffects()) 917226633Sdim return false; 918226633Sdim 919327952Sdim if (IncV == PN) 920226633Sdim return true; 921226633Sdim 922226633Sdim return isNormalAddRecExprPHI(PN, IncV, L); 923226633Sdim} 924226633Sdim 925234353Sdim/// getIVIncOperand returns an induction variable increment's induction 926234353Sdim/// variable operand. 927234353Sdim/// 928234353Sdim/// If allowScale is set, any type of GEP is allowed as long as the nonIV 929234353Sdim/// operands dominate InsertPos. 930234353Sdim/// 931234353Sdim/// If allowScale is not set, ensure that a GEP increment conforms to one of the 932234353Sdim/// simple patterns generated by getAddRecExprPHILiterally and 933234353Sdim/// expandAddtoGEP. If the pattern isn't recognized, return NULL. 934234353SdimInstruction *SCEVExpander::getIVIncOperand(Instruction *IncV, 935234353Sdim Instruction *InsertPos, 936234353Sdim bool allowScale) { 937234353Sdim if (IncV == InsertPos) 938276479Sdim return nullptr; 939234353Sdim 940226633Sdim switch (IncV->getOpcode()) { 941234353Sdim default: 942276479Sdim return nullptr; 943226633Sdim // Check for a simple Add/Sub or GEP of a loop invariant step. 944226633Sdim case Instruction::Add: 945234353Sdim case Instruction::Sub: { 946234353Sdim Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1)); 947296417Sdim if (!OInst || SE.DT.dominates(OInst, InsertPos)) 948234353Sdim return dyn_cast<Instruction>(IncV->getOperand(0)); 949276479Sdim return nullptr; 950234353Sdim } 951226633Sdim case Instruction::BitCast: 952234353Sdim return dyn_cast<Instruction>(IncV->getOperand(0)); 953234353Sdim case Instruction::GetElementPtr: 954296417Sdim for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) { 955226633Sdim if (isa<Constant>(*I)) 956226633Sdim continue; 957234353Sdim if (Instruction *OInst = dyn_cast<Instruction>(*I)) { 958296417Sdim if (!SE.DT.dominates(OInst, InsertPos)) 959276479Sdim return nullptr; 960234353Sdim } 961234353Sdim if (allowScale) { 962234353Sdim // allow any kind of GEP as long as it can be hoisted. 963234353Sdim continue; 964234353Sdim } 965234353Sdim // This must be a pointer addition of constants (pretty), which is already 966234353Sdim // handled, or some number of address-size elements (ugly). Ugly geps 967234353Sdim // have 2 operands. i1* is used by the expander to represent an 968234353Sdim // address-size element. 969226633Sdim if (IncV->getNumOperands() != 2) 970276479Sdim return nullptr; 971226633Sdim unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace(); 972226633Sdim if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS) 973226633Sdim && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS)) 974276479Sdim return nullptr; 975226633Sdim break; 976226633Sdim } 977234353Sdim return dyn_cast<Instruction>(IncV->getOperand(0)); 978226633Sdim } 979234353Sdim} 980234353Sdim 981309124Sdim/// If the insert point of the current builder or any of the builders on the 982309124Sdim/// stack of saved builders has 'I' as its insert point, update it to point to 983309124Sdim/// the instruction after 'I'. This is intended to be used when the instruction 984309124Sdim/// 'I' is being moved. If this fixup is not done and 'I' is moved to a 985309124Sdim/// different block, the inconsistent insert point (with a mismatched 986309124Sdim/// Instruction and Block) can lead to an instruction being inserted in a block 987309124Sdim/// other than its parent. 988309124Sdimvoid SCEVExpander::fixupInsertPoints(Instruction *I) { 989309124Sdim BasicBlock::iterator It(*I); 990309124Sdim BasicBlock::iterator NewInsertPt = std::next(It); 991309124Sdim if (Builder.GetInsertPoint() == It) 992309124Sdim Builder.SetInsertPoint(&*NewInsertPt); 993309124Sdim for (auto *InsertPtGuard : InsertPointGuards) 994309124Sdim if (InsertPtGuard->GetInsertPoint() == It) 995309124Sdim InsertPtGuard->SetInsertPoint(NewInsertPt); 996309124Sdim} 997309124Sdim 998234353Sdim/// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make 999234353Sdim/// it available to other uses in this loop. Recursively hoist any operands, 1000234353Sdim/// until we reach a value that dominates InsertPos. 1001234353Sdimbool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { 1002296417Sdim if (SE.DT.dominates(IncV, InsertPos)) 1003234353Sdim return true; 1004234353Sdim 1005234353Sdim // InsertPos must itself dominate IncV so that IncV's new position satisfies 1006234353Sdim // its existing users. 1007296417Sdim if (isa<PHINode>(InsertPos) || 1008296417Sdim !SE.DT.dominates(InsertPos->getParent(), IncV->getParent())) 1009226633Sdim return false; 1010234353Sdim 1011296417Sdim if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos)) 1012296417Sdim return false; 1013296417Sdim 1014234353Sdim // Check that the chain of IV operands leading back to Phi can be hoisted. 1015234353Sdim SmallVector<Instruction*, 4> IVIncs; 1016234353Sdim for(;;) { 1017234353Sdim Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true); 1018234353Sdim if (!Oper) 1019234353Sdim return false; 1020234353Sdim // IncV is safe to hoist. 1021234353Sdim IVIncs.push_back(IncV); 1022234353Sdim IncV = Oper; 1023296417Sdim if (SE.DT.dominates(IncV, InsertPos)) 1024234353Sdim break; 1025226633Sdim } 1026296417Sdim for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) { 1027309124Sdim fixupInsertPoints(*I); 1028234353Sdim (*I)->moveBefore(InsertPos); 1029234353Sdim } 1030234353Sdim return true; 1031226633Sdim} 1032226633Sdim 1033234353Sdim/// Determine if this cyclic phi is in a form that would have been generated by 1034234353Sdim/// LSR. We don't care if the phi was actually expanded in this pass, as long 1035234353Sdim/// as it is in a low-cost form, for example, no implied multiplication. This 1036234353Sdim/// should match any patterns generated by getAddRecExprPHILiterally and 1037234353Sdim/// expandAddtoGEP. 1038234353Sdimbool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, 1039234353Sdim const Loop *L) { 1040234353Sdim for(Instruction *IVOper = IncV; 1041234353Sdim (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(), 1042234353Sdim /*allowScale=*/false));) { 1043234353Sdim if (IVOper == PN) 1044234353Sdim return true; 1045234353Sdim } 1046234353Sdim return false; 1047234353Sdim} 1048234353Sdim 1049234353Sdim/// expandIVInc - Expand an IV increment at Builder's current InsertPos. 1050234353Sdim/// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may 1051234353Sdim/// need to materialize IV increments elsewhere to handle difficult situations. 1052234353SdimValue *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L, 1053234353Sdim Type *ExpandTy, Type *IntTy, 1054234353Sdim bool useSubtract) { 1055234353Sdim Value *IncV; 1056234353Sdim // If the PHI is a pointer, use a GEP, otherwise use an add or sub. 1057234353Sdim if (ExpandTy->isPointerTy()) { 1058234353Sdim PointerType *GEPPtrTy = cast<PointerType>(ExpandTy); 1059234353Sdim // If the step isn't constant, don't use an implicitly scaled GEP, because 1060234353Sdim // that would require a multiply inside the loop. 1061234353Sdim if (!isa<ConstantInt>(StepV)) 1062234353Sdim GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()), 1063234353Sdim GEPPtrTy->getAddressSpace()); 1064341825Sdim IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN); 1065234353Sdim if (IncV->getType() != PN->getType()) { 1066234353Sdim IncV = Builder.CreateBitCast(IncV, PN->getType()); 1067234353Sdim rememberInstruction(IncV); 1068234353Sdim } 1069234353Sdim } else { 1070234353Sdim IncV = useSubtract ? 1071234353Sdim Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") : 1072234353Sdim Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next"); 1073234353Sdim rememberInstruction(IncV); 1074234353Sdim } 1075234353Sdim return IncV; 1076234353Sdim} 1077234353Sdim 1078341825Sdim/// Hoist the addrec instruction chain rooted in the loop phi above the 1079276479Sdim/// position. This routine assumes that this is possible (has been checked). 1080309124Sdimvoid SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, 1081309124Sdim Instruction *Pos, PHINode *LoopPhi) { 1082276479Sdim do { 1083276479Sdim if (DT->dominates(InstToHoist, Pos)) 1084276479Sdim break; 1085276479Sdim // Make sure the increment is where we want it. But don't move it 1086276479Sdim // down past a potential existing post-inc user. 1087309124Sdim fixupInsertPoints(InstToHoist); 1088276479Sdim InstToHoist->moveBefore(Pos); 1089276479Sdim Pos = InstToHoist; 1090276479Sdim InstToHoist = cast<Instruction>(InstToHoist->getOperand(0)); 1091276479Sdim } while (InstToHoist != LoopPhi); 1092276479Sdim} 1093276479Sdim 1094341825Sdim/// Check whether we can cheaply express the requested SCEV in terms of 1095296417Sdim/// the available PHI SCEV by truncation and/or inversion of the step. 1096276479Sdimstatic bool canBeCheaplyTransformed(ScalarEvolution &SE, 1097276479Sdim const SCEVAddRecExpr *Phi, 1098276479Sdim const SCEVAddRecExpr *Requested, 1099276479Sdim bool &InvertStep) { 1100276479Sdim Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType()); 1101276479Sdim Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType()); 1102276479Sdim 1103276479Sdim if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth()) 1104276479Sdim return false; 1105276479Sdim 1106276479Sdim // Try truncate it if necessary. 1107276479Sdim Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy)); 1108276479Sdim if (!Phi) 1109276479Sdim return false; 1110276479Sdim 1111276479Sdim // Check whether truncation will help. 1112276479Sdim if (Phi == Requested) { 1113276479Sdim InvertStep = false; 1114276479Sdim return true; 1115276479Sdim } 1116276479Sdim 1117276479Sdim // Check whether inverting will help: {R,+,-1} == R - {0,+,1}. 1118276479Sdim if (SE.getAddExpr(Requested->getStart(), 1119276479Sdim SE.getNegativeSCEV(Requested)) == Phi) { 1120276479Sdim InvertStep = true; 1121276479Sdim return true; 1122276479Sdim } 1123276479Sdim 1124276479Sdim return false; 1125276479Sdim} 1126276479Sdim 1127288943Sdimstatic bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) { 1128288943Sdim if (!isa<IntegerType>(AR->getType())) 1129288943Sdim return false; 1130288943Sdim 1131288943Sdim unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth(); 1132288943Sdim Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2); 1133288943Sdim const SCEV *Step = AR->getStepRecurrence(SE); 1134288943Sdim const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy), 1135288943Sdim SE.getSignExtendExpr(AR, WideTy)); 1136288943Sdim const SCEV *ExtendAfterOp = 1137288943Sdim SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy); 1138288943Sdim return ExtendAfterOp == OpAfterExtend; 1139288943Sdim} 1140288943Sdim 1141288943Sdimstatic bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) { 1142288943Sdim if (!isa<IntegerType>(AR->getType())) 1143288943Sdim return false; 1144288943Sdim 1145288943Sdim unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth(); 1146288943Sdim Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2); 1147288943Sdim const SCEV *Step = AR->getStepRecurrence(SE); 1148288943Sdim const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy), 1149288943Sdim SE.getZeroExtendExpr(AR, WideTy)); 1150288943Sdim const SCEV *ExtendAfterOp = 1151288943Sdim SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy); 1152288943Sdim return ExtendAfterOp == OpAfterExtend; 1153288943Sdim} 1154288943Sdim 1155202878Srdivacky/// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand 1156202878Srdivacky/// the base addrec, which is the addrec without any non-loop-dominating 1157202878Srdivacky/// values, and return the PHI. 1158202878SrdivackyPHINode * 1159202878SrdivackySCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, 1160202878Srdivacky const Loop *L, 1161226633Sdim Type *ExpandTy, 1162276479Sdim Type *IntTy, 1163276479Sdim Type *&TruncTy, 1164276479Sdim bool &InvertStep) { 1165224145Sdim assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position"); 1166224145Sdim 1167202878Srdivacky // Reuse a previously-inserted PHI, if present. 1168226633Sdim BasicBlock *LatchBlock = L->getLoopLatch(); 1169226633Sdim if (LatchBlock) { 1170276479Sdim PHINode *AddRecPhiMatch = nullptr; 1171276479Sdim Instruction *IncV = nullptr; 1172276479Sdim TruncTy = nullptr; 1173276479Sdim InvertStep = false; 1174276479Sdim 1175276479Sdim // Only try partially matching scevs that need truncation and/or 1176276479Sdim // step-inversion if we know this loop is outside the current loop. 1177296417Sdim bool TryNonMatchingSCEV = 1178296417Sdim IVIncInsertLoop && 1179296417Sdim SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader()); 1180276479Sdim 1181327952Sdim for (PHINode &PN : L->getHeader()->phis()) { 1182327952Sdim if (!SE.isSCEVable(PN.getType())) 1183226633Sdim continue; 1184202878Srdivacky 1185327952Sdim const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN)); 1186276479Sdim if (!PhiSCEV) 1187276479Sdim continue; 1188226633Sdim 1189276479Sdim bool IsMatchingSCEV = PhiSCEV == Normalized; 1190276479Sdim // We only handle truncation and inversion of phi recurrences for the 1191276479Sdim // expanded expression if the expanded expression's loop dominates the 1192276479Sdim // loop we insert to. Check now, so we can bail out early. 1193276479Sdim if (!IsMatchingSCEV && !TryNonMatchingSCEV) 1194276479Sdim continue; 1195276479Sdim 1196341825Sdim // TODO: this possibly can be reworked to avoid this cast at all. 1197276479Sdim Instruction *TempIncV = 1198341825Sdim dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock)); 1199341825Sdim if (!TempIncV) 1200341825Sdim continue; 1201276479Sdim 1202276479Sdim // Check whether we can reuse this PHI node. 1203226633Sdim if (LSRMode) { 1204327952Sdim if (!isExpandedAddRecExprPHI(&PN, TempIncV, L)) 1205226633Sdim continue; 1206276479Sdim if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos)) 1207234353Sdim continue; 1208276479Sdim } else { 1209327952Sdim if (!isNormalAddRecExprPHI(&PN, TempIncV, L)) 1210226633Sdim continue; 1211226633Sdim } 1212276479Sdim 1213276479Sdim // Stop if we have found an exact match SCEV. 1214276479Sdim if (IsMatchingSCEV) { 1215276479Sdim IncV = TempIncV; 1216276479Sdim TruncTy = nullptr; 1217276479Sdim InvertStep = false; 1218327952Sdim AddRecPhiMatch = &PN; 1219276479Sdim break; 1220276479Sdim } 1221276479Sdim 1222276479Sdim // Try whether the phi can be translated into the requested form 1223276479Sdim // (truncated and/or offset by a constant). 1224276479Sdim if ((!TruncTy || InvertStep) && 1225276479Sdim canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) { 1226276479Sdim // Record the phi node. But don't stop we might find an exact match 1227276479Sdim // later. 1228327952Sdim AddRecPhiMatch = &PN; 1229276479Sdim IncV = TempIncV; 1230276479Sdim TruncTy = SE.getEffectiveSCEVType(Normalized->getType()); 1231276479Sdim } 1232276479Sdim } 1233276479Sdim 1234276479Sdim if (AddRecPhiMatch) { 1235276479Sdim // Potentially, move the increment. We have made sure in 1236276479Sdim // isExpandedAddRecExprPHI or hoistIVInc that this is possible. 1237276479Sdim if (L == IVIncInsertLoop) 1238296417Sdim hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch); 1239276479Sdim 1240226633Sdim // Ok, the add recurrence looks usable. 1241226633Sdim // Remember this PHI, even in post-inc mode. 1242276479Sdim InsertedValues.insert(AddRecPhiMatch); 1243226633Sdim // Remember the increment. 1244226633Sdim rememberInstruction(IncV); 1245276479Sdim return AddRecPhiMatch; 1246226633Sdim } 1247226633Sdim } 1248203954Srdivacky 1249202878Srdivacky // Save the original insertion point so we can restore it when we're done. 1250309124Sdim SCEVInsertPointGuard Guard(Builder, this); 1251202878Srdivacky 1252234353Sdim // Another AddRec may need to be recursively expanded below. For example, if 1253234353Sdim // this AddRec is quadratic, the StepV may itself be an AddRec in this 1254234353Sdim // loop. Remove this loop from the PostIncLoops set before expanding such 1255234353Sdim // AddRecs. Otherwise, we cannot find a valid position for the step 1256234353Sdim // (i.e. StepV can never dominate its loop header). Ideally, we could do 1257234353Sdim // SavedIncLoops.swap(PostIncLoops), but we generally have a single element, 1258234353Sdim // so it's not worth implementing SmallPtrSet::swap. 1259234353Sdim PostIncLoopSet SavedPostIncLoops = PostIncLoops; 1260234353Sdim PostIncLoops.clear(); 1261234353Sdim 1262314564Sdim // Expand code for the start value into the loop preheader. 1263314564Sdim assert(L->getLoopPreheader() && 1264314564Sdim "Can't expand add recurrences without a loop preheader!"); 1265314564Sdim Value *StartV = expandCodeFor(Normalized->getStart(), ExpandTy, 1266314564Sdim L->getLoopPreheader()->getTerminator()); 1267202878Srdivacky 1268314564Sdim // StartV must have been be inserted into L's preheader to dominate the new 1269314564Sdim // phi. 1270224145Sdim assert(!isa<Instruction>(StartV) || 1271296417Sdim SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), 1272296417Sdim L->getHeader())); 1273224145Sdim 1274234353Sdim // Expand code for the step value. Do this before creating the PHI so that PHI 1275234353Sdim // reuse code doesn't see an incomplete PHI. 1276202878Srdivacky const SCEV *Step = Normalized->getStepRecurrence(SE); 1277234353Sdim // If the stride is negative, insert a sub instead of an add for the increment 1278234353Sdim // (unless it's a constant, because subtracts of constants are canonicalized 1279234353Sdim // to adds). 1280234353Sdim bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative(); 1281234353Sdim if (useSubtract) 1282202878Srdivacky Step = SE.getNegativeSCEV(Step); 1283234353Sdim // Expand the step somewhere that dominates the loop header. 1284296417Sdim Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front()); 1285202878Srdivacky 1286288943Sdim // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if 1287288943Sdim // we actually do emit an addition. It does not apply if we emit a 1288288943Sdim // subtraction. 1289288943Sdim bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized); 1290288943Sdim bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized); 1291288943Sdim 1292202878Srdivacky // Create the PHI. 1293221345Sdim BasicBlock *Header = L->getHeader(); 1294221345Sdim Builder.SetInsertPoint(Header, Header->begin()); 1295221345Sdim pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); 1296224145Sdim PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE), 1297224145Sdim Twine(IVName) + ".iv"); 1298202878Srdivacky rememberInstruction(PN); 1299202878Srdivacky 1300202878Srdivacky // Create the step instructions and populate the PHI. 1301221345Sdim for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { 1302202878Srdivacky BasicBlock *Pred = *HPI; 1303202878Srdivacky 1304202878Srdivacky // Add a start value. 1305202878Srdivacky if (!L->contains(Pred)) { 1306202878Srdivacky PN->addIncoming(StartV, Pred); 1307202878Srdivacky continue; 1308202878Srdivacky } 1309202878Srdivacky 1310234353Sdim // Create a step value and add it to the PHI. 1311234353Sdim // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the 1312234353Sdim // instructions at IVIncInsertPos. 1313202878Srdivacky Instruction *InsertPos = L == IVIncInsertLoop ? 1314202878Srdivacky IVIncInsertPos : Pred->getTerminator(); 1315224145Sdim Builder.SetInsertPoint(InsertPos); 1316234353Sdim Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); 1317288943Sdim 1318261991Sdim if (isa<OverflowingBinaryOperator>(IncV)) { 1319288943Sdim if (IncrementIsNUW) 1320261991Sdim cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap(); 1321288943Sdim if (IncrementIsNSW) 1322261991Sdim cast<BinaryOperator>(IncV)->setHasNoSignedWrap(); 1323261991Sdim } 1324202878Srdivacky PN->addIncoming(IncV, Pred); 1325202878Srdivacky } 1326202878Srdivacky 1327234353Sdim // After expanding subexpressions, restore the PostIncLoops set so the caller 1328234353Sdim // can ensure that IVIncrement dominates the current uses. 1329234353Sdim PostIncLoops = SavedPostIncLoops; 1330234353Sdim 1331202878Srdivacky // Remember this PHI, even in post-inc mode. 1332202878Srdivacky InsertedValues.insert(PN); 1333202878Srdivacky 1334202878Srdivacky return PN; 1335202878Srdivacky} 1336202878Srdivacky 1337202878SrdivackyValue *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { 1338226633Sdim Type *STy = S->getType(); 1339226633Sdim Type *IntTy = SE.getEffectiveSCEVType(STy); 1340202878Srdivacky const Loop *L = S->getLoop(); 1341202878Srdivacky 1342202878Srdivacky // Determine a normalized form of this expression, which is the expression 1343202878Srdivacky // before any post-inc adjustment is made. 1344202878Srdivacky const SCEVAddRecExpr *Normalized = S; 1345207618Srdivacky if (PostIncLoops.count(L)) { 1346207618Srdivacky PostIncLoopSet Loops; 1347207618Srdivacky Loops.insert(L); 1348321369Sdim Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE)); 1349202878Srdivacky } 1350202878Srdivacky 1351202878Srdivacky // Strip off any non-loop-dominating component from the addrec start. 1352202878Srdivacky const SCEV *Start = Normalized->getStart(); 1353276479Sdim const SCEV *PostLoopOffset = nullptr; 1354218893Sdim if (!SE.properlyDominates(Start, L->getHeader())) { 1355202878Srdivacky PostLoopOffset = Start; 1356207618Srdivacky Start = SE.getConstant(Normalized->getType(), 0); 1357221345Sdim Normalized = cast<SCEVAddRecExpr>( 1358221345Sdim SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE), 1359221345Sdim Normalized->getLoop(), 1360261991Sdim Normalized->getNoWrapFlags(SCEV::FlagNW))); 1361202878Srdivacky } 1362202878Srdivacky 1363202878Srdivacky // Strip off any non-loop-dominating component from the addrec step. 1364202878Srdivacky const SCEV *Step = Normalized->getStepRecurrence(SE); 1365276479Sdim const SCEV *PostLoopScale = nullptr; 1366218893Sdim if (!SE.dominates(Step, L->getHeader())) { 1367202878Srdivacky PostLoopScale = Step; 1368207618Srdivacky Step = SE.getConstant(Normalized->getType(), 1); 1369309124Sdim if (!Start->isZero()) { 1370309124Sdim // The normalization below assumes that Start is constant zero, so if 1371309124Sdim // it isn't re-associate Start to PostLoopOffset. 1372309124Sdim assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?"); 1373309124Sdim PostLoopOffset = Start; 1374309124Sdim Start = SE.getConstant(Normalized->getType(), 0); 1375309124Sdim } 1376202878Srdivacky Normalized = 1377261991Sdim cast<SCEVAddRecExpr>(SE.getAddRecExpr( 1378261991Sdim Start, Step, Normalized->getLoop(), 1379261991Sdim Normalized->getNoWrapFlags(SCEV::FlagNW))); 1380202878Srdivacky } 1381202878Srdivacky 1382202878Srdivacky // Expand the core addrec. If we need post-loop scaling, force it to 1383202878Srdivacky // expand to an integer type to avoid the need for additional casting. 1384226633Sdim Type *ExpandTy = PostLoopScale ? IntTy : STy; 1385321369Sdim // We can't use a pointer type for the addrec if the pointer type is 1386321369Sdim // non-integral. 1387321369Sdim Type *AddRecPHIExpandTy = 1388321369Sdim DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy; 1389321369Sdim 1390276479Sdim // In some cases, we decide to reuse an existing phi node but need to truncate 1391276479Sdim // it and/or invert the step. 1392276479Sdim Type *TruncTy = nullptr; 1393276479Sdim bool InvertStep = false; 1394321369Sdim PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy, 1395321369Sdim IntTy, TruncTy, InvertStep); 1396202878Srdivacky 1397204642Srdivacky // Accommodate post-inc mode, if necessary. 1398202878Srdivacky Value *Result; 1399207618Srdivacky if (!PostIncLoops.count(L)) 1400202878Srdivacky Result = PN; 1401202878Srdivacky else { 1402202878Srdivacky // In PostInc mode, use the post-incremented value. 1403202878Srdivacky BasicBlock *LatchBlock = L->getLoopLatch(); 1404202878Srdivacky assert(LatchBlock && "PostInc mode requires a unique loop latch!"); 1405202878Srdivacky Result = PN->getIncomingValueForBlock(LatchBlock); 1406226633Sdim 1407226633Sdim // For an expansion to use the postinc form, the client must call 1408226633Sdim // expandCodeFor with an InsertPoint that is either outside the PostIncLoop 1409226633Sdim // or dominated by IVIncInsertPos. 1410296417Sdim if (isa<Instruction>(Result) && 1411296417Sdim !SE.DT.dominates(cast<Instruction>(Result), 1412296417Sdim &*Builder.GetInsertPoint())) { 1413234353Sdim // The induction variable's postinc expansion does not dominate this use. 1414234353Sdim // IVUsers tries to prevent this case, so it is rare. However, it can 1415234353Sdim // happen when an IVUser outside the loop is not dominated by the latch 1416234353Sdim // block. Adjusting IVIncInsertPos before expansion begins cannot handle 1417341825Sdim // all cases. Consider a phi outside whose operand is replaced during 1418234353Sdim // expansion with the value of the postinc user. Without fundamentally 1419234353Sdim // changing the way postinc users are tracked, the only remedy is 1420234353Sdim // inserting an extra IV increment. StepV might fold into PostLoopOffset, 1421234353Sdim // but hopefully expandCodeFor handles that. 1422234353Sdim bool useSubtract = 1423234353Sdim !ExpandTy->isPointerTy() && Step->isNonConstantNegative(); 1424234353Sdim if (useSubtract) 1425234353Sdim Step = SE.getNegativeSCEV(Step); 1426261991Sdim Value *StepV; 1427261991Sdim { 1428261991Sdim // Expand the step somewhere that dominates the loop header. 1429309124Sdim SCEVInsertPointGuard Guard(Builder, this); 1430296417Sdim StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front()); 1431261991Sdim } 1432234353Sdim Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); 1433234353Sdim } 1434202878Srdivacky } 1435202878Srdivacky 1436276479Sdim // We have decided to reuse an induction variable of a dominating loop. Apply 1437341825Sdim // truncation and/or inversion of the step. 1438276479Sdim if (TruncTy) { 1439276479Sdim Type *ResTy = Result->getType(); 1440276479Sdim // Normalize the result type. 1441276479Sdim if (ResTy != SE.getEffectiveSCEVType(ResTy)) 1442276479Sdim Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy)); 1443276479Sdim // Truncate the result. 1444276479Sdim if (TruncTy != Result->getType()) { 1445276479Sdim Result = Builder.CreateTrunc(Result, TruncTy); 1446276479Sdim rememberInstruction(Result); 1447276479Sdim } 1448276479Sdim // Invert the result. 1449276479Sdim if (InvertStep) { 1450276479Sdim Result = Builder.CreateSub(expandCodeFor(Normalized->getStart(), TruncTy), 1451276479Sdim Result); 1452276479Sdim rememberInstruction(Result); 1453276479Sdim } 1454276479Sdim } 1455276479Sdim 1456202878Srdivacky // Re-apply any non-loop-dominating scale. 1457202878Srdivacky if (PostLoopScale) { 1458261991Sdim assert(S->isAffine() && "Can't linearly scale non-affine recurrences."); 1459203954Srdivacky Result = InsertNoopCastOfTo(Result, IntTy); 1460202878Srdivacky Result = Builder.CreateMul(Result, 1461202878Srdivacky expandCodeFor(PostLoopScale, IntTy)); 1462202878Srdivacky rememberInstruction(Result); 1463202878Srdivacky } 1464202878Srdivacky 1465202878Srdivacky // Re-apply any non-loop-dominating offset. 1466202878Srdivacky if (PostLoopOffset) { 1467226633Sdim if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) { 1468321369Sdim if (Result->getType()->isIntegerTy()) { 1469321369Sdim Value *Base = expandCodeFor(PostLoopOffset, ExpandTy); 1470341825Sdim Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base); 1471321369Sdim } else { 1472341825Sdim Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result); 1473321369Sdim } 1474202878Srdivacky } else { 1475203954Srdivacky Result = InsertNoopCastOfTo(Result, IntTy); 1476202878Srdivacky Result = Builder.CreateAdd(Result, 1477202878Srdivacky expandCodeFor(PostLoopOffset, IntTy)); 1478202878Srdivacky rememberInstruction(Result); 1479202878Srdivacky } 1480202878Srdivacky } 1481202878Srdivacky 1482202878Srdivacky return Result; 1483202878Srdivacky} 1484202878Srdivacky 1485193323SedValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 1486360784Sdim // In canonical mode we compute the addrec as an expression of a canonical IV 1487360784Sdim // using evaluateAtIteration and expand the resulting SCEV expression. This 1488360784Sdim // way we avoid introducing new IVs to carry on the comutation of the addrec 1489360784Sdim // throughout the loop. 1490360784Sdim // 1491360784Sdim // For nested addrecs evaluateAtIteration might need a canonical IV of a 1492360784Sdim // type wider than the addrec itself. Emitting a canonical IV of the 1493360784Sdim // proper type might produce non-legal types, for example expanding an i64 1494360784Sdim // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall 1495360784Sdim // back to non-canonical mode for nested addrecs. 1496360784Sdim if (!CanonicalMode || (S->getNumOperands() > 2)) 1497360784Sdim return expandAddRecExprLiterally(S); 1498202878Srdivacky 1499226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1500193323Sed const Loop *L = S->getLoop(); 1501193323Sed 1502194178Sed // First check for an existing canonical IV in a suitable type. 1503276479Sdim PHINode *CanonicalIV = nullptr; 1504194178Sed if (PHINode *PN = L->getCanonicalInductionVariable()) 1505212904Sdim if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 1506194178Sed CanonicalIV = PN; 1507194178Sed 1508194178Sed // Rewrite an AddRec in terms of the canonical induction variable, if 1509194178Sed // its type is more narrow. 1510194178Sed if (CanonicalIV && 1511194178Sed SE.getTypeSizeInBits(CanonicalIV->getType()) > 1512194178Sed SE.getTypeSizeInBits(Ty)) { 1513205407Srdivacky SmallVector<const SCEV *, 4> NewOps(S->getNumOperands()); 1514205407Srdivacky for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i) 1515205407Srdivacky NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType()); 1516221345Sdim Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(), 1517261991Sdim S->getNoWrapFlags(SCEV::FlagNW))); 1518194178Sed BasicBlock::iterator NewInsertPt = 1519296417Sdim findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock()); 1520276479Sdim V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr, 1521296417Sdim &*NewInsertPt); 1522194178Sed return V; 1523194178Sed } 1524194178Sed 1525193323Sed // {X,+,F} --> X + {0,+,F} 1526193323Sed if (!S->getStart()->isZero()) { 1527205407Srdivacky SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end()); 1528207618Srdivacky NewOps[0] = SE.getConstant(Ty, 0); 1529261991Sdim const SCEV *Rest = SE.getAddRecExpr(NewOps, L, 1530261991Sdim S->getNoWrapFlags(SCEV::FlagNW)); 1531193323Sed 1532193323Sed // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 1533193323Sed // comments on expandAddToGEP for details. 1534198090Srdivacky const SCEV *Base = S->getStart(); 1535198090Srdivacky // Dig into the expression to find the pointer base for a GEP. 1536341825Sdim const SCEV *ExposedRest = Rest; 1537341825Sdim ExposePointerBase(Base, ExposedRest, SE); 1538198090Srdivacky // If we found a pointer, expand the AddRec with a GEP. 1539226633Sdim if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 1540198090Srdivacky // Make sure the Base isn't something exotic, such as a multiplied 1541198090Srdivacky // or divided pointer value. In those cases, the result type isn't 1542198090Srdivacky // actually a pointer type. 1543198090Srdivacky if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 1544198090Srdivacky Value *StartV = expand(Base); 1545198090Srdivacky assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 1546341825Sdim return expandAddToGEP(ExposedRest, PTy, Ty, StartV); 1547193323Sed } 1548193323Sed } 1549193323Sed 1550195098Sed // Just do a normal add. Pre-expand the operands to suppress folding. 1551309124Sdim // 1552309124Sdim // The LHS and RHS values are factored out of the expand call to make the 1553309124Sdim // output independent of the argument evaluation order. 1554309124Sdim const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart())); 1555309124Sdim const SCEV *AddExprRHS = SE.getUnknown(expand(Rest)); 1556309124Sdim return expand(SE.getAddExpr(AddExprLHS, AddExprRHS)); 1557193323Sed } 1558193323Sed 1559212904Sdim // If we don't yet have a canonical IV, create one. 1560212904Sdim if (!CanonicalIV) { 1561193323Sed // Create and insert the PHI node for the induction variable in the 1562193323Sed // specified loop. 1563193323Sed BasicBlock *Header = L->getHeader(); 1564221345Sdim pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); 1565221345Sdim CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar", 1566296417Sdim &Header->front()); 1567212904Sdim rememberInstruction(CanonicalIV); 1568193323Sed 1569261991Sdim SmallSet<BasicBlock *, 4> PredSeen; 1570193323Sed Constant *One = ConstantInt::get(Ty, 1); 1571221345Sdim for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { 1572210299Sed BasicBlock *HP = *HPI; 1573280031Sdim if (!PredSeen.insert(HP).second) { 1574276479Sdim // There must be an incoming value for each predecessor, even the 1575276479Sdim // duplicates! 1576276479Sdim CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP); 1577261991Sdim continue; 1578276479Sdim } 1579261991Sdim 1580210299Sed if (L->contains(HP)) { 1581202878Srdivacky // Insert a unit add instruction right before the terminator 1582202878Srdivacky // corresponding to the back-edge. 1583212904Sdim Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One, 1584212904Sdim "indvar.next", 1585212904Sdim HP->getTerminator()); 1586224145Sdim Add->setDebugLoc(HP->getTerminator()->getDebugLoc()); 1587202878Srdivacky rememberInstruction(Add); 1588212904Sdim CanonicalIV->addIncoming(Add, HP); 1589198090Srdivacky } else { 1590212904Sdim CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP); 1591198090Srdivacky } 1592210299Sed } 1593193323Sed } 1594193323Sed 1595212904Sdim // {0,+,1} --> Insert a canonical induction variable into the loop! 1596212904Sdim if (S->isAffine() && S->getOperand(1)->isOne()) { 1597212904Sdim assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 1598212904Sdim "IVs with types different from the canonical IV should " 1599212904Sdim "already have been handled!"); 1600212904Sdim return CanonicalIV; 1601212904Sdim } 1602212904Sdim 1603194178Sed // {0,+,F} --> {0,+,1} * F 1604193323Sed 1605193323Sed // If this is a simple linear addrec, emit it now as a special case. 1606195098Sed if (S->isAffine()) // {0,+,F} --> i*F 1607195098Sed return 1608195098Sed expand(SE.getTruncateOrNoop( 1609212904Sdim SE.getMulExpr(SE.getUnknown(CanonicalIV), 1610195098Sed SE.getNoopOrAnyExtend(S->getOperand(1), 1611212904Sdim CanonicalIV->getType())), 1612195098Sed Ty)); 1613194178Sed 1614193323Sed // If this is a chain of recurrences, turn it into a closed form, using the 1615193323Sed // folders, then expandCodeFor the closed form. This allows the folders to 1616193323Sed // simplify the expression without having to build a bunch of special code 1617193323Sed // into this folder. 1618212904Sdim const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV. 1619193323Sed 1620194178Sed // Promote S up to the canonical IV type, if the cast is foldable. 1621198090Srdivacky const SCEV *NewS = S; 1622212904Sdim const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType()); 1623194178Sed if (isa<SCEVAddRecExpr>(Ext)) 1624194178Sed NewS = Ext; 1625194178Sed 1626198090Srdivacky const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 1627193323Sed //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 1628193323Sed 1629194178Sed // Truncate the result down to the original type, if needed. 1630198090Srdivacky const SCEV *T = SE.getTruncateOrNoop(V, Ty); 1631194710Sed return expand(T); 1632193323Sed} 1633193323Sed 1634193323SedValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 1635226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1636194178Sed Value *V = expandCodeFor(S->getOperand(), 1637194178Sed SE.getEffectiveSCEVType(S->getOperand()->getType())); 1638226633Sdim Value *I = Builder.CreateTrunc(V, Ty); 1639202878Srdivacky rememberInstruction(I); 1640193323Sed return I; 1641193323Sed} 1642193323Sed 1643193323SedValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 1644226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1645194178Sed Value *V = expandCodeFor(S->getOperand(), 1646194178Sed SE.getEffectiveSCEVType(S->getOperand()->getType())); 1647226633Sdim Value *I = Builder.CreateZExt(V, Ty); 1648202878Srdivacky rememberInstruction(I); 1649193323Sed return I; 1650193323Sed} 1651193323Sed 1652193323SedValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 1653226633Sdim Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1654194178Sed Value *V = expandCodeFor(S->getOperand(), 1655194178Sed SE.getEffectiveSCEVType(S->getOperand()->getType())); 1656226633Sdim Value *I = Builder.CreateSExt(V, Ty); 1657202878Srdivacky rememberInstruction(I); 1658193323Sed return I; 1659193323Sed} 1660193323Sed 1661193323SedValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 1662198090Srdivacky Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 1663226633Sdim Type *Ty = LHS->getType(); 1664198090Srdivacky for (int i = S->getNumOperands()-2; i >= 0; --i) { 1665198090Srdivacky // In the case of mixed integer and pointer types, do the 1666198090Srdivacky // rest of the comparisons as integer. 1667353358Sdim Type *OpTy = S->getOperand(i)->getType(); 1668353358Sdim if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1669198090Srdivacky Ty = SE.getEffectiveSCEVType(Ty); 1670198090Srdivacky LHS = InsertNoopCastOfTo(LHS, Ty); 1671198090Srdivacky } 1672194178Sed Value *RHS = expandCodeFor(S->getOperand(i), Ty); 1673226633Sdim Value *ICmp = Builder.CreateICmpSGT(LHS, RHS); 1674202878Srdivacky rememberInstruction(ICmp); 1675195340Sed Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax"); 1676202878Srdivacky rememberInstruction(Sel); 1677193323Sed LHS = Sel; 1678193323Sed } 1679198090Srdivacky // In the case of mixed integer and pointer types, cast the 1680198090Srdivacky // final result back to the pointer type. 1681198090Srdivacky if (LHS->getType() != S->getType()) 1682198090Srdivacky LHS = InsertNoopCastOfTo(LHS, S->getType()); 1683193323Sed return LHS; 1684193323Sed} 1685193323Sed 1686193323SedValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 1687198090Srdivacky Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 1688226633Sdim Type *Ty = LHS->getType(); 1689198090Srdivacky for (int i = S->getNumOperands()-2; i >= 0; --i) { 1690198090Srdivacky // In the case of mixed integer and pointer types, do the 1691198090Srdivacky // rest of the comparisons as integer. 1692353358Sdim Type *OpTy = S->getOperand(i)->getType(); 1693353358Sdim if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1694198090Srdivacky Ty = SE.getEffectiveSCEVType(Ty); 1695198090Srdivacky LHS = InsertNoopCastOfTo(LHS, Ty); 1696198090Srdivacky } 1697194178Sed Value *RHS = expandCodeFor(S->getOperand(i), Ty); 1698226633Sdim Value *ICmp = Builder.CreateICmpUGT(LHS, RHS); 1699202878Srdivacky rememberInstruction(ICmp); 1700195340Sed Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax"); 1701202878Srdivacky rememberInstruction(Sel); 1702193323Sed LHS = Sel; 1703193323Sed } 1704198090Srdivacky // In the case of mixed integer and pointer types, cast the 1705198090Srdivacky // final result back to the pointer type. 1706198090Srdivacky if (LHS->getType() != S->getType()) 1707198090Srdivacky LHS = InsertNoopCastOfTo(LHS, S->getType()); 1708193323Sed return LHS; 1709193323Sed} 1710193323Sed 1711353358SdimValue *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) { 1712353358Sdim Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); 1713353358Sdim Type *Ty = LHS->getType(); 1714353358Sdim for (int i = S->getNumOperands() - 2; i >= 0; --i) { 1715353358Sdim // In the case of mixed integer and pointer types, do the 1716353358Sdim // rest of the comparisons as integer. 1717353358Sdim Type *OpTy = S->getOperand(i)->getType(); 1718353358Sdim if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1719353358Sdim Ty = SE.getEffectiveSCEVType(Ty); 1720353358Sdim LHS = InsertNoopCastOfTo(LHS, Ty); 1721353358Sdim } 1722353358Sdim Value *RHS = expandCodeFor(S->getOperand(i), Ty); 1723353358Sdim Value *ICmp = Builder.CreateICmpSLT(LHS, RHS); 1724353358Sdim rememberInstruction(ICmp); 1725353358Sdim Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin"); 1726353358Sdim rememberInstruction(Sel); 1727353358Sdim LHS = Sel; 1728353358Sdim } 1729353358Sdim // In the case of mixed integer and pointer types, cast the 1730353358Sdim // final result back to the pointer type. 1731353358Sdim if (LHS->getType() != S->getType()) 1732353358Sdim LHS = InsertNoopCastOfTo(LHS, S->getType()); 1733353358Sdim return LHS; 1734353358Sdim} 1735353358Sdim 1736353358SdimValue *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) { 1737353358Sdim Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); 1738353358Sdim Type *Ty = LHS->getType(); 1739353358Sdim for (int i = S->getNumOperands() - 2; i >= 0; --i) { 1740353358Sdim // In the case of mixed integer and pointer types, do the 1741353358Sdim // rest of the comparisons as integer. 1742353358Sdim Type *OpTy = S->getOperand(i)->getType(); 1743353358Sdim if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { 1744353358Sdim Ty = SE.getEffectiveSCEVType(Ty); 1745353358Sdim LHS = InsertNoopCastOfTo(LHS, Ty); 1746353358Sdim } 1747353358Sdim Value *RHS = expandCodeFor(S->getOperand(i), Ty); 1748353358Sdim Value *ICmp = Builder.CreateICmpULT(LHS, RHS); 1749353358Sdim rememberInstruction(ICmp); 1750353358Sdim Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin"); 1751353358Sdim rememberInstruction(Sel); 1752353358Sdim LHS = Sel; 1753353358Sdim } 1754353358Sdim // In the case of mixed integer and pointer types, cast the 1755353358Sdim // final result back to the pointer type. 1756353358Sdim if (LHS->getType() != S->getType()) 1757353358Sdim LHS = InsertNoopCastOfTo(LHS, S->getType()); 1758353358Sdim return LHS; 1759353358Sdim} 1760353358Sdim 1761226633SdimValue *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty, 1762234353Sdim Instruction *IP) { 1763309124Sdim setInsertPoint(IP); 1764205407Srdivacky return expandCodeFor(SH, Ty); 1765205407Srdivacky} 1766205407Srdivacky 1767226633SdimValue *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) { 1768193323Sed // Expand the code for this SCEV. 1769193323Sed Value *V = expand(SH); 1770193323Sed if (Ty) { 1771193323Sed assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 1772193323Sed "non-trivial casts should be done with the SCEVs directly!"); 1773193323Sed V = InsertNoopCastOfTo(V, Ty); 1774193323Sed } 1775193323Sed return V; 1776193323Sed} 1777193323Sed 1778312832SdimScalarEvolution::ValueOffsetPair 1779312832SdimSCEVExpander::FindValueInExprValueMap(const SCEV *S, 1780312832Sdim const Instruction *InsertPt) { 1781312832Sdim SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S); 1782309124Sdim // If the expansion is not in CanonicalMode, and the SCEV contains any 1783309124Sdim // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally. 1784309124Sdim if (CanonicalMode || !SE.containsAddRecurrence(S)) { 1785309124Sdim // If S is scConstant, it may be worse to reuse an existing Value. 1786309124Sdim if (S->getSCEVType() != scConstant && Set) { 1787309124Sdim // Choose a Value from the set which dominates the insertPt. 1788309124Sdim // insertPt should be inside the Value's parent loop so as not to break 1789309124Sdim // the LCSSA form. 1790312832Sdim for (auto const &VOPair : *Set) { 1791312832Sdim Value *V = VOPair.first; 1792312832Sdim ConstantInt *Offset = VOPair.second; 1793309124Sdim Instruction *EntInst = nullptr; 1794312832Sdim if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) && 1795312832Sdim S->getType() == V->getType() && 1796309124Sdim EntInst->getFunction() == InsertPt->getFunction() && 1797309124Sdim SE.DT.dominates(EntInst, InsertPt) && 1798309124Sdim (SE.LI.getLoopFor(EntInst->getParent()) == nullptr || 1799312832Sdim SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt))) 1800312832Sdim return {V, Offset}; 1801309124Sdim } 1802309124Sdim } 1803309124Sdim } 1804312832Sdim return {nullptr, nullptr}; 1805309124Sdim} 1806309124Sdim 1807309124Sdim// The expansion of SCEV will either reuse a previous Value in ExprValueMap, 1808309124Sdim// or expand the SCEV literally. Specifically, if the expansion is in LSRMode, 1809309124Sdim// and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded 1810309124Sdim// literally, to prevent LSR's transformed SCEV from being reverted. Otherwise, 1811309124Sdim// the expansion will try to reuse Value from ExprValueMap, and only when it 1812309124Sdim// fails, expand the SCEV literally. 1813193323SedValue *SCEVExpander::expand(const SCEV *S) { 1814195098Sed // Compute an insertion point for this SCEV object. Hoist the instructions 1815195098Sed // as far out in the loop nest as possible. 1816296417Sdim Instruction *InsertPt = &*Builder.GetInsertPoint(); 1817353358Sdim 1818353358Sdim // We can move insertion point only if there is no div or rem operations 1819353358Sdim // otherwise we are risky to move it over the check for zero denominator. 1820353358Sdim auto SafeToHoist = [](const SCEV *S) { 1821353358Sdim return !SCEVExprContains(S, [](const SCEV *S) { 1822353358Sdim if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) { 1823353358Sdim if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS())) 1824353358Sdim // Division by non-zero constants can be hoisted. 1825353358Sdim return SC->getValue()->isZero(); 1826353358Sdim // All other divisions should not be moved as they may be 1827353358Sdim // divisions by zero and should be kept within the 1828353358Sdim // conditions of the surrounding loops that guard their 1829353358Sdim // execution (see PR35406). 1830353358Sdim return true; 1831353358Sdim } 1832353358Sdim return false; 1833353358Sdim }); 1834353358Sdim }; 1835353358Sdim if (SafeToHoist(S)) { 1836353358Sdim for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; 1837353358Sdim L = L->getParentLoop()) { 1838353358Sdim if (SE.isLoopInvariant(S, L)) { 1839353358Sdim if (!L) break; 1840353358Sdim if (BasicBlock *Preheader = L->getLoopPreheader()) 1841353358Sdim InsertPt = Preheader->getTerminator(); 1842353358Sdim else 1843353358Sdim // LSR sets the insertion point for AddRec start/step values to the 1844353358Sdim // block start to simplify value reuse, even though it's an invalid 1845353358Sdim // position. SCEVExpander must correct for this in all cases. 1846353358Sdim InsertPt = &*L->getHeader()->getFirstInsertionPt(); 1847353358Sdim } else { 1848353358Sdim // If the SCEV is computable at this level, insert it into the header 1849353358Sdim // after the PHIs (and after any other instructions that we've inserted 1850353358Sdim // there) so that it is guaranteed to dominate any user inside the loop. 1851353358Sdim if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L)) 1852353358Sdim InsertPt = &*L->getHeader()->getFirstInsertionPt(); 1853353358Sdim while (InsertPt->getIterator() != Builder.GetInsertPoint() && 1854353358Sdim (isInsertedInstruction(InsertPt) || 1855353358Sdim isa<DbgInfoIntrinsic>(InsertPt))) 1856353358Sdim InsertPt = &*std::next(InsertPt->getIterator()); 1857353358Sdim break; 1858234353Sdim } 1859195098Sed } 1860353358Sdim } 1861195098Sed 1862353358Sdim // IndVarSimplify sometimes sets the insertion point at the block start, even 1863353358Sdim // when there are PHIs at that point. We must correct for this. 1864353358Sdim if (isa<PHINode>(*InsertPt)) 1865353358Sdim InsertPt = &*InsertPt->getParent()->getFirstInsertionPt(); 1866353358Sdim 1867195098Sed // Check to see if we already expanded this here. 1868296417Sdim auto I = InsertedExpressions.find(std::make_pair(S, InsertPt)); 1869195340Sed if (I != InsertedExpressions.end()) 1870193323Sed return I->second; 1871195098Sed 1872309124Sdim SCEVInsertPointGuard Guard(Builder, this); 1873296417Sdim Builder.SetInsertPoint(InsertPt); 1874195340Sed 1875195098Sed // Expand the expression into instructions. 1876312832Sdim ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt); 1877312832Sdim Value *V = VO.first; 1878195098Sed 1879309124Sdim if (!V) 1880309124Sdim V = visit(S); 1881312832Sdim else if (VO.second) { 1882312832Sdim if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) { 1883312832Sdim Type *Ety = Vty->getPointerElementType(); 1884312832Sdim int64_t Offset = VO.second->getSExtValue(); 1885312832Sdim int64_t ESize = SE.getTypeSizeInBits(Ety); 1886312832Sdim if ((Offset * 8) % ESize == 0) { 1887312832Sdim ConstantInt *Idx = 1888312832Sdim ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize); 1889312832Sdim V = Builder.CreateGEP(Ety, V, Idx, "scevgep"); 1890312832Sdim } else { 1891312832Sdim ConstantInt *Idx = 1892312832Sdim ConstantInt::getSigned(VO.second->getType(), -Offset); 1893312832Sdim unsigned AS = Vty->getAddressSpace(); 1894312832Sdim V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS)); 1895312832Sdim V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx, 1896312832Sdim "uglygep"); 1897312832Sdim V = Builder.CreateBitCast(V, Vty); 1898312832Sdim } 1899312832Sdim } else { 1900312832Sdim V = Builder.CreateSub(V, VO.second); 1901312832Sdim } 1902312832Sdim } 1903195098Sed // Remember the expanded value for this SCEV at this location. 1904226633Sdim // 1905226633Sdim // This is independent of PostIncLoops. The mapped value simply materializes 1906226633Sdim // the expression at this insertion point. If the mapped value happened to be 1907276479Sdim // a postinc expansion, it could be reused by a non-postinc user, but only if 1908226633Sdim // its insertion point was already at the head of the loop. 1909226633Sdim InsertedExpressions[std::make_pair(S, InsertPt)] = V; 1910193323Sed return V; 1911193323Sed} 1912193574Sed 1913203954Srdivackyvoid SCEVExpander::rememberInstruction(Value *I) { 1914210299Sed if (!PostIncLoops.empty()) 1915210299Sed InsertedPostIncValues.insert(I); 1916210299Sed else 1917203954Srdivacky InsertedValues.insert(I); 1918203954Srdivacky} 1919203954Srdivacky 1920193574Sed/// getOrInsertCanonicalInductionVariable - This method returns the 1921193574Sed/// canonical induction variable of the specified type for the specified 1922193574Sed/// loop (inserting one if there is none). A canonical induction variable 1923193574Sed/// starts at zero and steps by one on each iteration. 1924212904SdimPHINode * 1925193574SedSCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 1926226633Sdim Type *Ty) { 1927203954Srdivacky assert(Ty->isIntegerTy() && "Can only insert integer induction variables!"); 1928212904Sdim 1929212904Sdim // Build a SCEV for {0,+,1}<L>. 1930221345Sdim // Conservatively use FlagAnyWrap for now. 1931207618Srdivacky const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0), 1932221345Sdim SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap); 1933212904Sdim 1934212904Sdim // Emit code for it. 1935309124Sdim SCEVInsertPointGuard Guard(Builder, this); 1936296417Sdim PHINode *V = 1937296417Sdim cast<PHINode>(expandCodeFor(H, nullptr, &L->getHeader()->front())); 1938212904Sdim 1939195098Sed return V; 1940193574Sed} 1941226633Sdim 1942226633Sdim/// replaceCongruentIVs - Check for congruent phis in this loop header and 1943226633Sdim/// replace them with their most canonical representative. Return the number of 1944226633Sdim/// phis eliminated. 1945226633Sdim/// 1946226633Sdim/// This does not depend on any SCEVExpander state but should be used in 1947226633Sdim/// the same context that SCEVExpander is used. 1948321369Sdimunsigned 1949321369SdimSCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, 1950321369Sdim SmallVectorImpl<WeakTrackingVH> &DeadInsts, 1951321369Sdim const TargetTransformInfo *TTI) { 1952234353Sdim // Find integer phis in order of increasing width. 1953234353Sdim SmallVector<PHINode*, 8> Phis; 1954327952Sdim for (PHINode &PN : L->getHeader()->phis()) 1955327952Sdim Phis.push_back(&PN); 1956296417Sdim 1957249423Sdim if (TTI) 1958344779Sdim llvm::sort(Phis, [](Value *LHS, Value *RHS) { 1959276479Sdim // Put pointers at the back and make sure pointer < pointer = false. 1960276479Sdim if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) 1961276479Sdim return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy(); 1962276479Sdim return RHS->getType()->getPrimitiveSizeInBits() < 1963276479Sdim LHS->getType()->getPrimitiveSizeInBits(); 1964276479Sdim }); 1965234353Sdim 1966226633Sdim unsigned NumElim = 0; 1967226633Sdim DenseMap<const SCEV *, PHINode *> ExprToIVMap; 1968288943Sdim // Process phis from wide to narrow. Map wide phis to their truncation 1969234353Sdim // so narrow phis can reuse them. 1970296417Sdim for (PHINode *Phi : Phis) { 1971296417Sdim auto SimplifyPHINode = [&](PHINode *PN) -> Value * { 1972321369Sdim if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC})) 1973296417Sdim return V; 1974296417Sdim if (!SE.isSCEVable(PN->getType())) 1975296417Sdim return nullptr; 1976296417Sdim auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN)); 1977296417Sdim if (!Const) 1978296417Sdim return nullptr; 1979296417Sdim return Const->getValue(); 1980296417Sdim }; 1981234353Sdim 1982243830Sdim // Fold constant phis. They may be congruent to other constant phis and 1983243830Sdim // would confuse the logic below that expects proper IVs. 1984296417Sdim if (Value *V = SimplifyPHINode(Phi)) { 1985296417Sdim if (V->getType() != Phi->getType()) 1986296417Sdim continue; 1987243830Sdim Phi->replaceAllUsesWith(V); 1988288943Sdim DeadInsts.emplace_back(Phi); 1989243830Sdim ++NumElim; 1990243830Sdim DEBUG_WITH_TYPE(DebugType, dbgs() 1991243830Sdim << "INDVARS: Eliminated constant iv: " << *Phi << '\n'); 1992243830Sdim continue; 1993243830Sdim } 1994243830Sdim 1995226633Sdim if (!SE.isSCEVable(Phi->getType())) 1996226633Sdim continue; 1997226633Sdim 1998226633Sdim PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)]; 1999226633Sdim if (!OrigPhiRef) { 2000226633Sdim OrigPhiRef = Phi; 2001309124Sdim if (Phi->getType()->isIntegerTy() && TTI && 2002309124Sdim TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) { 2003234353Sdim // This phi can be freely truncated to the narrowest phi type. Map the 2004234353Sdim // truncated expression to it so it will be reused for narrow types. 2005234353Sdim const SCEV *TruncExpr = 2006234353Sdim SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType()); 2007234353Sdim ExprToIVMap[TruncExpr] = Phi; 2008234353Sdim } 2009226633Sdim continue; 2010226633Sdim } 2011226633Sdim 2012234353Sdim // Replacing a pointer phi with an integer phi or vice-versa doesn't make 2013234353Sdim // sense. 2014234353Sdim if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy()) 2015226633Sdim continue; 2016226633Sdim 2017226633Sdim if (BasicBlock *LatchBlock = L->getLoopLatch()) { 2018309124Sdim Instruction *OrigInc = dyn_cast<Instruction>( 2019309124Sdim OrigPhiRef->getIncomingValueForBlock(LatchBlock)); 2020226633Sdim Instruction *IsomorphicInc = 2021309124Sdim dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock)); 2022226633Sdim 2023309124Sdim if (OrigInc && IsomorphicInc) { 2024309124Sdim // If this phi has the same width but is more canonical, replace the 2025309124Sdim // original with it. As part of the "more canonical" determination, 2026309124Sdim // respect a prior decision to use an IV chain. 2027309124Sdim if (OrigPhiRef->getType() == Phi->getType() && 2028309124Sdim !(ChainedPhis.count(Phi) || 2029309124Sdim isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) && 2030309124Sdim (ChainedPhis.count(Phi) || 2031309124Sdim isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) { 2032309124Sdim std::swap(OrigPhiRef, Phi); 2033309124Sdim std::swap(OrigInc, IsomorphicInc); 2034309124Sdim } 2035309124Sdim // Replacing the congruent phi is sufficient because acyclic 2036309124Sdim // redundancy elimination, CSE/GVN, should handle the 2037309124Sdim // rest. However, once SCEV proves that a phi is congruent, 2038309124Sdim // it's often the head of an IV user cycle that is isomorphic 2039309124Sdim // with the original phi. It's worth eagerly cleaning up the 2040309124Sdim // common case of a single IV increment so that DeleteDeadPHIs 2041309124Sdim // can remove cycles that had postinc uses. 2042309124Sdim const SCEV *TruncExpr = 2043309124Sdim SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType()); 2044309124Sdim if (OrigInc != IsomorphicInc && 2045309124Sdim TruncExpr == SE.getSCEV(IsomorphicInc) && 2046309124Sdim SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) && 2047309124Sdim hoistIVInc(OrigInc, IsomorphicInc)) { 2048309124Sdim DEBUG_WITH_TYPE(DebugType, 2049309124Sdim dbgs() << "INDVARS: Eliminated congruent iv.inc: " 2050309124Sdim << *IsomorphicInc << '\n'); 2051309124Sdim Value *NewInc = OrigInc; 2052309124Sdim if (OrigInc->getType() != IsomorphicInc->getType()) { 2053309124Sdim Instruction *IP = nullptr; 2054309124Sdim if (PHINode *PN = dyn_cast<PHINode>(OrigInc)) 2055309124Sdim IP = &*PN->getParent()->getFirstInsertionPt(); 2056309124Sdim else 2057309124Sdim IP = OrigInc->getNextNode(); 2058283526Sdim 2059309124Sdim IRBuilder<> Builder(IP); 2060309124Sdim Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc()); 2061309124Sdim NewInc = Builder.CreateTruncOrBitCast( 2062309124Sdim OrigInc, IsomorphicInc->getType(), IVName); 2063309124Sdim } 2064309124Sdim IsomorphicInc->replaceAllUsesWith(NewInc); 2065309124Sdim DeadInsts.emplace_back(IsomorphicInc); 2066234353Sdim } 2067226633Sdim } 2068226633Sdim } 2069309124Sdim DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: " 2070309124Sdim << *Phi << '\n'); 2071226633Sdim ++NumElim; 2072234353Sdim Value *NewIV = OrigPhiRef; 2073234353Sdim if (OrigPhiRef->getType() != Phi->getType()) { 2074296417Sdim IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt()); 2075234353Sdim Builder.SetCurrentDebugLocation(Phi->getDebugLoc()); 2076234353Sdim NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName); 2077234353Sdim } 2078234353Sdim Phi->replaceAllUsesWith(NewIV); 2079288943Sdim DeadInsts.emplace_back(Phi); 2080226633Sdim } 2081226633Sdim return NumElim; 2082226633Sdim} 2083239462Sdim 2084312832SdimValue *SCEVExpander::getExactExistingExpansion(const SCEV *S, 2085312832Sdim const Instruction *At, Loop *L) { 2086312832Sdim Optional<ScalarEvolution::ValueOffsetPair> VO = 2087312832Sdim getRelatedExistingExpansion(S, At, L); 2088312832Sdim if (VO && VO.getValue().second == nullptr) 2089312832Sdim return VO.getValue().first; 2090312832Sdim return nullptr; 2091312832Sdim} 2092312832Sdim 2093312832SdimOptional<ScalarEvolution::ValueOffsetPair> 2094312832SdimSCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At, 2095312832Sdim Loop *L) { 2096296417Sdim using namespace llvm::PatternMatch; 2097296417Sdim 2098296417Sdim SmallVector<BasicBlock *, 4> ExitingBlocks; 2099296417Sdim L->getExitingBlocks(ExitingBlocks); 2100296417Sdim 2101296417Sdim // Look for suitable value in simple conditions at the loop exits. 2102296417Sdim for (BasicBlock *BB : ExitingBlocks) { 2103296417Sdim ICmpInst::Predicate Pred; 2104296417Sdim Instruction *LHS, *RHS; 2105296417Sdim 2106296417Sdim if (!match(BB->getTerminator(), 2107296417Sdim m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)), 2108360784Sdim m_BasicBlock(), m_BasicBlock()))) 2109296417Sdim continue; 2110296417Sdim 2111296417Sdim if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At)) 2112312832Sdim return ScalarEvolution::ValueOffsetPair(LHS, nullptr); 2113296417Sdim 2114296417Sdim if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At)) 2115312832Sdim return ScalarEvolution::ValueOffsetPair(RHS, nullptr); 2116296417Sdim } 2117296417Sdim 2118309124Sdim // Use expand's logic which is used for reusing a previous Value in 2119309124Sdim // ExprValueMap. 2120312832Sdim ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At); 2121312832Sdim if (VO.first) 2122312832Sdim return VO; 2123309124Sdim 2124296417Sdim // There is potential to make this significantly smarter, but this simple 2125296417Sdim // heuristic already gets some interesting cases. 2126296417Sdim 2127296417Sdim // Can not find suitable value. 2128312832Sdim return None; 2129296417Sdim} 2130296417Sdim 2131288943Sdimbool SCEVExpander::isHighCostExpansionHelper( 2132296417Sdim const SCEV *S, Loop *L, const Instruction *At, 2133296417Sdim SmallPtrSetImpl<const SCEV *> &Processed) { 2134288943Sdim 2135314564Sdim // If we can find an existing value for this scev available at the point "At" 2136296417Sdim // then consider the expression cheap. 2137312832Sdim if (At && getRelatedExistingExpansion(S, At, L)) 2138296417Sdim return false; 2139296417Sdim 2140288943Sdim // Zero/One operand expressions 2141288943Sdim switch (S->getSCEVType()) { 2142288943Sdim case scUnknown: 2143288943Sdim case scConstant: 2144288943Sdim return false; 2145288943Sdim case scTruncate: 2146296417Sdim return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(), 2147296417Sdim L, At, Processed); 2148288943Sdim case scZeroExtend: 2149288943Sdim return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(), 2150296417Sdim L, At, Processed); 2151288943Sdim case scSignExtend: 2152288943Sdim return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(), 2153296417Sdim L, At, Processed); 2154288943Sdim } 2155288943Sdim 2156288943Sdim if (!Processed.insert(S).second) 2157288943Sdim return false; 2158288943Sdim 2159288943Sdim if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) { 2160288943Sdim // If the divisor is a power of two and the SCEV type fits in a native 2161353358Sdim // integer (and the LHS not expensive), consider the division cheap 2162353358Sdim // irrespective of whether it occurs in the user code since it can be 2163353358Sdim // lowered into a right shift. 2164288943Sdim if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS())) 2165296417Sdim if (SC->getAPInt().isPowerOf2()) { 2166353358Sdim if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At, Processed)) 2167353358Sdim return true; 2168288943Sdim const DataLayout &DL = 2169288943Sdim L->getHeader()->getParent()->getParent()->getDataLayout(); 2170288943Sdim unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth(); 2171288943Sdim return DL.isIllegalInteger(Width); 2172288943Sdim } 2173288943Sdim 2174288943Sdim // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or 2175288943Sdim // HowManyLessThans produced to compute a precise expression, rather than a 2176288943Sdim // UDiv from the user's code. If we can't find a UDiv in the code with some 2177288943Sdim // simple searching, assume the former consider UDivExpr expensive to 2178288943Sdim // compute. 2179288943Sdim BasicBlock *ExitingBB = L->getExitingBlock(); 2180288943Sdim if (!ExitingBB) 2181288943Sdim return true; 2182288943Sdim 2183296417Sdim // At the beginning of this function we already tried to find existing value 2184296417Sdim // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern 2185296417Sdim // involving division. This is just a simple search heuristic. 2186296417Sdim if (!At) 2187296417Sdim At = &ExitingBB->back(); 2188312832Sdim if (!getRelatedExistingExpansion( 2189296417Sdim SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L)) 2190288943Sdim return true; 2191288943Sdim } 2192288943Sdim 2193288943Sdim // HowManyLessThans uses a Max expression whenever the loop is not guarded by 2194288943Sdim // the exit condition. 2195353358Sdim if (isa<SCEVMinMaxExpr>(S)) 2196288943Sdim return true; 2197288943Sdim 2198288943Sdim // Recurse past nary expressions, which commonly occur in the 2199288943Sdim // BackedgeTakenCount. They may already exist in program code, and if not, 2200288943Sdim // they are not too expensive rematerialize. 2201288943Sdim if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) { 2202296417Sdim for (auto *Op : NAry->operands()) 2203296417Sdim if (isHighCostExpansionHelper(Op, L, At, Processed)) 2204288943Sdim return true; 2205288943Sdim } 2206288943Sdim 2207288943Sdim // If we haven't recognized an expensive SCEV pattern, assume it's an 2208288943Sdim // expression produced by program code. 2209288943Sdim return false; 2210288943Sdim} 2211288943Sdim 2212296417SdimValue *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred, 2213296417Sdim Instruction *IP) { 2214296417Sdim assert(IP); 2215296417Sdim switch (Pred->getKind()) { 2216296417Sdim case SCEVPredicate::P_Union: 2217296417Sdim return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP); 2218296417Sdim case SCEVPredicate::P_Equal: 2219296417Sdim return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP); 2220309124Sdim case SCEVPredicate::P_Wrap: { 2221309124Sdim auto *AddRecPred = cast<SCEVWrapPredicate>(Pred); 2222309124Sdim return expandWrapPredicate(AddRecPred, IP); 2223296417Sdim } 2224309124Sdim } 2225296417Sdim llvm_unreachable("Unknown SCEV predicate type"); 2226296417Sdim} 2227296417Sdim 2228296417SdimValue *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred, 2229296417Sdim Instruction *IP) { 2230296417Sdim Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP); 2231296417Sdim Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP); 2232296417Sdim 2233296417Sdim Builder.SetInsertPoint(IP); 2234296417Sdim auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check"); 2235296417Sdim return I; 2236296417Sdim} 2237296417Sdim 2238309124SdimValue *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR, 2239309124Sdim Instruction *Loc, bool Signed) { 2240309124Sdim assert(AR->isAffine() && "Cannot generate RT check for " 2241309124Sdim "non-affine expression"); 2242309124Sdim 2243309124Sdim SCEVUnionPredicate Pred; 2244309124Sdim const SCEV *ExitCount = 2245309124Sdim SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred); 2246309124Sdim 2247309124Sdim assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count"); 2248309124Sdim 2249309124Sdim const SCEV *Step = AR->getStepRecurrence(SE); 2250309124Sdim const SCEV *Start = AR->getStart(); 2251309124Sdim 2252341825Sdim Type *ARTy = AR->getType(); 2253309124Sdim unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType()); 2254341825Sdim unsigned DstBits = SE.getTypeSizeInBits(ARTy); 2255309124Sdim 2256309124Sdim // The expression {Start,+,Step} has nusw/nssw if 2257309124Sdim // Step < 0, Start - |Step| * Backedge <= Start 2258309124Sdim // Step >= 0, Start + |Step| * Backedge > Start 2259309124Sdim // and |Step| * Backedge doesn't unsigned overflow. 2260309124Sdim 2261309124Sdim IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits); 2262309124Sdim Builder.SetInsertPoint(Loc); 2263309124Sdim Value *TripCountVal = expandCodeFor(ExitCount, CountTy, Loc); 2264309124Sdim 2265309124Sdim IntegerType *Ty = 2266341825Sdim IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy)); 2267341825Sdim Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty; 2268309124Sdim 2269309124Sdim Value *StepValue = expandCodeFor(Step, Ty, Loc); 2270309124Sdim Value *NegStepValue = expandCodeFor(SE.getNegativeSCEV(Step), Ty, Loc); 2271341825Sdim Value *StartValue = expandCodeFor(Start, ARExpandTy, Loc); 2272309124Sdim 2273309124Sdim ConstantInt *Zero = 2274309124Sdim ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits)); 2275309124Sdim 2276309124Sdim Builder.SetInsertPoint(Loc); 2277309124Sdim // Compute |Step| 2278309124Sdim Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero); 2279309124Sdim Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue); 2280309124Sdim 2281309124Sdim // Get the backedge taken count and truncate or extended to the AR type. 2282309124Sdim Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty); 2283309124Sdim auto *MulF = Intrinsic::getDeclaration(Loc->getModule(), 2284309124Sdim Intrinsic::umul_with_overflow, Ty); 2285309124Sdim 2286309124Sdim // Compute |Step| * Backedge 2287309124Sdim CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul"); 2288309124Sdim Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result"); 2289309124Sdim Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow"); 2290309124Sdim 2291309124Sdim // Compute: 2292309124Sdim // Start + |Step| * Backedge < Start 2293309124Sdim // Start - |Step| * Backedge > Start 2294341825Sdim Value *Add = nullptr, *Sub = nullptr; 2295341825Sdim if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) { 2296341825Sdim const SCEV *MulS = SE.getSCEV(MulV); 2297341825Sdim const SCEV *NegMulS = SE.getNegativeSCEV(MulS); 2298341825Sdim Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue), 2299341825Sdim ARPtrTy); 2300341825Sdim Sub = Builder.CreateBitCast( 2301341825Sdim expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy); 2302341825Sdim } else { 2303341825Sdim Add = Builder.CreateAdd(StartValue, MulV); 2304341825Sdim Sub = Builder.CreateSub(StartValue, MulV); 2305341825Sdim } 2306309124Sdim 2307309124Sdim Value *EndCompareGT = Builder.CreateICmp( 2308309124Sdim Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue); 2309309124Sdim 2310309124Sdim Value *EndCompareLT = Builder.CreateICmp( 2311309124Sdim Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue); 2312309124Sdim 2313309124Sdim // Select the answer based on the sign of Step. 2314309124Sdim Value *EndCheck = 2315309124Sdim Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT); 2316309124Sdim 2317309124Sdim // If the backedge taken count type is larger than the AR type, 2318309124Sdim // check that we don't drop any bits by truncating it. If we are 2319341825Sdim // dropping bits, then we have overflow (unless the step is zero). 2320309124Sdim if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) { 2321309124Sdim auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits); 2322309124Sdim auto *BackedgeCheck = 2323309124Sdim Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal, 2324309124Sdim ConstantInt::get(Loc->getContext(), MaxVal)); 2325309124Sdim BackedgeCheck = Builder.CreateAnd( 2326309124Sdim BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero)); 2327309124Sdim 2328309124Sdim EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck); 2329309124Sdim } 2330309124Sdim 2331309124Sdim EndCheck = Builder.CreateOr(EndCheck, OfMul); 2332309124Sdim return EndCheck; 2333309124Sdim} 2334309124Sdim 2335309124SdimValue *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred, 2336309124Sdim Instruction *IP) { 2337309124Sdim const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr()); 2338309124Sdim Value *NSSWCheck = nullptr, *NUSWCheck = nullptr; 2339309124Sdim 2340309124Sdim // Add a check for NUSW 2341309124Sdim if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW) 2342309124Sdim NUSWCheck = generateOverflowCheck(A, IP, false); 2343309124Sdim 2344309124Sdim // Add a check for NSSW 2345309124Sdim if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW) 2346309124Sdim NSSWCheck = generateOverflowCheck(A, IP, true); 2347309124Sdim 2348309124Sdim if (NUSWCheck && NSSWCheck) 2349309124Sdim return Builder.CreateOr(NUSWCheck, NSSWCheck); 2350309124Sdim 2351309124Sdim if (NUSWCheck) 2352309124Sdim return NUSWCheck; 2353309124Sdim 2354309124Sdim if (NSSWCheck) 2355309124Sdim return NSSWCheck; 2356309124Sdim 2357309124Sdim return ConstantInt::getFalse(IP->getContext()); 2358309124Sdim} 2359309124Sdim 2360296417SdimValue *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union, 2361296417Sdim Instruction *IP) { 2362296417Sdim auto *BoolType = IntegerType::get(IP->getContext(), 1); 2363296417Sdim Value *Check = ConstantInt::getNullValue(BoolType); 2364296417Sdim 2365296417Sdim // Loop over all checks in this set. 2366296417Sdim for (auto Pred : Union->getPredicates()) { 2367296417Sdim auto *NextCheck = expandCodeForPredicate(Pred, IP); 2368296417Sdim Builder.SetInsertPoint(IP); 2369296417Sdim Check = Builder.CreateOr(Check, NextCheck); 2370296417Sdim } 2371296417Sdim 2372296417Sdim return Check; 2373296417Sdim} 2374296417Sdim 2375239462Sdimnamespace { 2376239462Sdim// Search for a SCEV subexpression that is not safe to expand. Any expression 2377239462Sdim// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely 2378239462Sdim// UDiv expressions. We don't know if the UDiv is derived from an IR divide 2379239462Sdim// instruction, but the important thing is that we prove the denominator is 2380239462Sdim// nonzero before expansion. 2381239462Sdim// 2382239462Sdim// IVUsers already checks that IV-derived expressions are safe. So this check is 2383239462Sdim// only needed when the expression includes some subexpression that is not IV 2384239462Sdim// derived. 2385239462Sdim// 2386239462Sdim// Currently, we only allow division by a nonzero constant here. If this is 2387239462Sdim// inadequate, we could easily allow division by SCEVUnknown by using 2388239462Sdim// ValueTracking to check isKnownNonZero(). 2389261991Sdim// 2390261991Sdim// We cannot generally expand recurrences unless the step dominates the loop 2391261991Sdim// header. The expander handles the special case of affine recurrences by 2392261991Sdim// scaling the recurrence outside the loop, but this technique isn't generally 2393261991Sdim// applicable. Expanding a nested recurrence outside a loop requires computing 2394261991Sdim// binomial coefficients. This could be done, but the recurrence has to be in a 2395261991Sdim// perfectly reduced form, which can't be guaranteed. 2396239462Sdimstruct SCEVFindUnsafe { 2397261991Sdim ScalarEvolution &SE; 2398239462Sdim bool IsUnsafe; 2399239462Sdim 2400261991Sdim SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {} 2401239462Sdim 2402239462Sdim bool follow(const SCEV *S) { 2403261991Sdim if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 2404261991Sdim const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS()); 2405261991Sdim if (!SC || SC->getValue()->isZero()) { 2406261991Sdim IsUnsafe = true; 2407261991Sdim return false; 2408261991Sdim } 2409261991Sdim } 2410261991Sdim if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 2411261991Sdim const SCEV *Step = AR->getStepRecurrence(SE); 2412261991Sdim if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) { 2413261991Sdim IsUnsafe = true; 2414261991Sdim return false; 2415261991Sdim } 2416261991Sdim } 2417261991Sdim return true; 2418239462Sdim } 2419239462Sdim bool isDone() const { return IsUnsafe; } 2420239462Sdim}; 2421239462Sdim} 2422239462Sdim 2423239462Sdimnamespace llvm { 2424261991Sdimbool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) { 2425261991Sdim SCEVFindUnsafe Search(SE); 2426239462Sdim visitAll(S, Search); 2427239462Sdim return !Search.IsUnsafe; 2428239462Sdim} 2429327952Sdim 2430327952Sdimbool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, 2431327952Sdim ScalarEvolution &SE) { 2432353358Sdim if (!isSafeToExpand(S, SE)) 2433353358Sdim return false; 2434353358Sdim // We have to prove that the expanded site of S dominates InsertionPoint. 2435353358Sdim // This is easy when not in the same block, but hard when S is an instruction 2436353358Sdim // to be expanded somewhere inside the same block as our insertion point. 2437353358Sdim // What we really need here is something analogous to an OrderedBasicBlock, 2438353358Sdim // but for the moment, we paper over the problem by handling two common and 2439353358Sdim // cheap to check cases. 2440353358Sdim if (SE.properlyDominates(S, InsertionPoint->getParent())) 2441353358Sdim return true; 2442353358Sdim if (SE.dominates(S, InsertionPoint->getParent())) { 2443353358Sdim if (InsertionPoint->getParent()->getTerminator() == InsertionPoint) 2444353358Sdim return true; 2445353358Sdim if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) 2446353358Sdim for (const Value *V : InsertionPoint->operand_values()) 2447353358Sdim if (V == U->getValue()) 2448353358Sdim return true; 2449353358Sdim } 2450353358Sdim return false; 2451239462Sdim} 2452327952Sdim} 2453