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. This file
16// for now contains only an initial step. Specifically, we look for strength
17// reduction candidates in the following forms:
18//
19// Form 1: B + i * S
20// Form 2: (B + i) * S
21// Form 3: &B[i * S]
22//
23// where S is an integer variable, and i is a constant integer. If we found two
24// candidates S1 and S2 in the same form and S1 dominates S2, we may rewrite S2
25// in a simpler way with respect to S1. For example,
26//
27// S1: X = B + i * S
28// S2: Y = B + i' * S => X + (i' - i) * S
29//
30// S1: X = (B + i) * S
31// S2: Y = (B + i') * S => X + (i' - i) * S
32//
33// S1: X = &B[i * S]
34// S2: Y = &B[i' * S] => &X[(i' - i) * S]
35//
36// Note: (i' - i) * S is folded to the extent possible.
37//
38// This rewriting is in general a good idea. The code patterns we focus on
39// usually come from loop unrolling, so (i' - i) * S is likely the same
40// across iterations and can be reused. When that happens, the optimized form
41// takes only one add starting from the second iteration.
42//
43// When such rewriting is possible, we call S1 a "basis" of S2. When S2 has
44// multiple bases, we choose to rewrite S2 with respect to its "immediate"
45// basis, the basis that is the closest ancestor in the dominator tree.
46//
47// TODO:
48//
49// - Floating point arithmetics when fast math is enabled.
50//
51// - SLSR may decrease ILP at the architecture level. Targets that are very
52// sensitive to ILP may want to disable it. Having SLSR to consider ILP is
53// left as future work.
54//
55// - When (i' - i) is constant but i and i' are not, we could still perform
56// SLSR.
57
58#include "llvm/Transforms/Scalar/StraightLineStrengthReduce.h"
59#include "llvm/ADT/APInt.h"
60#include "llvm/ADT/DepthFirstIterator.h"
61#include "llvm/ADT/SmallVector.h"
62#include "llvm/Analysis/ScalarEvolution.h"
63#include "llvm/Analysis/TargetTransformInfo.h"
64#include "llvm/Analysis/ValueTracking.h"
65#include "llvm/IR/Constants.h"
66#include "llvm/IR/DataLayout.h"
67#include "llvm/IR/DerivedTypes.h"
68#include "llvm/IR/Dominators.h"
69#include "llvm/IR/GetElementPtrTypeIterator.h"
70#include "llvm/IR/IRBuilder.h"
71#include "llvm/IR/Instruction.h"
72#include "llvm/IR/Instructions.h"
73#include "llvm/IR/Module.h"
74#include "llvm/IR/Operator.h"
75#include "llvm/IR/PatternMatch.h"
76#include "llvm/IR/Type.h"
77#include "llvm/IR/Value.h"
78#include "llvm/InitializePasses.h"
79#include "llvm/Pass.h"
80#include "llvm/Support/Casting.h"
81#include "llvm/Support/DebugCounter.h"
82#include "llvm/Support/ErrorHandling.h"
83#include "llvm/Transforms/Scalar.h"
84#include "llvm/Transforms/Utils/Local.h"
85#include <cassert>
86#include <cstdint>
87#include <limits>
88#include <list>
89#include <vector>
90
91using namespace llvm;
92using namespace PatternMatch;
93
94static const unsigned UnknownAddressSpace =
95 std::numeric_limits<unsigned>::max();
96
97DEBUG_COUNTER(StraightLineStrengthReduceCounter, "slsr-counter",
98 "Controls whether rewriteCandidateWithBasis is executed.");
99
100namespace {
101
102class StraightLineStrengthReduceLegacyPass : public FunctionPass {
103 const DataLayout *DL = nullptr;
104
105public:
106 static char ID;
107
108 StraightLineStrengthReduceLegacyPass() : FunctionPass(ID) {
109 initializeStraightLineStrengthReduceLegacyPassPass(
110 *PassRegistry::getPassRegistry());
111 }
112
113 void getAnalysisUsage(AnalysisUsage &AU) const override {
114 AU.addRequired<DominatorTreeWrapperPass>();
115 AU.addRequired<ScalarEvolutionWrapperPass>();
116 AU.addRequired<TargetTransformInfoWrapperPass>();
117 // We do not modify the shape of the CFG.
118 AU.setPreservesCFG();
119 }
120
121 bool doInitialization(Module &M) override {
122 DL = &M.getDataLayout();
123 return false;
124 }
125
126 bool runOnFunction(Function &F) override;
127};
128
129class StraightLineStrengthReduce {
130public:
131 StraightLineStrengthReduce(const DataLayout *DL, DominatorTree *DT,
132 ScalarEvolution *SE, TargetTransformInfo *TTI)
133 : DL(DL), DT(DT), SE(SE), TTI(TTI) {}
134
135 // SLSR candidate. Such a candidate must be in one of the forms described in
136 // the header comments.
137 struct Candidate {
138 enum Kind {
139 Invalid, // reserved for the default constructor
140 Add, // B + i * S
141 Mul, // (B + i) * S
142 GEP, // &B[..][i * S][..]
143 };
144
145 Candidate() = default;
146 Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
147 Instruction *I)
148 : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I) {}
149
150 Kind CandidateKind = Invalid;
151
152 const SCEV *Base = nullptr;
153
154 // Note that Index and Stride of a GEP candidate do not necessarily have the
155 // same integer type. In that case, during rewriting, Stride will be
156 // sign-extended or truncated to Index's type.
157 ConstantInt *Index = nullptr;
158
159 Value *Stride = nullptr;
160
161 // The instruction this candidate corresponds to. It helps us to rewrite a
162 // candidate with respect to its immediate basis. Note that one instruction
163 // can correspond to multiple candidates depending on how you associate the
164 // expression. For instance,
165 //
166 // (a + 1) * (b + 2)
167 //
168 // can be treated as
169 //
170 // <Base: a, Index: 1, Stride: b + 2>
171 //
172 // or
173 //
174 // <Base: b, Index: 2, Stride: a + 1>
175 Instruction *Ins = nullptr;
176
177 // Points to the immediate basis of this candidate, or nullptr if we cannot
178 // find any basis for this candidate.
179 Candidate *Basis = nullptr;
180 };
181
182 bool runOnFunction(Function &F);
183
184private:
185 // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
186 // share the same base and stride.
187 bool isBasisFor(const Candidate &Basis, const Candidate &C);
188
189 // Returns whether the candidate can be folded into an addressing mode.
190 bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,
191 const DataLayout *DL);
192
193 // Returns true if C is already in a simplest form and not worth being
194 // rewritten.
195 bool isSimplestForm(const Candidate &C);
196
197 // Checks whether I is in a candidate form. If so, adds all the matching forms
198 // to Candidates, and tries to find the immediate basis for each of them.
199 void allocateCandidatesAndFindBasis(Instruction *I);
200
201 // Allocate candidates and find bases for Add instructions.
202 void allocateCandidatesAndFindBasisForAdd(Instruction *I);
203
204 // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a
205 // candidate.
206 void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
207 Instruction *I);
208 // Allocate candidates and find bases for Mul instructions.
209 void allocateCandidatesAndFindBasisForMul(Instruction *I);
210
211 // Splits LHS into Base + Index and, if succeeds, calls
212 // allocateCandidatesAndFindBasis.
213 void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
214 Instruction *I);
215
216 // Allocate candidates and find bases for GetElementPtr instructions.
217 void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
218
219 // A helper function that scales Idx with ElementSize before invoking
220 // allocateCandidatesAndFindBasis.
221 void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,
222 Value *S, uint64_t ElementSize,
223 Instruction *I);
224
225 // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate
226 // basis.
227 void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
228 ConstantInt *Idx, Value *S,
229 Instruction *I);
230
231 // Rewrites candidate C with respect to Basis.
232 void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
233
234 // A helper function that factors ArrayIdx to a product of a stride and a
235 // constant index, and invokes allocateCandidatesAndFindBasis with the
236 // factorings.
237 void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,
238 GetElementPtrInst *GEP);
239
240 // Emit code that computes the "bump" from Basis to C.
241 static Value *emitBump(const Candidate &Basis, const Candidate &C,
242 IRBuilder<> &Builder, const DataLayout *DL);
243
244 const DataLayout *DL = nullptr;
245 DominatorTree *DT = nullptr;
246 ScalarEvolution *SE;
247 TargetTransformInfo *TTI = nullptr;
248 std::list<Candidate> Candidates;
249
250 // Temporarily holds all instructions that are unlinked (but not deleted) by
251 // rewriteCandidateWithBasis. These instructions will be actually removed
252 // after all rewriting finishes.
253 std::vector<Instruction *> UnlinkedInstructions;
254};
255
256} // end anonymous namespace
257
258char StraightLineStrengthReduceLegacyPass::ID = 0;
259
260INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr",
261 "Straight line strength reduction", false, false)
262INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
263INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
264INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
265INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass, "slsr",
266 "Straight line strength reduction", false, false)
267
268FunctionPass *llvm::createStraightLineStrengthReducePass() {
269 return new StraightLineStrengthReduceLegacyPass();
270}
271
272bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
273 const Candidate &C) {
274 return (Basis.Ins != C.Ins && // skip the same instruction
275 // They must have the same type too. Basis.Base == C.Base
276 // doesn't guarantee their types are the same (PR23975).
277 Basis.Ins->getType() == C.Ins->getType() &&
278 // Basis must dominate C in order to rewrite C with respect to Basis.
279 DT->dominates(A: Basis.Ins->getParent(), B: C.Ins->getParent()) &&
280 // They share the same base, stride, and candidate kind.
281 Basis.Base == C.Base && Basis.Stride == C.Stride &&
282 Basis.CandidateKind == C.CandidateKind);
283}
284
285static bool isGEPFoldable(GetElementPtrInst *GEP,
286 const TargetTransformInfo *TTI) {
287 SmallVector<const Value *, 4> Indices(GEP->indices());
288 return TTI->getGEPCost(PointeeType: GEP->getSourceElementType(), Ptr: GEP->getPointerOperand(),
289 Operands: Indices) == TargetTransformInfo::TCC_Free;
290}
291
292// Returns whether (Base + Index * Stride) can be folded to an addressing mode.
293static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
294 TargetTransformInfo *TTI) {
295 // Index->getSExtValue() may crash if Index is wider than 64-bit.
296 return Index->getBitWidth() <= 64 &&
297 TTI->isLegalAddressingMode(Ty: Base->getType(), BaseGV: nullptr, BaseOffset: 0, HasBaseReg: true,
298 Scale: Index->getSExtValue(), AddrSpace: UnknownAddressSpace);
299}
300
301bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
302 TargetTransformInfo *TTI,
303 const DataLayout *DL) {
304 if (C.CandidateKind == Candidate::Add)
305 return isAddFoldable(Base: C.Base, Index: C.Index, Stride: C.Stride, TTI);
306 if (C.CandidateKind == Candidate::GEP)
307 return isGEPFoldable(GEP: cast<GetElementPtrInst>(Val: C.Ins), TTI);
308 return false;
309}
310
311// Returns true if GEP has zero or one non-zero index.
312static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP) {
313 unsigned NumNonZeroIndices = 0;
314 for (Use &Idx : GEP->indices()) {
315 ConstantInt *ConstIdx = dyn_cast<ConstantInt>(Val&: Idx);
316 if (ConstIdx == nullptr || !ConstIdx->isZero())
317 ++NumNonZeroIndices;
318 }
319 return NumNonZeroIndices <= 1;
320}
321
322bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) {
323 if (C.CandidateKind == Candidate::Add) {
324 // B + 1 * S or B + (-1) * S
325 return C.Index->isOne() || C.Index->isMinusOne();
326 }
327 if (C.CandidateKind == Candidate::Mul) {
328 // (B + 0) * S
329 return C.Index->isZero();
330 }
331 if (C.CandidateKind == Candidate::GEP) {
332 // (char*)B + S or (char*)B - S
333 return ((C.Index->isOne() || C.Index->isMinusOne()) &&
334 hasOnlyOneNonZeroIndex(GEP: cast<GetElementPtrInst>(Val: C.Ins)));
335 }
336 return false;
337}
338
339// TODO: We currently implement an algorithm whose time complexity is linear in
340// the number of existing candidates. However, we could do better by using
341// ScopedHashTable. Specifically, while traversing the dominator tree, we could
342// maintain all the candidates that dominate the basic block being traversed in
343// a ScopedHashTable. This hash table is indexed by the base and the stride of
344// a candidate. Therefore, finding the immediate basis of a candidate boils down
345// to one hash-table look up.
346void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
347 Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
348 Instruction *I) {
349 Candidate C(CT, B, Idx, S, I);
350 // SLSR can complicate an instruction in two cases:
351 //
352 // 1. If we can fold I into an addressing mode, computing I is likely free or
353 // takes only one instruction.
354 //
355 // 2. I is already in a simplest form. For example, when
356 // X = B + 8 * S
357 // Y = B + S,
358 // rewriting Y to X - 7 * S is probably a bad idea.
359 //
360 // In the above cases, we still add I to the candidate list so that I can be
361 // the basis of other candidates, but we leave I's basis blank so that I
362 // won't be rewritten.
363 if (!isFoldable(C, TTI, DL) && !isSimplestForm(C)) {
364 // Try to compute the immediate basis of C.
365 unsigned NumIterations = 0;
366 // Limit the scan radius to avoid running in quadratice time.
367 static const unsigned MaxNumIterations = 50;
368 for (auto Basis = Candidates.rbegin();
369 Basis != Candidates.rend() && NumIterations < MaxNumIterations;
370 ++Basis, ++NumIterations) {
371 if (isBasisFor(Basis: *Basis, C)) {
372 C.Basis = &(*Basis);
373 break;
374 }
375 }
376 }
377 // Regardless of whether we find a basis for C, we need to push C to the
378 // candidate list so that it can be the basis of other candidates.
379 Candidates.push_back(x: C);
380}
381
382void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
383 Instruction *I) {
384 switch (I->getOpcode()) {
385 case Instruction::Add:
386 allocateCandidatesAndFindBasisForAdd(I);
387 break;
388 case Instruction::Mul:
389 allocateCandidatesAndFindBasisForMul(I);
390 break;
391 case Instruction::GetElementPtr:
392 allocateCandidatesAndFindBasisForGEP(GEP: cast<GetElementPtrInst>(Val: I));
393 break;
394 }
395}
396
397void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
398 Instruction *I) {
399 // Try matching B + i * S.
400 if (!isa<IntegerType>(Val: I->getType()))
401 return;
402
403 assert(I->getNumOperands() == 2 && "isn't I an add?");
404 Value *LHS = I->getOperand(i: 0), *RHS = I->getOperand(i: 1);
405 allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
406 if (LHS != RHS)
407 allocateCandidatesAndFindBasisForAdd(LHS: RHS, RHS: LHS, I);
408}
409
410void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
411 Value *LHS, Value *RHS, Instruction *I) {
412 Value *S = nullptr;
413 ConstantInt *Idx = nullptr;
414 if (match(V: RHS, P: m_Mul(L: m_Value(V&: S), R: m_ConstantInt(CI&: Idx)))) {
415 // I = LHS + RHS = LHS + Idx * S
416 allocateCandidatesAndFindBasis(CT: Candidate::Add, B: SE->getSCEV(V: LHS), Idx, S, I);
417 } else if (match(V: RHS, P: m_Shl(L: m_Value(V&: S), R: m_ConstantInt(CI&: Idx)))) {
418 // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)
419 APInt One(Idx->getBitWidth(), 1);
420 Idx = ConstantInt::get(Context&: Idx->getContext(), V: One << Idx->getValue());
421 allocateCandidatesAndFindBasis(CT: Candidate::Add, B: SE->getSCEV(V: LHS), Idx, S, I);
422 } else {
423 // At least, I = LHS + 1 * RHS
424 ConstantInt *One = ConstantInt::get(Ty: cast<IntegerType>(Val: I->getType()), V: 1);
425 allocateCandidatesAndFindBasis(CT: Candidate::Add, B: SE->getSCEV(V: LHS), Idx: One, S: RHS,
426 I);
427 }
428}
429
430// Returns true if A matches B + C where C is constant.
431static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {
432 return match(V: A, P: m_c_Add(L: m_Value(V&: B), R: m_ConstantInt(CI&: C)));
433}
434
435// Returns true if A matches B | C where C is constant.
436static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
437 return match(V: A, P: m_c_Or(L: m_Value(V&: B), R: m_ConstantInt(CI&: C)));
438}
439
440void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
441 Value *LHS, Value *RHS, Instruction *I) {
442 Value *B = nullptr;
443 ConstantInt *Idx = nullptr;
444 if (matchesAdd(A: LHS, B, C&: Idx)) {
445 // If LHS is in the form of "Base + Index", then I is in the form of
446 // "(Base + Index) * RHS".
447 allocateCandidatesAndFindBasis(CT: Candidate::Mul, B: SE->getSCEV(V: B), Idx, S: RHS, I);
448 } else if (matchesOr(A: LHS, B, C&: Idx) && haveNoCommonBitsSet(LHSCache: B, RHSCache: Idx, SQ: *DL)) {
449 // If LHS is in the form of "Base | Index" and Base and Index have no common
450 // bits set, then
451 // Base | Index = Base + Index
452 // and I is thus in the form of "(Base + Index) * RHS".
453 allocateCandidatesAndFindBasis(CT: Candidate::Mul, B: SE->getSCEV(V: B), Idx, S: RHS, I);
454 } else {
455 // Otherwise, at least try the form (LHS + 0) * RHS.
456 ConstantInt *Zero = ConstantInt::get(Ty: cast<IntegerType>(Val: I->getType()), V: 0);
457 allocateCandidatesAndFindBasis(CT: Candidate::Mul, B: SE->getSCEV(V: LHS), Idx: Zero, S: RHS,
458 I);
459 }
460}
461
462void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
463 Instruction *I) {
464 // Try matching (B + i) * S.
465 // TODO: we could extend SLSR to float and vector types.
466 if (!isa<IntegerType>(Val: I->getType()))
467 return;
468
469 assert(I->getNumOperands() == 2 && "isn't I a mul?");
470 Value *LHS = I->getOperand(i: 0), *RHS = I->getOperand(i: 1);
471 allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
472 if (LHS != RHS) {
473 // Symmetrically, try to split RHS to Base + Index.
474 allocateCandidatesAndFindBasisForMul(LHS: RHS, RHS: LHS, I);
475 }
476}
477
478void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
479 const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,
480 Instruction *I) {
481 // I = B + sext(Idx *nsw S) * ElementSize
482 // = B + (sext(Idx) * sext(S)) * ElementSize
483 // = B + (sext(Idx) * ElementSize) * sext(S)
484 // Casting to IntegerType is safe because we skipped vector GEPs.
485 IntegerType *PtrIdxTy = cast<IntegerType>(Val: DL->getIndexType(PtrTy: I->getType()));
486 ConstantInt *ScaledIdx = ConstantInt::get(
487 Ty: PtrIdxTy, V: Idx->getSExtValue() * (int64_t)ElementSize, IsSigned: true);
488 allocateCandidatesAndFindBasis(CT: Candidate::GEP, B, Idx: ScaledIdx, S, I);
489}
490
491void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,
492 const SCEV *Base,
493 uint64_t ElementSize,
494 GetElementPtrInst *GEP) {
495 // At least, ArrayIdx = ArrayIdx *nsw 1.
496 allocateCandidatesAndFindBasisForGEP(
497 B: Base, Idx: ConstantInt::get(Ty: cast<IntegerType>(Val: ArrayIdx->getType()), V: 1),
498 S: ArrayIdx, ElementSize, I: GEP);
499 Value *LHS = nullptr;
500 ConstantInt *RHS = nullptr;
501 // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx
502 // itself. This would allow us to handle the shl case for free. However,
503 // matching SCEVs has two issues:
504 //
505 // 1. this would complicate rewriting because the rewriting procedure
506 // would have to translate SCEVs back to IR instructions. This translation
507 // is difficult when LHS is further evaluated to a composite SCEV.
508 //
509 // 2. ScalarEvolution is designed to be control-flow oblivious. It tends
510 // to strip nsw/nuw flags which are critical for SLSR to trace into
511 // sext'ed multiplication.
512 if (match(V: ArrayIdx, P: m_NSWMul(L: m_Value(V&: LHS), R: m_ConstantInt(CI&: RHS)))) {
513 // SLSR is currently unsafe if i * S may overflow.
514 // GEP = Base + sext(LHS *nsw RHS) * ElementSize
515 allocateCandidatesAndFindBasisForGEP(B: Base, Idx: RHS, S: LHS, ElementSize, I: GEP);
516 } else if (match(V: ArrayIdx, P: m_NSWShl(L: m_Value(V&: LHS), R: m_ConstantInt(CI&: RHS)))) {
517 // GEP = Base + sext(LHS <<nsw RHS) * ElementSize
518 // = Base + sext(LHS *nsw (1 << RHS)) * ElementSize
519 APInt One(RHS->getBitWidth(), 1);
520 ConstantInt *PowerOf2 =
521 ConstantInt::get(Context&: RHS->getContext(), V: One << RHS->getValue());
522 allocateCandidatesAndFindBasisForGEP(B: Base, Idx: PowerOf2, S: LHS, ElementSize, I: GEP);
523 }
524}
525
526void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
527 GetElementPtrInst *GEP) {
528 // TODO: handle vector GEPs
529 if (GEP->getType()->isVectorTy())
530 return;
531
532 SmallVector<const SCEV *, 4> IndexExprs;
533 for (Use &Idx : GEP->indices())
534 IndexExprs.push_back(Elt: SE->getSCEV(V: Idx));
535
536 gep_type_iterator GTI = gep_type_begin(GEP);
537 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
538 if (GTI.isStruct())
539 continue;
540
541 const SCEV *OrigIndexExpr = IndexExprs[I - 1];
542 IndexExprs[I - 1] = SE->getZero(Ty: OrigIndexExpr->getType());
543
544 // The base of this candidate is GEP's base plus the offsets of all
545 // indices except this current one.
546 const SCEV *BaseExpr = SE->getGEPExpr(GEP: cast<GEPOperator>(Val: GEP), IndexExprs);
547 Value *ArrayIdx = GEP->getOperand(i_nocapture: I);
548 uint64_t ElementSize = GTI.getSequentialElementStride(DL: *DL);
549 if (ArrayIdx->getType()->getIntegerBitWidth() <=
550 DL->getIndexSizeInBits(AS: GEP->getAddressSpace())) {
551 // Skip factoring if ArrayIdx is wider than the index size, because
552 // ArrayIdx is implicitly truncated to the index size.
553 factorArrayIndex(ArrayIdx, Base: BaseExpr, ElementSize, GEP);
554 }
555 // When ArrayIdx is the sext of a value, we try to factor that value as
556 // well. Handling this case is important because array indices are
557 // typically sign-extended to the pointer index size.
558 Value *TruncatedArrayIdx = nullptr;
559 if (match(V: ArrayIdx, P: m_SExt(Op: m_Value(V&: TruncatedArrayIdx))) &&
560 TruncatedArrayIdx->getType()->getIntegerBitWidth() <=
561 DL->getIndexSizeInBits(AS: GEP->getAddressSpace())) {
562 // Skip factoring if TruncatedArrayIdx is wider than the pointer size,
563 // because TruncatedArrayIdx is implicitly truncated to the pointer size.
564 factorArrayIndex(ArrayIdx: TruncatedArrayIdx, Base: BaseExpr, ElementSize, GEP);
565 }
566
567 IndexExprs[I - 1] = OrigIndexExpr;
568 }
569}
570
571// A helper function that unifies the bitwidth of A and B.
572static void unifyBitWidth(APInt &A, APInt &B) {
573 if (A.getBitWidth() < B.getBitWidth())
574 A = A.sext(width: B.getBitWidth());
575 else if (A.getBitWidth() > B.getBitWidth())
576 B = B.sext(width: A.getBitWidth());
577}
578
579Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
580 const Candidate &C,
581 IRBuilder<> &Builder,
582 const DataLayout *DL) {
583 APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
584 unifyBitWidth(A&: Idx, B&: BasisIdx);
585 APInt IndexOffset = Idx - BasisIdx;
586
587 // Compute Bump = C - Basis = (i' - i) * S.
588 // Common case 1: if (i' - i) is 1, Bump = S.
589 if (IndexOffset == 1)
590 return C.Stride;
591 // Common case 2: if (i' - i) is -1, Bump = -S.
592 if (IndexOffset.isAllOnes())
593 return Builder.CreateNeg(V: C.Stride);
594
595 // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may
596 // have different bit widths.
597 IntegerType *DeltaType =
598 IntegerType::get(C&: Basis.Ins->getContext(), NumBits: IndexOffset.getBitWidth());
599 Value *ExtendedStride = Builder.CreateSExtOrTrunc(V: C.Stride, DestTy: DeltaType);
600 if (IndexOffset.isPowerOf2()) {
601 // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i).
602 ConstantInt *Exponent = ConstantInt::get(Ty: DeltaType, V: IndexOffset.logBase2());
603 return Builder.CreateShl(LHS: ExtendedStride, RHS: Exponent);
604 }
605 if (IndexOffset.isNegatedPowerOf2()) {
606 // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i).
607 ConstantInt *Exponent =
608 ConstantInt::get(Ty: DeltaType, V: (-IndexOffset).logBase2());
609 return Builder.CreateNeg(V: Builder.CreateShl(LHS: ExtendedStride, RHS: Exponent));
610 }
611 Constant *Delta = ConstantInt::get(Ty: DeltaType, V: IndexOffset);
612 return Builder.CreateMul(LHS: ExtendedStride, RHS: Delta);
613}
614
615void StraightLineStrengthReduce::rewriteCandidateWithBasis(
616 const Candidate &C, const Candidate &Basis) {
617 if (!DebugCounter::shouldExecute(CounterName: StraightLineStrengthReduceCounter))
618 return;
619
620 assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
621 C.Stride == Basis.Stride);
622 // We run rewriteCandidateWithBasis on all candidates in a post-order, so the
623 // basis of a candidate cannot be unlinked before the candidate.
624 assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
625
626 // An instruction can correspond to multiple candidates. Therefore, instead of
627 // simply deleting an instruction when we rewrite it, we mark its parent as
628 // nullptr (i.e. unlink it) so that we can skip the candidates whose
629 // instruction is already rewritten.
630 if (!C.Ins->getParent())
631 return;
632
633 IRBuilder<> Builder(C.Ins);
634 Value *Bump = emitBump(Basis, C, Builder, DL);
635 Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
636 switch (C.CandidateKind) {
637 case Candidate::Add:
638 case Candidate::Mul: {
639 // C = Basis + Bump
640 Value *NegBump;
641 if (match(V: Bump, P: m_Neg(V: m_Value(V&: NegBump)))) {
642 // If Bump is a neg instruction, emit C = Basis - (-Bump).
643 Reduced = Builder.CreateSub(LHS: Basis.Ins, RHS: NegBump);
644 // We only use the negative argument of Bump, and Bump itself may be
645 // trivially dead.
646 RecursivelyDeleteTriviallyDeadInstructions(V: Bump);
647 } else {
648 // It's tempting to preserve nsw on Bump and/or Reduced. However, it's
649 // usually unsound, e.g.,
650 //
651 // X = (-2 +nsw 1) *nsw INT_MAX
652 // Y = (-2 +nsw 3) *nsw INT_MAX
653 // =>
654 // Y = X + 2 * INT_MAX
655 //
656 // Neither + and * in the resultant expression are nsw.
657 Reduced = Builder.CreateAdd(LHS: Basis.Ins, RHS: Bump);
658 }
659 break;
660 }
661 case Candidate::GEP: {
662 bool InBounds = cast<GetElementPtrInst>(Val: C.Ins)->isInBounds();
663 // C = (char *)Basis + Bump
664 Reduced = Builder.CreatePtrAdd(Ptr: Basis.Ins, Offset: Bump, Name: "", NW: InBounds);
665 break;
666 }
667 default:
668 llvm_unreachable("C.CandidateKind is invalid");
669 };
670 Reduced->takeName(V: C.Ins);
671 C.Ins->replaceAllUsesWith(V: Reduced);
672 // Unlink C.Ins so that we can skip other candidates also corresponding to
673 // C.Ins. The actual deletion is postponed to the end of runOnFunction.
674 C.Ins->removeFromParent();
675 UnlinkedInstructions.push_back(x: C.Ins);
676}
677
678bool StraightLineStrengthReduceLegacyPass::runOnFunction(Function &F) {
679 if (skipFunction(F))
680 return false;
681
682 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
683 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
684 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
685 return StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F);
686}
687
688bool StraightLineStrengthReduce::runOnFunction(Function &F) {
689 // Traverse the dominator tree in the depth-first order. This order makes sure
690 // all bases of a candidate are in Candidates when we process it.
691 for (const auto Node : depth_first(G: DT))
692 for (auto &I : *(Node->getBlock()))
693 allocateCandidatesAndFindBasis(I: &I);
694
695 // Rewrite candidates in the reverse depth-first order. This order makes sure
696 // a candidate being rewritten is not a basis for any other candidate.
697 while (!Candidates.empty()) {
698 const Candidate &C = Candidates.back();
699 if (C.Basis != nullptr) {
700 rewriteCandidateWithBasis(C, Basis: *C.Basis);
701 }
702 Candidates.pop_back();
703 }
704
705 // Delete all unlink instructions.
706 for (auto *UnlinkedInst : UnlinkedInstructions) {
707 for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
708 Value *Op = UnlinkedInst->getOperand(i: I);
709 UnlinkedInst->setOperand(i: I, Val: nullptr);
710 RecursivelyDeleteTriviallyDeadInstructions(V: Op);
711 }
712 UnlinkedInst->deleteValue();
713 }
714 bool Ret = !UnlinkedInstructions.empty();
715 UnlinkedInstructions.clear();
716 return Ret;
717}
718
719namespace llvm {
720
721PreservedAnalyses
722StraightLineStrengthReducePass::run(Function &F, FunctionAnalysisManager &AM) {
723 const DataLayout *DL = &F.getDataLayout();
724 auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
725 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
726 auto *TTI = &AM.getResult<TargetIRAnalysis>(IR&: F);
727
728 if (!StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F))
729 return PreservedAnalyses::all();
730
731 PreservedAnalyses PA;
732 PA.preserveSet<CFGAnalyses>();
733 PA.preserve<DominatorTreeAnalysis>();
734 PA.preserve<ScalarEvolutionAnalysis>();
735 PA.preserve<TargetIRAnalysis>();
736 return PA;
737}
738
739} // namespace llvm
740