LLVM 18.0.0git
StraightLineStrengthReduce.cpp
Go to the documentation of this file.
1//===- StraightLineStrengthReduce.cpp - -----------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
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
65#include "llvm/IR/Constants.h"
66#include "llvm/IR/DataLayout.h"
68#include "llvm/IR/Dominators.h"
70#include "llvm/IR/IRBuilder.h"
71#include "llvm/IR/Instruction.h"
73#include "llvm/IR/Module.h"
74#include "llvm/IR/Operator.h"
76#include "llvm/IR/Type.h"
77#include "llvm/IR/Value.h"
79#include "llvm/Pass.h"
84#include <cassert>
85#include <cstdint>
86#include <limits>
87#include <list>
88#include <vector>
89
90using namespace llvm;
91using namespace PatternMatch;
92
94 std::numeric_limits<unsigned>::max();
95
96namespace {
97
98class StraightLineStrengthReduceLegacyPass : public FunctionPass {
99 const DataLayout *DL = nullptr;
100
101public:
102 static char ID;
103
104 StraightLineStrengthReduceLegacyPass() : FunctionPass(ID) {
107 }
108
109 void getAnalysisUsage(AnalysisUsage &AU) const override {
113 // We do not modify the shape of the CFG.
114 AU.setPreservesCFG();
115 }
116
117 bool doInitialization(Module &M) override {
118 DL = &M.getDataLayout();
119 return false;
120 }
121
122 bool runOnFunction(Function &F) override;
123};
124
125class StraightLineStrengthReduce {
126public:
127 StraightLineStrengthReduce(const DataLayout *DL, DominatorTree *DT,
129 : DL(DL), DT(DT), SE(SE), TTI(TTI) {}
130
131 // SLSR candidate. Such a candidate must be in one of the forms described in
133 struct Candidate {
134 enum Kind {
135 Invalid, // reserved for the default constructor
136 Add, // B + i * S
137 Mul, // (B + i) * S
138 GEP, // &B[..][i * S][..]
139 };
140
141 Candidate() = default;
142 Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
143 Instruction *I)
144 : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I) {}
145
146 Kind CandidateKind = Invalid;
147
148 const SCEV *Base = nullptr;
149
150 // Note that Index and Stride of a GEP candidate do not necessarily have the
151 // same integer type. In that case, during rewriting, Stride will be
152 // sign-extended or truncated to Index's type.
153 ConstantInt *Index = nullptr;
154
155 Value *Stride = nullptr;
156
157 // The instruction this candidate corresponds to. It helps us to rewrite a
158 // candidate with respect to its immediate basis. Note that one instruction
159 // can correspond to multiple candidates depending on how you associate the
160 // expression. For instance,
161 //
162 // (a + 1) * (b + 2)
163 //
164 // can be treated as
165 //
166 // <Base: a, Index: 1, Stride: b + 2>
167 //
168 // or
169 //
170 // <Base: b, Index: 2, Stride: a + 1>
171 Instruction *Ins = nullptr;
172
173 // Points to the immediate basis of this candidate, or nullptr if we cannot
174 // find any basis for this candidate.
175 Candidate *Basis = nullptr;
176 };
177
178 bool runOnFunction(Function &F);
179
180private:
181 // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
182 // share the same base and stride.
183 bool isBasisFor(const Candidate &Basis, const Candidate &C);
184
185 // Returns whether the candidate can be folded into an addressing mode.
186 bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,
187 const DataLayout *DL);
188
189 // Returns true if C is already in a simplest form and not worth being
190 // rewritten.
191 bool isSimplestForm(const Candidate &C);
192
193 // Checks whether I is in a candidate form. If so, adds all the matching forms
194 // to Candidates, and tries to find the immediate basis for each of them.
195 void allocateCandidatesAndFindBasis(Instruction *I);
196
197 // Allocate candidates and find bases for Add instructions.
199
200 // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a
201 // candidate.
202 void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
203 Instruction *I);
204 // Allocate candidates and find bases for Mul instructions.
205 void allocateCandidatesAndFindBasisForMul(Instruction *I);
206
207 // Splits LHS into Base + Index and, if succeeds, calls
208 // allocateCandidatesAndFindBasis.
209 void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
210 Instruction *I);
211
212 // Allocate candidates and find bases for GetElementPtr instructions.
213 void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
214
215 // A helper function that scales Idx with ElementSize before invoking
216 // allocateCandidatesAndFindBasis.
217 void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,
218 Value *S, uint64_t ElementSize,
219 Instruction *I);
220
221 // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate
222 // basis.
223 void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
224 ConstantInt *Idx, Value *S,
225 Instruction *I);
226
227 // Rewrites candidate C with respect to Basis.
228 void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
229
230 // A helper function that factors ArrayIdx to a product of a stride and a
231 // constant index, and invokes allocateCandidatesAndFindBasis with the
232 // factorings.
233 void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,
235
236 // Emit code that computes the "bump" from Basis to C. If the candidate is a
237 // GEP and the bump is not divisible by the element size of the GEP, this
238 // function sets the BumpWithUglyGEP flag to notify its caller to bump the
239 // basis using an ugly GEP.
240 static Value *emitBump(const Candidate &Basis, const Candidate &C,
241 IRBuilder<> &Builder, const DataLayout *DL,
242 bool &BumpWithUglyGEP);
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.
254};
255
256} // end anonymous namespace
257
258char StraightLineStrengthReduceLegacyPass::ID = 0;
259
260INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr",
261 "Straight line strength reduction", false, false)
265INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass, "slsr",
266 "Straight line strength reduction", false, false)
267
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 doesn't
276 // 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(Basis.Ins->getParent(), 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
286 const TargetTransformInfo *TTI) {
287 SmallVector<const Value *, 4> Indices(GEP->indices());
288 return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
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,
295 // Index->getSExtValue() may crash if Index is wider than 64-bit.
296 return Index->getBitWidth() <= 64 &&
299}
300
301bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
303 const DataLayout *DL) {
305 return isAddFoldable(C.Base, C.Index, C.Stride, TTI);
306 if (C.CandidateKind == Candidate::GEP)
307 return isGEPFoldable(cast<GetElementPtrInst>(C.Ins), TTI);
308 return false;
309}
310
311// Returns true if GEP has zero or one non-zero index.
313 unsigned NumNonZeroIndices = 0;
314 for (Use &Idx : GEP->indices()) {
315 ConstantInt *ConstIdx = dyn_cast<ConstantInt>(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(cast<GetElementPtrInst>(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, 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(C);
380}
381
382void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
383 Instruction *I) {
384 switch (I->getOpcode()) {
387 break;
388 case Instruction::Mul:
389 allocateCandidatesAndFindBasisForMul(I);
390 break;
391 case Instruction::GetElementPtr:
392 allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(I));
393 break;
394 }
395}
396
398 Instruction *I) {
399 // Try matching B + i * S.
400 if (!isa<IntegerType>(I->getType()))
401 return;
402
403 assert(I->getNumOperands() == 2 && "isn't I an add?");
404 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
406 if (LHS != RHS)
408}
409
411 Value *LHS, Value *RHS, Instruction *I) {
412 Value *S = nullptr;
413 ConstantInt *Idx = nullptr;
414 if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) {
415 // I = LHS + RHS = LHS + Idx * S
416 allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
417 } else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) {
418 // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)
419 APInt One(Idx->getBitWidth(), 1);
420 Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue());
421 allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
422 } else {
423 // At least, I = LHS + 1 * RHS
424 ConstantInt *One = ConstantInt::get(cast<IntegerType>(I->getType()), 1);
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(A, m_Add(m_Value(B), m_ConstantInt(C))) ||
434}
435
436// Returns true if A matches B | C where C is constant.
437static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
438 return (match(A, m_Or(m_Value(B), m_ConstantInt(C))) ||
440}
441
442void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
443 Value *LHS, Value *RHS, Instruction *I) {
444 Value *B = nullptr;
445 ConstantInt *Idx = nullptr;
446 if (matchesAdd(LHS, B, Idx)) {
447 // If LHS is in the form of "Base + Index", then I is in the form of
448 // "(Base + Index) * RHS".
449 allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
450 } else if (matchesOr(LHS, B, Idx) && haveNoCommonBitsSet(B, Idx, *DL)) {
451 // If LHS is in the form of "Base | Index" and Base and Index have no common
452 // bits set, then
453 // Base | Index = Base + Index
454 // and I is thus in the form of "(Base + Index) * RHS".
455 allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
456 } else {
457 // Otherwise, at least try the form (LHS + 0) * RHS.
458 ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);
459 allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,
460 I);
461 }
462}
463
464void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
465 Instruction *I) {
466 // Try matching (B + i) * S.
467 // TODO: we could extend SLSR to float and vector types.
468 if (!isa<IntegerType>(I->getType()))
469 return;
470
471 assert(I->getNumOperands() == 2 && "isn't I a mul?");
472 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
473 allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
474 if (LHS != RHS) {
475 // Symmetrically, try to split RHS to Base + Index.
476 allocateCandidatesAndFindBasisForMul(RHS, LHS, I);
477 }
478}
479
480void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
481 const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,
482 Instruction *I) {
483 // I = B + sext(Idx *nsw S) * ElementSize
484 // = B + (sext(Idx) * sext(S)) * ElementSize
485 // = B + (sext(Idx) * ElementSize) * sext(S)
486 // Casting to IntegerType is safe because we skipped vector GEPs.
487 IntegerType *PtrIdxTy = cast<IntegerType>(DL->getIndexType(I->getType()));
488 ConstantInt *ScaledIdx = ConstantInt::get(
489 PtrIdxTy, Idx->getSExtValue() * (int64_t)ElementSize, true);
490 allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);
491}
492
493void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,
494 const SCEV *Base,
495 uint64_t ElementSize,
497 // At least, ArrayIdx = ArrayIdx *nsw 1.
498 allocateCandidatesAndFindBasisForGEP(
499 Base, ConstantInt::get(cast<IntegerType>(ArrayIdx->getType()), 1),
500 ArrayIdx, ElementSize, GEP);
501 Value *LHS = nullptr;
502 ConstantInt *RHS = nullptr;
503 // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx
504 // itself. This would allow us to handle the shl case for free. However,
505 // matching SCEVs has two issues:
506 //
507 // 1. this would complicate rewriting because the rewriting procedure
508 // would have to translate SCEVs back to IR instructions. This translation
509 // is difficult when LHS is further evaluated to a composite SCEV.
510 //
511 // 2. ScalarEvolution is designed to be control-flow oblivious. It tends
512 // to strip nsw/nuw flags which are critical for SLSR to trace into
513 // sext'ed multiplication.
514 if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) {
515 // SLSR is currently unsafe if i * S may overflow.
516 // GEP = Base + sext(LHS *nsw RHS) * ElementSize
517 allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP);
518 } else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) {
519 // GEP = Base + sext(LHS <<nsw RHS) * ElementSize
520 // = Base + sext(LHS *nsw (1 << RHS)) * ElementSize
521 APInt One(RHS->getBitWidth(), 1);
522 ConstantInt *PowerOf2 =
523 ConstantInt::get(RHS->getContext(), One << RHS->getValue());
524 allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP);
525 }
526}
527
528void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
530 // TODO: handle vector GEPs
531 if (GEP->getType()->isVectorTy())
532 return;
533
535 for (Use &Idx : GEP->indices())
536 IndexExprs.push_back(SE->getSCEV(Idx));
537
539 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
540 if (GTI.isStruct())
541 continue;
542
543 const SCEV *OrigIndexExpr = IndexExprs[I - 1];
544 IndexExprs[I - 1] = SE->getZero(OrigIndexExpr->getType());
545
546 // The base of this candidate is GEP's base plus the offsets of all
547 // indices except this current one.
548 const SCEV *BaseExpr = SE->getGEPExpr(cast<GEPOperator>(GEP), IndexExprs);
549 Value *ArrayIdx = GEP->getOperand(I);
550 uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
551 if (ArrayIdx->getType()->getIntegerBitWidth() <=
553 // Skip factoring if ArrayIdx is wider than the index size, because
554 // ArrayIdx is implicitly truncated to the index size.
555 factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);
556 }
557 // When ArrayIdx is the sext of a value, we try to factor that value as
558 // well. Handling this case is important because array indices are
559 // typically sign-extended to the pointer index size.
560 Value *TruncatedArrayIdx = nullptr;
561 if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))) &&
562 TruncatedArrayIdx->getType()->getIntegerBitWidth() <=
564 // Skip factoring if TruncatedArrayIdx is wider than the pointer size,
565 // because TruncatedArrayIdx is implicitly truncated to the pointer size.
566 factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP);
567 }
568
569 IndexExprs[I - 1] = OrigIndexExpr;
570 }
571}
572
573// A helper function that unifies the bitwidth of A and B.
574static void unifyBitWidth(APInt &A, APInt &B) {
575 if (A.getBitWidth() < B.getBitWidth())
576 A = A.sext(B.getBitWidth());
577 else if (A.getBitWidth() > B.getBitWidth())
578 B = B.sext(A.getBitWidth());
579}
580
581Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
582 const Candidate &C,
583 IRBuilder<> &Builder,
584 const DataLayout *DL,
585 bool &BumpWithUglyGEP) {
586 APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
587 unifyBitWidth(Idx, BasisIdx);
588 APInt IndexOffset = Idx - BasisIdx;
589
590 BumpWithUglyGEP = false;
591 if (Basis.CandidateKind == Candidate::GEP) {
592 APInt ElementSize(
593 IndexOffset.getBitWidth(),
594 DL->getTypeAllocSize(
595 cast<GetElementPtrInst>(Basis.Ins)->getResultElementType()));
596 APInt Q, R;
597 APInt::sdivrem(IndexOffset, ElementSize, Q, R);
598 if (R == 0)
599 IndexOffset = Q;
600 else
601 BumpWithUglyGEP = true;
602 }
603
604 // Compute Bump = C - Basis = (i' - i) * S.
605 // Common case 1: if (i' - i) is 1, Bump = S.
606 if (IndexOffset == 1)
607 return C.Stride;
608 // Common case 2: if (i' - i) is -1, Bump = -S.
609 if (IndexOffset.isAllOnes())
610 return Builder.CreateNeg(C.Stride);
611
612 // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may
613 // have different bit widths.
614 IntegerType *DeltaType =
615 IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());
616 Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType);
617 if (IndexOffset.isPowerOf2()) {
618 // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i).
619 ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2());
620 return Builder.CreateShl(ExtendedStride, Exponent);
621 }
622 if (IndexOffset.isNegatedPowerOf2()) {
623 // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i).
625 ConstantInt::get(DeltaType, (-IndexOffset).logBase2());
626 return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent));
627 }
628 Constant *Delta = ConstantInt::get(DeltaType, IndexOffset);
629 return Builder.CreateMul(ExtendedStride, Delta);
630}
631
632void StraightLineStrengthReduce::rewriteCandidateWithBasis(
633 const Candidate &C, const Candidate &Basis) {
634 assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
635 C.Stride == Basis.Stride);
636 // We run rewriteCandidateWithBasis on all candidates in a post-order, so the
637 // basis of a candidate cannot be unlinked before the candidate.
638 assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
639
640 // An instruction can correspond to multiple candidates. Therefore, instead of
641 // simply deleting an instruction when we rewrite it, we mark its parent as
642 // nullptr (i.e. unlink it) so that we can skip the candidates whose
643 // instruction is already rewritten.
644 if (!C.Ins->getParent())
645 return;
646
647 IRBuilder<> Builder(C.Ins);
648 bool BumpWithUglyGEP;
649 Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
650 Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
651 switch (C.CandidateKind) {
653 case Candidate::Mul: {
654 // C = Basis + Bump
655 Value *NegBump;
656 if (match(Bump, m_Neg(m_Value(NegBump)))) {
657 // If Bump is a neg instruction, emit C = Basis - (-Bump).
658 Reduced = Builder.CreateSub(Basis.Ins, NegBump);
659 // We only use the negative argument of Bump, and Bump itself may be
662 } else {
663 // It's tempting to preserve nsw on Bump and/or Reduced. However, it's
664 // usually unsound, e.g.,
665 //
666 // X = (-2 +nsw 1) *nsw INT_MAX
667 // Y = (-2 +nsw 3) *nsw INT_MAX
668 // =>
669 // Y = X + 2 * INT_MAX
670 //
671 // Neither + and * in the resultant expression are nsw.
673 }
674 break;
675 }
676 case Candidate::GEP:
677 {
678 Type *OffsetTy = DL->getIndexType(C.Ins->getType());
679 bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
680 if (BumpWithUglyGEP) {
681 // C = (char *)Basis + Bump
683 Type *CharTy = PointerType::get(Basis.Ins->getContext(), AS);
684 Reduced = Builder.CreateBitCast(Basis.Ins, CharTy);
685 Reduced =
686 Builder.CreateGEP(Builder.getInt8Ty(), Reduced, Bump, "", InBounds);
687 Reduced = Builder.CreateBitCast(Reduced, C.Ins->getType());
688 } else {
689 // C = gep Basis, Bump
690 // Canonicalize bump to pointer size.
691 Bump = Builder.CreateSExtOrTrunc(Bump, OffsetTy);
692 Reduced = Builder.CreateGEP(
693 cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(), Basis.Ins,
694 Bump, "", InBounds);
695 }
696 break;
697 }
698 default:
699 llvm_unreachable("C.CandidateKind is invalid");
700 };
701 Reduced->takeName(C.Ins);
702 C.Ins->replaceAllUsesWith(Reduced);
703 // Unlink C.Ins so that we can skip other candidates also corresponding to
704 // C.Ins. The actual deletion is postponed to the end of runOnFunction.
705 C.Ins->removeFromParent();
707}
708
709bool StraightLineStrengthReduceLegacyPass::runOnFunction(Function &F) {
710 if (skipFunction(F))
711 return false;
712
713 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
714 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
715 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
716 return StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F);
717}
718
719bool StraightLineStrengthReduce::runOnFunction(Function &F) {
720 // Traverse the dominator tree in the depth-first order. This order makes sure
721 // all bases of a candidate are in Candidates when we process it.
722 for (const auto Node : depth_first(DT))
723 for (auto &I : *(Node->getBlock()))
724 allocateCandidatesAndFindBasis(&I);
725
726 // Rewrite candidates in the reverse depth-first order. This order makes sure
727 // a candidate being rewritten is not a basis for any other candidate.
728 while (!Candidates.empty()) {
729 const Candidate &C = Candidates.back();
730 if (C.Basis != nullptr) {
731 rewriteCandidateWithBasis(C, *C.Basis);
732 }
733 Candidates.pop_back();
734 }
735
736 // Delete all unlink instructions.
738 for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
742 }
744 }
747 return Ret;
748}
749
750namespace llvm {
751
754 const DataLayout *DL = &F.getParent()->getDataLayout();
755 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
756 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
757 auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
758
759 if (!StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F))
760 return PreservedAnalyses::all();
761
767 return PA;
768}
769
770} // namespace llvm
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool runOnFunction(Function &F, bool PostInlining)
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
static bool matchesOr(Value *A, Value *&B, ConstantInt *&C)
static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride, TargetTransformInfo *TTI)
static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP)
static void unifyBitWidth(APInt &A, APInt &B)
static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C)
static bool isGEPFoldable(GetElementPtrInst *GEP, const TargetTransformInfo *TTI)
Straight line strength reduction
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
BinaryOperator * Mul
Class for arbitrary precision integers.
Definition: APInt.h:76
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
Definition: APInt.h:427
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1896
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:349
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1433
unsigned logBase2() const
Definition: APInt.h:1696
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:418
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:133
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:197
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:313
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:165
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1712
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1335
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2097
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1407
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1318
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
Definition: IRBuilder.h:1862
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
Definition: IRBuilder.h:502
Value * CreateSExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a SExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:2030
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1352
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2636
Class to represent integer types.
Definition: DerivedTypes.h:40
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:285
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:119
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:172
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:208
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:193
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Analysis pass providing the TargetTransformInfo.
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr, ArrayRef< const Value * > Operands, Type *AccessType=nullptr, TargetCostKind CostKind=TCK_SizeAndLatency) const
Estimate the cost of a GEP operation when lowered.
bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale, unsigned AddrSpace=0, Instruction *I=nullptr) const
Return true if the addressing mode represented by AM is legal for this target, for a load/store of th...
@ TCC_Free
Expected to fold away in lowering.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
@ Invalid
Invalid file type.
Definition: InterfaceFile.h:55
Definition: PatternMatch.h:982
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
CastInst_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
This is an optimization pass for GlobalISel generic memory operations.