LLVM  8.0.0svn
AggressiveInstCombine.cpp
Go to the documentation of this file.
1 //===- AggressiveInstCombine.cpp ------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the aggressive expression pattern combiner classes.
11 // Currently, it handles expression patterns for:
12 // * Truncate instruction
13 //
14 //===----------------------------------------------------------------------===//
15 
18 #include "llvm-c/Initialization.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/Pass.h"
31 using namespace llvm;
32 using namespace PatternMatch;
33 
34 #define DEBUG_TYPE "aggressive-instcombine"
35 
36 namespace {
37 /// Contains expression pattern combiner logic.
38 /// This class provides both the logic to combine expression patterns and
39 /// combine them. It differs from InstCombiner class in that each pattern
40 /// combiner runs only once as opposed to InstCombine's multi-iteration,
41 /// which allows pattern combiner to have higher complexity than the O(1)
42 /// required by the instruction combiner.
43 class AggressiveInstCombinerLegacyPass : public FunctionPass {
44 public:
45  static char ID; // Pass identification, replacement for typeid
46 
47  AggressiveInstCombinerLegacyPass() : FunctionPass(ID) {
50  }
51 
52  void getAnalysisUsage(AnalysisUsage &AU) const override;
53 
54  /// Run all expression pattern optimizations on the given /p F function.
55  ///
56  /// \param F function to optimize.
57  /// \returns true if the IR is changed.
58  bool runOnFunction(Function &F) override;
59 };
60 } // namespace
61 
62 /// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
63 /// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
64 /// of 'and' ops, then we also need to capture the fact that we saw an
65 /// "and X, 1", so that's an extra return value for that case.
66 struct MaskOps {
70  bool FoundAnd1;
71 
72  MaskOps(unsigned BitWidth, bool MatchAnds) :
73  Root(nullptr), Mask(APInt::getNullValue(BitWidth)),
74  MatchAndChain(MatchAnds), FoundAnd1(false) {}
75 };
76 
77 /// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
78 /// chain of 'and' or 'or' instructions looking for shift ops of a common source
79 /// value. Examples:
80 /// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
81 /// returns { X, 0x129 }
82 /// and (and (X >> 1), 1), (X >> 4)
83 /// returns { X, 0x12 }
84 static bool matchAndOrChain(Value *V, MaskOps &MOps) {
85  Value *Op0, *Op1;
86  if (MOps.MatchAndChain) {
87  // Recurse through a chain of 'and' operands. This requires an extra check
88  // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
89  // in the chain to know that all of the high bits are cleared.
90  if (match(V, m_And(m_Value(Op0), m_One()))) {
91  MOps.FoundAnd1 = true;
92  return matchAndOrChain(Op0, MOps);
93  }
94  if (match(V, m_And(m_Value(Op0), m_Value(Op1))))
95  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
96  } else {
97  // Recurse through a chain of 'or' operands.
98  if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))
99  return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
100  }
101 
102  // We need a shift-right or a bare value representing a compare of bit 0 of
103  // the original source operand.
104  Value *Candidate;
105  uint64_t BitIndex = 0;
106  if (!match(V, m_LShr(m_Value(Candidate), m_ConstantInt(BitIndex))))
107  Candidate = V;
108 
109  // Initialize result source operand.
110  if (!MOps.Root)
111  MOps.Root = Candidate;
112 
113  // The shift constant is out-of-range? This code hasn't been simplified.
114  if (BitIndex >= MOps.Mask.getBitWidth())
115  return false;
116 
117  // Fill in the mask bit derived from the shift constant.
118  MOps.Mask.setBit(BitIndex);
119  return MOps.Root == Candidate;
120 }
121 
122 /// Match patterns that correspond to "any-bits-set" and "all-bits-set".
123 /// These will include a chain of 'or' or 'and'-shifted bits from a
124 /// common source value:
125 /// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0
126 /// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
127 /// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
128 /// that differ only with a final 'not' of the result. We expect that final
129 /// 'not' to be folded with the compare that we create here (invert predicate).
131  // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
132  // final "and X, 1" instruction must be the final op in the sequence.
133  bool MatchAllBitsSet;
134  if (match(&I, m_c_And(m_OneUse(m_And(m_Value(), m_Value())), m_Value())))
135  MatchAllBitsSet = true;
136  else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))
137  MatchAllBitsSet = false;
138  else
139  return false;
140 
141  MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
142  if (MatchAllBitsSet) {
143  if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || !MOps.FoundAnd1)
144  return false;
145  } else {
146  if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))
147  return false;
148  }
149 
150  // The pattern was found. Create a masked compare that replaces all of the
151  // shift and logic ops.
152  IRBuilder<> Builder(&I);
153  Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);
154  Value *And = Builder.CreateAnd(MOps.Root, Mask);
155  Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(And, Mask) :
156  Builder.CreateIsNotNull(And);
157  Value *Zext = Builder.CreateZExt(Cmp, I.getType());
158  I.replaceAllUsesWith(Zext);
159  return true;
160 }
161 
162 /// This is the entry point for folds that could be implemented in regular
163 /// InstCombine, but they are separated because they are not expected to
164 /// occur frequently and/or have more than a constant-length pattern match.
166  bool MadeChange = false;
167  for (BasicBlock &BB : F) {
168  // Ignore unreachable basic blocks.
169  if (!DT.isReachableFromEntry(&BB))
170  continue;
171  // Do not delete instructions under here and invalidate the iterator.
172  // Walk the block backwards for efficiency. We're matching a chain of
173  // use->defs, so we're more likely to succeed by starting from the bottom.
174  // Also, we want to avoid matching partial patterns.
175  // TODO: It would be more efficient if we removed dead instructions
176  // iteratively in this loop rather than waiting until the end.
177  for (Instruction &I : make_range(BB.rbegin(), BB.rend()))
178  MadeChange |= foldAnyOrAllBitsSet(I);
179  }
180 
181  // We're done with transforms, so remove dead instructions.
182  if (MadeChange)
183  for (BasicBlock &BB : F)
185 
186  return MadeChange;
187 }
188 
189 /// This is the entry point for all transforms. Pass manager differences are
190 /// handled in the callers of this function.
192  bool MadeChange = false;
193  const DataLayout &DL = F.getParent()->getDataLayout();
194  TruncInstCombine TIC(TLI, DL, DT);
195  MadeChange |= TIC.run(F);
196  MadeChange |= foldUnusualPatterns(F, DT);
197  return MadeChange;
198 }
199 
200 void AggressiveInstCombinerLegacyPass::getAnalysisUsage(
201  AnalysisUsage &AU) const {
202  AU.setPreservesCFG();
209 }
210 
212  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
213  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
214  return runImpl(F, TLI, DT);
215 }
216 
219  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
220  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
221  if (!runImpl(F, TLI, DT)) {
222  // No changes, all analyses are preserved.
223  return PreservedAnalyses::all();
224  }
225  // Mark all the analyses that instcombine updates as preserved.
227  PA.preserveSet<CFGAnalyses>();
228  PA.preserve<AAManager>();
229  PA.preserve<GlobalsAA>();
230  return PA;
231 }
232 
234 INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass,
235  "aggressive-instcombine",
236  "Combine pattern based expressions", false, false)
239 INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass, "aggressive-instcombine",
240  "Combine pattern based expressions", false, false)
241 
242 // Initialization Routines
245 }
246 
249 }
250 
252  return new AggressiveInstCombinerLegacyPass();
253 }
254 
257 }
Legacy wrapper pass to provide the GlobalsAAResult object.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:746
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is not null.
Definition: IRBuilder.h:2008
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:45
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
struct LLVMOpaquePassRegistry * LLVMPassRegistryRef
Definition: Types.h:131
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:581
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:300
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1503
static bool matchAndOrChain(Value *V, MaskOps &MOps)
This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of &#39;and&#39; or &#39;or&#39; inst...
aggressive Combine pattern based expressions
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
void setBit(unsigned BitPosition)
Set a given bit to 1.
Definition: APInt.h:1397
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
Attribute unwrap(LLVMAttributeRef Attr)
Definition: Attributes.h:195
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) nee...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
FunctionPass * createAggressiveInstCombinerPass()
void LLVMAddAggressiveInstCombinerPass(LLVMPassManagerRef PM)
See llvm::createAggressiveInstCombinerPass function.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void LLVMInitializeAggressiveInstCombiner(LLVMPassRegistryRef R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1568
static bool foldAnyOrAllBitsSet(Instruction &I)
Match patterns that correspond to "any-bits-set" and "all-bits-set".
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
aggressive instcombine
INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass, "aggressive-instcombine", "Combine pattern based expressions", false, false) INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
static bool runOnFunction(Function &F, bool PostInlining)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:770
static bool foldUnusualPatterns(Function &F, DominatorTree &DT)
This is the entry point for folds that could be implemented in regular InstCombine, but they are separated because they are not expected to occur frequently and/or have more than a constant-length pattern match.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:752
This is an important base class in LLVM.
Definition: Constant.h:42
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
A manager for alias analyses.
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1748
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
void initializeAggressiveInstCombine(PassRegistry &)
Initialize all passes linked into the AggressiveInstCombine library.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
This file provides the primary interface to the aggressive instcombine pass.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
Provides information about what library functions are available for the current target.
void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry &)
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
struct LLVMOpaquePassManager * LLVMPassManagerRef
Definition: Types.h:128
Class for arbitrary precision integers.
Definition: APInt.h:70
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
MaskOps(unsigned BitWidth, bool MatchAnds)
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
#define I(x, y, z)
Definition: MD5.cpp:58
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1124
Analysis pass providing the TargetLibraryInfo.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
LLVM Value Representation.
Definition: Value.h:73
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:352
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
Legacy wrapper pass to provide the BasicAAResult object.