LLVM  14.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/DataLayout.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Pass.h"
35 
36 using namespace llvm;
37 using namespace PatternMatch;
38 
39 #define DEBUG_TYPE "aggressive-instcombine"
40 
41 STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded");
42 STATISTIC(NumGuardedRotates,
43  "Number of guarded rotates transformed into funnel shifts");
44 STATISTIC(NumGuardedFunnelShifts,
45  "Number of guarded funnel shifts transformed into funnel shifts");
46 STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized");
47 
48 namespace {
49 /// Contains expression pattern combiner logic.
50 /// This class provides both the logic to combine expression patterns and
51 /// combine them. It differs from InstCombiner class in that each pattern
52 /// combiner runs only once as opposed to InstCombine's multi-iteration,
53 /// which allows pattern combiner to have higher complexity than the O(1)
54 /// required by the instruction combiner.
55 class AggressiveInstCombinerLegacyPass : public FunctionPass {
56 public:
57  static char ID; // Pass identification, replacement for typeid
58 
59  AggressiveInstCombinerLegacyPass() : FunctionPass(ID) {
62  }
63 
64  void getAnalysisUsage(AnalysisUsage &AU) const override;
65 
66  /// Run all expression pattern optimizations on the given /p F function.
67  ///
68  /// \param F function to optimize.
69  /// \returns true if the IR is changed.
70  bool runOnFunction(Function &F) override;
71 };
72 } // namespace
73 
74 /// Match a pattern for a bitwise funnel/rotate operation that partially guards
75 /// against undefined behavior by branching around the funnel-shift/rotation
76 /// when the shift amount is 0.
78  if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)
79  return false;
80 
81  // As with the one-use checks below, this is not strictly necessary, but we
82  // are being cautious to avoid potential perf regressions on targets that
83  // do not actually have a funnel/rotate instruction (where the funnel shift
84  // would be expanded back into math/shift/logic ops).
85  if (!isPowerOf2_32(I.getType()->getScalarSizeInBits()))
86  return false;
87 
88  // Match V to funnel shift left/right and capture the source operands and
89  // shift amount.
90  auto matchFunnelShift = [](Value *V, Value *&ShVal0, Value *&ShVal1,
91  Value *&ShAmt) {
92  Value *SubAmt;
93  unsigned Width = V->getType()->getScalarSizeInBits();
94 
95  // fshl(ShVal0, ShVal1, ShAmt)
96  // == (ShVal0 << ShAmt) | (ShVal1 >> (Width -ShAmt))
97  if (match(V, m_OneUse(m_c_Or(
98  m_Shl(m_Value(ShVal0), m_Value(ShAmt)),
99  m_LShr(m_Value(ShVal1),
100  m_Sub(m_SpecificInt(Width), m_Value(SubAmt))))))) {
101  if (ShAmt == SubAmt) // TODO: Use m_Specific
102  return Intrinsic::fshl;
103  }
104 
105  // fshr(ShVal0, ShVal1, ShAmt)
106  // == (ShVal0 >> ShAmt) | (ShVal1 << (Width - ShAmt))
107  if (match(V,
109  m_Value(SubAmt))),
110  m_LShr(m_Value(ShVal1), m_Value(ShAmt)))))) {
111  if (ShAmt == SubAmt) // TODO: Use m_Specific
112  return Intrinsic::fshr;
113  }
114 
116  };
117 
118  // One phi operand must be a funnel/rotate operation, and the other phi
119  // operand must be the source value of that funnel/rotate operation:
120  // phi [ rotate(RotSrc, ShAmt), FunnelBB ], [ RotSrc, GuardBB ]
121  // phi [ fshl(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal0, GuardBB ]
122  // phi [ fshr(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal1, GuardBB ]
123  PHINode &Phi = cast<PHINode>(I);
124  unsigned FunnelOp = 0, GuardOp = 1;
125  Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);
126  Value *ShVal0, *ShVal1, *ShAmt;
127  Intrinsic::ID IID = matchFunnelShift(P0, ShVal0, ShVal1, ShAmt);
128  if (IID == Intrinsic::not_intrinsic ||
129  (IID == Intrinsic::fshl && ShVal0 != P1) ||
130  (IID == Intrinsic::fshr && ShVal1 != P1)) {
131  IID = matchFunnelShift(P1, ShVal0, ShVal1, ShAmt);
132  if (IID == Intrinsic::not_intrinsic ||
133  (IID == Intrinsic::fshl && ShVal0 != P0) ||
134  (IID == Intrinsic::fshr && ShVal1 != P0))
135  return false;
136  assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
137  "Pattern must match funnel shift left or right");
138  std::swap(FunnelOp, GuardOp);
139  }
140 
141  // The incoming block with our source operand must be the "guard" block.
142  // That must contain a cmp+branch to avoid the funnel/rotate when the shift
143  // amount is equal to 0. The other incoming block is the block with the
144  // funnel/rotate.
145  BasicBlock *GuardBB = Phi.getIncomingBlock(GuardOp);
146  BasicBlock *FunnelBB = Phi.getIncomingBlock(FunnelOp);
147  Instruction *TermI = GuardBB->getTerminator();
148 
149  // Ensure that the shift values dominate each block.
150  if (!DT.dominates(ShVal0, TermI) || !DT.dominates(ShVal1, TermI))
151  return false;
152 
153  ICmpInst::Predicate Pred;
154  BasicBlock *PhiBB = Phi.getParent();
155  if (!match(TermI, m_Br(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()),
156  m_SpecificBB(PhiBB), m_SpecificBB(FunnelBB))))
157  return false;
158 
159  if (Pred != CmpInst::ICMP_EQ)
160  return false;
161 
162  IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt());
163 
164  if (ShVal0 == ShVal1)
165  ++NumGuardedRotates;
166  else
167  ++NumGuardedFunnelShifts;
168 
169  // If this is not a rotate then the select was blocking poison from the
170  // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
171  bool IsFshl = IID == Intrinsic::fshl;
172  if (ShVal0 != ShVal1) {
173  if (IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal1))
174  ShVal1 = Builder.CreateFreeze(ShVal1);
175  else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal0))
176  ShVal0 = Builder.CreateFreeze(ShVal0);
177  }
178 
179  // We matched a variation of this IR pattern:
180  // GuardBB:
181  // %cmp = icmp eq i32 %ShAmt, 0
182  // br i1 %cmp, label %PhiBB, label %FunnelBB
183  // FunnelBB:
184  // %sub = sub i32 32, %ShAmt
185  // %shr = lshr i32 %ShVal1, %sub
186  // %shl = shl i32 %ShVal0, %ShAmt
187  // %fsh = or i32 %shr, %shl
188  // br label %PhiBB
189  // PhiBB:
190  // %cond = phi i32 [ %fsh, %FunnelBB ], [ %ShVal0, %GuardBB ]
191  // -->
192  // llvm.fshl.i32(i32 %ShVal0, i32 %ShVal1, i32 %ShAmt)
193  Function *F = Intrinsic::getDeclaration(Phi.getModule(), IID, Phi.getType());
194  Phi.replaceAllUsesWith(Builder.CreateCall(F, {ShVal0, ShVal1, ShAmt}));
195  return true;
196 }
197 
198 /// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
199 /// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
200 /// of 'and' ops, then we also need to capture the fact that we saw an
201 /// "and X, 1", so that's an extra return value for that case.
202 struct MaskOps {
206  bool FoundAnd1;
207 
208  MaskOps(unsigned BitWidth, bool MatchAnds)
209  : Root(nullptr), Mask(APInt::getZero(BitWidth)), MatchAndChain(MatchAnds),
210  FoundAnd1(false) {}
211 };
212 
213 /// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
214 /// chain of 'and' or 'or' instructions looking for shift ops of a common source
215 /// value. Examples:
216 /// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
217 /// returns { X, 0x129 }
218 /// and (and (X >> 1), 1), (X >> 4)
219 /// returns { X, 0x12 }
220 static bool matchAndOrChain(Value *V, MaskOps &MOps) {
221  Value *Op0, *Op1;
222  if (MOps.MatchAndChain) {
223  // Recurse through a chain of 'and' operands. This requires an extra check
224  // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
225  // in the chain to know that all of the high bits are cleared.
226  if (match(V, m_And(m_Value(Op0), m_One()))) {
227  MOps.FoundAnd1 = true;
228  return matchAndOrChain(Op0, MOps);
229  }
230  if (match(V, m_And(m_Value(Op0), m_Value(Op1))))
231  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
232  } else {
233  // Recurse through a chain of 'or' operands.
234  if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))
235  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
236  }
237 
238  // We need a shift-right or a bare value representing a compare of bit 0 of
239  // the original source operand.
240  Value *Candidate;
241  const APInt *BitIndex = nullptr;
242  if (!match(V, m_LShr(m_Value(Candidate), m_APInt(BitIndex))))
243  Candidate = V;
244 
245  // Initialize result source operand.
246  if (!MOps.Root)
247  MOps.Root = Candidate;
248 
249  // The shift constant is out-of-range? This code hasn't been simplified.
250  if (BitIndex && BitIndex->uge(MOps.Mask.getBitWidth()))
251  return false;
252 
253  // Fill in the mask bit derived from the shift constant.
254  MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0);
255  return MOps.Root == Candidate;
256 }
257 
258 /// Match patterns that correspond to "any-bits-set" and "all-bits-set".
259 /// These will include a chain of 'or' or 'and'-shifted bits from a
260 /// common source value:
261 /// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0
262 /// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
263 /// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
264 /// that differ only with a final 'not' of the result. We expect that final
265 /// 'not' to be folded with the compare that we create here (invert predicate).
267  // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
268  // final "and X, 1" instruction must be the final op in the sequence.
269  bool MatchAllBitsSet;
270  if (match(&I, m_c_And(m_OneUse(m_And(m_Value(), m_Value())), m_Value())))
271  MatchAllBitsSet = true;
272  else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))
273  MatchAllBitsSet = false;
274  else
275  return false;
276 
277  MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
278  if (MatchAllBitsSet) {
279  if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || !MOps.FoundAnd1)
280  return false;
281  } else {
282  if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))
283  return false;
284  }
285 
286  // The pattern was found. Create a masked compare that replaces all of the
287  // shift and logic ops.
289  Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);
290  Value *And = Builder.CreateAnd(MOps.Root, Mask);
291  Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(And, Mask)
292  : Builder.CreateIsNotNull(And);
293  Value *Zext = Builder.CreateZExt(Cmp, I.getType());
294  I.replaceAllUsesWith(Zext);
295  ++NumAnyOrAllBitsSet;
296  return true;
297 }
298 
299 // Try to recognize below function as popcount intrinsic.
300 // This is the "best" algorithm from
301 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
302 // Also used in TargetLowering::expandCTPOP().
303 //
304 // int popcount(unsigned int i) {
305 // i = i - ((i >> 1) & 0x55555555);
306 // i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
307 // i = ((i + (i >> 4)) & 0x0F0F0F0F);
308 // return (i * 0x01010101) >> 24;
309 // }
311  if (I.getOpcode() != Instruction::LShr)
312  return false;
313 
314  Type *Ty = I.getType();
315  if (!Ty->isIntOrIntVectorTy())
316  return false;
317 
318  unsigned Len = Ty->getScalarSizeInBits();
319  // FIXME: fix Len == 8 and other irregular type lengths.
320  if (!(Len <= 128 && Len > 8 && Len % 8 == 0))
321  return false;
322 
323  APInt Mask55 = APInt::getSplat(Len, APInt(8, 0x55));
324  APInt Mask33 = APInt::getSplat(Len, APInt(8, 0x33));
325  APInt Mask0F = APInt::getSplat(Len, APInt(8, 0x0F));
326  APInt Mask01 = APInt::getSplat(Len, APInt(8, 0x01));
327  APInt MaskShift = APInt(Len, Len - 8);
328 
329  Value *Op0 = I.getOperand(0);
330  Value *Op1 = I.getOperand(1);
331  Value *MulOp0;
332  // Matching "(i * 0x01010101...) >> 24".
333  if ((match(Op0, m_Mul(m_Value(MulOp0), m_SpecificInt(Mask01)))) &&
334  match(Op1, m_SpecificInt(MaskShift))) {
335  Value *ShiftOp0;
336  // Matching "((i + (i >> 4)) & 0x0F0F0F0F...)".
337  if (match(MulOp0, m_And(m_c_Add(m_LShr(m_Value(ShiftOp0), m_SpecificInt(4)),
338  m_Deferred(ShiftOp0)),
339  m_SpecificInt(Mask0F)))) {
340  Value *AndOp0;
341  // Matching "(i & 0x33333333...) + ((i >> 2) & 0x33333333...)".
342  if (match(ShiftOp0,
343  m_c_Add(m_And(m_Value(AndOp0), m_SpecificInt(Mask33)),
344  m_And(m_LShr(m_Deferred(AndOp0), m_SpecificInt(2)),
345  m_SpecificInt(Mask33))))) {
346  Value *Root, *SubOp1;
347  // Matching "i - ((i >> 1) & 0x55555555...)".
348  if (match(AndOp0, m_Sub(m_Value(Root), m_Value(SubOp1))) &&
349  match(SubOp1, m_And(m_LShr(m_Specific(Root), m_SpecificInt(1)),
350  m_SpecificInt(Mask55)))) {
351  LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
354  I.getModule(), Intrinsic::ctpop, I.getType());
355  I.replaceAllUsesWith(Builder.CreateCall(Func, {Root}));
356  ++NumPopCountRecognized;
357  return true;
358  }
359  }
360  }
361  }
362 
363  return false;
364 }
365 
366 /// This is the entry point for folds that could be implemented in regular
367 /// InstCombine, but they are separated because they are not expected to
368 /// occur frequently and/or have more than a constant-length pattern match.
370  bool MadeChange = false;
371  for (BasicBlock &BB : F) {
372  // Ignore unreachable basic blocks.
373  if (!DT.isReachableFromEntry(&BB))
374  continue;
375  // Do not delete instructions under here and invalidate the iterator.
376  // Walk the block backwards for efficiency. We're matching a chain of
377  // use->defs, so we're more likely to succeed by starting from the bottom.
378  // Also, we want to avoid matching partial patterns.
379  // TODO: It would be more efficient if we removed dead instructions
380  // iteratively in this loop rather than waiting until the end.
381  for (Instruction &I : make_range(BB.rbegin(), BB.rend())) {
382  MadeChange |= foldAnyOrAllBitsSet(I);
383  MadeChange |= foldGuardedFunnelShift(I, DT);
384  MadeChange |= tryToRecognizePopCount(I);
385  }
386  }
387 
388  // We're done with transforms, so remove dead instructions.
389  if (MadeChange)
390  for (BasicBlock &BB : F)
392 
393  return MadeChange;
394 }
395 
396 /// This is the entry point for all transforms. Pass manager differences are
397 /// handled in the callers of this function.
399  DominatorTree &DT) {
400  bool MadeChange = false;
401  const DataLayout &DL = F.getParent()->getDataLayout();
402  TruncInstCombine TIC(AC, TLI, DL, DT);
403  MadeChange |= TIC.run(F);
404  MadeChange |= foldUnusualPatterns(F, DT);
405  return MadeChange;
406 }
407 
408 void AggressiveInstCombinerLegacyPass::getAnalysisUsage(
409  AnalysisUsage &AU) const {
410  AU.setPreservesCFG();
418 }
419 
421  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
422  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
423  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
424  return runImpl(F, AC, TLI, DT);
425 }
426 
429  auto &AC = AM.getResult<AssumptionAnalysis>(F);
430  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
431  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
432  if (!runImpl(F, AC, TLI, DT)) {
433  // No changes, all analyses are preserved.
434  return PreservedAnalyses::all();
435  }
436  // Mark all the analyses that instcombine updates as preserved.
438  PA.preserveSet<CFGAnalyses>();
439  return PA;
440 }
441 
443 INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass,
444  "aggressive-instcombine",
445  "Combine pattern based expressions", false, false)
449 INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass, "aggressive-instcombine",
450  "Combine pattern based expressions", false, false)
451 
452 // Initialization Routines
455 }
456 
459 }
460 
462  return new AggressiveInstCombinerLegacyPass();
463 }
464 
467 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
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:66
MaskOps::MatchAndChain
bool MatchAndChain
Definition: AggressiveInstCombine.cpp:205
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
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:1379
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
MaskOps::Mask
APInt Mask
Definition: AggressiveInstCombine.cpp:204
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:77
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:783
llvm::Function
Definition: Function.h:62
Pass.h
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1147
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:151
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:1410
tryToRecognizePopCount
static bool tryToRecognizePopCount(Instruction &I)
Definition: AggressiveInstCombine.cpp:310
llvm::AggressiveInstCombinePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AggressiveInstCombine.cpp:427
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:369
llvm::PatternMatch::m_SpecificBB
specific_bbval m_SpecificBB(BasicBlock *BB)
Match a specific basic block value.
Definition: PatternMatch.h:918
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:2242
BasicAliasAnalysis.h
LegacyPassManager.h
llvm::BitmaskEnumDetail::Mask
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
MaskOps::Root
Value * Root
Definition: AggressiveInstCombine.cpp:203
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:820
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::TruncInstCombine::run
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
Definition: TruncInstCombine.cpp:487
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:115
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:1152
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:701
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:1279
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:453
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:253
false
Definition: StackSlotColoring.cpp:142
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:2228
runImpl
static bool runImpl(Function &F, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
Definition: AggressiveInstCombine.cpp:398
llvm::Instruction
Definition: Instruction.h:45
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:191
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:2249
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
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:257
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1460
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:925
LLVMInitializeAggressiveInstCombiner
void LLVMInitializeAggressiveInstCombiner(LLVMPassRegistryRef R)
Definition: AggressiveInstCombine.cpp:457
PatternMatch.h
expressions
aggressive Combine pattern based expressions
Definition: AggressiveInstCombine.cpp:450
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:220
instcombine
aggressive instcombine
Definition: AggressiveInstCombine.cpp:449
Combine
Hexagon Vector Combine
Definition: HexagonVectorCombine.cpp:1525
matchFunnelShift
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
Definition: InstCombineAndOrXor.cpp:2120
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:465
MaskOps::MaskOps
MaskOps(unsigned BitWidth, bool MatchAnds)
Definition: AggressiveInstCombine.cpp:208
llvm::createAggressiveInstCombinerPass
FunctionPass * createAggressiveInstCombinerPass()
Definition: AggressiveInstCombine.cpp:461
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:176
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1129
I
#define I(x, y, z)
Definition: MD5.cpp:59
AggressiveInstCombine.h
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
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:1020
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
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:885
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
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:116
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:532
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
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.cpp:152
MaskOps
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) nee...
Definition: AggressiveInstCombine.cpp:202
MaskOps::FoundAnd1
bool FoundAnd1
Definition: AggressiveInstCombine.cpp:206
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:161
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:196
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:221
llvm::APInt::getSplat
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition: APInt.cpp:597
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:413
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
foldAnyOrAllBitsSet
static bool foldAnyOrAllBitsSet(Instruction &I)
Match patterns that correspond to "any-bits-set" and "all-bits-set".
Definition: AggressiveInstCombine.cpp:266
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:802
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:1336
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2749
llvm::PHINode
Definition: Instructions.h:2633
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
LLVMAddAggressiveInstCombinerPass
void LLVMAddAggressiveInstCombinerPass(LLVMPassManagerRef PM)
See llvm::createAggressiveInstCombinerPass function.
Definition: AggressiveInstCombine.cpp:465
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5278
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:1141
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:440
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1075
Initialization.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37