Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp
Line
Count
Source (jump to first uncovered line)
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
15
#include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
16
#include "AggressiveInstCombineInternal.h"
17
#include "llvm-c/Initialization.h"
18
#include "llvm-c/Transforms/AggressiveInstCombine.h"
19
#include "llvm/Analysis/AliasAnalysis.h"
20
#include "llvm/Analysis/BasicAliasAnalysis.h"
21
#include "llvm/Analysis/GlobalsModRef.h"
22
#include "llvm/Analysis/TargetLibraryInfo.h"
23
#include "llvm/IR/DataLayout.h"
24
#include "llvm/IR/Dominators.h"
25
#include "llvm/IR/IRBuilder.h"
26
#include "llvm/IR/LegacyPassManager.h"
27
#include "llvm/IR/PatternMatch.h"
28
#include "llvm/Pass.h"
29
#include "llvm/Transforms/Utils/Local.h"
30
using namespace llvm;
31
using namespace PatternMatch;
32
33
#define DEBUG_TYPE "aggressive-instcombine"
34
35
namespace {
36
/// Contains expression pattern combiner logic.
37
/// This class provides both the logic to combine expression patterns and
38
/// combine them. It differs from InstCombiner class in that each pattern
39
/// combiner runs only once as opposed to InstCombine's multi-iteration,
40
/// which allows pattern combiner to have higher complexity than the O(1)
41
/// required by the instruction combiner.
42
class AggressiveInstCombinerLegacyPass : public FunctionPass {
43
public:
44
  static char ID; // Pass identification, replacement for typeid
45
46
10.8k
  AggressiveInstCombinerLegacyPass() : FunctionPass(ID) {
47
10.8k
    initializeAggressiveInstCombinerLegacyPassPass(
48
10.8k
        *PassRegistry::getPassRegistry());
49
10.8k
  }
50
51
  void getAnalysisUsage(AnalysisUsage &AU) const override;
52
53
  /// Run all expression pattern optimizations on the given /p F function.
54
  ///
55
  /// \param F function to optimize.
56
  /// \returns true if the IR is changed.
57
  bool runOnFunction(Function &F) override;
58
};
59
} // namespace
60
61
/// Match a pattern for a bitwise rotate operation that partially guards
62
/// against undefined behavior by branching around the rotation when the shift
63
/// amount is 0.
64
14.3M
static bool foldGuardedRotateToFunnelShift(Instruction &I) {
65
14.3M
  if (I.getOpcode() != Instruction::PHI || 
I.getNumOperands() != 2588k
)
66
13.8M
    return false;
67
489k
68
489k
  // As with the one-use checks below, this is not strictly necessary, but we
69
489k
  // are being cautious to avoid potential perf regressions on targets that
70
489k
  // do not actually have a rotate instruction (where the funnel shift would be
71
489k
  // expanded back into math/shift/logic ops).
72
489k
  if (!isPowerOf2_32(I.getType()->getScalarSizeInBits()))
73
161k
    return false;
74
328k
75
328k
  // Match V to funnel shift left/right and capture the source operand and
76
328k
  // shift amount in X and Y.
77
656k
  
auto matchRotate = [](Value *V, Value *&X, Value *&Y) 328k
{
78
656k
    Value *L0, *L1, *R0, *R1;
79
656k
    unsigned Width = V->getType()->getScalarSizeInBits();
80
656k
    auto Sub = m_Sub(m_SpecificInt(Width), m_Value(R1));
81
656k
82
656k
    // rotate_left(X, Y) == (X << Y) | (X >> (Width - Y))
83
656k
    auto RotL = m_OneUse(
84
656k
        m_c_Or(m_Shl(m_Value(L0), m_Value(L1)), m_LShr(m_Value(R0), Sub)));
85
656k
    if (RotL.match(V) && 
L0 == R021
&&
L1 == R15
) {
86
5
      X = L0;
87
5
      Y = L1;
88
5
      return Intrinsic::fshl;
89
5
    }
90
656k
91
656k
    // rotate_right(X, Y) == (X >> Y) | (X << (Width - Y))
92
656k
    auto RotR = m_OneUse(
93
656k
        m_c_Or(m_LShr(m_Value(L0), m_Value(L1)), m_Shl(m_Value(R0), Sub)));
94
656k
    if (RotR.match(V) && 
L0 == R029
&&
L1 == R16
) {
95
6
      X = L0;
96
6
      Y = L1;
97
6
      return Intrinsic::fshr;
98
6
    }
99
656k
100
656k
    return Intrinsic::not_intrinsic;
101
656k
  };
102
328k
103
328k
  // One phi operand must be a rotate operation, and the other phi operand must
104
328k
  // be the source value of that rotate operation:
105
328k
  // phi [ rotate(RotSrc, RotAmt), RotBB ], [ RotSrc, GuardBB ]
106
328k
  PHINode &Phi = cast<PHINode>(I);
107
328k
  Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);
108
328k
  Value *RotSrc, *RotAmt;
109
328k
  Intrinsic::ID IID = matchRotate(P0, RotSrc, RotAmt);
110
328k
  if (IID == Intrinsic::not_intrinsic || 
RotSrc != P14
) {
111
328k
    IID = matchRotate(P1, RotSrc, RotAmt);
112
328k
    if (IID == Intrinsic::not_intrinsic || 
RotSrc != P07
)
113
328k
      return false;
114
5
    assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
115
5
           "Pattern must match funnel shift left or right");
116
5
  }
117
328k
118
328k
  // The incoming block with our source operand must be the "guard" block.
119
328k
  // That must contain a cmp+branch to avoid the rotate when the shift amount
120
328k
  // is equal to 0. The other incoming block is the block with the rotate.
121
328k
  BasicBlock *GuardBB = Phi.getIncomingBlock(RotSrc == P1);
122
7
  BasicBlock *RotBB = Phi.getIncomingBlock(RotSrc != P1);
123
7
  Instruction *TermI = GuardBB->getTerminator();
124
7
  BasicBlock *TrueBB, *FalseBB;
125
7
  ICmpInst::Predicate Pred;
126
7
  if (!match(TermI, m_Br(m_ICmp(Pred, m_Specific(RotAmt), m_ZeroInt()), TrueBB,
127
7
                         FalseBB)))
128
0
    return false;
129
7
130
7
  BasicBlock *PhiBB = Phi.getParent();
131
8
  if (
Pred != CmpInst::ICMP_EQ7
|| TrueBB != PhiBB || FalseBB != RotBB)
132
1
    return false;
133
6
134
6
  // We matched a variation of this IR pattern:
135
6
  // GuardBB:
136
6
  //   %cmp = icmp eq i32 %RotAmt, 0
137
6
  //   br i1 %cmp, label %PhiBB, label %RotBB
138
6
  // RotBB:
139
6
  //   %sub = sub i32 32, %RotAmt
140
6
  //   %shr = lshr i32 %X, %sub
141
6
  //   %shl = shl i32 %X, %RotAmt
142
6
  //   %rot = or i32 %shr, %shl
143
6
  //   br label %PhiBB
144
6
  // PhiBB:
145
6
  //   %cond = phi i32 [ %rot, %RotBB ], [ %X, %GuardBB ]
146
6
  // -->
147
6
  // llvm.fshl.i32(i32 %X, i32 %RotAmt)
148
6
  IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt());
149
6
  Function *F = Intrinsic::getDeclaration(Phi.getModule(), IID, Phi.getType());
150
6
  Phi.replaceAllUsesWith(Builder.CreateCall(F, {RotSrc, RotSrc, RotAmt}));
151
6
  return true;
152
6
}
153
154
/// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
155
/// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
156
/// of 'and' ops, then we also need to capture the fact that we saw an
157
/// "and X, 1", so that's an extra return value for that case.
158
struct MaskOps {
159
  Value *Root;
160
  APInt Mask;
161
  bool MatchAndChain;
162
  bool FoundAnd1;
163
164
  MaskOps(unsigned BitWidth, bool MatchAnds)
165
      : Root(nullptr), Mask(APInt::getNullValue(BitWidth)),
166
3.74k
        MatchAndChain(MatchAnds), FoundAnd1(false) {}
167
};
168
169
/// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
170
/// chain of 'and' or 'or' instructions looking for shift ops of a common source
171
/// value. Examples:
172
///   or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
173
/// returns { X, 0x129 }
174
///   and (and (X >> 1), 1), (X >> 4)
175
/// returns { X, 0x12 }
176
16.8k
static bool matchAndOrChain(Value *V, MaskOps &MOps) {
177
16.8k
  Value *Op0, *Op1;
178
16.8k
  if (MOps.MatchAndChain) {
179
16.7k
    // Recurse through a chain of 'and' operands. This requires an extra check
180
16.7k
    // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
181
16.7k
    // in the chain to know that all of the high bits are cleared.
182
16.7k
    if (match(V, m_And(m_Value(Op0), m_One()))) {
183
59
      MOps.FoundAnd1 = true;
184
59
      return matchAndOrChain(Op0, MOps);
185
59
    }
186
16.7k
    if (match(V, m_And(m_Value(Op0), m_Value(Op1))))
187
8.52k
      return matchAndOrChain(Op0, MOps) && 
matchAndOrChain(Op1, MOps)4.48k
;
188
76
  } else {
189
76
    // Recurse through a chain of 'or' operands.
190
76
    if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))
191
29
      return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
192
8.25k
  }
193
8.25k
194
8.25k
  // We need a shift-right or a bare value representing a compare of bit 0 of
195
8.25k
  // the original source operand.
196
8.25k
  Value *Candidate;
197
8.25k
  uint64_t BitIndex = 0;
198
8.25k
  if (!match(V, m_LShr(m_Value(Candidate), m_ConstantInt(BitIndex))))
199
7.37k
    Candidate = V;
200
8.25k
201
8.25k
  // Initialize result source operand.
202
8.25k
  if (!MOps.Root)
203
3.74k
    MOps.Root = Candidate;
204
8.25k
205
8.25k
  // The shift constant is out-of-range? This code hasn't been simplified.
206
8.25k
  if (BitIndex >= MOps.Mask.getBitWidth())
207
1
    return false;
208
8.25k
209
8.25k
  // Fill in the mask bit derived from the shift constant.
210
8.25k
  MOps.Mask.setBit(BitIndex);
211
8.25k
  return MOps.Root == Candidate;
212
8.25k
}
213
214
/// Match patterns that correspond to "any-bits-set" and "all-bits-set".
215
/// These will include a chain of 'or' or 'and'-shifted bits from a
216
/// common source value:
217
/// and (or  (lshr X, C), ...), 1 --> (X & CMask) != 0
218
/// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
219
/// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
220
/// that differ only with a final 'not' of the result. We expect that final
221
/// 'not' to be folded with the compare that we create here (invert predicate).
222
14.3M
static bool foldAnyOrAllBitsSet(Instruction &I) {
223
14.3M
  // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
224
14.3M
  // final "and X, 1" instruction must be the final op in the sequence.
225
14.3M
  bool MatchAllBitsSet;
226
14.3M
  if (match(&I, m_c_And(m_OneUse(m_And(m_Value(), m_Value())), m_Value())))
227
3.72k
    MatchAllBitsSet = true;
228
14.3M
  else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))
229
18
    MatchAllBitsSet = false;
230
14.3M
  else
231
14.3M
    return false;
232
3.74k
233
3.74k
  MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
234
3.74k
  if (MatchAllBitsSet) {
235
3.72k
    if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || 
!MOps.FoundAnd156
)
236
3.67k
      return false;
237
18
  } else {
238
18
    if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))
239
11
      return false;
240
62
  }
241
62
242
62
  // The pattern was found. Create a masked compare that replaces all of the
243
62
  // shift and logic ops.
244
62
  IRBuilder<> Builder(&I);
245
62
  Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);
246
62
  Value *And = Builder.CreateAnd(MOps.Root, Mask);
247
62
  Value *Cmp = MatchAllBitsSet ? 
Builder.CreateICmpEQ(And, Mask)55
248
62
                               : 
Builder.CreateIsNotNull(And)7
;
249
62
  Value *Zext = Builder.CreateZExt(Cmp, I.getType());
250
62
  I.replaceAllUsesWith(Zext);
251
62
  return true;
252
62
}
253
254
/// This is the entry point for folds that could be implemented in regular
255
/// InstCombine, but they are separated because they are not expected to
256
/// occur frequently and/or have more than a constant-length pattern match.
257
454k
static bool foldUnusualPatterns(Function &F, DominatorTree &DT) {
258
454k
  bool MadeChange = false;
259
2.59M
  for (BasicBlock &BB : F) {
260
2.59M
    // Ignore unreachable basic blocks.
261
2.59M
    if (!DT.isReachableFromEntry(&BB))
262
4
      continue;
263
2.59M
    // Do not delete instructions under here and invalidate the iterator.
264
2.59M
    // Walk the block backwards for efficiency. We're matching a chain of
265
2.59M
    // use->defs, so we're more likely to succeed by starting from the bottom.
266
2.59M
    // Also, we want to avoid matching partial patterns.
267
2.59M
    // TODO: It would be more efficient if we removed dead instructions
268
2.59M
    // iteratively in this loop rather than waiting until the end.
269
14.3M
    
for (Instruction &I : make_range(BB.rbegin(), BB.rend()))2.59M
{
270
14.3M
      MadeChange |= foldAnyOrAllBitsSet(I);
271
14.3M
      MadeChange |= foldGuardedRotateToFunnelShift(I);
272
14.3M
    }
273
2.59M
  }
274
454k
275
454k
  // We're done with transforms, so remove dead instructions.
276
454k
  if (MadeChange)
277
22
    for (BasicBlock &BB : F)
278
38
      SimplifyInstructionsInBlock(&BB);
279
454k
280
454k
  return MadeChange;
281
454k
}
282
283
/// This is the entry point for all transforms. Pass manager differences are
284
/// handled in the callers of this function.
285
454k
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT) {
286
454k
  bool MadeChange = false;
287
454k
  const DataLayout &DL = F.getParent()->getDataLayout();
288
454k
  TruncInstCombine TIC(TLI, DL, DT);
289
454k
  MadeChange |= TIC.run(F);
290
454k
  MadeChange |= foldUnusualPatterns(F, DT);
291
454k
  return MadeChange;
292
454k
}
293
294
void AggressiveInstCombinerLegacyPass::getAnalysisUsage(
295
10.8k
    AnalysisUsage &AU) const {
296
10.8k
  AU.setPreservesCFG();
297
10.8k
  AU.addRequired<DominatorTreeWrapperPass>();
298
10.8k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
299
10.8k
  AU.addPreserved<AAResultsWrapperPass>();
300
10.8k
  AU.addPreserved<BasicAAWrapperPass>();
301
10.8k
  AU.addPreserved<DominatorTreeWrapperPass>();
302
10.8k
  AU.addPreserved<GlobalsAAWrapperPass>();
303
10.8k
}
304
305
454k
bool AggressiveInstCombinerLegacyPass::runOnFunction(Function &F) {
306
454k
  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
307
454k
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
308
454k
  return runImpl(F, TLI, DT);
309
454k
}
310
311
PreservedAnalyses AggressiveInstCombinePass::run(Function &F,
312
69
                                                 FunctionAnalysisManager &AM) {
313
69
  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
314
69
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
315
69
  if (!runImpl(F, TLI, DT)) {
316
45
    // No changes, all analyses are preserved.
317
45
    return PreservedAnalyses::all();
318
45
  }
319
24
  // Mark all the analyses that instcombine updates as preserved.
320
24
  PreservedAnalyses PA;
321
24
  PA.preserveSet<CFGAnalyses>();
322
24
  PA.preserve<AAManager>();
323
24
  PA.preserve<GlobalsAA>();
324
24
  return PA;
325
24
}
326
327
char AggressiveInstCombinerLegacyPass::ID = 0;
328
21.7k
INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass,
329
21.7k
                      "aggressive-instcombine",
330
21.7k
                      "Combine pattern based expressions", false, false)
331
21.7k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
332
21.7k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
333
21.7k
INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass, "aggressive-instcombine",
334
                    "Combine pattern based expressions", false, false)
335
336
// Initialization Routines
337
11.0k
void llvm::initializeAggressiveInstCombine(PassRegistry &Registry) {
338
11.0k
  initializeAggressiveInstCombinerLegacyPassPass(Registry);
339
11.0k
}
340
341
0
void LLVMInitializeAggressiveInstCombiner(LLVMPassRegistryRef R) {
342
0
  initializeAggressiveInstCombinerLegacyPassPass(*unwrap(R));
343
0
}
344
345
10.8k
FunctionPass *llvm::createAggressiveInstCombinerPass() {
346
10.8k
  return new AggressiveInstCombinerLegacyPass();
347
10.8k
}
348
349
0
void LLVMAddAggressiveInstCombinerPass(LLVMPassManagerRef PM) {
350
0
  unwrap(PM)->add(createAggressiveInstCombinerPass());
351
0
}