1//===- StraightLineStrengthReduce.cpp - -----------------------------------===//
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 implements straight-line strength reduction (SLSR). Unlike loop
10// strength reduction, this algorithm is designed to reduce arithmetic
11// redundancy in straight-line code instead of loops. It has proven to be
12// effective in simplifying arithmetic statements derived from an unrolled loop.
13// It can also simplify the logic of SeparateConstOffsetFromGEP.
14//
15// There are many optimizations we can perform in the domain of SLSR.
16// We look for strength reduction candidates in the following forms:
17//
18// Form Add: B + i * S
19// Form Mul: (B + i) * S
20// Form GEP: &B[i * S]
21//
22// where S is an integer variable, and i is a constant integer. If we found two
23// candidates S1 and S2 in the same form and S1 dominates S2, we may rewrite S2
24// in a simpler way with respect to S1 (index delta). For example,
25//
26// S1: X = B + i * S
27// S2: Y = B + i' * S => X + (i' - i) * S
28//
29// S1: X = (B + i) * S
30// S2: Y = (B + i') * S => X + (i' - i) * S
31//
32// S1: X = &B[i * S]
33// S2: Y = &B[i' * S] => &X[(i' - i) * S]
34//
35// Note: (i' - i) * S is folded to the extent possible.
36//
37// For Add and GEP forms, we can also rewrite a candidate in a simpler way
38// with respect to other dominating candidates if their B or S are different
39// but other parts are the same. For example,
40//
41// Base Delta:
42// S1: X = B + i * S
43// S2: Y = B' + i * S => X + (B' - B)
44//
45// S1: X = &B [i * S]
46// S2: Y = &B'[i * S] => X + (B' - B)
47//
48// Stride Delta:
49// S1: X = B + i * S
50// S2: Y = B + i * S' => X + i * (S' - S)
51//
52// S1: X = &B[i * S]
53// S2: Y = &B[i * S'] => X + i * (S' - S)
54//
55// PS: Stride delta rewrite on Mul form is usually non-profitable, and Base
56// delta rewrite sometimes is profitable, so we do not support them on Mul.
57//
58// This rewriting is in general a good idea. The code patterns we focus on
59// usually come from loop unrolling, so the delta is likely the same
60// across iterations and can be reused. When that happens, the optimized form
61// takes only one add starting from the second iteration.
62//
63// When such rewriting is possible, we call S1 a "basis" of S2. When S2 has
64// multiple bases, we choose to rewrite S2 with respect to its "immediate"
65// basis, the basis that is the closest ancestor in the dominator tree.
66//
67// TODO:
68//
69// - Floating point arithmetics when fast math is enabled.
70
71#include "llvm/Transforms/Scalar/StraightLineStrengthReduce.h"
72#include "ScalarOptions.h"
73#include "llvm/ADT/APInt.h"
74#include "llvm/ADT/DepthFirstIterator.h"
75#include "llvm/ADT/SetVector.h"
76#include "llvm/ADT/SmallPtrSet.h"
77#include "llvm/ADT/SmallVector.h"
78#include "llvm/ADT/Statistic.h"
79#include "llvm/Analysis/ScalarEvolution.h"
80#include "llvm/Analysis/ScalarEvolutionExpressions.h"
81#include "llvm/Analysis/TargetTransformInfo.h"
82#include "llvm/Analysis/ValueTracking.h"
83#include "llvm/IR/Constants.h"
84#include "llvm/IR/DataLayout.h"
85#include "llvm/IR/DerivedTypes.h"
86#include "llvm/IR/Dominators.h"
87#include "llvm/IR/GetElementPtrTypeIterator.h"
88#include "llvm/IR/IRBuilder.h"
89#include "llvm/IR/Instruction.h"
90#include "llvm/IR/Instructions.h"
91#include "llvm/IR/Module.h"
92#include "llvm/IR/Operator.h"
93#include "llvm/IR/PatternMatch.h"
94#include "llvm/IR/Type.h"
95#include "llvm/IR/Value.h"
96#include "llvm/InitializePasses.h"
97#include "llvm/Pass.h"
98#include "llvm/Support/Casting.h"
99#include "llvm/Support/DebugCounter.h"
100#include "llvm/Support/ErrorHandling.h"
101#include "llvm/Transforms/Scalar.h"
102#include "llvm/Transforms/Utils/Local.h"
103#include <cassert>
104#include <cstdint>
105#include <limits>
106#include <list>
107#include <queue>
108#include <vector>
109
110using namespace llvm;
111using namespace PatternMatch;
112
113#define DEBUG_TYPE "slsr"
114
115static const unsigned UnknownAddressSpace =
116 std::numeric_limits<unsigned>::max();
117
118DEBUG_COUNTER(StraightLineStrengthReduceCounter, "slsr-counter",
119 "Controls whether rewriteCandidate is executed.");
120
121STATISTIC(NumSCEVCandidateBasisDifferences,
122 "Number of candidate-basis SCEV differences computed by SLSR");
123
124namespace {
125
126class StraightLineStrengthReduceLegacyPass : public FunctionPass {
127 const DataLayout *DL = nullptr;
128
129public:
130 static char ID;
131
132 StraightLineStrengthReduceLegacyPass() : FunctionPass(ID) {
133 initializeStraightLineStrengthReduceLegacyPassPass(
134 *PassRegistry::getPassRegistry());
135 }
136
137 void getAnalysisUsage(AnalysisUsage &AU) const override {
138 AU.addRequired<DominatorTreeWrapperPass>();
139 AU.addRequired<ScalarEvolutionWrapperPass>();
140 AU.addRequired<TargetTransformInfoWrapperPass>();
141 // We do not modify the shape of the CFG.
142 AU.setPreservesCFG();
143 }
144
145 bool doInitialization(Module &M) override {
146 DL = &M.getDataLayout();
147 return false;
148 }
149
150 bool runOnFunction(Function &F) override;
151};
152
153class StraightLineStrengthReduce {
154public:
155 StraightLineStrengthReduce(const ScalarOptions &Opts, const DataLayout *DL,
156 DominatorTree *DT, ScalarEvolution *SE,
157 TargetTransformInfo *TTI)
158 : Opts(Opts), DL(DL), DT(DT), SE(SE), TTI(TTI) {}
159
160 // SLSR candidate. Such a candidate must be in one of the forms described in
161 // the header comments.
162 struct Candidate {
163 enum Kind {
164 Invalid, // reserved for the default constructor
165 Add, // B + i * S
166 Mul, // (B + i) * S
167 GEP, // &B[..][i * S][..]
168 };
169
170 enum DKind {
171 InvalidDelta, // reserved for the default constructor
172 IndexDelta, // Delta is a constant from Index
173 BaseDelta, // Delta is a constant or variable from Base
174 StrideDelta, // Delta is a constant or variable from Stride
175 };
176
177 Candidate() = default;
178 Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
179 Instruction *I, const SCEV *StrideSCEV)
180 : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I),
181 StrideSCEV(StrideSCEV) {}
182
183 Kind CandidateKind = Invalid;
184
185 const SCEV *Base = nullptr;
186 // TODO: Swap Index and Stride's name.
187 // Note that Index and Stride of a GEP candidate do not necessarily have the
188 // same integer type. In that case, during rewriting, Stride will be
189 // sign-extended or truncated to Index's type.
190 ConstantInt *Index = nullptr;
191
192 Value *Stride = nullptr;
193
194 // The instruction this candidate corresponds to. It helps us to rewrite a
195 // candidate with respect to its immediate basis. Note that one instruction
196 // can correspond to multiple candidates depending on how you associate the
197 // expression. For instance,
198 //
199 // (a + 1) * (b + 2)
200 //
201 // can be treated as
202 //
203 // <Base: a, Index: 1, Stride: b + 2>
204 //
205 // or
206 //
207 // <Base: b, Index: 2, Stride: a + 1>
208 Instruction *Ins = nullptr;
209
210 // Points to the immediate basis of this candidate, or nullptr if we cannot
211 // find any basis for this candidate.
212 Candidate *Basis = nullptr;
213
214 DKind DeltaKind = InvalidDelta;
215
216 // Store SCEV of Stride to compute delta from different strides
217 const SCEV *StrideSCEV = nullptr;
218
219 // Points to (Y - X) that will be used to rewrite this candidate.
220 Value *Delta = nullptr;
221
222 // List of instructions whose poison-generating annotations must be dropped
223 // if this candidate is used as the basis of an executed rewrite.
224 SmallVector<Instruction *> DropList;
225
226 /// Cost model: Evaluate the computational efficiency of the candidate.
227 ///
228 /// Efficiency levels (higher is better):
229 /// ZeroInst (5) - [Variable] or [Const]
230 /// OneInstOneVar (4) - [Variable + Const] or [Variable * Const]
231 /// OneInstTwoVar (3) - [Variable + Variable] or [Variable * Variable]
232 /// TwoInstOneVar (2) - [Const + Const * Variable]
233 /// TwoInstTwoVar (1) - [Variable + Const * Variable]
234 enum EfficiencyLevel : unsigned {
235 Unknown = 0,
236 TwoInstTwoVar = 1,
237 TwoInstOneVar = 2,
238 OneInstTwoVar = 3,
239 OneInstOneVar = 4,
240 ZeroInst = 5
241 };
242
243 static EfficiencyLevel
244 getComputationEfficiency(Kind CandidateKind, const ConstantInt *Index,
245 const Value *Stride, const SCEV *Base = nullptr) {
246 bool IsConstantBase = false;
247 bool IsZeroBase = false;
248 // When evaluating the efficiency of a rewrite, if the Base's SCEV is
249 // not available, conservatively assume the base is not constant.
250 if (auto *ConstBase = dyn_cast_or_null<SCEVConstant>(Val: Base)) {
251 IsConstantBase = true;
252 IsZeroBase = ConstBase->getValue()->isZero();
253 }
254
255 bool IsConstantStride = isa<ConstantInt>(Val: Stride);
256 bool IsZeroStride =
257 IsConstantStride && cast<ConstantInt>(Val: Stride)->isZero();
258 // All constants
259 if (IsConstantBase && IsConstantStride)
260 return ZeroInst;
261
262 // (Base + Index) * Stride
263 if (CandidateKind == Mul) {
264 if (IsZeroStride)
265 return ZeroInst;
266 if (Index->isZero())
267 return (IsConstantStride || IsConstantBase) ? OneInstOneVar
268 : OneInstTwoVar;
269
270 if (IsConstantBase)
271 return IsZeroBase && (Index->isOne() || Index->isMinusOne())
272 ? ZeroInst
273 : OneInstOneVar;
274
275 if (IsConstantStride) {
276 auto *CI = cast<ConstantInt>(Val: Stride);
277 return (CI->isOne() || CI->isMinusOne()) ? OneInstOneVar
278 : TwoInstOneVar;
279 }
280 return TwoInstTwoVar;
281 }
282
283 // Base + Index * Stride
284 assert(CandidateKind == Add || CandidateKind == GEP);
285 if (Index->isZero() || IsZeroStride)
286 return ZeroInst;
287
288 bool IsSimpleIndex = Index->isOne() || Index->isMinusOne();
289
290 if (IsConstantBase)
291 return IsZeroBase ? (IsSimpleIndex ? ZeroInst : OneInstOneVar)
292 : (IsSimpleIndex ? OneInstOneVar : TwoInstOneVar);
293
294 if (IsConstantStride)
295 return IsZeroStride ? ZeroInst : OneInstOneVar;
296
297 if (IsSimpleIndex)
298 return OneInstTwoVar;
299
300 return TwoInstTwoVar;
301 }
302
303 // Evaluate if the given delta is profitable to rewrite this candidate.
304 bool isProfitableRewrite(const Value &Delta, const DKind DeltaKind) const {
305 // This function cannot accurately evaluate the profit of whole expression
306 // with context. A candidate (B + I * S) cannot express whether this
307 // instruction needs to compute on its own (I * S), which may be shared
308 // with other candidates or may need instructions to compute.
309 // If the rewritten form has the same strength, still rewrite to
310 // (X + Delta) since it may expose more CSE opportunities on Delta, as
311 // unrolled loops usually have identical Delta for each unrolled body.
312 //
313 // Note, this function should only be used on Index Delta rewrite.
314 // Base and Stride delta need context info to evaluate the register
315 // pressure impact from variable delta.
316 return getComputationEfficiency(CandidateKind, Index, Stride, Base) <=
317 getRewriteEfficiency(Delta, DeltaKind);
318 }
319
320 // Evaluate the rewrite efficiency of this candidate with its Basis
321 EfficiencyLevel getRewriteEfficiency() const {
322 return Basis ? getRewriteEfficiency(Delta: *Delta, DeltaKind) : Unknown;
323 }
324
325 // Evaluate the rewrite efficiency of this candidate with a given delta
326 EfficiencyLevel getRewriteEfficiency(const Value &Delta,
327 const DKind DeltaKind) const {
328 switch (DeltaKind) {
329 case BaseDelta: // [X + Delta]
330 return getComputationEfficiency(
331 CandidateKind,
332 Index: ConstantInt::get(Ty: cast<IntegerType>(Val: Delta.getType()), V: 1), Stride: &Delta);
333 case StrideDelta: // [X + Index * Delta]
334 return getComputationEfficiency(CandidateKind, Index, Stride: &Delta);
335 case IndexDelta: // [X + Delta * Stride]
336 return getComputationEfficiency(CandidateKind,
337 Index: cast<ConstantInt>(Val: &Delta), Stride);
338 default:
339 return Unknown;
340 }
341 }
342
343 bool isHighEfficiency() const {
344 return getComputationEfficiency(CandidateKind, Index, Stride, Base) >=
345 OneInstOneVar;
346 }
347
348 // Verify that this candidate has valid delta components relative to the
349 // basis
350 bool hasValidDelta(const Candidate &Basis) const {
351 switch (DeltaKind) {
352 case IndexDelta:
353 // Index differs, Base and Stride must match
354 return Base == Basis.Base && StrideSCEV == Basis.StrideSCEV;
355 case StrideDelta:
356 // Stride differs, Base and Index must match
357 return Base == Basis.Base && Index == Basis.Index;
358 case BaseDelta:
359 // Base differs, Stride and Index must match
360 return StrideSCEV == Basis.StrideSCEV && Index == Basis.Index;
361 default:
362 return false;
363 }
364 }
365 };
366
367 bool runOnFunction(Function &F);
368
369private:
370 // Fetch straight-line basis for rewriting C, update C.Basis to point to it,
371 // and store the delta between C and its Basis in C.Delta.
372 void setBasisAndDeltaFor(Candidate &C);
373 // Returns whether the candidate can be folded into an addressing mode.
374 bool isFoldable(const Candidate &C, TargetTransformInfo *TTI);
375
376 // Checks whether I is in a candidate form. If so, adds all the matching forms
377 // to Candidates, and tries to find the immediate basis for each of them.
378 void allocateCandidatesAndFindBasis(Instruction *I);
379
380 // Allocate candidates and find bases for Add instructions.
381 void allocateCandidatesAndFindBasisForAdd(Instruction *I);
382
383 // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a
384 // candidate.
385 void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
386 Instruction *I);
387 // Allocate candidates and find bases for Mul instructions.
388 void allocateCandidatesAndFindBasisForMul(Instruction *I);
389
390 // Splits LHS into Base + Index and, if succeeds, calls
391 // allocateCandidatesAndFindBasis.
392 void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
393 Instruction *I);
394
395 // Allocate candidates and find bases for GetElementPtr instructions.
396 void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
397
398 // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate
399 // basis.
400 void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
401 ConstantInt *Idx, Value *S,
402 Instruction *I);
403
404 // Rewrites candidate C with respect to Basis.
405 void rewriteCandidate(const Candidate &C);
406
407 // Emit code that computes the "bump" from Basis to C.
408 static Value *emitBump(const Candidate &Basis, const Candidate &C,
409 IRBuilder<> &Builder, const DataLayout *DL);
410
411 const ScalarOptions &Opts;
412 const DataLayout *DL = nullptr;
413 DominatorTree *DT = nullptr;
414 ScalarEvolution *SE;
415 TargetTransformInfo *TTI = nullptr;
416 std::list<Candidate> Candidates;
417
418 // Map from SCEV to instructions that represent the value,
419 // instructions are sorted in depth-first order.
420 DenseMap<const SCEV *, SmallSetVector<Instruction *, 2>> SCEVToInsts;
421
422 using SCEVUnknownSet = SmallPtrSet<const SCEVUnknown *, 4>;
423 DenseMap<const SCEV *, SCEVUnknownSet> SCEVUnknownsCache;
424
425 // Record the dependency between instructions. If C.Basis == B, we would have
426 // {B.Ins -> {C.Ins, ...}}.
427 MapVector<Instruction *, std::vector<Instruction *>> DependencyGraph;
428
429 // Map between each instruction and its possible candidates.
430 DenseMap<Instruction *, SmallVector<Candidate *, 3>> RewriteCandidates;
431
432 // All instructions that have candidates sort in topological order based on
433 // dependency graph, from roots to leaves.
434 std::vector<Instruction *> SortedCandidateInsts;
435
436 // Record all instructions that are already rewritten and will be removed
437 // later.
438 std::vector<Instruction *> DeadInstructions;
439
440 // Classify candidates against Delta kind
441 class CandidateDictTy {
442 public:
443 using CandsTy = SmallVector<Candidate *, 8>;
444 using BBToCandsTy = DenseMap<const BasicBlock *, CandsTy>;
445
446 private:
447 // Index delta Basis must have the same (Base, StrideSCEV, Inst.Type)
448 using IndexDeltaKeyTy = std::tuple<const SCEV *, const SCEV *, Type *>;
449 DenseMap<IndexDeltaKeyTy, BBToCandsTy> IndexDeltaCandidates;
450
451 // Base delta Basis must have the same (StrideSCEV, Index, Inst.Type)
452 using BaseDeltaKeyTy = std::tuple<const SCEV *, ConstantInt *, Type *>;
453 DenseMap<BaseDeltaKeyTy, BBToCandsTy> BaseDeltaCandidates;
454
455 // Stride delta Basis must have the same (Base, Index, Inst.Type)
456 using StrideDeltaKeyTy = std::tuple<const SCEV *, ConstantInt *, Type *>;
457 DenseMap<StrideDeltaKeyTy, BBToCandsTy> StrideDeltaCandidates;
458
459 public:
460 // TODO: Disable index delta on GEP after we completely move
461 // from typed GEP to PtrAdd.
462 const BBToCandsTy *getCandidatesWithDeltaKind(const Candidate &C,
463 Candidate::DKind K) const {
464 assert(K != Candidate::InvalidDelta);
465 if (K == Candidate::IndexDelta) {
466 IndexDeltaKeyTy IndexDeltaKey(C.Base, C.StrideSCEV, C.Ins->getType());
467 auto It = IndexDeltaCandidates.find(Val: IndexDeltaKey);
468 if (It != IndexDeltaCandidates.end())
469 return &It->second;
470 } else if (K == Candidate::BaseDelta) {
471 BaseDeltaKeyTy BaseDeltaKey(C.StrideSCEV, C.Index, C.Ins->getType());
472 auto It = BaseDeltaCandidates.find(Val: BaseDeltaKey);
473 if (It != BaseDeltaCandidates.end())
474 return &It->second;
475 } else {
476 assert(K == Candidate::StrideDelta);
477 StrideDeltaKeyTy StrideDeltaKey(C.Base, C.Index, C.Ins->getType());
478 auto It = StrideDeltaCandidates.find(Val: StrideDeltaKey);
479 if (It != StrideDeltaCandidates.end())
480 return &It->second;
481 }
482 return nullptr;
483 }
484
485 // Pointers to C must remain valid until CandidateDict is cleared.
486 void add(Candidate &C) {
487 Type *ValueType = C.Ins->getType();
488 BasicBlock *BB = C.Ins->getParent();
489 IndexDeltaKeyTy IndexDeltaKey(C.Base, C.StrideSCEV, ValueType);
490 BaseDeltaKeyTy BaseDeltaKey(C.StrideSCEV, C.Index, ValueType);
491 StrideDeltaKeyTy StrideDeltaKey(C.Base, C.Index, ValueType);
492 IndexDeltaCandidates[IndexDeltaKey][BB].push_back(Elt: &C);
493 BaseDeltaCandidates[BaseDeltaKey][BB].push_back(Elt: &C);
494 StrideDeltaCandidates[StrideDeltaKey][BB].push_back(Elt: &C);
495 }
496 // Remove all mappings from set
497 void clear() {
498 IndexDeltaCandidates.clear();
499 BaseDeltaCandidates.clear();
500 StrideDeltaCandidates.clear();
501 }
502 } CandidateDict;
503
504 const SCEV *getAndRecordSCEV(Value *V) {
505 auto *S = SE->getSCEV(V);
506 if (isa<Instruction>(Val: V) && !(isa<SCEVCouldNotCompute>(Val: S) ||
507 isa<SCEVUnknown>(Val: S) || isa<SCEVConstant>(Val: S)))
508 SCEVToInsts[S].insert(X: cast<Instruction>(Val: V));
509
510 return S;
511 }
512
513 bool candidatePredicate(Candidate *Basis, Candidate &C, Candidate::DKind K);
514
515 bool hasSameSCEVUnknowns(const SCEV *A, const SCEV *B);
516
517 bool searchFrom(const CandidateDictTy::BBToCandsTy &BBToCands, Candidate &C,
518 Candidate::DKind K);
519
520 // Get the nearest instruction before CI that represents the value of S,
521 // return nullptr if no instruction is associated with S or S is not a
522 // reusable expression.
523 Value *getNearestValueOfSCEV(const SCEV *S, const Instruction *CI) const {
524 if (isa<SCEVCouldNotCompute>(Val: S))
525 return nullptr;
526
527 if (auto *SU = dyn_cast<SCEVUnknown>(Val: S))
528 return SU->getValue();
529 if (auto *SC = dyn_cast<SCEVConstant>(Val: S))
530 return SC->getValue();
531
532 auto It = SCEVToInsts.find(Val: S);
533 if (It == SCEVToInsts.end())
534 return nullptr;
535
536 // Instructions are sorted in depth-first order, so search for the nearest
537 // instruction by walking the list in reverse order.
538 for (Instruction *I : reverse(C: It->second))
539 if (DT->dominates(Def: I, User: CI))
540 return I;
541
542 return nullptr;
543 }
544
545 struct DeltaInfo {
546 Candidate *Cand;
547 Candidate::DKind DeltaKind;
548 Value *Delta;
549
550 DeltaInfo()
551 : Cand(nullptr), DeltaKind(Candidate::InvalidDelta), Delta(nullptr) {}
552 DeltaInfo(Candidate *Cand, Candidate::DKind DeltaKind, Value *Delta)
553 : Cand(Cand), DeltaKind(DeltaKind), Delta(Delta) {}
554 operator bool() const { return Cand != nullptr; }
555 };
556
557 friend raw_ostream &operator<<(raw_ostream &OS, const DeltaInfo &DI);
558
559 DeltaInfo compressPath(Candidate &C, Candidate *Basis) const;
560
561 Candidate *pickRewriteCandidate(Instruction *I) const;
562 void sortCandidateInstructions();
563 Value *getDelta(const Candidate &C, const Candidate &Basis,
564 Candidate::DKind K) const;
565 static bool isSimilar(Candidate &C, Candidate &Basis, Candidate::DKind K);
566
567 // Add Basis -> C in DependencyGraph and propagate
568 // C.Stride and C.Delta's dependency to C
569 void addDependency(Candidate &C, Candidate *Basis) {
570 if (Basis)
571 DependencyGraph[Basis->Ins].emplace_back(args&: C.Ins);
572
573 // If any candidate of Inst has a basis, then Inst will be rewritten,
574 // C must be rewritten after rewriting Inst, so we need to propagate
575 // the dependency to C
576 auto PropagateDependency = [&](Instruction *Inst) {
577 if (auto CandsIt = RewriteCandidates.find(Val: Inst);
578 CandsIt != RewriteCandidates.end() &&
579 llvm::any_of(Range&: CandsIt->second,
580 P: [](Candidate *Cand) { return Cand->Basis; }))
581 DependencyGraph[Inst].emplace_back(args&: C.Ins);
582 };
583
584 // If C has a variable delta and the delta is a candidate,
585 // propagate its dependency to C
586 if (auto *DeltaInst = dyn_cast_or_null<Instruction>(Val: C.Delta))
587 PropagateDependency(DeltaInst);
588
589 // If the stride is a candidate, propagate its dependency to C
590 if (auto *StrideInst = dyn_cast<Instruction>(Val: C.Stride))
591 PropagateDependency(StrideInst);
592 };
593};
594
595inline raw_ostream &operator<<(raw_ostream &OS,
596 const StraightLineStrengthReduce::Candidate &C) {
597 OS << "Ins: " << *C.Ins << "\n Base: " << *C.Base
598 << "\n Index: " << *C.Index << "\n Stride: " << *C.Stride
599 << "\n StrideSCEV: " << *C.StrideSCEV;
600 if (C.Basis)
601 OS << "\n Delta: " << *C.Delta << "\n Basis: \n [ " << *C.Basis << " ]";
602 return OS;
603}
604
605[[maybe_unused]] LLVM_DUMP_METHOD inline raw_ostream &
606operator<<(raw_ostream &OS, const StraightLineStrengthReduce::DeltaInfo &DI) {
607 OS << "Cand: " << *DI.Cand << "\n";
608 OS << "Delta Kind: ";
609 switch (DI.DeltaKind) {
610 case StraightLineStrengthReduce::Candidate::IndexDelta:
611 OS << "Index";
612 break;
613 case StraightLineStrengthReduce::Candidate::BaseDelta:
614 OS << "Base";
615 break;
616 case StraightLineStrengthReduce::Candidate::StrideDelta:
617 OS << "Stride";
618 break;
619 default:
620 break;
621 }
622 OS << "\nDelta: " << *DI.Delta;
623 return OS;
624}
625
626} // end anonymous namespace
627
628char StraightLineStrengthReduceLegacyPass::ID = 0;
629
630INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr",
631 "Straight line strength reduction", false, false)
632INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
633INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
634INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
635INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass, "slsr",
636 "Straight line strength reduction", false, false)
637
638FunctionPass *llvm::createStraightLineStrengthReducePass() {
639 return new StraightLineStrengthReduceLegacyPass();
640}
641
642// A helper function that unifies the bitwidth of A and B.
643static void unifyBitWidth(APInt &A, APInt &B) {
644 if (A.getBitWidth() < B.getBitWidth())
645 A = A.sext(width: B.getBitWidth());
646 else if (A.getBitWidth() > B.getBitWidth())
647 B = B.sext(width: A.getBitWidth());
648}
649
650// Whether sign-extending V to a wider type may not distribute over arithmetic,
651// i.e. the narrow value does not sign-extend linearly. Only an add/sub/mul/shl
652// carrying the `nsw` flag is known to sign-extend linearly; anything else is
653// treated conservatively as possibly wrapping. This notably covers
654// `xor X, signmask`, which merely flips the sign bit but ScalarEvolution models
655// as a non-nsw `add X, signmask` (so sext does not distribute over it).
656static bool mayHaveSignedWrap(const Value *V) {
657 // OverflowingBinaryOperator covers exactly add/sub/mul/shl.
658 const auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: V);
659 return !OBO || !OBO->hasNoSignedWrap();
660}
661
662// True when the GEP index is narrower than the index width, i.e. it is
663// implicitly sign-extended to the index width (not the pointer width) of the
664// address space before the address computation. A value already at or wider
665// than the index width is not sign-extended (it is used as-is or truncated), so
666// it cannot trigger the non-distributing-sext problem.
667static bool isSignExtendedGepIndex(const Value *Idx, GetElementPtrInst *GEP,
668 const DataLayout *DL) {
669 return Idx->getType()->getIntegerBitWidth() <
670 DL->getIndexSizeInBits(AS: GEP->getAddressSpace());
671}
672
673// A narrow GEP index is sign-extended to the index width before the address
674// computation. SLSR's Stride-delta rewrite turns two such GEPs into
675// Basis + Index * (Sc - Sb), so the stride difference Sc - Sb is reconstructed
676// in the sign-extended domain. This requires sext(Sc) == sext(Sb) +
677// sext(Delta).
678//
679// This screens the rewritten candidate's stride Sc = Sb + Delta: if Sc is
680// computed by a possibly-wrapping op, sext(Sc) does not equal sext(Sb) +
681// sext(Delta) and the rewrite would produce a wrong pointer.
682static bool isSafeToFactorGepIndex(const Value *Idx, GetElementPtrInst *GEP,
683 const DataLayout *DL) {
684 return !isSignExtendedGepIndex(Idx, GEP, DL) || !mayHaveSignedWrap(V: Idx);
685}
686
687Value *StraightLineStrengthReduce::getDelta(const Candidate &C,
688 const Candidate &Basis,
689 Candidate::DKind K) const {
690 if (K == Candidate::IndexDelta) {
691 APInt Idx = C.Index->getValue();
692 APInt BasisIdx = Basis.Index->getValue();
693 unifyBitWidth(A&: Idx, B&: BasisIdx);
694 APInt IndexDelta = Idx - BasisIdx;
695 IntegerType *DeltaType =
696 IntegerType::get(C&: C.Ins->getContext(), NumBits: IndexDelta.getBitWidth());
697 return ConstantInt::get(Ty: DeltaType, V: IndexDelta);
698 } else if (K == Candidate::BaseDelta || K == Candidate::StrideDelta) {
699 const SCEV *BasisPart =
700 (K == Candidate::BaseDelta) ? Basis.Base : Basis.StrideSCEV;
701 const SCEV *CandPart = (K == Candidate::BaseDelta) ? C.Base : C.StrideSCEV;
702 ++NumSCEVCandidateBasisDifferences;
703 const SCEV *Diff = SE->getMinusSCEV(LHS: CandPart, RHS: BasisPart);
704 return getNearestValueOfSCEV(S: Diff, CI: C.Ins);
705 }
706 return nullptr;
707}
708
709bool StraightLineStrengthReduce::isSimilar(Candidate &C, Candidate &Basis,
710 Candidate::DKind K) {
711 bool SameType = false;
712 switch (K) {
713 case Candidate::StrideDelta:
714 SameType = C.StrideSCEV->getType() == Basis.StrideSCEV->getType();
715 break;
716 case Candidate::BaseDelta:
717 SameType = C.Base->getType() == Basis.Base->getType();
718 break;
719 case Candidate::IndexDelta:
720 SameType = true;
721 break;
722 default:;
723 }
724 return SameType && Basis.Ins != C.Ins &&
725 Basis.CandidateKind == C.CandidateKind;
726}
727
728bool StraightLineStrengthReduce::hasSameSCEVUnknowns(const SCEV *A,
729 const SCEV *B) {
730 auto CacheUnknowns = [&](const SCEV *Root) {
731 auto [It, Inserted] = SCEVUnknownsCache.try_emplace(Key: Root);
732 if (!Inserted)
733 return;
734
735 struct Collector {
736 SCEVUnknownSet &Unknowns;
737
738 bool follow(const SCEV *S) {
739 if (auto *Unknown = dyn_cast<SCEVUnknown>(Val: S))
740 Unknowns.insert(Ptr: Unknown);
741 return true;
742 }
743 bool isDone() const { return false; }
744 } C{.Unknowns: It->second};
745 visitAll(Root, Visitor&: C);
746 };
747 CacheUnknowns(A);
748 CacheUnknowns(B);
749
750 return SCEVUnknownsCache.find(Val: A)->second == SCEVUnknownsCache.find(Val: B)->second;
751}
752
753// Try to find a Delta that C can reuse Basis to rewrite.
754// Set C.Delta, C.Basis, and C.DeltaKind if found.
755// Return true if found a constant delta.
756// Return false if not found or the delta is not a constant.
757bool StraightLineStrengthReduce::candidatePredicate(Candidate *Basis,
758 Candidate &C,
759 Candidate::DKind K) {
760 if (!isSimilar(C, Basis&: *Basis, K))
761 return false;
762
763 // Once a reusable delta is found, only a constant delta can improve it.
764 // Different symbolic leaves cannot cancel to a constant, so such a basis
765 // cannot improve C. Skip it and continue searching older candidates.
766 if (C.Delta && K != Candidate::IndexDelta) {
767 const SCEV *CandidateSCEV =
768 K == Candidate::BaseDelta ? C.Base : C.StrideSCEV;
769 const SCEV *BasisSCEV =
770 K == Candidate::BaseDelta ? Basis->Base : Basis->StrideSCEV;
771 if (!hasSameSCEVUnknowns(A: CandidateSCEV, B: BasisSCEV))
772 return false;
773 }
774
775 assert(DT->dominates(Basis->Ins, C.Ins));
776 Value *Delta = getDelta(C, Basis: *Basis, K);
777 if (!Delta)
778 return false;
779
780 // For a GEP Stride-delta rewrite g2 = g1 + Index * Delta, the addresses are
781 // computed from the sign-extended strides, so this requires
782 // sext(Sc) == sext(Sb) + sext(Delta).
783 //
784 // The rewritten candidate's stride Sc = Sb + Delta is already screened
785 // broadly at allocation time (allocateCandidatesAndFindBasis): a wrapping Sc
786 // breaks the identity for any Delta. The basis's stride Sb = Sc - Delta only
787 // needs screening when Delta folds to a *constant*: then sext(Sb) + C can
788 // differ from sext(Sc) if Sb wraps. For a *variable* Delta the basis may wrap
789 // and still be sound, because the candidate stride carries the no-wrap
790 // guarantee (e.g. Sc is an `add nsw`, as in stride_var); rejecting it would
791 // pessimize those.
792 if (K == Candidate::StrideDelta && C.CandidateKind == Candidate::GEP &&
793 isa<ConstantInt>(Val: Delta)) {
794 auto *BasisGEP = cast<GetElementPtrInst>(Val: Basis->Ins);
795 if (!isSafeToFactorGepIndex(Idx: Basis->Stride, GEP: BasisGEP, DL))
796 return false;
797 }
798
799 // IndexDelta rewrite is not always profitable, e.g.,
800 // X = B + 8 * S
801 // Y = B + S,
802 // rewriting Y to X - 7 * S is probably a bad idea.
803 // So, we need to check if the rewrite form's computation efficiency
804 // is better than the original form.
805 if (K == Candidate::IndexDelta &&
806 !C.isProfitableRewrite(Delta: *Delta, DeltaKind: Candidate::IndexDelta))
807 return false;
808
809 // Record delta if none has been found yet, or the new delta is
810 // a constant that is better than the existing delta.
811 if (!C.Delta || isa<ConstantInt>(Val: Delta)) {
812 C.Delta = Delta;
813 C.Basis = Basis;
814 C.DeltaKind = K;
815 }
816 return isa<ConstantInt>(Val: C.Delta);
817}
818
819// return true if find a Basis with constant delta and stop searching,
820// return false if did not find a Basis or the delta is not a constant
821// and continue searching for a Basis with constant delta
822bool StraightLineStrengthReduce::searchFrom(
823 const CandidateDictTy::BBToCandsTy &BBToCands, Candidate &C,
824 Candidate::DKind K) {
825
826 // Stride delta rewrite on Mul form is usually non-profitable, and Base
827 // delta rewrite sometimes is profitable, so we do not support them on Mul.
828 if (C.CandidateKind == Candidate::Mul && K != Candidate::IndexDelta)
829 return false;
830
831 // Search dominating candidates by walking the immediate-dominator chain
832 // from the candidate's defining block upward. Visiting blocks in this
833 // order ensures we prefer the closest dominating basis.
834 const BasicBlock *BB = C.Ins->getParent();
835 while (BB) {
836 auto It = BBToCands.find(Val: BB);
837 if (It != BBToCands.end())
838 for (Candidate *Basis : reverse(C: It->second))
839 if (candidatePredicate(Basis, C, K))
840 return true;
841
842 const DomTreeNode *Node = DT->getNode(BB);
843 if (!Node)
844 break;
845 Node = Node->getIDom();
846 BB = Node ? Node->getBlock() : nullptr;
847 }
848 return false;
849}
850
851void StraightLineStrengthReduce::setBasisAndDeltaFor(Candidate &C) {
852 if (const auto *BaseDeltaCandidates =
853 CandidateDict.getCandidatesWithDeltaKind(C, K: Candidate::BaseDelta))
854 if (searchFrom(BBToCands: *BaseDeltaCandidates, C, K: Candidate::BaseDelta)) {
855 LLVM_DEBUG(dbgs() << "Found delta from Base: " << *C.Delta << "\n");
856 return;
857 }
858
859 if (const auto *StrideDeltaCandidates =
860 CandidateDict.getCandidatesWithDeltaKind(C, K: Candidate::StrideDelta))
861 if (searchFrom(BBToCands: *StrideDeltaCandidates, C, K: Candidate::StrideDelta)) {
862 LLVM_DEBUG(dbgs() << "Found delta from Stride: " << *C.Delta << "\n");
863 return;
864 }
865
866 if (const auto *IndexDeltaCandidates =
867 CandidateDict.getCandidatesWithDeltaKind(C, K: Candidate::IndexDelta))
868 if (searchFrom(BBToCands: *IndexDeltaCandidates, C, K: Candidate::IndexDelta)) {
869 LLVM_DEBUG(dbgs() << "Found delta from Index: " << *C.Delta << "\n");
870 return;
871 }
872
873 // If we did not find a constant delta, we might have found a variable delta
874 if (C.Delta) {
875 LLVM_DEBUG({
876 dbgs() << "Found delta from ";
877 if (C.DeltaKind == Candidate::BaseDelta)
878 dbgs() << "Base: ";
879 else
880 dbgs() << "Stride: ";
881 dbgs() << *C.Delta << "\n";
882 });
883 assert(C.DeltaKind != Candidate::InvalidDelta && C.Basis);
884 }
885}
886
887// Compress the path from `Basis` to the deepest Basis in the Basis chain
888// to avoid non-profitable data dependency and improve ILP.
889// X = A + 1
890// Y = X + 1
891// Z = Y + 1
892// ->
893// X = A + 1
894// Y = A + 2
895// Z = A + 3
896// Return the delta info for C aginst the new Basis
897auto StraightLineStrengthReduce::compressPath(Candidate &C,
898 Candidate *Basis) const
899 -> DeltaInfo {
900 if (!Basis || !Basis->Basis || C.CandidateKind == Candidate::Mul)
901 return {};
902 Candidate *Root = Basis;
903 Value *NewDelta = nullptr;
904 auto NewKind = Candidate::InvalidDelta;
905
906 while (Root->Basis) {
907 Candidate *NextRoot = Root->Basis;
908 if (C.Base == NextRoot->Base && C.StrideSCEV == NextRoot->StrideSCEV &&
909 isSimilar(C, Basis&: *NextRoot, K: Candidate::IndexDelta)) {
910 ConstantInt *CI =
911 cast<ConstantInt>(Val: getDelta(C, Basis: *NextRoot, K: Candidate::IndexDelta));
912 if (CI->isZero() || CI->isOne() || isa<SCEVConstant>(Val: C.StrideSCEV)) {
913 Root = NextRoot;
914 NewKind = Candidate::IndexDelta;
915 NewDelta = CI;
916 continue;
917 }
918 }
919
920 const SCEV *CandPart = nullptr;
921 const SCEV *BasisPart = nullptr;
922 auto CurrKind = Candidate::InvalidDelta;
923 if (C.Base == NextRoot->Base && C.Index == NextRoot->Index) {
924 CandPart = C.StrideSCEV;
925 BasisPart = NextRoot->StrideSCEV;
926 CurrKind = Candidate::StrideDelta;
927 } else if (C.StrideSCEV == NextRoot->StrideSCEV &&
928 C.Index == NextRoot->Index) {
929 CandPart = C.Base;
930 BasisPart = NextRoot->Base;
931 CurrKind = Candidate::BaseDelta;
932 } else
933 break;
934
935 assert(CandPart && BasisPart);
936 if (!isSimilar(C, Basis&: *NextRoot, K: CurrKind))
937 break;
938
939 // Path compression folds a constant Stride-delta directly against the
940 // deeper basis NextRoot, bypassing candidatePredicate's wrap guard. With a
941 // constant delta sext(Sb) + C can differ from sext(Sc) if the deeper
942 // basis's stride wraps, so do not compress past such a basis (mirrors the
943 // check in candidatePredicate).
944 if (CurrKind == Candidate::StrideDelta &&
945 C.CandidateKind == Candidate::GEP &&
946 !isSafeToFactorGepIndex(Idx: NextRoot->Stride,
947 GEP: cast<GetElementPtrInst>(Val: NextRoot->Ins), DL))
948 break;
949
950 ++NumSCEVCandidateBasisDifferences;
951 if (auto DeltaVal =
952 dyn_cast<SCEVConstant>(Val: SE->getMinusSCEV(LHS: CandPart, RHS: BasisPart))) {
953 Root = NextRoot;
954 NewDelta = DeltaVal->getValue();
955 NewKind = CurrKind;
956 } else
957 break;
958 }
959
960 if (Root != Basis) {
961 assert(NewKind != Candidate::InvalidDelta && NewDelta);
962 LLVM_DEBUG(dbgs() << "Found new Basis with " << *NewDelta
963 << " from path compression.\n");
964 return {Root, NewKind, NewDelta};
965 }
966
967 return {};
968}
969
970// Topologically sort candidate instructions based on their relationship in
971// dependency graph.
972void StraightLineStrengthReduce::sortCandidateInstructions() {
973 SortedCandidateInsts.clear();
974 // An instruction may have multiple candidates that get different Basis
975 // instructions, and each candidate can get dependencies from Basis and
976 // Stride when Stride will also be rewritten by SLSR. Hence, an instruction
977 // may have multiple dependencies. Use InDegree to ensure all dependencies
978 // processed before processing itself.
979 DenseMap<Instruction *, int> InDegree;
980 for (auto &KV : DependencyGraph) {
981 InDegree.try_emplace(Key: KV.first, Args: 0);
982
983 for (auto *Child : KV.second) {
984 InDegree[Child]++;
985 }
986 }
987 std::queue<Instruction *> WorkList;
988 DenseSet<Instruction *> Visited;
989
990 for (auto &KV : DependencyGraph)
991 if (InDegree[KV.first] == 0)
992 WorkList.push(x: KV.first);
993
994 while (!WorkList.empty()) {
995 Instruction *I = WorkList.front();
996 WorkList.pop();
997 if (!Visited.insert(V: I).second)
998 continue;
999
1000 SortedCandidateInsts.push_back(x: I);
1001
1002 for (auto *Next : DependencyGraph[I]) {
1003 auto &Degree = InDegree[Next];
1004 if (--Degree == 0)
1005 WorkList.push(x: Next);
1006 }
1007 }
1008
1009 assert(SortedCandidateInsts.size() == DependencyGraph.size() &&
1010 "Dependency graph should not have cycles");
1011}
1012
1013auto StraightLineStrengthReduce::pickRewriteCandidate(Instruction *I) const
1014 -> Candidate * {
1015 // Return the candidate of instruction I that has the highest profit.
1016 auto It = RewriteCandidates.find(Val: I);
1017 if (It == RewriteCandidates.end())
1018 return nullptr;
1019
1020 Candidate *BestC = nullptr;
1021 auto BestEfficiency = Candidate::Unknown;
1022 for (Candidate *C : reverse(C: It->second))
1023 if (C->Basis) {
1024 auto Efficiency = C->getRewriteEfficiency();
1025 if (Efficiency > BestEfficiency) {
1026 BestEfficiency = Efficiency;
1027 BestC = C;
1028 }
1029 }
1030
1031 return BestC;
1032}
1033
1034static bool isGEPFoldable(GetElementPtrInst *GEP,
1035 const TargetTransformInfo *TTI) {
1036 SmallVector<const Value *, 4> Indices(GEP->indices());
1037 return TTI->getGEPCost(
1038 PointeeType: GEP->getSourceElementType(), Ptr: GEP->getPointerOperand(), Operands: Indices,
1039 /*CostKind*/ TTI::TargetCostKind::TCK_SizeAndLatency) ==
1040 TargetTransformInfo::TCC_Free;
1041}
1042
1043// Returns whether (Base + Index * Stride) can be folded to an addressing mode.
1044static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
1045 TargetTransformInfo *TTI) {
1046 // Index->getSExtValue() may crash if Index is wider than 64-bit.
1047 return Index->getBitWidth() <= 64 &&
1048 TTI->isLegalAddressingMode(Ty: Base->getType(), BaseGV: nullptr, BaseOffset: 0, HasBaseReg: true,
1049 Scale: Index->getSExtValue(), AddrSpace: UnknownAddressSpace);
1050}
1051
1052bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
1053 TargetTransformInfo *TTI) {
1054 if (C.CandidateKind == Candidate::Add)
1055 return isAddFoldable(Base: C.Base, Index: C.Index, Stride: C.Stride, TTI);
1056 if (C.CandidateKind == Candidate::GEP)
1057 return isGEPFoldable(GEP: cast<GetElementPtrInst>(Val: C.Ins), TTI);
1058 return false;
1059}
1060
1061void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
1062 Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
1063 Instruction *I) {
1064 bool IsSafe = CT != Candidate::GEP ||
1065 isSafeToFactorGepIndex(Idx: S, GEP: cast<GetElementPtrInst>(Val: I), DL);
1066 // Record the SCEV of S that we may use it as a variable delta.
1067 // Ensure that we rewrite C with a existing IR that reproduces delta value.
1068
1069 Candidate C(CT, B, Idx, S, I, getAndRecordSCEV(V: S));
1070 // If we can fold I into an addressing mode, computing I is likely free or
1071 // takes only one instruction. So, we don't need to analyze or rewrite it.
1072 //
1073 // Currently, this algorithm can at best optimize complex computations into
1074 // a `variable +/* constant` form. However, some targets have stricter
1075 // constraints on the their addressing mode.
1076 // For example, a `variable + constant` can only be folded to an addressing
1077 // mode if the constant falls within a certain range.
1078 // So, we also check if the instruction is already high efficient enough
1079 // for the strength reduction algorithm.
1080 if (IsSafe && !isFoldable(C, TTI) && !C.isHighEfficiency()) {
1081 setBasisAndDeltaFor(C);
1082
1083 // Compress unnecessary rewrite to improve ILP
1084 if (auto Res = compressPath(C, Basis: C.Basis)) {
1085 C.Basis = Res.Cand;
1086 C.DeltaKind = Res.DeltaKind;
1087 C.Delta = Res.Delta;
1088 }
1089 }
1090 // Regardless of whether we find a basis for C, we need to push C to the
1091 // candidate list so that it can be the basis of other candidates.
1092 LLVM_DEBUG(dbgs() << "Allocated Candidate: " << C << "\n");
1093 Candidates.push_back(x: C);
1094 RewriteCandidates[C.Ins].push_back(Elt: &Candidates.back());
1095 // Only add to the dict if this instruction is safe to reuse as a basis. By
1096 // doing this early we avoid calling canReuseInstruction repeatedly for the
1097 // same instruction. The DropList is stored on the Candidate so the flags can
1098 // be dropped only if this candidate is used by an executed rewrite.
1099 if (!Opts.enable_poison_reuse_guard ||
1100 SE->canReuseInstruction(S: SE->getSCEV(V: I), I, DropPoisonGeneratingInsts&: Candidates.back().DropList)) {
1101 CandidateDict.add(C&: Candidates.back());
1102 }
1103}
1104
1105void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
1106 Instruction *I) {
1107 switch (I->getOpcode()) {
1108 case Instruction::Add:
1109 allocateCandidatesAndFindBasisForAdd(I);
1110 break;
1111 case Instruction::Mul:
1112 allocateCandidatesAndFindBasisForMul(I);
1113 break;
1114 case Instruction::GetElementPtr:
1115 allocateCandidatesAndFindBasisForGEP(GEP: cast<GetElementPtrInst>(Val: I));
1116 break;
1117 }
1118}
1119
1120void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
1121 Instruction *I) {
1122 // Try matching B + i * S.
1123 if (!isa<IntegerType>(Val: I->getType()))
1124 return;
1125
1126 assert(I->getNumOperands() == 2 && "isn't I an add?");
1127 Value *LHS = I->getOperand(i: 0), *RHS = I->getOperand(i: 1);
1128 allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
1129 if (LHS != RHS)
1130 allocateCandidatesAndFindBasisForAdd(LHS: RHS, RHS: LHS, I);
1131}
1132
1133void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
1134 Value *LHS, Value *RHS, Instruction *I) {
1135 Value *S = nullptr;
1136 ConstantInt *Idx = nullptr;
1137 if (match(V: RHS, P: m_Mul(L: m_Value(V&: S), R: m_ConstantInt(CI&: Idx)))) {
1138 // I = LHS + RHS = LHS + Idx * S
1139 allocateCandidatesAndFindBasis(CT: Candidate::Add, B: SE->getSCEV(V: LHS), Idx, S, I);
1140 } else if (match(V: RHS, P: m_Shl(L: m_Value(V&: S), R: m_ConstantInt(CI&: Idx)))) {
1141 // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)
1142 APInt One(Idx->getBitWidth(), 1);
1143 Idx = ConstantInt::get(Context&: Idx->getContext(), V: One << Idx->getValue());
1144 allocateCandidatesAndFindBasis(CT: Candidate::Add, B: SE->getSCEV(V: LHS), Idx, S, I);
1145 } else {
1146 // At least, I = LHS + 1 * RHS
1147 ConstantInt *One = ConstantInt::get(Ty: cast<IntegerType>(Val: I->getType()), V: 1);
1148 allocateCandidatesAndFindBasis(CT: Candidate::Add, B: SE->getSCEV(V: LHS), Idx: One, S: RHS,
1149 I);
1150 }
1151}
1152
1153// Returns true if A matches B + C where C is constant.
1154static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {
1155 return match(V: A, P: m_c_Add(L: m_Value(V&: B), R: m_ConstantInt(CI&: C)));
1156}
1157
1158// Returns true if A matches B | C where C is constant.
1159static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
1160 return match(V: A, P: m_c_Or(L: m_Value(V&: B), R: m_ConstantInt(CI&: C)));
1161}
1162
1163void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
1164 Value *LHS, Value *RHS, Instruction *I) {
1165 Value *B = nullptr;
1166 ConstantInt *Idx = nullptr;
1167 if (matchesAdd(A: LHS, B, C&: Idx)) {
1168 // If LHS is in the form of "Base + Index", then I is in the form of
1169 // "(Base + Index) * RHS".
1170 allocateCandidatesAndFindBasis(CT: Candidate::Mul, B: SE->getSCEV(V: B), Idx, S: RHS, I);
1171 } else if (matchesOr(A: LHS, B, C&: Idx) && haveNoCommonBitsSet(LHSCache: B, RHSCache: Idx, SQ: *DL)) {
1172 // If LHS is in the form of "Base | Index" and Base and Index have no common
1173 // bits set, then
1174 // Base | Index = Base + Index
1175 // and I is thus in the form of "(Base + Index) * RHS".
1176 allocateCandidatesAndFindBasis(CT: Candidate::Mul, B: SE->getSCEV(V: B), Idx, S: RHS, I);
1177 } else {
1178 // Otherwise, at least try the form (LHS + 0) * RHS.
1179 ConstantInt *Zero = ConstantInt::get(Ty: cast<IntegerType>(Val: I->getType()), V: 0);
1180 allocateCandidatesAndFindBasis(CT: Candidate::Mul, B: SE->getSCEV(V: LHS), Idx: Zero, S: RHS,
1181 I);
1182 }
1183}
1184
1185void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
1186 Instruction *I) {
1187 // Try matching (B + i) * S.
1188 // TODO: we could extend SLSR to float and vector types.
1189 if (!isa<IntegerType>(Val: I->getType()))
1190 return;
1191
1192 assert(I->getNumOperands() == 2 && "isn't I a mul?");
1193 Value *LHS = I->getOperand(i: 0), *RHS = I->getOperand(i: 1);
1194 allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
1195 if (LHS != RHS) {
1196 // Symmetrically, try to split RHS to Base + Index.
1197 allocateCandidatesAndFindBasisForMul(LHS: RHS, RHS: LHS, I);
1198 }
1199}
1200
1201void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
1202 GetElementPtrInst *GEP) {
1203 // TODO: handle vector GEPs
1204 if (GEP->getType()->isVectorTy())
1205 return;
1206
1207 SmallVector<SCEVUse, 4> IndexExprs;
1208 for (Use &Idx : GEP->indices())
1209 IndexExprs.push_back(Elt: SE->getSCEV(V: Idx));
1210
1211 gep_type_iterator GTI = gep_type_begin(GEP);
1212 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
1213 if (GTI.isStruct())
1214 continue;
1215
1216 SCEVUse OrigIndexExpr = IndexExprs[I - 1];
1217 IndexExprs[I - 1] = SE->getZero(Ty: OrigIndexExpr.getPointer()->getType());
1218
1219 // The base of this candidate is GEP's base plus the offsets of all
1220 // indices except this current one.
1221 SCEVUse BaseExpr = SE->getGEPExpr(GEP: cast<GEPOperator>(Val: GEP), IndexExprs);
1222 Value *ArrayIdx = GEP->getOperand(i_nocapture: I);
1223 uint64_t ElementSize = GTI.getSequentialElementStride(DL: *DL);
1224 IntegerType *PtrIdxTy = cast<IntegerType>(Val: DL->getIndexType(PtrTy: GEP->getType()));
1225 // If the element size overflows the type, truncate.
1226 ConstantInt *ElementSizeIdx =
1227 ConstantInt::getSigned(Ty: PtrIdxTy, V: ElementSize, /*ImplicitTrunc=*/true);
1228 if (ArrayIdx->getType()->getIntegerBitWidth() <=
1229 DL->getIndexSizeInBits(AS: GEP->getAddressSpace())) {
1230 // Skip factoring if ArrayIdx is wider than the index size, because
1231 // ArrayIdx is implicitly truncated to the index size.
1232 allocateCandidatesAndFindBasis(CT: Candidate::GEP, B: BaseExpr, Idx: ElementSizeIdx,
1233 S: ArrayIdx, I: GEP);
1234 }
1235 // When ArrayIdx is the sext of a value, we try to factor that value as
1236 // well. Handling this case is important because array indices are
1237 // typically sign-extended to the pointer index size.
1238 Value *TruncatedArrayIdx = nullptr;
1239 if (match(V: ArrayIdx, P: m_SExt(Op: m_Value(V&: TruncatedArrayIdx))) &&
1240 TruncatedArrayIdx->getType()->getIntegerBitWidth() <=
1241 DL->getIndexSizeInBits(AS: GEP->getAddressSpace())) {
1242 // Skip factoring if TruncatedArrayIdx is wider than the pointer size,
1243 // because TruncatedArrayIdx is implicitly truncated to the pointer size.
1244 allocateCandidatesAndFindBasis(CT: Candidate::GEP, B: BaseExpr, Idx: ElementSizeIdx,
1245 S: TruncatedArrayIdx, I: GEP);
1246 }
1247
1248 IndexExprs[I - 1] = OrigIndexExpr;
1249 }
1250}
1251
1252Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
1253 const Candidate &C,
1254 IRBuilder<> &Builder,
1255 const DataLayout *DL) {
1256 auto CreateMul = [&](Value *LHS, Value *RHS) {
1257 if (ConstantInt *CR = dyn_cast<ConstantInt>(Val: RHS)) {
1258 const APInt &ConstRHS = CR->getValue();
1259 IntegerType *DeltaType =
1260 IntegerType::get(C&: C.Ins->getContext(), NumBits: ConstRHS.getBitWidth());
1261 if (ConstRHS.isPowerOf2()) {
1262 ConstantInt *Exponent =
1263 ConstantInt::get(Ty: DeltaType, V: ConstRHS.logBase2());
1264 return Builder.CreateShl(LHS, RHS: Exponent);
1265 }
1266 if (ConstRHS.isNegatedPowerOf2()) {
1267 ConstantInt *Exponent =
1268 ConstantInt::get(Ty: DeltaType, V: (-ConstRHS).logBase2());
1269 return Builder.CreateNeg(V: Builder.CreateShl(LHS, RHS: Exponent));
1270 }
1271 }
1272
1273 return Builder.CreateMul(LHS, RHS);
1274 };
1275
1276 Value *Delta = C.Delta;
1277 // If Delta is 0, C is a fully redundant of C.Basis,
1278 // just replace C.Ins with Basis.Ins
1279 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Delta);
1280 CI && CI->getValue().isZero())
1281 return nullptr;
1282
1283 if (C.DeltaKind == Candidate::IndexDelta) {
1284 APInt IndexDelta = cast<ConstantInt>(Val: C.Delta)->getValue();
1285 // IndexDelta
1286 // X = B + i * S
1287 // Y = B + i` * S
1288 // = B + (i + IndexDelta) * S
1289 // = B + i * S + IndexDelta * S
1290 // = X + IndexDelta * S
1291 // Bump = (i' - i) * S
1292
1293 // Common case 1: if (i' - i) is 1, Bump = S.
1294 if (IndexDelta == 1)
1295 return C.Stride;
1296 // Common case 2: if (i' - i) is -1, Bump = -S.
1297 if (IndexDelta.isAllOnes())
1298 return Builder.CreateNeg(V: C.Stride);
1299
1300 IntegerType *DeltaType =
1301 IntegerType::get(C&: Basis.Ins->getContext(), NumBits: IndexDelta.getBitWidth());
1302 Value *ExtendedStride = Builder.CreateSExtOrTrunc(V: C.Stride, DestTy: DeltaType);
1303
1304 return CreateMul(ExtendedStride, C.Delta);
1305 }
1306
1307 assert(C.DeltaKind == Candidate::StrideDelta ||
1308 C.DeltaKind == Candidate::BaseDelta);
1309 assert(C.CandidateKind != Candidate::Mul);
1310 // StrideDelta
1311 // X = B + i * S
1312 // Y = B + i * S'
1313 // = B + i * (S + StrideDelta)
1314 // = B + i * S + i * StrideDelta
1315 // = X + i * StrideDelta
1316 // Bump = i * (S' - S)
1317 //
1318 // BaseDelta
1319 // X = B + i * S
1320 // Y = B' + i * S
1321 // = (B + BaseDelta) + i * S
1322 // = X + BaseDelta
1323 // Bump = (B' - B).
1324 Value *Bump = C.Delta;
1325 if (C.DeltaKind == Candidate::StrideDelta) {
1326 // If this value is consumed by a GEP, promote StrideDelta before doing
1327 // StrideDelta * Index to ensure the same semantics as the original GEP.
1328 if (C.CandidateKind == Candidate::GEP) {
1329 auto *GEP = cast<GetElementPtrInst>(Val: C.Ins);
1330 Type *NewScalarIndexTy =
1331 DL->getIndexType(PtrTy: GEP->getPointerOperandType()->getScalarType());
1332 Bump = Builder.CreateSExtOrTrunc(V: Bump, DestTy: NewScalarIndexTy);
1333 }
1334 if (!C.Index->isOne()) {
1335 Value *ExtendedIndex =
1336 Builder.CreateSExtOrTrunc(V: C.Index, DestTy: Bump->getType());
1337 Bump = CreateMul(Bump, ExtendedIndex);
1338 }
1339 }
1340 return Bump;
1341}
1342
1343void StraightLineStrengthReduce::rewriteCandidate(const Candidate &C) {
1344 if (!DebugCounter::shouldExecute(Counter&: StraightLineStrengthReduceCounter))
1345 return;
1346
1347 const Candidate &Basis = *C.Basis;
1348 assert(C.Delta && C.CandidateKind == Basis.CandidateKind &&
1349 C.hasValidDelta(Basis));
1350
1351 for (Instruction *I : Basis.DropList)
1352 I->dropPoisonGeneratingAnnotations();
1353
1354 IRBuilder<> Builder(C.Ins);
1355 Value *Bump = emitBump(Basis, C, Builder, DL);
1356 Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
1357 // If delta is 0, C is a fully redundant of Basis, and Bump is nullptr,
1358 // just replace C.Ins with Basis.Ins
1359 if (!Bump)
1360 Reduced = Basis.Ins;
1361 else {
1362 switch (C.CandidateKind) {
1363 case Candidate::Add:
1364 case Candidate::Mul: {
1365 // C = Basis + Bump
1366 Value *NegBump;
1367 if (match(V: Bump, P: m_Neg(V: m_Value(V&: NegBump)))) {
1368 // If Bump is a neg instruction, emit C = Basis - (-Bump).
1369 Reduced = Builder.CreateSub(LHS: Basis.Ins, RHS: NegBump);
1370 // We only use the negative argument of Bump, and Bump itself may be
1371 // trivially dead.
1372 RecursivelyDeleteTriviallyDeadInstructions(V: Bump);
1373 } else {
1374 // It's tempting to preserve nsw on Bump and/or Reduced. However, it's
1375 // usually unsound, e.g.,
1376 //
1377 // X = (-2 +nsw 1) *nsw INT_MAX
1378 // Y = (-2 +nsw 3) *nsw INT_MAX
1379 // =>
1380 // Y = X + 2 * INT_MAX
1381 //
1382 // Neither + and * in the resultant expression are nsw.
1383 Reduced = Builder.CreateAdd(LHS: Basis.Ins, RHS: Bump);
1384 }
1385 break;
1386 }
1387 case Candidate::GEP: {
1388 bool InBounds = cast<GetElementPtrInst>(Val: C.Ins)->isInBounds();
1389 // C = (char *)Basis + Bump
1390 Reduced = Builder.CreatePtrAdd(Ptr: Basis.Ins, Offset: Bump, Name: "", NW: InBounds);
1391 break;
1392 }
1393 default:
1394 llvm_unreachable("C.CandidateKind is invalid");
1395 };
1396 Reduced->takeName(V: C.Ins);
1397 }
1398 C.Ins->replaceAllUsesWith(V: Reduced);
1399 DeadInstructions.push_back(x: C.Ins);
1400}
1401
1402bool StraightLineStrengthReduceLegacyPass::runOnFunction(Function &F) {
1403 if (skipFunction(F))
1404 return false;
1405
1406 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1407 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1408 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1409 const ScalarOptions &Opts =
1410 F.getContext().getLibraryOptions().get<ScalarOptions>();
1411 return StraightLineStrengthReduce(Opts, DL, DT, SE, TTI).runOnFunction(F);
1412}
1413
1414bool StraightLineStrengthReduce::runOnFunction(Function &F) {
1415 LLVM_DEBUG(dbgs() << "SLSR on Function: " << F.getName() << "\n");
1416 // Traverse the dominator tree in the depth-first order. This order makes sure
1417 // all bases of a candidate are in Candidates when we process it.
1418 for (const auto Node : depth_first(G: DT))
1419 for (auto &I : *(Node->getBlock()))
1420 allocateCandidatesAndFindBasis(I: &I);
1421
1422 // Build the dependency graph and sort candidate instructions from dependency
1423 // roots to leaves
1424 for (auto &C : Candidates) {
1425 DependencyGraph.try_emplace(Key: C.Ins);
1426 addDependency(C, Basis: C.Basis);
1427 }
1428 sortCandidateInstructions();
1429
1430 // Rewrite candidates in the topological order that rewrites a Candidate
1431 // always before rewriting its Basis
1432 for (Instruction *I : reverse(C&: SortedCandidateInsts))
1433 if (Candidate *C = pickRewriteCandidate(I))
1434 rewriteCandidate(C: *C);
1435
1436 for (auto *DeadIns : DeadInstructions)
1437 // A dead instruction may be another dead instruction's op,
1438 // don't delete an instruction twice
1439 if (DeadIns->getParent())
1440 RecursivelyDeleteTriviallyDeadInstructions(V: DeadIns);
1441
1442 bool Ret = !DeadInstructions.empty();
1443 DeadInstructions.clear();
1444 DependencyGraph.clear();
1445 RewriteCandidates.clear();
1446 SortedCandidateInsts.clear();
1447 // First clear all references to candidates in the list
1448 CandidateDict.clear();
1449 // Then destroy the list
1450 Candidates.clear();
1451 return Ret;
1452}
1453
1454PreservedAnalyses
1455StraightLineStrengthReducePass::run(Function &F, FunctionAnalysisManager &AM) {
1456 const DataLayout *DL = &F.getDataLayout();
1457 auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
1458 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
1459 auto *TTI = &AM.getResult<TargetIRAnalysis>(IR&: F);
1460
1461 const ScalarOptions &Opts =
1462 F.getContext().getLibraryOptions().get<ScalarOptions>();
1463 if (!StraightLineStrengthReduce(Opts, DL, DT, SE, TTI).runOnFunction(F))
1464 return PreservedAnalyses::all();
1465
1466 PreservedAnalyses PA;
1467 PA.preserveSet<CFGAnalyses>();
1468 PA.preserve<ScalarEvolutionAnalysis>();
1469 PA.preserve<TargetIRAnalysis>();
1470 return PA;
1471}
1472