LLVM  10.0.0svn
NaryReassociate.cpp
Go to the documentation of this file.
1 //===- NaryReassociate.cpp - Reassociate n-ary expressions ----------------===//
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 pass reassociates n-ary add expressions and eliminates the redundancy
10 // exposed by the reassociation.
11 //
12 // A motivating example:
13 //
14 // void foo(int a, int b) {
15 // bar(a + b);
16 // bar((a + 2) + b);
17 // }
18 //
19 // An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify
20 // the above code to
21 //
22 // int t = a + b;
23 // bar(t);
24 // bar(t + 2);
25 //
26 // However, the Reassociate pass is unable to do that because it processes each
27 // instruction individually and believes (a + 2) + b is the best form according
28 // to its rank system.
29 //
30 // To address this limitation, NaryReassociate reassociates an expression in a
31 // form that reuses existing instructions. As a result, NaryReassociate can
32 // reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that
33 // (a + b) is computed before.
34 //
35 // NaryReassociate works as follows. For every instruction in the form of (a +
36 // b) + c, it checks whether a + c or b + c is already computed by a dominating
37 // instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +
38 // c) + a and removes the redundancy accordingly. To efficiently look up whether
39 // an expression is computed before, we store each instruction seen and its SCEV
40 // into an SCEV-to-instruction map.
41 //
42 // Although the algorithm pattern-matches only ternary additions, it
43 // automatically handles many >3-ary expressions by walking through the function
44 // in the depth-first order. For example, given
45 //
46 // (a + c) + d
47 // ((a + b) + c) + d
48 //
49 // NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites
50 // ((a + c) + b) + d into ((a + c) + d) + b.
51 //
52 // Finally, the above dominator-based algorithm may need to be run multiple
53 // iterations before emitting optimal code. One source of this need is that we
54 // only split an operand when it is used only once. The above algorithm can
55 // eliminate an instruction and decrease the usage count of its operands. As a
56 // result, an instruction that previously had multiple uses may become a
57 // single-use instruction and thus eligible for split consideration. For
58 // example,
59 //
60 // ac = a + c
61 // ab = a + b
62 // abc = ab + c
63 // ab2 = ab + b
64 // ab2c = ab2 + c
65 //
66 // In the first iteration, we cannot reassociate abc to ac+b because ab is used
67 // twice. However, we can reassociate ab2c to abc+b in the first iteration. As a
68 // result, ab2 becomes dead and ab will be used only once in the second
69 // iteration.
70 //
71 // Limitations and TODO items:
72 //
73 // 1) We only considers n-ary adds and muls for now. This should be extended
74 // and generalized.
75 //
76 //===----------------------------------------------------------------------===//
77 
80 #include "llvm/ADT/SmallVector.h"
87 #include "llvm/IR/BasicBlock.h"
88 #include "llvm/IR/Constants.h"
89 #include "llvm/IR/DataLayout.h"
90 #include "llvm/IR/DerivedTypes.h"
91 #include "llvm/IR/Dominators.h"
92 #include "llvm/IR/Function.h"
94 #include "llvm/IR/IRBuilder.h"
95 #include "llvm/IR/InstrTypes.h"
96 #include "llvm/IR/Instruction.h"
97 #include "llvm/IR/Instructions.h"
98 #include "llvm/IR/Module.h"
99 #include "llvm/IR/Operator.h"
100 #include "llvm/IR/PatternMatch.h"
101 #include "llvm/IR/Type.h"
102 #include "llvm/IR/Value.h"
103 #include "llvm/IR/ValueHandle.h"
104 #include "llvm/Pass.h"
105 #include "llvm/Support/Casting.h"
107 #include "llvm/Transforms/Scalar.h"
108 #include <cassert>
109 #include <cstdint>
110 
111 using namespace llvm;
112 using namespace PatternMatch;
113 
114 #define DEBUG_TYPE "nary-reassociate"
115 
116 namespace {
117 
118 class NaryReassociateLegacyPass : public FunctionPass {
119 public:
120  static char ID;
121 
122  NaryReassociateLegacyPass() : FunctionPass(ID) {
124  }
125 
126  bool doInitialization(Module &M) override {
127  return false;
128  }
129 
130  bool runOnFunction(Function &F) override;
131 
132  void getAnalysisUsage(AnalysisUsage &AU) const override {
141  AU.setPreservesCFG();
142  }
143 
144 private:
145  NaryReassociatePass Impl;
146 };
147 
148 } // end anonymous namespace
149 
151 
152 INITIALIZE_PASS_BEGIN(NaryReassociateLegacyPass, "nary-reassociate",
153  "Nary reassociation", false, false)
159 INITIALIZE_PASS_END(NaryReassociateLegacyPass, "nary-reassociate",
160  "Nary reassociation", false, false)
161 
163  return new NaryReassociateLegacyPass();
164 }
165 
167  if (skipFunction(F))
168  return false;
169 
170  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
171  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
172  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
173  auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
174  auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
175 
176  return Impl.runImpl(F, AC, DT, SE, TLI, TTI);
177 }
178 
181  auto *AC = &AM.getResult<AssumptionAnalysis>(F);
182  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
183  auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
184  auto *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
185  auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
186 
187  if (!runImpl(F, AC, DT, SE, TLI, TTI))
188  return PreservedAnalyses::all();
189 
191  PA.preserveSet<CFGAnalyses>();
193  return PA;
194 }
195 
197  DominatorTree *DT_, ScalarEvolution *SE_,
198  TargetLibraryInfo *TLI_,
199  TargetTransformInfo *TTI_) {
200  AC = AC_;
201  DT = DT_;
202  SE = SE_;
203  TLI = TLI_;
204  TTI = TTI_;
205  DL = &F.getParent()->getDataLayout();
206 
207  bool Changed = false, ChangedInThisIteration;
208  do {
209  ChangedInThisIteration = doOneIteration(F);
210  Changed |= ChangedInThisIteration;
211  } while (ChangedInThisIteration);
212  return Changed;
213 }
214 
215 // Whitelist the instruction types NaryReassociate handles for now.
217  switch (I->getOpcode()) {
218  case Instruction::Add:
219  case Instruction::GetElementPtr:
220  case Instruction::Mul:
221  return true;
222  default:
223  return false;
224  }
225 }
226 
227 bool NaryReassociatePass::doOneIteration(Function &F) {
228  bool Changed = false;
229  SeenExprs.clear();
230  // Process the basic blocks in a depth first traversal of the dominator
231  // tree. This order ensures that all bases of a candidate are in Candidates
232  // when we process it.
233  for (const auto Node : depth_first(DT)) {
234  BasicBlock *BB = Node->getBlock();
235  for (auto I = BB->begin(); I != BB->end(); ++I) {
236  if (SE->isSCEVable(I->getType()) && isPotentiallyNaryReassociable(&*I)) {
237  const SCEV *OldSCEV = SE->getSCEV(&*I);
238  if (Instruction *NewI = tryReassociate(&*I)) {
239  Changed = true;
240  SE->forgetValue(&*I);
241  I->replaceAllUsesWith(NewI);
242  WeakVH NewIExist = NewI;
243  // If SeenExprs/NewIExist contains I's WeakTrackingVH/WeakVH, that
244  // entry will be replaced with nullptr if deleted.
246  if (!NewIExist) {
247  // Rare occation where the new instruction (NewI) have been removed,
248  // probably due to parts of the input code was dead from the
249  // beginning, reset the iterator and start over from the beginning
250  I = BB->begin();
251  continue;
252  }
253  I = NewI->getIterator();
254  }
255  // Add the rewritten instruction to SeenExprs; the original instruction
256  // is deleted.
257  const SCEV *NewSCEV = SE->getSCEV(&*I);
258  SeenExprs[NewSCEV].push_back(WeakTrackingVH(&*I));
259  // Ideally, NewSCEV should equal OldSCEV because tryReassociate(I)
260  // is equivalent to I. However, ScalarEvolution::getSCEV may
261  // weaken nsw causing NewSCEV not to equal OldSCEV. For example, suppose
262  // we reassociate
263  // I = &a[sext(i +nsw j)] // assuming sizeof(a[0]) = 4
264  // to
265  // NewI = &a[sext(i)] + sext(j).
266  //
267  // ScalarEvolution computes
268  // getSCEV(I) = a + 4 * sext(i + j)
269  // getSCEV(newI) = a + 4 * sext(i) + 4 * sext(j)
270  // which are different SCEVs.
271  //
272  // To alleviate this issue of ScalarEvolution not always capturing
273  // equivalence, we add I to SeenExprs[OldSCEV] as well so that we can
274  // map both SCEV before and after tryReassociate(I) to I.
275  //
276  // This improvement is exercised in @reassociate_gep_nsw in nary-gep.ll.
277  if (NewSCEV != OldSCEV)
278  SeenExprs[OldSCEV].push_back(WeakTrackingVH(&*I));
279  }
280  }
281  }
282  return Changed;
283 }
284 
285 Instruction *NaryReassociatePass::tryReassociate(Instruction *I) {
286  switch (I->getOpcode()) {
287  case Instruction::Add:
288  case Instruction::Mul:
289  return tryReassociateBinaryOp(cast<BinaryOperator>(I));
290  case Instruction::GetElementPtr:
291  return tryReassociateGEP(cast<GetElementPtrInst>(I));
292  default:
293  llvm_unreachable("should be filtered out by isPotentiallyNaryReassociable");
294  }
295 }
296 
298  const TargetTransformInfo *TTI) {
300  for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
301  Indices.push_back(*I);
302  return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
303  Indices) == TargetTransformInfo::TCC_Free;
304 }
305 
306 Instruction *NaryReassociatePass::tryReassociateGEP(GetElementPtrInst *GEP) {
307  // Not worth reassociating GEP if it is foldable.
308  if (isGEPFoldable(GEP, TTI))
309  return nullptr;
310 
311  gep_type_iterator GTI = gep_type_begin(*GEP);
312  for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
313  if (GTI.isSequential()) {
314  if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I - 1,
315  GTI.getIndexedType())) {
316  return NewGEP;
317  }
318  }
319  }
320  return nullptr;
321 }
322 
323 bool NaryReassociatePass::requiresSignExtension(Value *Index,
324  GetElementPtrInst *GEP) {
325  unsigned PointerSizeInBits =
326  DL->getPointerSizeInBits(GEP->getType()->getPointerAddressSpace());
327  return cast<IntegerType>(Index->getType())->getBitWidth() < PointerSizeInBits;
328 }
329 
331 NaryReassociatePass::tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
332  unsigned I, Type *IndexedType) {
333  Value *IndexToSplit = GEP->getOperand(I + 1);
334  if (SExtInst *SExt = dyn_cast<SExtInst>(IndexToSplit)) {
335  IndexToSplit = SExt->getOperand(0);
336  } else if (ZExtInst *ZExt = dyn_cast<ZExtInst>(IndexToSplit)) {
337  // zext can be treated as sext if the source is non-negative.
338  if (isKnownNonNegative(ZExt->getOperand(0), *DL, 0, AC, GEP, DT))
339  IndexToSplit = ZExt->getOperand(0);
340  }
341 
342  if (AddOperator *AO = dyn_cast<AddOperator>(IndexToSplit)) {
343  // If the I-th index needs sext and the underlying add is not equipped with
344  // nsw, we cannot split the add because
345  // sext(LHS + RHS) != sext(LHS) + sext(RHS).
346  if (requiresSignExtension(IndexToSplit, GEP) &&
347  computeOverflowForSignedAdd(AO, *DL, AC, GEP, DT) !=
349  return nullptr;
350 
351  Value *LHS = AO->getOperand(0), *RHS = AO->getOperand(1);
352  // IndexToSplit = LHS + RHS.
353  if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I, LHS, RHS, IndexedType))
354  return NewGEP;
355  // Symmetrically, try IndexToSplit = RHS + LHS.
356  if (LHS != RHS) {
357  if (auto *NewGEP =
358  tryReassociateGEPAtIndex(GEP, I, RHS, LHS, IndexedType))
359  return NewGEP;
360  }
361  }
362  return nullptr;
363 }
364 
366 NaryReassociatePass::tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
367  unsigned I, Value *LHS,
368  Value *RHS, Type *IndexedType) {
369  // Look for GEP's closest dominator that has the same SCEV as GEP except that
370  // the I-th index is replaced with LHS.
371  SmallVector<const SCEV *, 4> IndexExprs;
372  for (auto Index = GEP->idx_begin(); Index != GEP->idx_end(); ++Index)
373  IndexExprs.push_back(SE->getSCEV(*Index));
374  // Replace the I-th index with LHS.
375  IndexExprs[I] = SE->getSCEV(LHS);
376  if (isKnownNonNegative(LHS, *DL, 0, AC, GEP, DT) &&
377  DL->getTypeSizeInBits(LHS->getType()) <
378  DL->getTypeSizeInBits(GEP->getOperand(I)->getType())) {
379  // Zero-extend LHS if it is non-negative. InstCombine canonicalizes sext to
380  // zext if the source operand is proved non-negative. We should do that
381  // consistently so that CandidateExpr more likely appears before. See
382  // @reassociate_gep_assume for an example of this canonicalization.
383  IndexExprs[I] =
384  SE->getZeroExtendExpr(IndexExprs[I], GEP->getOperand(I)->getType());
385  }
386  const SCEV *CandidateExpr = SE->getGEPExpr(cast<GEPOperator>(GEP),
387  IndexExprs);
388 
389  Value *Candidate = findClosestMatchingDominator(CandidateExpr, GEP);
390  if (Candidate == nullptr)
391  return nullptr;
392 
393  IRBuilder<> Builder(GEP);
394  // Candidate does not necessarily have the same pointer type as GEP. Use
395  // bitcast or pointer cast to make sure they have the same type, so that the
396  // later RAUW doesn't complain.
397  Candidate = Builder.CreateBitOrPointerCast(Candidate, GEP->getType());
398  assert(Candidate->getType() == GEP->getType());
399 
400  // NewGEP = (char *)Candidate + RHS * sizeof(IndexedType)
401  uint64_t IndexedSize = DL->getTypeAllocSize(IndexedType);
402  Type *ElementType = GEP->getResultElementType();
403  uint64_t ElementSize = DL->getTypeAllocSize(ElementType);
404  // Another less rare case: because I is not necessarily the last index of the
405  // GEP, the size of the type at the I-th index (IndexedSize) is not
406  // necessarily divisible by ElementSize. For example,
407  //
408  // #pragma pack(1)
409  // struct S {
410  // int a[3];
411  // int64 b[8];
412  // };
413  // #pragma pack()
414  //
415  // sizeof(S) = 100 is indivisible by sizeof(int64) = 8.
416  //
417  // TODO: bail out on this case for now. We could emit uglygep.
418  if (IndexedSize % ElementSize != 0)
419  return nullptr;
420 
421  // NewGEP = &Candidate[RHS * (sizeof(IndexedType) / sizeof(Candidate[0])));
422  Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
423  if (RHS->getType() != IntPtrTy)
424  RHS = Builder.CreateSExtOrTrunc(RHS, IntPtrTy);
425  if (IndexedSize != ElementSize) {
426  RHS = Builder.CreateMul(
427  RHS, ConstantInt::get(IntPtrTy, IndexedSize / ElementSize));
428  }
429  GetElementPtrInst *NewGEP = cast<GetElementPtrInst>(
430  Builder.CreateGEP(GEP->getResultElementType(), Candidate, RHS));
431  NewGEP->setIsInBounds(GEP->isInBounds());
432  NewGEP->takeName(GEP);
433  return NewGEP;
434 }
435 
436 Instruction *NaryReassociatePass::tryReassociateBinaryOp(BinaryOperator *I) {
437  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
438  // There is no need to reassociate 0.
439  if (SE->getSCEV(I)->isZero())
440  return nullptr;
441  if (auto *NewI = tryReassociateBinaryOp(LHS, RHS, I))
442  return NewI;
443  if (auto *NewI = tryReassociateBinaryOp(RHS, LHS, I))
444  return NewI;
445  return nullptr;
446 }
447 
448 Instruction *NaryReassociatePass::tryReassociateBinaryOp(Value *LHS, Value *RHS,
449  BinaryOperator *I) {
450  Value *A = nullptr, *B = nullptr;
451  // To be conservative, we reassociate I only when it is the only user of (A op
452  // B).
453  if (LHS->hasOneUse() && matchTernaryOp(I, LHS, A, B)) {
454  // I = (A op B) op RHS
455  // = (A op RHS) op B or (B op RHS) op A
456  const SCEV *AExpr = SE->getSCEV(A), *BExpr = SE->getSCEV(B);
457  const SCEV *RHSExpr = SE->getSCEV(RHS);
458  if (BExpr != RHSExpr) {
459  if (auto *NewI =
460  tryReassociatedBinaryOp(getBinarySCEV(I, AExpr, RHSExpr), B, I))
461  return NewI;
462  }
463  if (AExpr != RHSExpr) {
464  if (auto *NewI =
465  tryReassociatedBinaryOp(getBinarySCEV(I, BExpr, RHSExpr), A, I))
466  return NewI;
467  }
468  }
469  return nullptr;
470 }
471 
472 Instruction *NaryReassociatePass::tryReassociatedBinaryOp(const SCEV *LHSExpr,
473  Value *RHS,
474  BinaryOperator *I) {
475  // Look for the closest dominator LHS of I that computes LHSExpr, and replace
476  // I with LHS op RHS.
477  auto *LHS = findClosestMatchingDominator(LHSExpr, I);
478  if (LHS == nullptr)
479  return nullptr;
480 
481  Instruction *NewI = nullptr;
482  switch (I->getOpcode()) {
483  case Instruction::Add:
484  NewI = BinaryOperator::CreateAdd(LHS, RHS, "", I);
485  break;
486  case Instruction::Mul:
487  NewI = BinaryOperator::CreateMul(LHS, RHS, "", I);
488  break;
489  default:
490  llvm_unreachable("Unexpected instruction.");
491  }
492  NewI->takeName(I);
493  return NewI;
494 }
495 
496 bool NaryReassociatePass::matchTernaryOp(BinaryOperator *I, Value *V,
497  Value *&Op1, Value *&Op2) {
498  switch (I->getOpcode()) {
499  case Instruction::Add:
500  return match(V, m_Add(m_Value(Op1), m_Value(Op2)));
501  case Instruction::Mul:
502  return match(V, m_Mul(m_Value(Op1), m_Value(Op2)));
503  default:
504  llvm_unreachable("Unexpected instruction.");
505  }
506  return false;
507 }
508 
509 const SCEV *NaryReassociatePass::getBinarySCEV(BinaryOperator *I,
510  const SCEV *LHS,
511  const SCEV *RHS) {
512  switch (I->getOpcode()) {
513  case Instruction::Add:
514  return SE->getAddExpr(LHS, RHS);
515  case Instruction::Mul:
516  return SE->getMulExpr(LHS, RHS);
517  default:
518  llvm_unreachable("Unexpected instruction.");
519  }
520  return nullptr;
521 }
522 
523 Instruction *
524 NaryReassociatePass::findClosestMatchingDominator(const SCEV *CandidateExpr,
525  Instruction *Dominatee) {
526  auto Pos = SeenExprs.find(CandidateExpr);
527  if (Pos == SeenExprs.end())
528  return nullptr;
529 
530  auto &Candidates = Pos->second;
531  // Because we process the basic blocks in pre-order of the dominator tree, a
532  // candidate that doesn't dominate the current instruction won't dominate any
533  // future instruction either. Therefore, we pop it out of the stack. This
534  // optimization makes the algorithm O(n).
535  while (!Candidates.empty()) {
536  // Candidates stores WeakTrackingVHs, so a candidate can be nullptr if it's
537  // removed
538  // during rewriting.
539  if (Value *Candidate = Candidates.back()) {
540  Instruction *CandidateInstruction = cast<Instruction>(Candidate);
541  if (DT->dominates(CandidateInstruction, Dominatee))
542  return CandidateInstruction;
543  }
544  Candidates.pop_back();
545  }
546  return nullptr;
547 }
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
This class represents zero extension of integer types.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:783
The main scalar evolution driver.
int getGEPCost(Type *PointeeType, const Value *Ptr, ArrayRef< const Value *> Operands) const
Estimate the cost of a GEP operation when lowered.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
Analysis pass providing the TargetTransformInfo.
nary reassociate
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
This class represents a sign extension of integer types.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:580
Hexagon Common GEP
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
Type * getSourceElementType() const
Definition: Instructions.h:972
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:716
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:181
Value * CreateSExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a SExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1903
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
A nullable Value handle that is nullable.
Definition: ValueHandle.h:140
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:169
INITIALIZE_PASS_BEGIN(NaryReassociateLegacyPass, "nary-reassociate", "Nary reassociation", false, false) INITIALIZE_PASS_END(NaryReassociateLegacyPass
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:875
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Expected to fold away in lowering.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:440
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1152
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1677
A function analysis which provides an AssumptionCache.
unsigned getNumOperands() const
Definition: User.h:191
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
iterator end()
Definition: BasicBlock.h:270
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_, ScalarEvolution *SE_, TargetLibraryInfo *TLI_, TargetTransformInfo *TTI_)
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:640
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
Analysis pass that exposes the ScalarEvolution for a function.
Value * CreateBitOrPointerCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2036
This class represents an analyzed expression in the program.
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
#define I(x, y, z)
Definition: MD5.cpp:58
nary Nary reassociation
Type * getResultElementType() const
Definition: Instructions.h:977
void initializeNaryReassociateLegacyPassPass(PassRegistry &)
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
Analysis pass providing the TargetLibraryInfo.
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:73
static bool isPotentiallyNaryReassociable(Instruction *I)
static bool isGEPFoldable(GetElementPtrInst *GEP, const TargetTransformInfo *TTI)
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:432
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This pass exposes codegen information to IR-level passes.
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
FunctionPass * createNaryReassociatePass()
gep_type_iterator gep_type_begin(const User *GEP)