LLVM  15.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/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"
82 #include "llvm/Transforms/Scalar.h"
84 #include <cassert>
85 #include <cstdint>
86 #include <limits>
87 #include <list>
88 #include <vector>
89 
90 using namespace llvm;
91 using namespace PatternMatch;
92 
93 static const unsigned UnknownAddressSpace =
95 
96 namespace {
97 
98 class StraightLineStrengthReduceLegacyPass : public FunctionPass {
99  const DataLayout *DL = nullptr;
100 
101 public:
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 
125 class StraightLineStrengthReduce {
126 public:
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
132  // the header comments.
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 
180 private:
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.
198  void allocateCandidatesAndFindBasisForAdd(Instruction *I);
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.
253  std::vector<Instruction *> UnlinkedInstructions;
254 };
255 
256 } // end anonymous namespace
257 
259 
260 INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr",
261  "Straight line strength reduction", false, false)
265 INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass, "slsr",
266  "Straight line strength reduction", false, false)
267 
269  return new StraightLineStrengthReduceLegacyPass();
270 }
271 
272 bool 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(),
289  Indices) == TargetTransformInfo::TCC_Free;
290 }
291 
292 // Returns whether (Base + Index * Stride) can be folded to an addressing mode.
293 static 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 &&
297  TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true,
298  Index->getSExtValue(), UnknownAddressSpace);
299 }
300 
301 bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
303  const DataLayout *DL) {
304  if (C.CandidateKind == Candidate::Add)
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 
322 bool 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.
346 void 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 
382 void 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(cast<GetElementPtrInst>(I));
393  break;
394  }
395 }
396 
397 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
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);
405  allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
406  if (LHS != RHS)
407  allocateCandidatesAndFindBasisForAdd(RHS, LHS, I);
408 }
409 
410 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
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);
425  allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS,
426  I);
427  }
428 }
429 
430 // Returns true if A matches B + C where C is constant.
431 static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {
432  return (match(A, m_Add(m_Value(B), m_ConstantInt(C))) ||
433  match(A, m_Add(m_ConstantInt(C), m_Value(B))));
434 }
435 
436 // Returns true if A matches B | C where C is constant.
437 static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
438  return (match(A, m_Or(m_Value(B), m_ConstantInt(C))) ||
439  match(A, m_Or(m_ConstantInt(C), m_Value(B))));
440 }
441 
442 void 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 
464 void 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 
480 void 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 *IntPtrTy = cast<IntegerType>(DL->getIntPtrType(I->getType()));
488  ConstantInt *ScaledIdx = ConstantInt::get(
489  IntPtrTy, Idx->getSExtValue() * (int64_t)ElementSize, true);
490  allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);
491 }
492 
493 void 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 
528 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
530  // TODO: handle vector GEPs
531  if (GEP->getType()->isVectorTy())
532  return;
533 
534  SmallVector<const SCEV *, 4> IndexExprs;
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() <=
552  DL->getPointerSizeInBits(GEP->getAddressSpace())) {
553  // Skip factoring if ArrayIdx is wider than the pointer size, because
554  // ArrayIdx is implicitly truncated to the pointer 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 size.
560  Value *TruncatedArrayIdx = nullptr;
561  if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))) &&
562  TruncatedArrayIdx->getType()->getIntegerBitWidth() <=
563  DL->getPointerSizeInBits(GEP->getAddressSpace())) {
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.
574 static 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 
581 Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
582  const Candidate &C,
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 
632 void 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) {
652  case Candidate::Add:
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
660  // trivially dead.
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.
672  Reduced = Builder.CreateAdd(Basis.Ins, Bump);
673  }
674  break;
675  }
676  case Candidate::GEP:
677  {
678  Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType());
679  bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
680  if (BumpWithUglyGEP) {
681  // C = (char *)Basis + Bump
682  unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
683  Type *CharTy = Type::getInt8PtrTy(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, IntPtrTy);
692  Reduced = Builder.CreateGEP(
693  cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(),
694  Basis.Ins, 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();
706  UnlinkedInstructions.push_back(C.Ins);
707 }
708 
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 
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.
737  for (auto *UnlinkedInst : UnlinkedInstructions) {
738  for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
739  Value *Op = UnlinkedInst->getOperand(I);
740  UnlinkedInst->setOperand(I, nullptr);
742  }
743  UnlinkedInst->deleteValue();
744  }
745  bool Ret = !UnlinkedInstructions.empty();
746  UnlinkedInstructions.clear();
747  return Ret;
748 }
749 
750 namespace 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 
763  PA.preserveSet<CFGAnalyses>();
767  return PA;
768 }
769 
770 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
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:517
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2458
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2115
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:267
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:265
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::generic_gep_type_iterator
Definition: GetElementPtrTypeIterator.h:31
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:291
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:780
llvm::ConstantInt::getBitWidth
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
Definition: Constants.h:136
Scalar.h
isAddFoldable
static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride, TargetTransformInfo *TTI)
Definition: StraightLineStrengthReduce.cpp:293
llvm::Function
Definition: Function.h:60
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:425
GetElementPtrTypeIterator.h
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:988
matchesOr
static bool matchesOr(Value *A, Value *&B, ConstantInt *&C)
Definition: StraightLineStrengthReduce.cpp:437
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:449
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::MachO::Invalid
@ Invalid
Invalid file type.
Definition: InterfaceFile.h:55
unifyBitWidth
static void unifyBitWidth(APInt &A, APInt &B)
Definition: StraightLineStrengthReduce.cpp:574
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:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1423
Module.h
Operator.h
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::gep_type_begin
gep_type_iterator gep_type_begin(const User *GEP)
Definition: GetElementPtrTypeIterator.h:123
isGEPFoldable
static bool isGEPFoldable(GetElementPtrInst *GEP, const TargetTransformInfo *TTI)
Definition: StraightLineStrengthReduce.cpp:285
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
matchesAdd
static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C)
Definition: StraightLineStrengthReduce.cpp:431
Instruction.h
llvm::initializeStraightLineStrengthReduceLegacyPassPass
void initializeStraightLineStrengthReduceLegacyPassPass(PassRegistry &)
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
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:312
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
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:42
llvm::PatternMatch::m_NSWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1182
llvm::APInt::isAllOnes
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:347
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
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:919
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2145
PatternMatch.h
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
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:75
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
uint64_t
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2514
llvm::APInt::sdivrem
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1906
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1664
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1109
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
IRBuilder.h
llvm::StraightLineStrengthReducePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StraightLineStrengthReduce.cpp:753
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::generic_gep_type_iterator::getIndexedType
Type * getIndexedType() const
Definition: GetElementPtrTypeIterator.h:70
reduction
Straight line strength reduction
Definition: StraightLineStrengthReduce.cpp:266
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:204
UnknownAddressSpace
static const unsigned UnknownAddressSpace
Definition: StraightLineStrengthReduce.cpp:93
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::FloatStyle::Exponent
@ Exponent
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
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:75
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
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
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::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:148
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
StraightLineStrengthReduce.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:326
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::APInt::isNegatedPowerOf2
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
Definition: APInt.h:434
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:1190
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
SmallVector.h
Dominators.h
llvm::generic_gep_type_iterator::isStruct
bool isStruct() const
Definition: GetElementPtrTypeIterator.h:111
llvm::createStraightLineStrengthReducePass
FunctionPass * createStraightLineStrengthReducePass()
Definition: StraightLineStrengthReduce.cpp:268
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
TargetTransformInfo.h
llvm::MipsISD::Ins
@ Ins
Definition: MipsISelLowering.h:160
DerivedTypes.h
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:393
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:2279
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:311
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
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:378
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1121
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1055
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:342
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37