LLVM  6.0.0svn
NaryReassociate.cpp
Go to the documentation of this file.
1 //===- NaryReassociate.cpp - Reassociate n-ary expressions ----------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass reassociates n-ary add expressions and eliminates the redundancy
11 // exposed by the reassociation.
12 //
13 // A motivating example:
14 //
15 // void foo(int a, int b) {
16 // bar(a + b);
17 // bar((a + 2) + b);
18 // }
19 //
20 // An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify
21 // the above code to
22 //
23 // int t = a + b;
24 // bar(t);
25 // bar(t + 2);
26 //
27 // However, the Reassociate pass is unable to do that because it processes each
28 // instruction individually and believes (a + 2) + b is the best form according
29 // to its rank system.
30 //
31 // To address this limitation, NaryReassociate reassociates an expression in a
32 // form that reuses existing instructions. As a result, NaryReassociate can
33 // reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that
34 // (a + b) is computed before.
35 //
36 // NaryReassociate works as follows. For every instruction in the form of (a +
37 // b) + c, it checks whether a + c or b + c is already computed by a dominating
38 // instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +
39 // c) + a and removes the redundancy accordingly. To efficiently look up whether
40 // an expression is computed before, we store each instruction seen and its SCEV
41 // into an SCEV-to-instruction map.
42 //
43 // Although the algorithm pattern-matches only ternary additions, it
44 // automatically handles many >3-ary expressions by walking through the function
45 // in the depth-first order. For example, given
46 //
47 // (a + c) + d
48 // ((a + b) + c) + d
49 //
50 // NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites
51 // ((a + c) + b) + d into ((a + c) + d) + b.
52 //
53 // Finally, the above dominator-based algorithm may need to be run multiple
54 // iterations before emitting optimal code. One source of this need is that we
55 // only split an operand when it is used only once. The above algorithm can
56 // eliminate an instruction and decrease the usage count of its operands. As a
57 // result, an instruction that previously had multiple uses may become a
58 // single-use instruction and thus eligible for split consideration. For
59 // example,
60 //
61 // ac = a + c
62 // ab = a + b
63 // abc = ab + c
64 // ab2 = ab + b
65 // ab2c = ab2 + c
66 //
67 // In the first iteration, we cannot reassociate abc to ac+b because ab is used
68 // twice. However, we can reassociate ab2c to abc+b in the first iteration. As a
69 // result, ab2 becomes dead and ab will be used only once in the second
70 // iteration.
71 //
72 // Limitations and TODO items:
73 //
74 // 1) We only considers n-ary adds and muls for now. This should be extended
75 // and generalized.
76 //
77 //===----------------------------------------------------------------------===//
78 
81 #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"
109 #include <cassert>
110 #include <cstdint>
111 
112 using namespace llvm;
113 using namespace PatternMatch;
114 
115 #define DEBUG_TYPE "nary-reassociate"
116 
117 namespace {
118 
119 class NaryReassociateLegacyPass : public FunctionPass {
120 public:
121  static char ID;
122 
123  NaryReassociateLegacyPass() : FunctionPass(ID) {
125  }
126 
127  bool doInitialization(Module &M) override {
128  return false;
129  }
130 
131  bool runOnFunction(Function &F) override;
132 
133  void getAnalysisUsage(AnalysisUsage &AU) const override {
142  AU.setPreservesCFG();
143  }
144 
145 private:
146  NaryReassociatePass Impl;
147 };
148 
149 } // end anonymous namespace
150 
152 
153 INITIALIZE_PASS_BEGIN(NaryReassociateLegacyPass, "nary-reassociate",
154  "Nary reassociation", false, false)
160 INITIALIZE_PASS_END(NaryReassociateLegacyPass, "nary-reassociate",
161  "Nary reassociation", false, false)
162 
164  return new NaryReassociateLegacyPass();
165 }
166 
168  if (skipFunction(F))
169  return false;
170 
171  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
172  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
173  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
174  auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
175  auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
176 
177  return Impl.runImpl(F, AC, DT, SE, TLI, TTI);
178 }
179 
182  auto *AC = &AM.getResult<AssumptionAnalysis>(F);
183  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
184  auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
185  auto *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
186  auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
187 
188  if (!runImpl(F, AC, DT, SE, TLI, TTI))
189  return PreservedAnalyses::all();
190 
192  PA.preserveSet<CFGAnalyses>();
194  return PA;
195 }
196 
198  DominatorTree *DT_, ScalarEvolution *SE_,
199  TargetLibraryInfo *TLI_,
200  TargetTransformInfo *TTI_) {
201  AC = AC_;
202  DT = DT_;
203  SE = SE_;
204  TLI = TLI_;
205  TTI = TTI_;
206  DL = &F.getParent()->getDataLayout();
207 
208  bool Changed = false, ChangedInThisIteration;
209  do {
210  ChangedInThisIteration = doOneIteration(F);
211  Changed |= ChangedInThisIteration;
212  } while (ChangedInThisIteration);
213  return Changed;
214 }
215 
216 // Whitelist the instruction types NaryReassociate handles for now.
218  switch (I->getOpcode()) {
219  case Instruction::Add:
220  case Instruction::GetElementPtr:
221  case Instruction::Mul:
222  return true;
223  default:
224  return false;
225  }
226 }
227 
228 bool NaryReassociatePass::doOneIteration(Function &F) {
229  bool Changed = false;
230  SeenExprs.clear();
231  // Process the basic blocks in a depth first traversal of the dominator
232  // tree. This order ensures that all bases of a candidate are in Candidates
233  // when we process it.
234  for (const auto Node : depth_first(DT)) {
235  BasicBlock *BB = Node->getBlock();
236  for (auto I = BB->begin(); I != BB->end(); ++I) {
237  if (SE->isSCEVable(I->getType()) && isPotentiallyNaryReassociable(&*I)) {
238  const SCEV *OldSCEV = SE->getSCEV(&*I);
239  if (Instruction *NewI = tryReassociate(&*I)) {
240  Changed = true;
241  SE->forgetValue(&*I);
242  I->replaceAllUsesWith(NewI);
243  // If SeenExprs constains I's WeakTrackingVH, that entry will be
244  // replaced with
245  // nullptr.
247  I = NewI->getIterator();
248  }
249  // Add the rewritten instruction to SeenExprs; the original instruction
250  // is deleted.
251  const SCEV *NewSCEV = SE->getSCEV(&*I);
252  SeenExprs[NewSCEV].push_back(WeakTrackingVH(&*I));
253  // Ideally, NewSCEV should equal OldSCEV because tryReassociate(I)
254  // is equivalent to I. However, ScalarEvolution::getSCEV may
255  // weaken nsw causing NewSCEV not to equal OldSCEV. For example, suppose
256  // we reassociate
257  // I = &a[sext(i +nsw j)] // assuming sizeof(a[0]) = 4
258  // to
259  // NewI = &a[sext(i)] + sext(j).
260  //
261  // ScalarEvolution computes
262  // getSCEV(I) = a + 4 * sext(i + j)
263  // getSCEV(newI) = a + 4 * sext(i) + 4 * sext(j)
264  // which are different SCEVs.
265  //
266  // To alleviate this issue of ScalarEvolution not always capturing
267  // equivalence, we add I to SeenExprs[OldSCEV] as well so that we can
268  // map both SCEV before and after tryReassociate(I) to I.
269  //
270  // This improvement is exercised in @reassociate_gep_nsw in nary-gep.ll.
271  if (NewSCEV != OldSCEV)
272  SeenExprs[OldSCEV].push_back(WeakTrackingVH(&*I));
273  }
274  }
275  }
276  return Changed;
277 }
278 
279 Instruction *NaryReassociatePass::tryReassociate(Instruction *I) {
280  switch (I->getOpcode()) {
281  case Instruction::Add:
282  case Instruction::Mul:
283  return tryReassociateBinaryOp(cast<BinaryOperator>(I));
284  case Instruction::GetElementPtr:
285  return tryReassociateGEP(cast<GetElementPtrInst>(I));
286  default:
287  llvm_unreachable("should be filtered out by isPotentiallyNaryReassociable");
288  }
289 }
290 
292  const TargetTransformInfo *TTI) {
294  for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
295  Indices.push_back(*I);
296  return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
297  Indices) == TargetTransformInfo::TCC_Free;
298 }
299 
300 Instruction *NaryReassociatePass::tryReassociateGEP(GetElementPtrInst *GEP) {
301  // Not worth reassociating GEP if it is foldable.
302  if (isGEPFoldable(GEP, TTI))
303  return nullptr;
304 
305  gep_type_iterator GTI = gep_type_begin(*GEP);
306  for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
307  if (GTI.isSequential()) {
308  if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I - 1,
309  GTI.getIndexedType())) {
310  return NewGEP;
311  }
312  }
313  }
314  return nullptr;
315 }
316 
317 bool NaryReassociatePass::requiresSignExtension(Value *Index,
318  GetElementPtrInst *GEP) {
319  unsigned PointerSizeInBits =
320  DL->getPointerSizeInBits(GEP->getType()->getPointerAddressSpace());
321  return cast<IntegerType>(Index->getType())->getBitWidth() < PointerSizeInBits;
322 }
323 
325 NaryReassociatePass::tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
326  unsigned I, Type *IndexedType) {
327  Value *IndexToSplit = GEP->getOperand(I + 1);
328  if (SExtInst *SExt = dyn_cast<SExtInst>(IndexToSplit)) {
329  IndexToSplit = SExt->getOperand(0);
330  } else if (ZExtInst *ZExt = dyn_cast<ZExtInst>(IndexToSplit)) {
331  // zext can be treated as sext if the source is non-negative.
332  if (isKnownNonNegative(ZExt->getOperand(0), *DL, 0, AC, GEP, DT))
333  IndexToSplit = ZExt->getOperand(0);
334  }
335 
336  if (AddOperator *AO = dyn_cast<AddOperator>(IndexToSplit)) {
337  // If the I-th index needs sext and the underlying add is not equipped with
338  // nsw, we cannot split the add because
339  // sext(LHS + RHS) != sext(LHS) + sext(RHS).
340  if (requiresSignExtension(IndexToSplit, GEP) &&
341  computeOverflowForSignedAdd(AO, *DL, AC, GEP, DT) !=
343  return nullptr;
344 
345  Value *LHS = AO->getOperand(0), *RHS = AO->getOperand(1);
346  // IndexToSplit = LHS + RHS.
347  if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I, LHS, RHS, IndexedType))
348  return NewGEP;
349  // Symmetrically, try IndexToSplit = RHS + LHS.
350  if (LHS != RHS) {
351  if (auto *NewGEP =
352  tryReassociateGEPAtIndex(GEP, I, RHS, LHS, IndexedType))
353  return NewGEP;
354  }
355  }
356  return nullptr;
357 }
358 
360 NaryReassociatePass::tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
361  unsigned I, Value *LHS,
362  Value *RHS, Type *IndexedType) {
363  // Look for GEP's closest dominator that has the same SCEV as GEP except that
364  // the I-th index is replaced with LHS.
365  SmallVector<const SCEV *, 4> IndexExprs;
366  for (auto Index = GEP->idx_begin(); Index != GEP->idx_end(); ++Index)
367  IndexExprs.push_back(SE->getSCEV(*Index));
368  // Replace the I-th index with LHS.
369  IndexExprs[I] = SE->getSCEV(LHS);
370  if (isKnownNonNegative(LHS, *DL, 0, AC, GEP, DT) &&
371  DL->getTypeSizeInBits(LHS->getType()) <
372  DL->getTypeSizeInBits(GEP->getOperand(I)->getType())) {
373  // Zero-extend LHS if it is non-negative. InstCombine canonicalizes sext to
374  // zext if the source operand is proved non-negative. We should do that
375  // consistently so that CandidateExpr more likely appears before. See
376  // @reassociate_gep_assume for an example of this canonicalization.
377  IndexExprs[I] =
378  SE->getZeroExtendExpr(IndexExprs[I], GEP->getOperand(I)->getType());
379  }
380  const SCEV *CandidateExpr = SE->getGEPExpr(cast<GEPOperator>(GEP),
381  IndexExprs);
382 
383  Value *Candidate = findClosestMatchingDominator(CandidateExpr, GEP);
384  if (Candidate == nullptr)
385  return nullptr;
386 
387  IRBuilder<> Builder(GEP);
388  // Candidate does not necessarily have the same pointer type as GEP. Use
389  // bitcast or pointer cast to make sure they have the same type, so that the
390  // later RAUW doesn't complain.
391  Candidate = Builder.CreateBitOrPointerCast(Candidate, GEP->getType());
392  assert(Candidate->getType() == GEP->getType());
393 
394  // NewGEP = (char *)Candidate + RHS * sizeof(IndexedType)
395  uint64_t IndexedSize = DL->getTypeAllocSize(IndexedType);
396  Type *ElementType = GEP->getResultElementType();
397  uint64_t ElementSize = DL->getTypeAllocSize(ElementType);
398  // Another less rare case: because I is not necessarily the last index of the
399  // GEP, the size of the type at the I-th index (IndexedSize) is not
400  // necessarily divisible by ElementSize. For example,
401  //
402  // #pragma pack(1)
403  // struct S {
404  // int a[3];
405  // int64 b[8];
406  // };
407  // #pragma pack()
408  //
409  // sizeof(S) = 100 is indivisible by sizeof(int64) = 8.
410  //
411  // TODO: bail out on this case for now. We could emit uglygep.
412  if (IndexedSize % ElementSize != 0)
413  return nullptr;
414 
415  // NewGEP = &Candidate[RHS * (sizeof(IndexedType) / sizeof(Candidate[0])));
416  Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
417  if (RHS->getType() != IntPtrTy)
418  RHS = Builder.CreateSExtOrTrunc(RHS, IntPtrTy);
419  if (IndexedSize != ElementSize) {
420  RHS = Builder.CreateMul(
421  RHS, ConstantInt::get(IntPtrTy, IndexedSize / ElementSize));
422  }
423  GetElementPtrInst *NewGEP =
424  cast<GetElementPtrInst>(Builder.CreateGEP(Candidate, RHS));
425  NewGEP->setIsInBounds(GEP->isInBounds());
426  NewGEP->takeName(GEP);
427  return NewGEP;
428 }
429 
430 Instruction *NaryReassociatePass::tryReassociateBinaryOp(BinaryOperator *I) {
431  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
432  if (auto *NewI = tryReassociateBinaryOp(LHS, RHS, I))
433  return NewI;
434  if (auto *NewI = tryReassociateBinaryOp(RHS, LHS, I))
435  return NewI;
436  return nullptr;
437 }
438 
439 Instruction *NaryReassociatePass::tryReassociateBinaryOp(Value *LHS, Value *RHS,
440  BinaryOperator *I) {
441  Value *A = nullptr, *B = nullptr;
442  // To be conservative, we reassociate I only when it is the only user of (A op
443  // B).
444  if (LHS->hasOneUse() && matchTernaryOp(I, LHS, A, B)) {
445  // I = (A op B) op RHS
446  // = (A op RHS) op B or (B op RHS) op A
447  const SCEV *AExpr = SE->getSCEV(A), *BExpr = SE->getSCEV(B);
448  const SCEV *RHSExpr = SE->getSCEV(RHS);
449  if (BExpr != RHSExpr) {
450  if (auto *NewI =
451  tryReassociatedBinaryOp(getBinarySCEV(I, AExpr, RHSExpr), B, I))
452  return NewI;
453  }
454  if (AExpr != RHSExpr) {
455  if (auto *NewI =
456  tryReassociatedBinaryOp(getBinarySCEV(I, BExpr, RHSExpr), A, I))
457  return NewI;
458  }
459  }
460  return nullptr;
461 }
462 
463 Instruction *NaryReassociatePass::tryReassociatedBinaryOp(const SCEV *LHSExpr,
464  Value *RHS,
465  BinaryOperator *I) {
466  // Look for the closest dominator LHS of I that computes LHSExpr, and replace
467  // I with LHS op RHS.
468  auto *LHS = findClosestMatchingDominator(LHSExpr, I);
469  if (LHS == nullptr)
470  return nullptr;
471 
472  Instruction *NewI = nullptr;
473  switch (I->getOpcode()) {
474  case Instruction::Add:
475  NewI = BinaryOperator::CreateAdd(LHS, RHS, "", I);
476  break;
477  case Instruction::Mul:
478  NewI = BinaryOperator::CreateMul(LHS, RHS, "", I);
479  break;
480  default:
481  llvm_unreachable("Unexpected instruction.");
482  }
483  NewI->takeName(I);
484  return NewI;
485 }
486 
487 bool NaryReassociatePass::matchTernaryOp(BinaryOperator *I, Value *V,
488  Value *&Op1, Value *&Op2) {
489  switch (I->getOpcode()) {
490  case Instruction::Add:
491  return match(V, m_Add(m_Value(Op1), m_Value(Op2)));
492  case Instruction::Mul:
493  return match(V, m_Mul(m_Value(Op1), m_Value(Op2)));
494  default:
495  llvm_unreachable("Unexpected instruction.");
496  }
497  return false;
498 }
499 
500 const SCEV *NaryReassociatePass::getBinarySCEV(BinaryOperator *I,
501  const SCEV *LHS,
502  const SCEV *RHS) {
503  switch (I->getOpcode()) {
504  case Instruction::Add:
505  return SE->getAddExpr(LHS, RHS);
506  case Instruction::Mul:
507  return SE->getMulExpr(LHS, RHS);
508  default:
509  llvm_unreachable("Unexpected instruction.");
510  }
511  return nullptr;
512 }
513 
514 Instruction *
515 NaryReassociatePass::findClosestMatchingDominator(const SCEV *CandidateExpr,
516  Instruction *Dominatee) {
517  auto Pos = SeenExprs.find(CandidateExpr);
518  if (Pos == SeenExprs.end())
519  return nullptr;
520 
521  auto &Candidates = Pos->second;
522  // Because we process the basic blocks in pre-order of the dominator tree, a
523  // candidate that doesn't dominate the current instruction won't dominate any
524  // future instruction either. Therefore, we pop it out of the stack. This
525  // optimization makes the algorithm O(n).
526  while (!Candidates.empty()) {
527  // Candidates stores WeakTrackingVHs, so a candidate can be nullptr if it's
528  // removed
529  // during rewriting.
530  if (Value *Candidate = Candidates.back()) {
531  Instruction *CandidateInstruction = cast<Instruction>(Candidate);
532  if (DT->dominates(CandidateInstruction, Dominatee))
533  return CandidateInstruction;
534  }
535  Candidates.pop_back();
536  }
537  return nullptr;
538 }
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:72
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:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
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:526
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 .assume calls within a function.
Analysis pass providing the TargetTransformInfo.
nary reassociate
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
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:503
Hexagon Common GEP
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
Type * getSourceElementType() const
Definition: Instructions.h:934
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:502
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:182
Value * CreateSExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a SExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1409
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
op_iterator idx_begin()
Definition: Instructions.h:962
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:292
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:154
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:837
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:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the give value is known to be non-negative.
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:285
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:401
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:937
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1227
A function analysis which provides an AssumptionCache.
unsigned getNumOperands() const
Definition: User.h:176
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
iterator end()
Definition: BasicBlock.h:254
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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:560
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
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:1520
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:939
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:556
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:414
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
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)