1 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the classes used to generate code from scalar expressions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H 14 #define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/Analysis/InstSimplifyFolder.h" 20 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 21 #include "llvm/Analysis/ScalarEvolutionNormalization.h" 22 #include "llvm/Analysis/TargetTransformInfo.h" 23 #include "llvm/IR/IRBuilder.h" 24 #include "llvm/IR/ValueHandle.h" 25 #include "llvm/Support/CommandLine.h" 26 #include "llvm/Support/InstructionCost.h" 27 28 namespace llvm { 29 extern cl::opt<unsigned> SCEVCheapExpansionBudget; 30 31 /// struct for holding enough information to help calculate the cost of the 32 /// given SCEV when expanded into IR. 33 struct SCEVOperand { 34 explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) : 35 ParentOpcode(Opc), OperandIdx(Idx), S(S) { } 36 /// LLVM instruction opcode that uses the operand. 37 unsigned ParentOpcode; 38 /// The use index of an expanded instruction. 39 int OperandIdx; 40 /// The SCEV operand to be costed. 41 const SCEV* S; 42 }; 43 44 /// This class uses information about analyze scalars to rewrite expressions 45 /// in canonical form. 46 /// 47 /// Clients should create an instance of this class when rewriting is needed, 48 /// and destroy it when finished to allow the release of the associated 49 /// memory. 50 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> { 51 ScalarEvolution &SE; 52 const DataLayout &DL; 53 54 // New instructions receive a name to identify them with the current pass. 55 const char *IVName; 56 57 /// Indicates whether LCSSA phis should be created for inserted values. 58 bool PreserveLCSSA; 59 60 // InsertedExpressions caches Values for reuse, so must track RAUW. 61 DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>> 62 InsertedExpressions; 63 64 // InsertedValues only flags inserted instructions so needs no RAUW. 65 DenseSet<AssertingVH<Value>> InsertedValues; 66 DenseSet<AssertingVH<Value>> InsertedPostIncValues; 67 68 /// Keep track of the existing IR values re-used during expansion. 69 /// FIXME: Ideally re-used instructions would not be added to 70 /// InsertedValues/InsertedPostIncValues. 71 SmallPtrSet<Value *, 16> ReusedValues; 72 73 // The induction variables generated. 74 SmallVector<WeakVH, 2> InsertedIVs; 75 76 /// A memoization of the "relevant" loop for a given SCEV. 77 DenseMap<const SCEV *, const Loop *> RelevantLoops; 78 79 /// Addrecs referring to any of the given loops are expanded in post-inc 80 /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add 81 /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new 82 /// phi starting at 1. This is only supported in non-canonical mode. 83 PostIncLoopSet PostIncLoops; 84 85 /// When this is non-null, addrecs expanded in the loop it indicates should 86 /// be inserted with increments at IVIncInsertPos. 87 const Loop *IVIncInsertLoop; 88 89 /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV 90 /// increment at this position. 91 Instruction *IVIncInsertPos; 92 93 /// Phis that complete an IV chain. Reuse 94 DenseSet<AssertingVH<PHINode>> ChainedPhis; 95 96 /// When true, SCEVExpander tries to expand expressions in "canonical" form. 97 /// When false, expressions are expanded in a more literal form. 98 /// 99 /// In "canonical" form addrecs are expanded as arithmetic based on a 100 /// canonical induction variable. Note that CanonicalMode doesn't guarantee 101 /// that all expressions are expanded in "canonical" form. For some 102 /// expressions literal mode can be preferred. 103 bool CanonicalMode; 104 105 /// When invoked from LSR, the expander is in "strength reduction" mode. The 106 /// only difference is that phi's are only reused if they are already in 107 /// "expanded" form. 108 bool LSRMode; 109 110 typedef IRBuilder<InstSimplifyFolder, IRBuilderCallbackInserter> BuilderType; 111 BuilderType Builder; 112 113 // RAII object that stores the current insertion point and restores it when 114 // the object is destroyed. This includes the debug location. Duplicated 115 // from InsertPointGuard to add SetInsertPoint() which is used to updated 116 // InsertPointGuards stack when insert points are moved during SCEV 117 // expansion. 118 class SCEVInsertPointGuard { 119 IRBuilderBase &Builder; 120 AssertingVH<BasicBlock> Block; 121 BasicBlock::iterator Point; 122 DebugLoc DbgLoc; 123 SCEVExpander *SE; 124 125 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete; 126 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete; 127 128 public: 129 SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE) 130 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()), 131 DbgLoc(B.getCurrentDebugLocation()), SE(SE) { 132 SE->InsertPointGuards.push_back(this); 133 } 134 135 ~SCEVInsertPointGuard() { 136 // These guards should always created/destroyed in FIFO order since they 137 // are used to guard lexically scoped blocks of code in 138 // ScalarEvolutionExpander. 139 assert(SE->InsertPointGuards.back() == this); 140 SE->InsertPointGuards.pop_back(); 141 Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point)); 142 Builder.SetCurrentDebugLocation(DbgLoc); 143 } 144 145 BasicBlock::iterator GetInsertPoint() const { return Point; } 146 void SetInsertPoint(BasicBlock::iterator I) { Point = I; } 147 }; 148 149 /// Stack of pointers to saved insert points, used to keep insert points 150 /// consistent when instructions are moved. 151 SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards; 152 153 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS 154 const char *DebugType; 155 #endif 156 157 friend struct SCEVVisitor<SCEVExpander, Value *>; 158 159 public: 160 /// Construct a SCEVExpander in "canonical" mode. 161 explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL, 162 const char *name, bool PreserveLCSSA = true) 163 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA), 164 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true), 165 LSRMode(false), 166 Builder(se.getContext(), InstSimplifyFolder(DL), 167 IRBuilderCallbackInserter( 168 [this](Instruction *I) { rememberInstruction(I); })) { 169 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS 170 DebugType = ""; 171 #endif 172 } 173 174 ~SCEVExpander() { 175 // Make sure the insert point guard stack is consistent. 176 assert(InsertPointGuards.empty()); 177 } 178 179 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS 180 void setDebugType(const char *s) { DebugType = s; } 181 #endif 182 183 /// Erase the contents of the InsertedExpressions map so that users trying 184 /// to expand the same expression into multiple BasicBlocks or different 185 /// places within the same BasicBlock can do so. 186 void clear() { 187 InsertedExpressions.clear(); 188 InsertedValues.clear(); 189 InsertedPostIncValues.clear(); 190 ReusedValues.clear(); 191 ChainedPhis.clear(); 192 InsertedIVs.clear(); 193 } 194 195 ScalarEvolution *getSE() { return &SE; } 196 const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; } 197 198 /// Return a vector containing all instructions inserted during expansion. 199 SmallVector<Instruction *, 32> getAllInsertedInstructions() const { 200 SmallVector<Instruction *, 32> Result; 201 for (auto &VH : InsertedValues) { 202 Value *V = VH; 203 if (ReusedValues.contains(V)) 204 continue; 205 if (auto *Inst = dyn_cast<Instruction>(V)) 206 Result.push_back(Inst); 207 } 208 for (auto &VH : InsertedPostIncValues) { 209 Value *V = VH; 210 if (ReusedValues.contains(V)) 211 continue; 212 if (auto *Inst = dyn_cast<Instruction>(V)) 213 Result.push_back(Inst); 214 } 215 216 return Result; 217 } 218 219 /// Return true for expressions that can't be evaluated at runtime 220 /// within given \b Budget. 221 /// 222 /// At is a parameter which specifies point in code where user is going to 223 /// expand this expression. Sometimes this knowledge can lead to 224 /// a less pessimistic cost estimation. 225 bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, 226 const TargetTransformInfo *TTI, 227 const Instruction *At) { 228 assert(TTI && "This function requires TTI to be provided."); 229 assert(At && "This function requires At instruction to be provided."); 230 if (!TTI) // In assert-less builds, avoid crashing 231 return true; // by always claiming to be high-cost. 232 SmallVector<SCEVOperand, 8> Worklist; 233 SmallPtrSet<const SCEV *, 8> Processed; 234 InstructionCost Cost = 0; 235 unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic; 236 Worklist.emplace_back(-1, -1, Expr); 237 while (!Worklist.empty()) { 238 const SCEVOperand WorkItem = Worklist.pop_back_val(); 239 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI, 240 Processed, Worklist)) 241 return true; 242 } 243 assert(Cost <= ScaledBudget && "Should have returned from inner loop."); 244 return false; 245 } 246 247 /// Return the induction variable increment's IV operand. 248 Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos, 249 bool allowScale); 250 251 /// Utility for hoisting an IV increment. 252 bool hoistIVInc(Instruction *IncV, Instruction *InsertPos); 253 254 /// replace congruent phis with their most canonical representative. Return 255 /// the number of phis eliminated. 256 unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, 257 SmallVectorImpl<WeakTrackingVH> &DeadInsts, 258 const TargetTransformInfo *TTI = nullptr); 259 260 /// Return true if the given expression is safe to expand in the sense that 261 /// all materialized values are safe to speculate anywhere their operands are 262 /// defined, and the expander is capable of expanding the expression. 263 bool isSafeToExpand(const SCEV *S) const; 264 265 /// Return true if the given expression is safe to expand in the sense that 266 /// all materialized values are defined and safe to speculate at the specified 267 /// location and their operands are defined at this location. 268 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const; 269 270 /// Insert code to directly compute the specified SCEV expression into the 271 /// program. The code is inserted into the specified block. 272 Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) { 273 return expandCodeForImpl(SH, Ty, I, true); 274 } 275 276 /// Insert code to directly compute the specified SCEV expression into the 277 /// program. The code is inserted into the SCEVExpander's current 278 /// insertion point. If a type is specified, the result will be expanded to 279 /// have that type, with a cast if necessary. 280 Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) { 281 return expandCodeForImpl(SH, Ty, true); 282 } 283 284 /// Generates a code sequence that evaluates this predicate. The inserted 285 /// instructions will be at position \p Loc. The result will be of type i1 286 /// and will have a value of 0 when the predicate is false and 1 otherwise. 287 Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc); 288 289 /// A specialized variant of expandCodeForPredicate, handling the case when 290 /// we are expanding code for a SCEVComparePredicate. 291 Value *expandComparePredicate(const SCEVComparePredicate *Pred, 292 Instruction *Loc); 293 294 /// Generates code that evaluates if the \p AR expression will overflow. 295 Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, 296 bool Signed); 297 298 /// A specialized variant of expandCodeForPredicate, handling the case when 299 /// we are expanding code for a SCEVWrapPredicate. 300 Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc); 301 302 /// A specialized variant of expandCodeForPredicate, handling the case when 303 /// we are expanding code for a SCEVUnionPredicate. 304 Value *expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc); 305 306 /// Set the current IV increment loop and position. 307 void setIVIncInsertPos(const Loop *L, Instruction *Pos) { 308 assert(!CanonicalMode && 309 "IV increment positions are not supported in CanonicalMode"); 310 IVIncInsertLoop = L; 311 IVIncInsertPos = Pos; 312 } 313 314 /// Enable post-inc expansion for addrecs referring to the given 315 /// loops. Post-inc expansion is only supported in non-canonical mode. 316 void setPostInc(const PostIncLoopSet &L) { 317 assert(!CanonicalMode && 318 "Post-inc expansion is not supported in CanonicalMode"); 319 PostIncLoops = L; 320 } 321 322 /// Disable all post-inc expansion. 323 void clearPostInc() { 324 PostIncLoops.clear(); 325 326 // When we change the post-inc loop set, cached expansions may no 327 // longer be valid. 328 InsertedPostIncValues.clear(); 329 } 330 331 /// Disable the behavior of expanding expressions in canonical form rather 332 /// than in a more literal form. Non-canonical mode is useful for late 333 /// optimization passes. 334 void disableCanonicalMode() { CanonicalMode = false; } 335 336 void enableLSRMode() { LSRMode = true; } 337 338 /// Set the current insertion point. This is useful if multiple calls to 339 /// expandCodeFor() are going to be made with the same insert point and the 340 /// insert point may be moved during one of the expansions (e.g. if the 341 /// insert point is not a block terminator). 342 void setInsertPoint(Instruction *IP) { 343 assert(IP); 344 Builder.SetInsertPoint(IP); 345 } 346 347 /// Clear the current insertion point. This is useful if the instruction 348 /// that had been serving as the insertion point may have been deleted. 349 void clearInsertPoint() { Builder.ClearInsertionPoint(); } 350 351 /// Set location information used by debugging information. 352 void SetCurrentDebugLocation(DebugLoc L) { 353 Builder.SetCurrentDebugLocation(std::move(L)); 354 } 355 356 /// Get location information used by debugging information. 357 DebugLoc getCurrentDebugLocation() const { 358 return Builder.getCurrentDebugLocation(); 359 } 360 361 /// Return true if the specified instruction was inserted by the code 362 /// rewriter. If so, the client should not modify the instruction. Note that 363 /// this also includes instructions re-used during expansion. 364 bool isInsertedInstruction(Instruction *I) const { 365 return InsertedValues.count(I) || InsertedPostIncValues.count(I); 366 } 367 368 void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); } 369 370 /// Try to find the ValueOffsetPair for S. The function is mainly used to 371 /// check whether S can be expanded cheaply. If this returns a non-None 372 /// value, we know we can codegen the `ValueOffsetPair` into a suitable 373 /// expansion identical with S so that S can be expanded cheaply. 374 /// 375 /// L is a hint which tells in which loop to look for the suitable value. 376 /// On success return value which is equivalent to the expanded S at point 377 /// At. Return nullptr if value was not found. 378 /// 379 /// Note that this function does not perform an exhaustive search. I.e if it 380 /// didn't find any value it does not mean that there is no such value. 381 /// 382 Value *getRelatedExistingExpansion(const SCEV *S, const Instruction *At, 383 Loop *L); 384 385 /// Returns a suitable insert point after \p I, that dominates \p 386 /// MustDominate. Skips instructions inserted by the expander. 387 BasicBlock::iterator findInsertPointAfter(Instruction *I, 388 Instruction *MustDominate) const; 389 390 private: 391 LLVMContext &getContext() const { return SE.getContext(); } 392 393 /// Insert code to directly compute the specified SCEV expression into the 394 /// program. The code is inserted into the SCEVExpander's current 395 /// insertion point. If a type is specified, the result will be expanded to 396 /// have that type, with a cast if necessary. If \p Root is true, this 397 /// indicates that \p SH is the top-level expression to expand passed from 398 /// an external client call. 399 Value *expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root); 400 401 /// Insert code to directly compute the specified SCEV expression into the 402 /// program. The code is inserted into the specified block. If \p 403 /// Root is true, this indicates that \p SH is the top-level expression to 404 /// expand passed from an external client call. 405 Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root); 406 407 /// Recursive helper function for isHighCostExpansion. 408 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L, 409 const Instruction &At, InstructionCost &Cost, 410 unsigned Budget, 411 const TargetTransformInfo &TTI, 412 SmallPtrSetImpl<const SCEV *> &Processed, 413 SmallVectorImpl<SCEVOperand> &Worklist); 414 415 /// Insert the specified binary operator, doing a small amount of work to 416 /// avoid inserting an obviously redundant operation, and hoisting to an 417 /// outer loop when the opportunity is there and it is safe. 418 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, 419 SCEV::NoWrapFlags Flags, bool IsSafeToHoist); 420 421 /// We want to cast \p V. What would be the best place for such a cast? 422 BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const; 423 424 /// Arrange for there to be a cast of V to Ty at IP, reusing an existing 425 /// cast if a suitable one exists, moving an existing cast if a suitable one 426 /// exists but isn't in the right place, or creating a new one. 427 Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op, 428 BasicBlock::iterator IP); 429 430 /// Insert a cast of V to the specified type, which must be possible with a 431 /// noop cast, doing what we can to share the casts. 432 Value *InsertNoopCastOfTo(Value *V, Type *Ty); 433 434 /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using 435 /// ptrtoint+arithmetic+inttoptr. 436 Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end, 437 PointerType *PTy, Type *Ty, Value *V); 438 Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V); 439 440 /// Find a previous Value in ExprValueMap for expand. 441 Value *FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt); 442 443 Value *expand(const SCEV *S); 444 445 /// Determine the most "relevant" loop for the given SCEV. 446 const Loop *getRelevantLoop(const SCEV *); 447 448 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID, 449 Twine Name, bool IsSequential = false); 450 451 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } 452 453 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S); 454 455 Value *visitTruncateExpr(const SCEVTruncateExpr *S); 456 457 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); 458 459 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); 460 461 Value *visitAddExpr(const SCEVAddExpr *S); 462 463 Value *visitMulExpr(const SCEVMulExpr *S); 464 465 Value *visitUDivExpr(const SCEVUDivExpr *S); 466 467 Value *visitAddRecExpr(const SCEVAddRecExpr *S); 468 469 Value *visitSMaxExpr(const SCEVSMaxExpr *S); 470 471 Value *visitUMaxExpr(const SCEVUMaxExpr *S); 472 473 Value *visitSMinExpr(const SCEVSMinExpr *S); 474 475 Value *visitUMinExpr(const SCEVUMinExpr *S); 476 477 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S); 478 479 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); } 480 481 void rememberInstruction(Value *I); 482 483 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); 484 485 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); 486 487 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *); 488 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, 489 const Loop *L, Type *ExpandTy, Type *IntTy, 490 Type *&TruncTy, bool &InvertStep); 491 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy, 492 Type *IntTy, bool useSubtract); 493 494 void fixupInsertPoints(Instruction *I); 495 496 /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new 497 /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User. 498 /// If no PHIs have been created, return the unchanged operand \p OpIdx. 499 Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx); 500 }; 501 502 /// Helper to remove instructions inserted during SCEV expansion, unless they 503 /// are marked as used. 504 class SCEVExpanderCleaner { 505 SCEVExpander &Expander; 506 507 /// Indicates whether the result of the expansion is used. If false, the 508 /// instructions added during expansion are removed. 509 bool ResultUsed; 510 511 public: 512 SCEVExpanderCleaner(SCEVExpander &Expander) 513 : Expander(Expander), ResultUsed(false) {} 514 515 ~SCEVExpanderCleaner() { cleanup(); } 516 517 /// Indicate that the result of the expansion is used. 518 void markResultUsed() { ResultUsed = true; } 519 520 void cleanup(); 521 }; 522 } // namespace llvm 523 524 #endif 525