LLVM  10.0.0svn
AggressiveInstCombine.cpp
Go to the documentation of this file.
1 //===- AggressiveInstCombine.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 the aggressive expression pattern combiner classes.
10 // Currently, it handles expression patterns for:
11 // * Truncate instruction
12 //
13 //===----------------------------------------------------------------------===//
14 
17 #include "llvm-c/Initialization.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/PatternMatch.h"
28 #include "llvm/Pass.h"
30 using namespace llvm;
31 using namespace PatternMatch;
32 
33 #define DEBUG_TYPE "aggressive-instcombine"
34 
35 namespace {
36 /// Contains expression pattern combiner logic.
37 /// This class provides both the logic to combine expression patterns and
38 /// combine them. It differs from InstCombiner class in that each pattern
39 /// combiner runs only once as opposed to InstCombine's multi-iteration,
40 /// which allows pattern combiner to have higher complexity than the O(1)
41 /// required by the instruction combiner.
42 class AggressiveInstCombinerLegacyPass : public FunctionPass {
43 public:
44  static char ID; // Pass identification, replacement for typeid
45 
46  AggressiveInstCombinerLegacyPass() : FunctionPass(ID) {
49  }
50 
51  void getAnalysisUsage(AnalysisUsage &AU) const override;
52 
53  /// Run all expression pattern optimizations on the given /p F function.
54  ///
55  /// \param F function to optimize.
56  /// \returns true if the IR is changed.
57  bool runOnFunction(Function &F) override;
58 };
59 } // namespace
60 
61 /// Match a pattern for a bitwise rotate operation that partially guards
62 /// against undefined behavior by branching around the rotation when the shift
63 /// amount is 0.
65  if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)
66  return false;
67 
68  // As with the one-use checks below, this is not strictly necessary, but we
69  // are being cautious to avoid potential perf regressions on targets that
70  // do not actually have a rotate instruction (where the funnel shift would be
71  // expanded back into math/shift/logic ops).
73  return false;
74 
75  // Match V to funnel shift left/right and capture the source operand and
76  // shift amount in X and Y.
77  auto matchRotate = [](Value *V, Value *&X, Value *&Y) {
78  Value *L0, *L1, *R0, *R1;
79  unsigned Width = V->getType()->getScalarSizeInBits();
80  auto Sub = m_Sub(m_SpecificInt(Width), m_Value(R1));
81 
82  // rotate_left(X, Y) == (X << Y) | (X >> (Width - Y))
83  auto RotL = m_OneUse(
84  m_c_Or(m_Shl(m_Value(L0), m_Value(L1)), m_LShr(m_Value(R0), Sub)));
85  if (RotL.match(V) && L0 == R0 && L1 == R1) {
86  X = L0;
87  Y = L1;
88  return Intrinsic::fshl;
89  }
90 
91  // rotate_right(X, Y) == (X >> Y) | (X << (Width - Y))
92  auto RotR = m_OneUse(
93  m_c_Or(m_LShr(m_Value(L0), m_Value(L1)), m_Shl(m_Value(R0), Sub)));
94  if (RotR.match(V) && L0 == R0 && L1 == R1) {
95  X = L0;
96  Y = L1;
97  return Intrinsic::fshr;
98  }
99 
101  };
102 
103  // One phi operand must be a rotate operation, and the other phi operand must
104  // be the source value of that rotate operation:
105  // phi [ rotate(RotSrc, RotAmt), RotBB ], [ RotSrc, GuardBB ]
106  PHINode &Phi = cast<PHINode>(I);
107  Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);
108  Value *RotSrc, *RotAmt;
109  Intrinsic::ID IID = matchRotate(P0, RotSrc, RotAmt);
110  if (IID == Intrinsic::not_intrinsic || RotSrc != P1) {
111  IID = matchRotate(P1, RotSrc, RotAmt);
112  if (IID == Intrinsic::not_intrinsic || RotSrc != P0)
113  return false;
114  assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
115  "Pattern must match funnel shift left or right");
116  }
117 
118  // The incoming block with our source operand must be the "guard" block.
119  // That must contain a cmp+branch to avoid the rotate when the shift amount
120  // is equal to 0. The other incoming block is the block with the rotate.
121  BasicBlock *GuardBB = Phi.getIncomingBlock(RotSrc == P1);
122  BasicBlock *RotBB = Phi.getIncomingBlock(RotSrc != P1);
123  Instruction *TermI = GuardBB->getTerminator();
124  ICmpInst::Predicate Pred;
125  BasicBlock *PhiBB = Phi.getParent();
126  if (!match(TermI, m_Br(m_ICmp(Pred, m_Specific(RotAmt), m_ZeroInt()),
127  m_SpecificBB(PhiBB), m_SpecificBB(RotBB))))
128  return false;
129 
130  if (Pred != CmpInst::ICMP_EQ)
131  return false;
132 
133  // We matched a variation of this IR pattern:
134  // GuardBB:
135  // %cmp = icmp eq i32 %RotAmt, 0
136  // br i1 %cmp, label %PhiBB, label %RotBB
137  // RotBB:
138  // %sub = sub i32 32, %RotAmt
139  // %shr = lshr i32 %X, %sub
140  // %shl = shl i32 %X, %RotAmt
141  // %rot = or i32 %shr, %shl
142  // br label %PhiBB
143  // PhiBB:
144  // %cond = phi i32 [ %rot, %RotBB ], [ %X, %GuardBB ]
145  // -->
146  // llvm.fshl.i32(i32 %X, i32 %RotAmt)
147  IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt());
148  Function *F = Intrinsic::getDeclaration(Phi.getModule(), IID, Phi.getType());
149  Phi.replaceAllUsesWith(Builder.CreateCall(F, {RotSrc, RotSrc, RotAmt}));
150  return true;
151 }
152 
153 /// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
154 /// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
155 /// of 'and' ops, then we also need to capture the fact that we saw an
156 /// "and X, 1", so that's an extra return value for that case.
157 struct MaskOps {
161  bool FoundAnd1;
162 
163  MaskOps(unsigned BitWidth, bool MatchAnds)
164  : Root(nullptr), Mask(APInt::getNullValue(BitWidth)),
165  MatchAndChain(MatchAnds), FoundAnd1(false) {}
166 };
167 
168 /// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
169 /// chain of 'and' or 'or' instructions looking for shift ops of a common source
170 /// value. Examples:
171 /// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
172 /// returns { X, 0x129 }
173 /// and (and (X >> 1), 1), (X >> 4)
174 /// returns { X, 0x12 }
175 static bool matchAndOrChain(Value *V, MaskOps &MOps) {
176  Value *Op0, *Op1;
177  if (MOps.MatchAndChain) {
178  // Recurse through a chain of 'and' operands. This requires an extra check
179  // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
180  // in the chain to know that all of the high bits are cleared.
181  if (match(V, m_And(m_Value(Op0), m_One()))) {
182  MOps.FoundAnd1 = true;
183  return matchAndOrChain(Op0, MOps);
184  }
185  if (match(V, m_And(m_Value(Op0), m_Value(Op1))))
186  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
187  } else {
188  // Recurse through a chain of 'or' operands.
189  if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))
190  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
191  }
192 
193  // We need a shift-right or a bare value representing a compare of bit 0 of
194  // the original source operand.
195  Value *Candidate;
196  uint64_t BitIndex = 0;
197  if (!match(V, m_LShr(m_Value(Candidate), m_ConstantInt(BitIndex))))
198  Candidate = V;
199 
200  // Initialize result source operand.
201  if (!MOps.Root)
202  MOps.Root = Candidate;
203 
204  // The shift constant is out-of-range? This code hasn't been simplified.
205  if (BitIndex >= MOps.Mask.getBitWidth())
206  return false;
207 
208  // Fill in the mask bit derived from the shift constant.
209  MOps.Mask.setBit(BitIndex);
210  return MOps.Root == Candidate;
211 }
212 
213 /// Match patterns that correspond to "any-bits-set" and "all-bits-set".
214 /// These will include a chain of 'or' or 'and'-shifted bits from a
215 /// common source value:
216 /// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0
217 /// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
218 /// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
219 /// that differ only with a final 'not' of the result. We expect that final
220 /// 'not' to be folded with the compare that we create here (invert predicate).
222  // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
223  // final "and X, 1" instruction must be the final op in the sequence.
224  bool MatchAllBitsSet;
225  if (match(&I, m_c_And(m_OneUse(m_And(m_Value(), m_Value())), m_Value())))
226  MatchAllBitsSet = true;
227  else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))
228  MatchAllBitsSet = false;
229  else
230  return false;
231 
232  MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
233  if (MatchAllBitsSet) {
234  if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || !MOps.FoundAnd1)
235  return false;
236  } else {
237  if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))
238  return false;
239  }
240 
241  // The pattern was found. Create a masked compare that replaces all of the
242  // shift and logic ops.
243  IRBuilder<> Builder(&I);
244  Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);
245  Value *And = Builder.CreateAnd(MOps.Root, Mask);
246  Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(And, Mask)
247  : Builder.CreateIsNotNull(And);
248  Value *Zext = Builder.CreateZExt(Cmp, I.getType());
249  I.replaceAllUsesWith(Zext);
250  return true;
251 }
252 
253 // Try to recognize below function as popcount intrinsic.
254 // This is the "best" algorithm from
255 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
256 // Also used in TargetLowering::expandCTPOP().
257 //
258 // int popcount(unsigned int i) {
259 // i = i - ((i >> 1) & 0x55555555);
260 // i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
261 // i = ((i + (i >> 4)) & 0x0F0F0F0F);
262 // return (i * 0x01010101) >> 24;
263 // }
265  if (I.getOpcode() != Instruction::LShr)
266  return false;
267 
268  Type *Ty = I.getType();
269  if (!Ty->isIntOrIntVectorTy())
270  return false;
271 
272  unsigned Len = Ty->getScalarSizeInBits();
273  // FIXME: fix Len == 8 and other irregular type lengths.
274  if (!(Len <= 128 && Len > 8 && Len % 8 == 0))
275  return false;
276 
277  APInt Mask55 = APInt::getSplat(Len, APInt(8, 0x55));
278  APInt Mask33 = APInt::getSplat(Len, APInt(8, 0x33));
279  APInt Mask0F = APInt::getSplat(Len, APInt(8, 0x0F));
280  APInt Mask01 = APInt::getSplat(Len, APInt(8, 0x01));
281  APInt MaskShift = APInt(Len, Len - 8);
282 
283  Value *Op0 = I.getOperand(0);
284  Value *Op1 = I.getOperand(1);
285  Value *MulOp0;
286  // Matching "(i * 0x01010101...) >> 24".
287  if ((match(Op0, m_Mul(m_Value(MulOp0), m_SpecificInt(Mask01)))) &&
288  match(Op1, m_SpecificInt(MaskShift))) {
289  Value *ShiftOp0;
290  // Matching "((i + (i >> 4)) & 0x0F0F0F0F...)".
291  if (match(MulOp0, m_And(m_c_Add(m_LShr(m_Value(ShiftOp0), m_SpecificInt(4)),
292  m_Deferred(ShiftOp0)),
293  m_SpecificInt(Mask0F)))) {
294  Value *AndOp0;
295  // Matching "(i & 0x33333333...) + ((i >> 2) & 0x33333333...)".
296  if (match(ShiftOp0,
297  m_c_Add(m_And(m_Value(AndOp0), m_SpecificInt(Mask33)),
298  m_And(m_LShr(m_Deferred(AndOp0), m_SpecificInt(2)),
299  m_SpecificInt(Mask33))))) {
300  Value *Root, *SubOp1;
301  // Matching "i - ((i >> 1) & 0x55555555...)".
302  if (match(AndOp0, m_Sub(m_Value(Root), m_Value(SubOp1))) &&
303  match(SubOp1, m_And(m_LShr(m_Specific(Root), m_SpecificInt(1)),
304  m_SpecificInt(Mask55)))) {
305  LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
306  IRBuilder<> Builder(&I);
308  I.getModule(), Intrinsic::ctpop, I.getType());
309  I.replaceAllUsesWith(Builder.CreateCall(Func, {Root}));
310  return true;
311  }
312  }
313  }
314  }
315 
316  return false;
317 }
318 
319 /// This is the entry point for folds that could be implemented in regular
320 /// InstCombine, but they are separated because they are not expected to
321 /// occur frequently and/or have more than a constant-length pattern match.
323  bool MadeChange = false;
324  for (BasicBlock &BB : F) {
325  // Ignore unreachable basic blocks.
326  if (!DT.isReachableFromEntry(&BB))
327  continue;
328  // Do not delete instructions under here and invalidate the iterator.
329  // Walk the block backwards for efficiency. We're matching a chain of
330  // use->defs, so we're more likely to succeed by starting from the bottom.
331  // Also, we want to avoid matching partial patterns.
332  // TODO: It would be more efficient if we removed dead instructions
333  // iteratively in this loop rather than waiting until the end.
334  for (Instruction &I : make_range(BB.rbegin(), BB.rend())) {
335  MadeChange |= foldAnyOrAllBitsSet(I);
336  MadeChange |= foldGuardedRotateToFunnelShift(I);
337  MadeChange |= tryToRecognizePopCount(I);
338  }
339  }
340 
341  // We're done with transforms, so remove dead instructions.
342  if (MadeChange)
343  for (BasicBlock &BB : F)
345 
346  return MadeChange;
347 }
348 
349 /// This is the entry point for all transforms. Pass manager differences are
350 /// handled in the callers of this function.
352  bool MadeChange = false;
353  const DataLayout &DL = F.getParent()->getDataLayout();
354  TruncInstCombine TIC(TLI, DL, DT);
355  MadeChange |= TIC.run(F);
356  MadeChange |= foldUnusualPatterns(F, DT);
357  return MadeChange;
358 }
359 
360 void AggressiveInstCombinerLegacyPass::getAnalysisUsage(
361  AnalysisUsage &AU) const {
362  AU.setPreservesCFG();
369 }
370 
372  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
373  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
374  return runImpl(F, TLI, DT);
375 }
376 
379  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
380  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
381  if (!runImpl(F, TLI, DT)) {
382  // No changes, all analyses are preserved.
383  return PreservedAnalyses::all();
384  }
385  // Mark all the analyses that instcombine updates as preserved.
387  PA.preserveSet<CFGAnalyses>();
388  PA.preserve<AAManager>();
389  PA.preserve<GlobalsAA>();
390  return PA;
391 }
392 
394 INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass,
395  "aggressive-instcombine",
396  "Combine pattern based expressions", false, false)
399 INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass, "aggressive-instcombine",
400  "Combine pattern based expressions", false, false)
401 
402 // Initialization Routines
405 }
406 
409 }
410 
412  return new AggressiveInstCombinerLegacyPass();
413 }
414 
417 }
Legacy wrapper pass to provide the GlobalsAAResult object.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:874
specific_bbval m_SpecificBB(BasicBlock *BB)
Match a specific basic block value.
Definition: PatternMatch.h:689
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
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...
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:771
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is not null.
Definition: IRBuilder.h:2384
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:777
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:826
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
struct LLVMOpaquePassRegistry * LLVMPassRegistryRef
Definition: Types.h:131
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:602
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:144
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:391
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1517
static bool matchAndOrChain(Value *V, MaskOps &MOps)
This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of &#39;and&#39; or &#39;or&#39; inst...
aggressive Combine pattern based expressions
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
void setBit(unsigned BitPosition)
Set a given bit to 1.
Definition: APInt.h:1402
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Attribute unwrap(LLVMAttributeRef Attr)
Definition: Attributes.h:204
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) nee...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
FunctionPass * createAggressiveInstCombinerPass()
void LLVMAddAggressiveInstCombinerPass(LLVMPassManagerRef PM)
See llvm::createAggressiveInstCombinerPass function.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
void LLVMInitializeAggressiveInstCombiner(LLVMPassRegistryRef R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:81
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:203
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
static bool tryToRecognizePopCount(Instruction &I)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1877
static bool foldAnyOrAllBitsSet(Instruction &I)
Match patterns that correspond to "any-bits-set" and "all-bits-set".
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1093
Value * getOperand(unsigned i) const
Definition: User.h:169
aggressive instcombine
INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass, "aggressive-instcombine", "Combine pattern based expressions", false, false) INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:61
static bool runOnFunction(Function &F, bool PostInlining)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:898
static bool foldUnusualPatterns(Function &F, DominatorTree &DT)
This is the entry point for folds that could be implemented in regular InstCombine, but they are separated because they are not expected to occur frequently and/or have more than a constant-length pattern match.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:223
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:465
static Instruction * matchRotate(Instruction &Or)
Transform UB-safe variants of bitwise rotate to the funnel shift intrinsic.
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:46
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:880
This is an important base class in LLVM.
Definition: Constant.h:41
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
A manager for alias analyses.
specific_intval m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:664
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:587
Represent the analysis usage information of a pass.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:892
Analysis pass providing a never-invalidated alias analysis result.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2101
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
void initializeAggressiveInstCombine(PassRegistry &)
Initialize all passes linked into the AggressiveInstCombine library.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
deferredval_ty< Value > m_Deferred(Value *const &V)
A commutative-friendly version of m_Specific().
Definition: PatternMatch.h:600
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
This file provides the primary interface to the aggressive instcombine pass.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getNumOperands() const
Definition: User.h:191
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
static bool foldGuardedRotateToFunnelShift(Instruction &I)
Match a pattern for a bitwise rotate operation that partially guards against undefined behavior by br...
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:134
Provides information about what library functions are available for the current target.
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition: APInt.cpp:577
void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry &)
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:653
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
struct LLVMOpaquePassManager * LLVMPassManagerRef
Definition: Types.h:128
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
Class for arbitrary precision integers.
Definition: APInt.h:69
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
MaskOps(unsigned BitWidth, bool MatchAnds)
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
#define I(x, y, z)
Definition: MD5.cpp:58
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2239
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1268
Analysis pass providing the TargetLibraryInfo.
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:74
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:382
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const BasicBlock * getParent() const
Definition: Instruction.h:66
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Legacy wrapper pass to provide the BasicAAResult object.