LLVM  13.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.
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 
59 #include "llvm/ADT/APInt.h"
61 #include "llvm/ADT/SmallVector.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"
70 #include "llvm/IR/IRBuilder.h"
71 #include "llvm/IR/InstrTypes.h"
72 #include "llvm/IR/Instruction.h"
73 #include "llvm/IR/Instructions.h"
74 #include "llvm/IR/Module.h"
75 #include "llvm/IR/Operator.h"
76 #include "llvm/IR/PatternMatch.h"
77 #include "llvm/IR/Type.h"
78 #include "llvm/IR/Value.h"
79 #include "llvm/InitializePasses.h"
80 #include "llvm/Pass.h"
81 #include "llvm/Support/Casting.h"
83 #include "llvm/Transforms/Scalar.h"
85 #include <cassert>
86 #include <cstdint>
87 #include <limits>
88 #include <list>
89 #include <vector>
90 
91 using namespace llvm;
92 using namespace PatternMatch;
93 
94 static const unsigned UnknownAddressSpace =
96 
97 namespace {
98 
99 class StraightLineStrengthReduceLegacyPass : public FunctionPass {
100  const DataLayout *DL = nullptr;
101 
102 public:
103  static char ID;
104 
105  StraightLineStrengthReduceLegacyPass() : FunctionPass(ID) {
108  }
109 
110  void getAnalysisUsage(AnalysisUsage &AU) const override {
114  // We do not modify the shape of the CFG.
115  AU.setPreservesCFG();
116  }
117 
118  bool doInitialization(Module &M) override {
119  DL = &M.getDataLayout();
120  return false;
121  }
122 
123  bool runOnFunction(Function &F) override;
124 };
125 
126 class StraightLineStrengthReduce {
127 public:
128  StraightLineStrengthReduce(const DataLayout *DL, DominatorTree *DT,
130  : DL(DL), DT(DT), SE(SE), TTI(TTI) {}
131 
132  // SLSR candidate. Such a candidate must be in one of the forms described in
133  // the header comments.
134  struct Candidate {
135  enum Kind {
136  Invalid, // reserved for the default constructor
137  Add, // B + i * S
138  Mul, // (B + i) * S
139  GEP, // &B[..][i * S][..]
140  };
141 
142  Candidate() = default;
143  Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
144  Instruction *I)
145  : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I) {}
146 
147  Kind CandidateKind = Invalid;
148 
149  const SCEV *Base = nullptr;
150 
151  // Note that Index and Stride of a GEP candidate do not necessarily have the
152  // same integer type. In that case, during rewriting, Stride will be
153  // sign-extended or truncated to Index's type.
154  ConstantInt *Index = nullptr;
155 
156  Value *Stride = nullptr;
157 
158  // The instruction this candidate corresponds to. It helps us to rewrite a
159  // candidate with respect to its immediate basis. Note that one instruction
160  // can correspond to multiple candidates depending on how you associate the
161  // expression. For instance,
162  //
163  // (a + 1) * (b + 2)
164  //
165  // can be treated as
166  //
167  // <Base: a, Index: 1, Stride: b + 2>
168  //
169  // or
170  //
171  // <Base: b, Index: 2, Stride: a + 1>
172  Instruction *Ins = nullptr;
173 
174  // Points to the immediate basis of this candidate, or nullptr if we cannot
175  // find any basis for this candidate.
176  Candidate *Basis = nullptr;
177  };
178 
179  bool runOnFunction(Function &F);
180 
181 private:
182  // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
183  // share the same base and stride.
184  bool isBasisFor(const Candidate &Basis, const Candidate &C);
185 
186  // Returns whether the candidate can be folded into an addressing mode.
187  bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,
188  const DataLayout *DL);
189 
190  // Returns true if C is already in a simplest form and not worth being
191  // rewritten.
192  bool isSimplestForm(const Candidate &C);
193 
194  // Checks whether I is in a candidate form. If so, adds all the matching forms
195  // to Candidates, and tries to find the immediate basis for each of them.
196  void allocateCandidatesAndFindBasis(Instruction *I);
197 
198  // Allocate candidates and find bases for Add instructions.
199  void allocateCandidatesAndFindBasisForAdd(Instruction *I);
200 
201  // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a
202  // candidate.
203  void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
204  Instruction *I);
205  // Allocate candidates and find bases for Mul instructions.
206  void allocateCandidatesAndFindBasisForMul(Instruction *I);
207 
208  // Splits LHS into Base + Index and, if succeeds, calls
209  // allocateCandidatesAndFindBasis.
210  void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
211  Instruction *I);
212 
213  // Allocate candidates and find bases for GetElementPtr instructions.
214  void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
215 
216  // A helper function that scales Idx with ElementSize before invoking
217  // allocateCandidatesAndFindBasis.
218  void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,
219  Value *S, uint64_t ElementSize,
220  Instruction *I);
221 
222  // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate
223  // basis.
224  void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
225  ConstantInt *Idx, Value *S,
226  Instruction *I);
227 
228  // Rewrites candidate C with respect to Basis.
229  void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
230 
231  // A helper function that factors ArrayIdx to a product of a stride and a
232  // constant index, and invokes allocateCandidatesAndFindBasis with the
233  // factorings.
234  void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,
236 
237  // Emit code that computes the "bump" from Basis to C. If the candidate is a
238  // GEP and the bump is not divisible by the element size of the GEP, this
239  // function sets the BumpWithUglyGEP flag to notify its caller to bump the
240  // basis using an ugly GEP.
241  static Value *emitBump(const Candidate &Basis, const Candidate &C,
242  IRBuilder<> &Builder, const DataLayout *DL,
243  bool &BumpWithUglyGEP);
244 
245  const DataLayout *DL = nullptr;
246  DominatorTree *DT = nullptr;
247  ScalarEvolution *SE;
248  TargetTransformInfo *TTI = nullptr;
249  std::list<Candidate> Candidates;
250 
251  // Temporarily holds all instructions that are unlinked (but not deleted) by
252  // rewriteCandidateWithBasis. These instructions will be actually removed
253  // after all rewriting finishes.
254  std::vector<Instruction *> UnlinkedInstructions;
255 };
256 
257 } // end anonymous namespace
258 
260 
261 INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr",
262  "Straight line strength reduction", false, false)
266 INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass, "slsr",
267  "Straight line strength reduction", false, false)
268 
270  return new StraightLineStrengthReduceLegacyPass();
271 }
272 
273 bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
274  const Candidate &C) {
275  return (Basis.Ins != C.Ins && // skip the same instruction
276  // They must have the same type too. Basis.Base == C.Base doesn't
277  // guarantee their types are the same (PR23975).
278  Basis.Ins->getType() == C.Ins->getType() &&
279  // Basis must dominate C in order to rewrite C with respect to Basis.
280  DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&
281  // They share the same base, stride, and candidate kind.
282  Basis.Base == C.Base && Basis.Stride == C.Stride &&
283  Basis.CandidateKind == C.CandidateKind);
284 }
285 
287  const TargetTransformInfo *TTI) {
288  SmallVector<const Value *, 4> Indices(GEP->indices());
289  return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
290  Indices) == TargetTransformInfo::TCC_Free;
291 }
292 
293 // Returns whether (Base + Index * Stride) can be folded to an addressing mode.
294 static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
296  // Index->getSExtValue() may crash if Index is wider than 64-bit.
297  return Index->getBitWidth() <= 64 &&
298  TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true,
299  Index->getSExtValue(), UnknownAddressSpace);
300 }
301 
302 bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
304  const DataLayout *DL) {
305  if (C.CandidateKind == Candidate::Add)
306  return isAddFoldable(C.Base, C.Index, C.Stride, TTI);
307  if (C.CandidateKind == Candidate::GEP)
308  return isGEPFoldable(cast<GetElementPtrInst>(C.Ins), TTI);
309  return false;
310 }
311 
312 // Returns true if GEP has zero or one non-zero index.
314  unsigned NumNonZeroIndices = 0;
315  for (Use &Idx : GEP->indices()) {
316  ConstantInt *ConstIdx = dyn_cast<ConstantInt>(Idx);
317  if (ConstIdx == nullptr || !ConstIdx->isZero())
318  ++NumNonZeroIndices;
319  }
320  return NumNonZeroIndices <= 1;
321 }
322 
323 bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) {
324  if (C.CandidateKind == Candidate::Add) {
325  // B + 1 * S or B + (-1) * S
326  return C.Index->isOne() || C.Index->isMinusOne();
327  }
328  if (C.CandidateKind == Candidate::Mul) {
329  // (B + 0) * S
330  return C.Index->isZero();
331  }
332  if (C.CandidateKind == Candidate::GEP) {
333  // (char*)B + S or (char*)B - S
334  return ((C.Index->isOne() || C.Index->isMinusOne()) &&
335  hasOnlyOneNonZeroIndex(cast<GetElementPtrInst>(C.Ins)));
336  }
337  return false;
338 }
339 
340 // TODO: We currently implement an algorithm whose time complexity is linear in
341 // the number of existing candidates. However, we could do better by using
342 // ScopedHashTable. Specifically, while traversing the dominator tree, we could
343 // maintain all the candidates that dominate the basic block being traversed in
344 // a ScopedHashTable. This hash table is indexed by the base and the stride of
345 // a candidate. Therefore, finding the immediate basis of a candidate boils down
346 // to one hash-table look up.
347 void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
348  Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
349  Instruction *I) {
350  Candidate C(CT, B, Idx, S, I);
351  // SLSR can complicate an instruction in two cases:
352  //
353  // 1. If we can fold I into an addressing mode, computing I is likely free or
354  // takes only one instruction.
355  //
356  // 2. I is already in a simplest form. For example, when
357  // X = B + 8 * S
358  // Y = B + S,
359  // rewriting Y to X - 7 * S is probably a bad idea.
360  //
361  // In the above cases, we still add I to the candidate list so that I can be
362  // the basis of other candidates, but we leave I's basis blank so that I
363  // won't be rewritten.
364  if (!isFoldable(C, TTI, DL) && !isSimplestForm(C)) {
365  // Try to compute the immediate basis of C.
366  unsigned NumIterations = 0;
367  // Limit the scan radius to avoid running in quadratice time.
368  static const unsigned MaxNumIterations = 50;
369  for (auto Basis = Candidates.rbegin();
370  Basis != Candidates.rend() && NumIterations < MaxNumIterations;
371  ++Basis, ++NumIterations) {
372  if (isBasisFor(*Basis, C)) {
373  C.Basis = &(*Basis);
374  break;
375  }
376  }
377  }
378  // Regardless of whether we find a basis for C, we need to push C to the
379  // candidate list so that it can be the basis of other candidates.
380  Candidates.push_back(C);
381 }
382 
383 void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
384  Instruction *I) {
385  switch (I->getOpcode()) {
386  case Instruction::Add:
387  allocateCandidatesAndFindBasisForAdd(I);
388  break;
389  case Instruction::Mul:
390  allocateCandidatesAndFindBasisForMul(I);
391  break;
392  case Instruction::GetElementPtr:
393  allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(I));
394  break;
395  }
396 }
397 
398 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
399  Instruction *I) {
400  // Try matching B + i * S.
401  if (!isa<IntegerType>(I->getType()))
402  return;
403 
404  assert(I->getNumOperands() == 2 && "isn't I an add?");
405  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
406  allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
407  if (LHS != RHS)
408  allocateCandidatesAndFindBasisForAdd(RHS, LHS, I);
409 }
410 
411 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
412  Value *LHS, Value *RHS, Instruction *I) {
413  Value *S = nullptr;
414  ConstantInt *Idx = nullptr;
415  if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) {
416  // I = LHS + RHS = LHS + Idx * S
417  allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
418  } else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) {
419  // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)
420  APInt One(Idx->getBitWidth(), 1);
421  Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue());
422  allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
423  } else {
424  // At least, I = LHS + 1 * RHS
425  ConstantInt *One = ConstantInt::get(cast<IntegerType>(I->getType()), 1);
426  allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS,
427  I);
428  }
429 }
430 
431 // Returns true if A matches B + C where C is constant.
432 static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {
433  return (match(A, m_Add(m_Value(B), m_ConstantInt(C))) ||
434  match(A, m_Add(m_ConstantInt(C), m_Value(B))));
435 }
436 
437 // Returns true if A matches B | C where C is constant.
438 static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
439  return (match(A, m_Or(m_Value(B), m_ConstantInt(C))) ||
440  match(A, m_Or(m_ConstantInt(C), m_Value(B))));
441 }
442 
443 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
444  Value *LHS, Value *RHS, Instruction *I) {
445  Value *B = nullptr;
446  ConstantInt *Idx = nullptr;
447  if (matchesAdd(LHS, B, Idx)) {
448  // If LHS is in the form of "Base + Index", then I is in the form of
449  // "(Base + Index) * RHS".
450  allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
451  } else if (matchesOr(LHS, B, Idx) && haveNoCommonBitsSet(B, Idx, *DL)) {
452  // If LHS is in the form of "Base | Index" and Base and Index have no common
453  // bits set, then
454  // Base | Index = Base + Index
455  // and I is thus in the form of "(Base + Index) * RHS".
456  allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
457  } else {
458  // Otherwise, at least try the form (LHS + 0) * RHS.
459  ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);
460  allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,
461  I);
462  }
463 }
464 
465 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
466  Instruction *I) {
467  // Try matching (B + i) * S.
468  // TODO: we could extend SLSR to float and vector types.
469  if (!isa<IntegerType>(I->getType()))
470  return;
471 
472  assert(I->getNumOperands() == 2 && "isn't I a mul?");
473  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
474  allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
475  if (LHS != RHS) {
476  // Symmetrically, try to split RHS to Base + Index.
477  allocateCandidatesAndFindBasisForMul(RHS, LHS, I);
478  }
479 }
480 
481 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
482  const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,
483  Instruction *I) {
484  // I = B + sext(Idx *nsw S) * ElementSize
485  // = B + (sext(Idx) * sext(S)) * ElementSize
486  // = B + (sext(Idx) * ElementSize) * sext(S)
487  // Casting to IntegerType is safe because we skipped vector GEPs.
488  IntegerType *IntPtrTy = cast<IntegerType>(DL->getIntPtrType(I->getType()));
489  ConstantInt *ScaledIdx = ConstantInt::get(
490  IntPtrTy, Idx->getSExtValue() * (int64_t)ElementSize, true);
491  allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);
492 }
493 
494 void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,
495  const SCEV *Base,
496  uint64_t ElementSize,
498  // At least, ArrayIdx = ArrayIdx *nsw 1.
499  allocateCandidatesAndFindBasisForGEP(
500  Base, ConstantInt::get(cast<IntegerType>(ArrayIdx->getType()), 1),
501  ArrayIdx, ElementSize, GEP);
502  Value *LHS = nullptr;
503  ConstantInt *RHS = nullptr;
504  // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx
505  // itself. This would allow us to handle the shl case for free. However,
506  // matching SCEVs has two issues:
507  //
508  // 1. this would complicate rewriting because the rewriting procedure
509  // would have to translate SCEVs back to IR instructions. This translation
510  // is difficult when LHS is further evaluated to a composite SCEV.
511  //
512  // 2. ScalarEvolution is designed to be control-flow oblivious. It tends
513  // to strip nsw/nuw flags which are critical for SLSR to trace into
514  // sext'ed multiplication.
515  if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) {
516  // SLSR is currently unsafe if i * S may overflow.
517  // GEP = Base + sext(LHS *nsw RHS) * ElementSize
518  allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP);
519  } else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) {
520  // GEP = Base + sext(LHS <<nsw RHS) * ElementSize
521  // = Base + sext(LHS *nsw (1 << RHS)) * ElementSize
522  APInt One(RHS->getBitWidth(), 1);
523  ConstantInt *PowerOf2 =
524  ConstantInt::get(RHS->getContext(), One << RHS->getValue());
525  allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP);
526  }
527 }
528 
529 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
531  // TODO: handle vector GEPs
532  if (GEP->getType()->isVectorTy())
533  return;
534 
535  SmallVector<const SCEV *, 4> IndexExprs;
536  for (Use &Idx : GEP->indices())
537  IndexExprs.push_back(SE->getSCEV(Idx));
538 
540  for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
541  if (GTI.isStruct())
542  continue;
543 
544  const SCEV *OrigIndexExpr = IndexExprs[I - 1];
545  IndexExprs[I - 1] = SE->getZero(OrigIndexExpr->getType());
546 
547  // The base of this candidate is GEP's base plus the offsets of all
548  // indices except this current one.
549  const SCEV *BaseExpr = SE->getGEPExpr(cast<GEPOperator>(GEP), IndexExprs);
550  Value *ArrayIdx = GEP->getOperand(I);
551  uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
552  if (ArrayIdx->getType()->getIntegerBitWidth() <=
553  DL->getPointerSizeInBits(GEP->getAddressSpace())) {
554  // Skip factoring if ArrayIdx is wider than the pointer size, because
555  // ArrayIdx is implicitly truncated to the pointer size.
556  factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);
557  }
558  // When ArrayIdx is the sext of a value, we try to factor that value as
559  // well. Handling this case is important because array indices are
560  // typically sign-extended to the pointer size.
561  Value *TruncatedArrayIdx = nullptr;
562  if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))) &&
563  TruncatedArrayIdx->getType()->getIntegerBitWidth() <=
564  DL->getPointerSizeInBits(GEP->getAddressSpace())) {
565  // Skip factoring if TruncatedArrayIdx is wider than the pointer size,
566  // because TruncatedArrayIdx is implicitly truncated to the pointer size.
567  factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP);
568  }
569 
570  IndexExprs[I - 1] = OrigIndexExpr;
571  }
572 }
573 
574 // A helper function that unifies the bitwidth of A and B.
575 static void unifyBitWidth(APInt &A, APInt &B) {
576  if (A.getBitWidth() < B.getBitWidth())
577  A = A.sext(B.getBitWidth());
578  else if (A.getBitWidth() > B.getBitWidth())
579  B = B.sext(A.getBitWidth());
580 }
581 
582 Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
583  const Candidate &C,
585  const DataLayout *DL,
586  bool &BumpWithUglyGEP) {
587  APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
588  unifyBitWidth(Idx, BasisIdx);
589  APInt IndexOffset = Idx - BasisIdx;
590 
591  BumpWithUglyGEP = false;
592  if (Basis.CandidateKind == Candidate::GEP) {
593  APInt ElementSize(
594  IndexOffset.getBitWidth(),
595  DL->getTypeAllocSize(
596  cast<GetElementPtrInst>(Basis.Ins)->getResultElementType()));
597  APInt Q, R;
598  APInt::sdivrem(IndexOffset, ElementSize, Q, R);
599  if (R == 0)
600  IndexOffset = Q;
601  else
602  BumpWithUglyGEP = true;
603  }
604 
605  // Compute Bump = C - Basis = (i' - i) * S.
606  // Common case 1: if (i' - i) is 1, Bump = S.
607  if (IndexOffset == 1)
608  return C.Stride;
609  // Common case 2: if (i' - i) is -1, Bump = -S.
610  if (IndexOffset.isAllOnesValue())
611  return Builder.CreateNeg(C.Stride);
612 
613  // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may
614  // have different bit widths.
615  IntegerType *DeltaType =
616  IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());
617  Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType);
618  if (IndexOffset.isPowerOf2()) {
619  // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i).
620  ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2());
621  return Builder.CreateShl(ExtendedStride, Exponent);
622  }
623  if ((-IndexOffset).isPowerOf2()) {
624  // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i).
626  ConstantInt::get(DeltaType, (-IndexOffset).logBase2());
627  return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent));
628  }
629  Constant *Delta = ConstantInt::get(DeltaType, IndexOffset);
630  return Builder.CreateMul(ExtendedStride, Delta);
631 }
632 
633 void StraightLineStrengthReduce::rewriteCandidateWithBasis(
634  const Candidate &C, const Candidate &Basis) {
635  assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
636  C.Stride == Basis.Stride);
637  // We run rewriteCandidateWithBasis on all candidates in a post-order, so the
638  // basis of a candidate cannot be unlinked before the candidate.
639  assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
640 
641  // An instruction can correspond to multiple candidates. Therefore, instead of
642  // simply deleting an instruction when we rewrite it, we mark its parent as
643  // nullptr (i.e. unlink it) so that we can skip the candidates whose
644  // instruction is already rewritten.
645  if (!C.Ins->getParent())
646  return;
647 
648  IRBuilder<> Builder(C.Ins);
649  bool BumpWithUglyGEP;
650  Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
651  Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
652  switch (C.CandidateKind) {
653  case Candidate::Add:
654  case Candidate::Mul: {
655  // C = Basis + Bump
656  Value *NegBump;
657  if (match(Bump, m_Neg(m_Value(NegBump)))) {
658  // If Bump is a neg instruction, emit C = Basis - (-Bump).
659  Reduced = Builder.CreateSub(Basis.Ins, NegBump);
660  // We only use the negative argument of Bump, and Bump itself may be
661  // trivially dead.
663  } else {
664  // It's tempting to preserve nsw on Bump and/or Reduced. However, it's
665  // usually unsound, e.g.,
666  //
667  // X = (-2 +nsw 1) *nsw INT_MAX
668  // Y = (-2 +nsw 3) *nsw INT_MAX
669  // =>
670  // Y = X + 2 * INT_MAX
671  //
672  // Neither + and * in the resultant expression are nsw.
673  Reduced = Builder.CreateAdd(Basis.Ins, Bump);
674  }
675  break;
676  }
677  case Candidate::GEP:
678  {
679  Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType());
680  bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
681  if (BumpWithUglyGEP) {
682  // C = (char *)Basis + Bump
683  unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
684  Type *CharTy = Type::getInt8PtrTy(Basis.Ins->getContext(), AS);
685  Reduced = Builder.CreateBitCast(Basis.Ins, CharTy);
686  if (InBounds)
687  Reduced =
688  Builder.CreateInBoundsGEP(Builder.getInt8Ty(), Reduced, Bump);
689  else
690  Reduced = Builder.CreateGEP(Builder.getInt8Ty(), Reduced, Bump);
691  Reduced = Builder.CreateBitCast(Reduced, C.Ins->getType());
692  } else {
693  // C = gep Basis, Bump
694  // Canonicalize bump to pointer size.
695  Bump = Builder.CreateSExtOrTrunc(Bump, IntPtrTy);
696  if (InBounds)
697  Reduced = Builder.CreateInBoundsGEP(
698  cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(),
699  Basis.Ins, Bump);
700  else
701  Reduced = Builder.CreateGEP(
702  cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(),
703  Basis.Ins, Bump);
704  }
705  break;
706  }
707  default:
708  llvm_unreachable("C.CandidateKind is invalid");
709  };
710  Reduced->takeName(C.Ins);
711  C.Ins->replaceAllUsesWith(Reduced);
712  // Unlink C.Ins so that we can skip other candidates also corresponding to
713  // C.Ins. The actual deletion is postponed to the end of runOnFunction.
714  C.Ins->removeFromParent();
715  UnlinkedInstructions.push_back(C.Ins);
716 }
717 
719  if (skipFunction(F))
720  return false;
721 
722  auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
723  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
724  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
725  return StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F);
726 }
727 
729  // Traverse the dominator tree in the depth-first order. This order makes sure
730  // all bases of a candidate are in Candidates when we process it.
731  for (const auto Node : depth_first(DT))
732  for (auto &I : *(Node->getBlock()))
733  allocateCandidatesAndFindBasis(&I);
734 
735  // Rewrite candidates in the reverse depth-first order. This order makes sure
736  // a candidate being rewritten is not a basis for any other candidate.
737  while (!Candidates.empty()) {
738  const Candidate &C = Candidates.back();
739  if (C.Basis != nullptr) {
740  rewriteCandidateWithBasis(C, *C.Basis);
741  }
742  Candidates.pop_back();
743  }
744 
745  // Delete all unlink instructions.
746  for (auto *UnlinkedInst : UnlinkedInstructions) {
747  for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
748  Value *Op = UnlinkedInst->getOperand(I);
749  UnlinkedInst->setOperand(I, nullptr);
751  }
752  UnlinkedInst->deleteValue();
753  }
754  bool Ret = !UnlinkedInstructions.empty();
755  UnlinkedInstructions.clear();
756  return Ret;
757 }
758 
759 namespace llvm {
760 
763  const DataLayout *DL = &F.getParent()->getDataLayout();
764  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
765  auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
766  auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
767 
768  if (!StraightLineStrengthReduce(DL, DT, SE, TTI).runOnFunction(F))
769  return PreservedAnalyses::all();
770 
772  PA.preserveSet<CFGAnalyses>();
776  return PA;
777 }
778 
779 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:496
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2319
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2074
llvm
Definition: AllocatorList.h:23
llvm::haveNoCommonBitsSet
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
Definition: ValueTracking.cpp:257
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
slsr
slsr
Definition: StraightLineStrengthReduce.cpp:266
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::generic_gep_type_iterator
Definition: GetElementPtrTypeIterator.h:31
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:249
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
llvm::ConstantInt::getBitWidth
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
Definition: Constants.h:134
Scalar.h
isAddFoldable
static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride, TargetTransformInfo *TTI)
Definition: StraightLineStrengthReduce.cpp:294
llvm::Function
Definition: Function.h:61
Pass.h
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:469
GetElementPtrTypeIterator.h
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1008
matchesOr
static bool matchesOr(Value *A, Value *&B, ConstantInt *&C)
Definition: StraightLineStrengthReduce.cpp:438
ErrorHandling.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::IRBuilder<>
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::MachO::Invalid
@ Invalid
Invalid file type.
Definition: InterfaceFile.h:59
unifyBitWidth
static void unifyBitWidth(APInt &A, APInt &B)
Definition: StraightLineStrengthReduce.cpp:575
APInt.h
ScalarEvolution.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1581
Module.h
Operator.h
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::gep_type_begin
gep_type_iterator gep_type_begin(const User *GEP)
Definition: GetElementPtrTypeIterator.h:139
isGEPFoldable
static bool isGEPFoldable(GetElementPtrInst *GEP, const TargetTransformInfo *TTI)
Definition: StraightLineStrengthReduce.cpp:286
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:133
matchesAdd
static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C)
Definition: StraightLineStrengthReduce.cpp:432
Instruction.h
llvm::initializeStraightLineStrengthReduceLegacyPassPass
void initializeStraightLineStrengthReduceLegacyPassPass(PassRegistry &)
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
hasOnlyOneNonZeroIndex
static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP)
Definition: StraightLineStrengthReduce.cpp:313
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:145
llvm::Instruction
Definition: Instruction.h:45
llvm::PatternMatch::m_NSWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1202
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::ConstantInt::get
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:885
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2104
PatternMatch.h
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:96
Type.h
llvm::APInt::isAllOnesValue
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:401
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2375
llvm::APInt::sdivrem
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1917
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1818
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1129
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:905
IRBuilder.h
llvm::StraightLineStrengthReducePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StraightLineStrengthReduce.cpp:762
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::generic_gep_type_iterator::getIndexedType
Type * getIndexedType() const
Definition: GetElementPtrTypeIterator.h:72
reduction
Straight line strength reduction
Definition: StraightLineStrengthReduce.cpp:267
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr", "Straight line strength reduction", false, false) INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass
llvm::TargetTransformInfo::getGEPCost
InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr, ArrayRef< const Value * > Operands, TargetCostKind CostKind=TCK_SizeAndLatency) const
Estimate the cost of a GEP operation when lowered.
Definition: TargetTransformInfo.cpp:210
UnknownAddressSpace
static const unsigned UnknownAddressSpace
Definition: StraightLineStrengthReduce.cpp:94
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::FloatStyle::Exponent
@ Exponent
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:649
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::TargetTransformInfo::TCC_Free
@ TCC_Free
Expected to fold away in lowering.
Definition: TargetTransformInfo.h:261
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1633
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:192
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:952
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::RecurKind::Mul
@ Mul
Product of integers.
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:146
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
StraightLineStrengthReduce.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
llvm::PatternMatch::m_NSWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1210
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
SmallVector.h
Dominators.h
llvm::generic_gep_type_iterator::isStruct
bool isStruct() const
Definition: GetElementPtrTypeIterator.h:118
llvm::createStraightLineStrengthReducePass
FunctionPass * createStraightLineStrengthReducePass()
Definition: StraightLineStrengthReduce.cpp:269
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
TargetTransformInfo.h
llvm::MipsISD::Ins
@ Ins
Definition: MipsISelLowering.h:157
DerivedTypes.h
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:379
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::PatternMatch::m_Neg
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
Definition: PatternMatch.h:2256
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:269
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:377
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1141
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1075
llvm::TargetTransformInfo::isLegalAddressingMode
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...
Definition: TargetTransformInfo.cpp:337
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38