LLVM  15.0.0git
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"
19 #include "llvm/ADT/Statistic.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/PatternMatch.h"
31 #include "llvm/InitializePasses.h"
32 #include "llvm/Pass.h"
34 
35 using namespace llvm;
36 using namespace PatternMatch;
37 
38 namespace llvm {
39 class DataLayout;
40 }
41 
42 #define DEBUG_TYPE "aggressive-instcombine"
43 
44 STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded");
45 STATISTIC(NumGuardedRotates,
46  "Number of guarded rotates transformed into funnel shifts");
47 STATISTIC(NumGuardedFunnelShifts,
48  "Number of guarded funnel shifts transformed into funnel shifts");
49 STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized");
50 
51 namespace {
52 /// Contains expression pattern combiner logic.
53 /// This class provides both the logic to combine expression patterns and
54 /// combine them. It differs from InstCombiner class in that each pattern
55 /// combiner runs only once as opposed to InstCombine's multi-iteration,
56 /// which allows pattern combiner to have higher complexity than the O(1)
57 /// required by the instruction combiner.
58 class AggressiveInstCombinerLegacyPass : public FunctionPass {
59 public:
60  static char ID; // Pass identification, replacement for typeid
61 
62  AggressiveInstCombinerLegacyPass() : FunctionPass(ID) {
65  }
66 
67  void getAnalysisUsage(AnalysisUsage &AU) const override;
68 
69  /// Run all expression pattern optimizations on the given /p F function.
70  ///
71  /// \param F function to optimize.
72  /// \returns true if the IR is changed.
73  bool runOnFunction(Function &F) override;
74 };
75 } // namespace
76 
77 /// Match a pattern for a bitwise funnel/rotate operation that partially guards
78 /// against undefined behavior by branching around the funnel-shift/rotation
79 /// when the shift amount is 0.
81  if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)
82  return false;
83 
84  // As with the one-use checks below, this is not strictly necessary, but we
85  // are being cautious to avoid potential perf regressions on targets that
86  // do not actually have a funnel/rotate instruction (where the funnel shift
87  // would be expanded back into math/shift/logic ops).
88  if (!isPowerOf2_32(I.getType()->getScalarSizeInBits()))
89  return false;
90 
91  // Match V to funnel shift left/right and capture the source operands and
92  // shift amount.
93  auto matchFunnelShift = [](Value *V, Value *&ShVal0, Value *&ShVal1,
94  Value *&ShAmt) {
95  Value *SubAmt;
96  unsigned Width = V->getType()->getScalarSizeInBits();
97 
98  // fshl(ShVal0, ShVal1, ShAmt)
99  // == (ShVal0 << ShAmt) | (ShVal1 >> (Width -ShAmt))
100  if (match(V, m_OneUse(m_c_Or(
101  m_Shl(m_Value(ShVal0), m_Value(ShAmt)),
102  m_LShr(m_Value(ShVal1),
103  m_Sub(m_SpecificInt(Width), m_Value(SubAmt))))))) {
104  if (ShAmt == SubAmt) // TODO: Use m_Specific
105  return Intrinsic::fshl;
106  }
107 
108  // fshr(ShVal0, ShVal1, ShAmt)
109  // == (ShVal0 >> ShAmt) | (ShVal1 << (Width - ShAmt))
110  if (match(V,
112  m_Value(SubAmt))),
113  m_LShr(m_Value(ShVal1), m_Value(ShAmt)))))) {
114  if (ShAmt == SubAmt) // TODO: Use m_Specific
115  return Intrinsic::fshr;
116  }
117 
119  };
120 
121  // One phi operand must be a funnel/rotate operation, and the other phi
122  // operand must be the source value of that funnel/rotate operation:
123  // phi [ rotate(RotSrc, ShAmt), FunnelBB ], [ RotSrc, GuardBB ]
124  // phi [ fshl(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal0, GuardBB ]
125  // phi [ fshr(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal1, GuardBB ]
126  PHINode &Phi = cast<PHINode>(I);
127  unsigned FunnelOp = 0, GuardOp = 1;
128  Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);
129  Value *ShVal0, *ShVal1, *ShAmt;
130  Intrinsic::ID IID = matchFunnelShift(P0, ShVal0, ShVal1, ShAmt);
131  if (IID == Intrinsic::not_intrinsic ||
132  (IID == Intrinsic::fshl && ShVal0 != P1) ||
133  (IID == Intrinsic::fshr && ShVal1 != P1)) {
134  IID = matchFunnelShift(P1, ShVal0, ShVal1, ShAmt);
135  if (IID == Intrinsic::not_intrinsic ||
136  (IID == Intrinsic::fshl && ShVal0 != P0) ||
137  (IID == Intrinsic::fshr && ShVal1 != P0))
138  return false;
139  assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
140  "Pattern must match funnel shift left or right");
141  std::swap(FunnelOp, GuardOp);
142  }
143 
144  // The incoming block with our source operand must be the "guard" block.
145  // That must contain a cmp+branch to avoid the funnel/rotate when the shift
146  // amount is equal to 0. The other incoming block is the block with the
147  // funnel/rotate.
148  BasicBlock *GuardBB = Phi.getIncomingBlock(GuardOp);
149  BasicBlock *FunnelBB = Phi.getIncomingBlock(FunnelOp);
150  Instruction *TermI = GuardBB->getTerminator();
151 
152  // Ensure that the shift values dominate each block.
153  if (!DT.dominates(ShVal0, TermI) || !DT.dominates(ShVal1, TermI))
154  return false;
155 
156  ICmpInst::Predicate Pred;
157  BasicBlock *PhiBB = Phi.getParent();
158  if (!match(TermI, m_Br(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()),
159  m_SpecificBB(PhiBB), m_SpecificBB(FunnelBB))))
160  return false;
161 
162  if (Pred != CmpInst::ICMP_EQ)
163  return false;
164 
165  IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt());
166 
167  if (ShVal0 == ShVal1)
168  ++NumGuardedRotates;
169  else
170  ++NumGuardedFunnelShifts;
171 
172  // If this is not a rotate then the select was blocking poison from the
173  // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
174  bool IsFshl = IID == Intrinsic::fshl;
175  if (ShVal0 != ShVal1) {
176  if (IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal1))
177  ShVal1 = Builder.CreateFreeze(ShVal1);
178  else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal0))
179  ShVal0 = Builder.CreateFreeze(ShVal0);
180  }
181 
182  // We matched a variation of this IR pattern:
183  // GuardBB:
184  // %cmp = icmp eq i32 %ShAmt, 0
185  // br i1 %cmp, label %PhiBB, label %FunnelBB
186  // FunnelBB:
187  // %sub = sub i32 32, %ShAmt
188  // %shr = lshr i32 %ShVal1, %sub
189  // %shl = shl i32 %ShVal0, %ShAmt
190  // %fsh = or i32 %shr, %shl
191  // br label %PhiBB
192  // PhiBB:
193  // %cond = phi i32 [ %fsh, %FunnelBB ], [ %ShVal0, %GuardBB ]
194  // -->
195  // llvm.fshl.i32(i32 %ShVal0, i32 %ShVal1, i32 %ShAmt)
196  Function *F = Intrinsic::getDeclaration(Phi.getModule(), IID, Phi.getType());
197  Phi.replaceAllUsesWith(Builder.CreateCall(F, {ShVal0, ShVal1, ShAmt}));
198  return true;
199 }
200 
201 /// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
202 /// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
203 /// of 'and' ops, then we also need to capture the fact that we saw an
204 /// "and X, 1", so that's an extra return value for that case.
205 struct MaskOps {
206  Value *Root = nullptr;
209  bool FoundAnd1 = false;
210 
211  MaskOps(unsigned BitWidth, bool MatchAnds)
212  : Mask(APInt::getZero(BitWidth)), MatchAndChain(MatchAnds) {}
213 };
214 
215 /// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
216 /// chain of 'and' or 'or' instructions looking for shift ops of a common source
217 /// value. Examples:
218 /// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
219 /// returns { X, 0x129 }
220 /// and (and (X >> 1), 1), (X >> 4)
221 /// returns { X, 0x12 }
222 static bool matchAndOrChain(Value *V, MaskOps &MOps) {
223  Value *Op0, *Op1;
224  if (MOps.MatchAndChain) {
225  // Recurse through a chain of 'and' operands. This requires an extra check
226  // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
227  // in the chain to know that all of the high bits are cleared.
228  if (match(V, m_And(m_Value(Op0), m_One()))) {
229  MOps.FoundAnd1 = true;
230  return matchAndOrChain(Op0, MOps);
231  }
232  if (match(V, m_And(m_Value(Op0), m_Value(Op1))))
233  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
234  } else {
235  // Recurse through a chain of 'or' operands.
236  if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))
237  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
238  }
239 
240  // We need a shift-right or a bare value representing a compare of bit 0 of
241  // the original source operand.
242  Value *Candidate;
243  const APInt *BitIndex = nullptr;
244  if (!match(V, m_LShr(m_Value(Candidate), m_APInt(BitIndex))))
245  Candidate = V;
246 
247  // Initialize result source operand.
248  if (!MOps.Root)
249  MOps.Root = Candidate;
250 
251  // The shift constant is out-of-range? This code hasn't been simplified.
252  if (BitIndex && BitIndex->uge(MOps.Mask.getBitWidth()))
253  return false;
254 
255  // Fill in the mask bit derived from the shift constant.
256  MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0);
257  return MOps.Root == Candidate;
258 }
259 
260 /// Match patterns that correspond to "any-bits-set" and "all-bits-set".
261 /// These will include a chain of 'or' or 'and'-shifted bits from a
262 /// common source value:
263 /// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0
264 /// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
265 /// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
266 /// that differ only with a final 'not' of the result. We expect that final
267 /// 'not' to be folded with the compare that we create here (invert predicate).
269  // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
270  // final "and X, 1" instruction must be the final op in the sequence.
271  bool MatchAllBitsSet;
272  if (match(&I, m_c_And(m_OneUse(m_And(m_Value(), m_Value())), m_Value())))
273  MatchAllBitsSet = true;
274  else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))
275  MatchAllBitsSet = false;
276  else
277  return false;
278 
279  MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
280  if (MatchAllBitsSet) {
281  if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || !MOps.FoundAnd1)
282  return false;
283  } else {
284  if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))
285  return false;
286  }
287 
288  // The pattern was found. Create a masked compare that replaces all of the
289  // shift and logic ops.
291  Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);
292  Value *And = Builder.CreateAnd(MOps.Root, Mask);
293  Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(And, Mask)
294  : Builder.CreateIsNotNull(And);
295  Value *Zext = Builder.CreateZExt(Cmp, I.getType());
296  I.replaceAllUsesWith(Zext);
297  ++NumAnyOrAllBitsSet;
298  return true;
299 }
300 
301 // Try to recognize below function as popcount intrinsic.
302 // This is the "best" algorithm from
303 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
304 // Also used in TargetLowering::expandCTPOP().
305 //
306 // int popcount(unsigned int i) {
307 // i = i - ((i >> 1) & 0x55555555);
308 // i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
309 // i = ((i + (i >> 4)) & 0x0F0F0F0F);
310 // return (i * 0x01010101) >> 24;
311 // }
313  if (I.getOpcode() != Instruction::LShr)
314  return false;
315 
316  Type *Ty = I.getType();
317  if (!Ty->isIntOrIntVectorTy())
318  return false;
319 
320  unsigned Len = Ty->getScalarSizeInBits();
321  // FIXME: fix Len == 8 and other irregular type lengths.
322  if (!(Len <= 128 && Len > 8 && Len % 8 == 0))
323  return false;
324 
325  APInt Mask55 = APInt::getSplat(Len, APInt(8, 0x55));
326  APInt Mask33 = APInt::getSplat(Len, APInt(8, 0x33));
327  APInt Mask0F = APInt::getSplat(Len, APInt(8, 0x0F));
328  APInt Mask01 = APInt::getSplat(Len, APInt(8, 0x01));
329  APInt MaskShift = APInt(Len, Len - 8);
330 
331  Value *Op0 = I.getOperand(0);
332  Value *Op1 = I.getOperand(1);
333  Value *MulOp0;
334  // Matching "(i * 0x01010101...) >> 24".
335  if ((match(Op0, m_Mul(m_Value(MulOp0), m_SpecificInt(Mask01)))) &&
336  match(Op1, m_SpecificInt(MaskShift))) {
337  Value *ShiftOp0;
338  // Matching "((i + (i >> 4)) & 0x0F0F0F0F...)".
339  if (match(MulOp0, m_And(m_c_Add(m_LShr(m_Value(ShiftOp0), m_SpecificInt(4)),
340  m_Deferred(ShiftOp0)),
341  m_SpecificInt(Mask0F)))) {
342  Value *AndOp0;
343  // Matching "(i & 0x33333333...) + ((i >> 2) & 0x33333333...)".
344  if (match(ShiftOp0,
345  m_c_Add(m_And(m_Value(AndOp0), m_SpecificInt(Mask33)),
346  m_And(m_LShr(m_Deferred(AndOp0), m_SpecificInt(2)),
347  m_SpecificInt(Mask33))))) {
348  Value *Root, *SubOp1;
349  // Matching "i - ((i >> 1) & 0x55555555...)".
350  if (match(AndOp0, m_Sub(m_Value(Root), m_Value(SubOp1))) &&
351  match(SubOp1, m_And(m_LShr(m_Specific(Root), m_SpecificInt(1)),
352  m_SpecificInt(Mask55)))) {
353  LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
356  I.getModule(), Intrinsic::ctpop, I.getType());
357  I.replaceAllUsesWith(Builder.CreateCall(Func, {Root}));
358  ++NumPopCountRecognized;
359  return true;
360  }
361  }
362  }
363  }
364 
365  return false;
366 }
367 
368 /// This is the entry point for folds that could be implemented in regular
369 /// InstCombine, but they are separated because they are not expected to
370 /// occur frequently and/or have more than a constant-length pattern match.
372  bool MadeChange = false;
373  for (BasicBlock &BB : F) {
374  // Ignore unreachable basic blocks.
375  if (!DT.isReachableFromEntry(&BB))
376  continue;
377  // Do not delete instructions under here and invalidate the iterator.
378  // Walk the block backwards for efficiency. We're matching a chain of
379  // use->defs, so we're more likely to succeed by starting from the bottom.
380  // Also, we want to avoid matching partial patterns.
381  // TODO: It would be more efficient if we removed dead instructions
382  // iteratively in this loop rather than waiting until the end.
383  for (Instruction &I : llvm::reverse(BB)) {
384  MadeChange |= foldAnyOrAllBitsSet(I);
385  MadeChange |= foldGuardedFunnelShift(I, DT);
386  MadeChange |= tryToRecognizePopCount(I);
387  }
388  }
389 
390  // We're done with transforms, so remove dead instructions.
391  if (MadeChange)
392  for (BasicBlock &BB : F)
394 
395  return MadeChange;
396 }
397 
398 /// This is the entry point for all transforms. Pass manager differences are
399 /// handled in the callers of this function.
401  DominatorTree &DT) {
402  bool MadeChange = false;
403  const DataLayout &DL = F.getParent()->getDataLayout();
404  TruncInstCombine TIC(AC, TLI, DL, DT);
405  MadeChange |= TIC.run(F);
406  MadeChange |= foldUnusualPatterns(F, DT);
407  return MadeChange;
408 }
409 
410 void AggressiveInstCombinerLegacyPass::getAnalysisUsage(
411  AnalysisUsage &AU) const {
412  AU.setPreservesCFG();
420 }
421 
423  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
424  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
425  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
426  return runImpl(F, AC, TLI, DT);
427 }
428 
431  auto &AC = AM.getResult<AssumptionAnalysis>(F);
432  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
433  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
434  if (!runImpl(F, AC, TLI, DT)) {
435  // No changes, all analyses are preserved.
436  return PreservedAnalyses::all();
437  }
438  // Mark all the analyses that instcombine updates as preserved.
440  PA.preserveSet<CFGAnalyses>();
441  return PA;
442 }
443 
445 INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass,
446  "aggressive-instcombine",
447  "Combine pattern based expressions", false, false)
451 INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass, "aggressive-instcombine",
452  "Combine pattern based expressions", false, false)
453 
454 // Initialization Routines
457 }
458 
461 }
462 
464  return new AggressiveInstCombinerLegacyPass();
465 }
466 
469 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
AssumptionCache.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:65
MaskOps::MatchAndChain
bool MatchAndChain
Definition: AggressiveInstCombine.cpp:208
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Intrinsic::getDeclaration
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:1410
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
MaskOps::Mask
APInt Mask
Definition: AggressiveInstCombine.cpp:207
LLVMPassRegistryRef
struct LLVMOpaquePassRegistry * LLVMPassRegistryRef
Definition: Types.h:130
foldGuardedFunnelShift
static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT)
Match a pattern for a bitwise funnel/rotate operation that partially guards against undefined behavio...
Definition: AggressiveInstCombine.cpp:80
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::Function
Definition: Function.h:60
Pass.h
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1127
Statistic.h
llvm::IRBuilder<>
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
GlobalsModRef.h
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1741
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
tryToRecognizePopCount
static bool tryToRecognizePopCount(Instruction &I)
Definition: AggressiveInstCombine.cpp:312
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::AggressiveInstCombinePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AggressiveInstCombine.cpp:429
foldUnusualPatterns
static bool foldUnusualPatterns(Function &F, DominatorTree &DT)
This is the entry point for folds that could be implemented in regular InstCombine,...
Definition: AggressiveInstCombine.cpp:371
llvm::PatternMatch::m_SpecificBB
specific_bbval m_SpecificBB(BasicBlock *BB)
Match a specific basic block value.
Definition: PatternMatch.h:896
llvm::Intrinsic::not_intrinsic
@ not_intrinsic
Definition: Intrinsics.h:45
aggressive
Note that only the low bits of effective_addr2 are used On bit we don t eliminate the computation of the top half of effective_addr2 because we don t have whole function selection dags On this means we use one extra register for the function when effective_addr2 is declared as U64 than when it is declared U32 PHI Slicing could be extended to do this Tail call elim should be more aggressive
Definition: README.txt:326
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:491
llvm::PatternMatch::m_c_And
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.
Definition: PatternMatch.h:2262
BasicAliasAnalysis.h
LegacyPassManager.h
MaskOps::Root
Value * Root
Definition: AggressiveInstCombine.cpp:206
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:798
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::TruncInstCombine::run
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
Definition: TruncInstCombine.cpp:525
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:270
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1171
llvm::SimplifyInstructionsInBlock
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:707
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
llvm::APInt::setBit
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
Definition: APInt.h:1292
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::TruncInstCombine
Definition: AggressiveInstCombineInternal.h:54
llvm::initializeAggressiveInstCombinerLegacyPassPass
void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry &)
llvm::initializeAggressiveInstCombine
void initializeAggressiveInstCombine(PassRegistry &)
Initialize all passes linked into the AggressiveInstCombine library.
Definition: AggressiveInstCombine.cpp:455
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TargetLibraryInfo.h
llvm::BasicBlock::getFirstInsertionPt
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:246
false
Definition: StackSlotColoring.cpp:141
llvm::PatternMatch::m_c_Add
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.
Definition: PatternMatch.h:2248
runImpl
static bool runImpl(Function &F, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
Definition: AggressiveInstCombine.cpp:400
llvm::Instruction
Definition: Instruction.h:42
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
llvm::PatternMatch::m_c_Or
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.
Definition: PatternMatch.h:2269
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::unwrap
Attribute unwrap(LLVMAttributeRef Attr)
Definition: Attributes.h:264
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1478
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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
LLVMInitializeAggressiveInstCombiner
void LLVMInitializeAggressiveInstCombiner(LLVMPassRegistryRef R)
Definition: AggressiveInstCombine.cpp:459
PatternMatch.h
expressions
aggressive Combine pattern based expressions
Definition: AggressiveInstCombine.cpp:452
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:513
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
AggressiveInstCombineInternal.h
matchAndOrChain
static bool matchAndOrChain(Value *V, MaskOps &MOps)
This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of 'and' or 'or' inst...
Definition: AggressiveInstCombine.cpp:222
instcombine
aggressive instcombine
Definition: AggressiveInstCombine.cpp:451
Combine
Hexagon Vector Combine
Definition: HexagonVectorCombine.cpp:1527
matchFunnelShift
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
Definition: InstCombineAndOrXor.cpp:2109
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
MaskOps::MaskOps
MaskOps(unsigned BitWidth, bool MatchAnds)
Definition: AggressiveInstCombine.cpp:211
llvm::createAggressiveInstCombinerPass
FunctionPass * createAggressiveInstCombinerPass()
Definition: AggressiveInstCombine.cpp:463
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:173
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
AggressiveInstCombine.h
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1103
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1000
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
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
LLVMPassManagerRef
struct LLVMOpaquePassManager * LLVMPassManagerRef
Definition: Types.h:127
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass, "aggressive-instcombine", "Combine pattern based expressions", false, false) INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass
llvm::PatternMatch::m_SpecificInt
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:863
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
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::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
MaskOps
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) nee...
Definition: AggressiveInstCombine.cpp:205
MaskOps::FoundAnd1
bool FoundAnd1
Definition: AggressiveInstCombine.cpp:209
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:197
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::APInt::getSplat
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition: APInt.cpp:612
llvm::PatternMatch::m_ZeroInt
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:522
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:435
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
foldAnyOrAllBitsSet
static bool foldAnyOrAllBitsSet(Instruction &I)
Match patterns that correspond to "any-bits-set" and "all-bits-set".
Definition: AggressiveInstCombine.cpp:268
llvm::Registry
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:780
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1404
Dominators.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1347
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::PHINode
Definition: Instructions.h:2664
llvm::BasicBlock::getTerminator
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.h:119
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
LLVMAddAggressiveInstCombinerPass
void LLVMAddAggressiveInstCombinerPass(LLVMPassManagerRef PM)
See llvm::createAggressiveInstCombinerPass function.
Definition: AggressiveInstCombine.cpp:467
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5274
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
AggressiveInstCombine.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::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:443
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1055
Initialization.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37