Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
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 dead code elimination and basic block merging, along
10
// with a collection of other peephole control flow optimizations.  For example:
11
//
12
//   * Removes basic blocks with no predecessors.
13
//   * Merges a basic block into its predecessor if there is only one and the
14
//     predecessor only has one successor.
15
//   * Eliminates PHI nodes for basic blocks with a single predecessor.
16
//   * Eliminates a basic block that only contains an unconditional branch.
17
//   * Changes invoke instructions to nounwind functions to be calls.
18
//   * Change things like "if (x) if (y)" into "if (x&y)".
19
//   * etc..
20
//
21
//===----------------------------------------------------------------------===//
22
23
#include "llvm/ADT/SmallPtrSet.h"
24
#include "llvm/ADT/SmallVector.h"
25
#include "llvm/ADT/Statistic.h"
26
#include "llvm/Analysis/AssumptionCache.h"
27
#include "llvm/Analysis/CFG.h"
28
#include "llvm/Analysis/GlobalsModRef.h"
29
#include "llvm/Analysis/TargetTransformInfo.h"
30
#include "llvm/Transforms/Utils/Local.h"
31
#include "llvm/IR/Attributes.h"
32
#include "llvm/IR/CFG.h"
33
#include "llvm/IR/Constants.h"
34
#include "llvm/IR/DataLayout.h"
35
#include "llvm/IR/Instructions.h"
36
#include "llvm/IR/IntrinsicInst.h"
37
#include "llvm/IR/Module.h"
38
#include "llvm/Pass.h"
39
#include "llvm/Support/CommandLine.h"
40
#include "llvm/Transforms/Scalar.h"
41
#include "llvm/Transforms/Scalar/SimplifyCFG.h"
42
#include <utility>
43
using namespace llvm;
44
45
#define DEBUG_TYPE "simplifycfg"
46
47
static cl::opt<unsigned> UserBonusInstThreshold(
48
    "bonus-inst-threshold", cl::Hidden, cl::init(1),
49
    cl::desc("Control the number of bonus instructions (default = 1)"));
50
51
static cl::opt<bool> UserKeepLoops(
52
    "keep-loops", cl::Hidden, cl::init(true),
53
    cl::desc("Preserve canonical loop structure (default = true)"));
54
55
static cl::opt<bool> UserSwitchToLookup(
56
    "switch-to-lookup", cl::Hidden, cl::init(false),
57
    cl::desc("Convert switches to lookup tables (default = false)"));
58
59
static cl::opt<bool> UserForwardSwitchCond(
60
    "forward-switch-cond", cl::Hidden, cl::init(false),
61
    cl::desc("Forward switch condition to phi ops (default = false)"));
62
63
static cl::opt<bool> UserSinkCommonInsts(
64
    "sink-common-insts", cl::Hidden, cl::init(false),
65
    cl::desc("Sink common instructions (default = false)"));
66
67
68
STATISTIC(NumSimpl, "Number of blocks simplified");
69
70
/// If we have more than one empty (other than phi node) return blocks,
71
/// merge them together to promote recursive block merging.
72
3.76M
static bool mergeEmptyReturnBlocks(Function &F) {
73
3.76M
  bool Changed = false;
74
3.76M
75
3.76M
  BasicBlock *RetBlock = nullptr;
76
3.76M
77
3.76M
  // Scan all the blocks in the function, looking for empty return blocks.
78
26.7M
  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
79
23.0M
    BasicBlock &BB = *BBI++;
80
23.0M
81
23.0M
    // Only look at return blocks.
82
23.0M
    ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
83
23.0M
    if (!Ret) 
continue19.2M
;
84
3.76M
85
3.76M
    // Only look at the block if it is empty or the only other thing in it is a
86
3.76M
    // single PHI node that is the operand to the return.
87
3.76M
    if (Ret != &BB.front()) {
88
3.08M
      // Check for something else in the block.
89
3.08M
      BasicBlock::iterator I(Ret);
90
3.08M
      --I;
91
3.08M
      // Skip over debug info.
92
3.08M
      while (isa<DbgInfoIntrinsic>(I) && 
I != BB.begin()174
)
93
141
        --I;
94
3.08M
      if (!isa<DbgInfoIntrinsic>(I) &&
95
3.08M
          
(3.08M
!isa<PHINode>(I)3.08M
||
I != BB.begin()460k
||
Ret->getNumOperands() == 0460k
||
96
3.08M
           
Ret->getOperand(0) != &*I458k
))
97
2.62M
        continue;
98
1.13M
    }
99
1.13M
100
1.13M
    // If this is the first returning block, remember it and keep going.
101
1.13M
    if (!RetBlock) {
102
1.13M
      RetBlock = &BB;
103
1.13M
      continue;
104
1.13M
    }
105
451
106
451
    // Otherwise, we found a duplicate return block.  Merge the two.
107
451
    Changed = true;
108
451
109
451
    // Case when there is no input to the return or when the returned values
110
451
    // agree is trivial.  Note that they can't agree if there are phis in the
111
451
    // blocks.
112
451
    if (Ret->getNumOperands() == 0 ||
113
451
        Ret->getOperand(0) ==
114
393
          cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
115
61
      BB.replaceAllUsesWith(RetBlock);
116
61
      BB.eraseFromParent();
117
61
      continue;
118
61
    }
119
390
120
390
    // If the canonical return block has no PHI node, create one now.
121
390
    PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
122
390
    if (!RetBlockPHI) {
123
106
      Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
124
106
      pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
125
106
      RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
126
106
                                    std::distance(PB, PE), "merge",
127
106
                                    &RetBlock->front());
128
106
129
241
      for (pred_iterator PI = PB; PI != PE; 
++PI135
)
130
135
        RetBlockPHI->addIncoming(InVal, *PI);
131
106
      RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
132
106
    }
133
390
134
390
    // Turn BB into a block that just unconditionally branches to the return
135
390
    // block.  This handles the case when the two return blocks have a common
136
390
    // predecessor but that return different things.
137
390
    RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
138
390
    BB.getTerminator()->eraseFromParent();
139
390
    BranchInst::Create(RetBlock, &BB);
140
390
  }
141
3.76M
142
3.76M
  return Changed;
143
3.76M
}
144
145
/// Call SimplifyCFG on all the blocks in the function,
146
/// iterating until no more changes are made.
147
static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
148
3.76M
                                   const SimplifyCFGOptions &Options) {
149
3.76M
  bool Changed = false;
150
3.76M
  bool LocalChange = true;
151
3.76M
152
3.76M
  SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
153
3.76M
  FindFunctionBackedges(F, Edges);
154
3.76M
  SmallPtrSet<BasicBlock *, 16> LoopHeaders;
155
5.51M
  for (unsigned i = 0, e = Edges.size(); i != e; 
++i1.75M
)
156
1.75M
    LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
157
3.76M
158
7.95M
  while (LocalChange) {
159
4.19M
    LocalChange = false;
160
4.19M
161
4.19M
    // Loop over all of the basic blocks and remove them if they are unneeded.
162
37.1M
    for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
163
32.9M
      if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
164
1.71M
        LocalChange = true;
165
1.71M
        ++NumSimpl;
166
1.71M
      }
167
32.9M
    }
168
4.19M
    Changed |= LocalChange;
169
4.19M
  }
170
3.76M
  return Changed;
171
3.76M
}
172
173
static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
174
3.76M
                                const SimplifyCFGOptions &Options) {
175
3.76M
  bool EverChanged = removeUnreachableBlocks(F);
176
3.76M
  EverChanged |= mergeEmptyReturnBlocks(F);
177
3.76M
  EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
178
3.76M
179
3.76M
  // If neither pass changed anything, we're done.
180
3.76M
  if (!EverChanged) 
return false3.35M
;
181
404k
182
404k
  // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
183
404k
  // removeUnreachableBlocks is needed to nuke them, which means we should
184
404k
  // iterate between the two optimizations.  We structure the code like this to
185
404k
  // avoid rerunning iterativelySimplifyCFG if the second pass of
186
404k
  // removeUnreachableBlocks doesn't do anything.
187
404k
  if (!removeUnreachableBlocks(F))
188
404k
    return true;
189
15
190
30
  
do 15
{
191
30
    EverChanged = iterativelySimplifyCFG(F, TTI, Options);
192
30
    EverChanged |= removeUnreachableBlocks(F);
193
30
  } while (EverChanged);
194
15
195
15
  return true;
196
15
}
197
198
// Command-line settings override compile-time settings.
199
1.33k
SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) {
200
1.33k
  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
201
1.33k
                                   ? 
UserBonusInstThreshold0
202
1.33k
                                   : Opts.BonusInstThreshold;
203
1.33k
  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
204
1.33k
                                       ? 
UserForwardSwitchCond0
205
1.33k
                                       : Opts.ForwardSwitchCondToPhi;
206
1.33k
  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
207
1.33k
                                           ? 
UserSwitchToLookup0
208
1.33k
                                           : Opts.ConvertSwitchToLookupTable;
209
1.33k
  Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
210
1.33k
                                  ? 
UserKeepLoops0
211
1.33k
                                  : Opts.NeedCanonicalLoop;
212
1.33k
  Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
213
1.33k
                                ? 
UserSinkCommonInsts0
214
1.33k
                                : Opts.SinkCommonInsts;
215
1.33k
}
216
217
PreservedAnalyses SimplifyCFGPass::run(Function &F,
218
8.93k
                                       FunctionAnalysisManager &AM) {
219
8.93k
  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
220
8.93k
  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
221
8.93k
  if (!simplifyFunctionCFG(F, TTI, Options))
222
8.65k
    return PreservedAnalyses::all();
223
281
  PreservedAnalyses PA;
224
281
  PA.preserve<GlobalsAA>();
225
281
  return PA;
226
281
}
227
228
namespace {
229
struct CFGSimplifyPass : public FunctionPass {
230
  static char ID;
231
  SimplifyCFGOptions Options;
232
  std::function<bool(const Function &)> PredicateFtor;
233
234
  CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
235
                  bool ConvertSwitch = false, bool KeepLoops = true,
236
                  bool SinkCommon = false,
237
                  std::function<bool(const Function &)> Ftor = nullptr)
238
119k
      : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
239
119k
240
119k
    initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
241
119k
242
119k
    // Check for command-line overrides of options for debug/customization.
243
119k
    Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
244
119k
                                    ? 
UserBonusInstThreshold2
245
119k
                                    : 
Threshold119k
;
246
119k
247
119k
    Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
248
119k
                                         ? 
UserForwardSwitchCond2
249
119k
                                         : 
ForwardSwitchCond119k
;
250
119k
251
119k
    Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
252
119k
                                             ? 
UserSwitchToLookup12
253
119k
                                             : 
ConvertSwitch119k
;
254
119k
255
119k
    Options.NeedCanonicalLoop =
256
119k
        UserKeepLoops.getNumOccurrences() ? 
UserKeepLoops16
:
KeepLoops119k
;
257
119k
258
119k
    Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
259
119k
                                  ? 
UserSinkCommonInsts3
260
119k
                                  : 
SinkCommon119k
;
261
119k
  }
262
263
3.75M
  bool runOnFunction(Function &F) override {
264
3.75M
    if (skipFunction(F) || 
(3.75M
PredicateFtor3.75M
&&
!PredicateFtor(F)25.2k
))
265
6.06k
      return false;
266
3.75M
267
3.75M
    Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
268
3.75M
    auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
269
3.75M
    return simplifyFunctionCFG(F, TTI, Options);
270
3.75M
  }
271
119k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
272
119k
    AU.addRequired<AssumptionCacheTracker>();
273
119k
    AU.addRequired<TargetTransformInfoWrapperPass>();
274
119k
    AU.addPreserved<GlobalsAAWrapperPass>();
275
119k
  }
276
};
277
}
278
279
char CFGSimplifyPass::ID = 0;
280
48.9k
INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
281
48.9k
                      false)
282
48.9k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
283
48.9k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
284
48.9k
INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
285
                    false)
286
287
// Public interface to the CFGSimplification pass
288
FunctionPass *
289
llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
290
                                  bool ConvertSwitch, bool KeepLoops,
291
                                  bool SinkCommon,
292
118k
                                  std::function<bool(const Function &)> Ftor) {
293
118k
  return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
294
118k
                             KeepLoops, SinkCommon, std::move(Ftor));
295
118k
}