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