SimplifyCFGPass.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
1//===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
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 dead code elimination and basic block merging, along
11// with a collection of other peephole control flow optimizations.  For example:
12//
13//   * Removes basic blocks with no predecessors.
14//   * Merges a basic block into its predecessor if there is only one and the
15//     predecessor only has one successor.
16//   * Eliminates PHI nodes for basic blocks with a single predecessor.
17//   * Eliminates a basic block that only contains an unconditional branch.
18//   * Changes invoke instructions to nounwind functions to be calls.
19//   * Change things like "if (x) if (y)" into "if (x&y)".
20//   * etc..
21//
22//===----------------------------------------------------------------------===//
23
24#include "llvm/Transforms/Scalar.h"
25#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/ADT/Statistic.h"
28#include "llvm/Analysis/TargetTransformInfo.h"
29#include "llvm/IR/Attributes.h"
30#include "llvm/IR/CFG.h"
31#include "llvm/IR/Constants.h"
32#include "llvm/IR/DataLayout.h"
33#include "llvm/IR/Instructions.h"
34#include "llvm/IR/IntrinsicInst.h"
35#include "llvm/IR/Module.h"
36#include "llvm/Pass.h"
37#include "llvm/Transforms/Utils/Local.h"
38using namespace llvm;
39
40#define DEBUG_TYPE "simplifycfg"
41
42STATISTIC(NumSimpl, "Number of blocks simplified");
43
44namespace {
45struct CFGSimplifyPass : public FunctionPass {
46  static char ID; // Pass identification, replacement for typeid
47  CFGSimplifyPass() : FunctionPass(ID) {
48    initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
49  }
50  bool runOnFunction(Function &F) override;
51
52  void getAnalysisUsage(AnalysisUsage &AU) const override {
53    AU.addRequired<TargetTransformInfo>();
54  }
55};
56}
57
58char CFGSimplifyPass::ID = 0;
59INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
60                      false)
61INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
62INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
63                    false)
64
65// Public interface to the CFGSimplification pass
66FunctionPass *llvm::createCFGSimplificationPass() {
67  return new CFGSimplifyPass();
68}
69
70/// mergeEmptyReturnBlocks - If we have more than one empty (other than phi
71/// node) return blocks, merge them together to promote recursive block merging.
72static bool mergeEmptyReturnBlocks(Function &F) {
73  bool Changed = false;
74
75  BasicBlock *RetBlock = nullptr;
76
77  // Scan all the blocks in the function, looking for empty return blocks.
78  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
79    BasicBlock &BB = *BBI++;
80
81    // Only look at return blocks.
82    ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
83    if (!Ret) continue;
84
85    // Only look at the block if it is empty or the only other thing in it is a
86    // single PHI node that is the operand to the return.
87    if (Ret != &BB.front()) {
88      // Check for something else in the block.
89      BasicBlock::iterator I = Ret;
90      --I;
91      // Skip over debug info.
92      while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
93        --I;
94      if (!isa<DbgInfoIntrinsic>(I) &&
95          (!isa<PHINode>(I) || I != BB.begin() ||
96           Ret->getNumOperands() == 0 ||
97           Ret->getOperand(0) != I))
98        continue;
99    }
100
101    // If this is the first returning block, remember it and keep going.
102    if (!RetBlock) {
103      RetBlock = &BB;
104      continue;
105    }
106
107    // Otherwise, we found a duplicate return block.  Merge the two.
108    Changed = true;
109
110    // Case when there is no input to the return or when the returned values
111    // agree is trivial.  Note that they can't agree if there are phis in the
112    // blocks.
113    if (Ret->getNumOperands() == 0 ||
114        Ret->getOperand(0) ==
115          cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
116      BB.replaceAllUsesWith(RetBlock);
117      BB.eraseFromParent();
118      continue;
119    }
120
121    // If the canonical return block has no PHI node, create one now.
122    PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
123    if (!RetBlockPHI) {
124      Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
125      pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
126      RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
127                                    std::distance(PB, PE), "merge",
128                                    &RetBlock->front());
129
130      for (pred_iterator PI = PB; PI != PE; ++PI)
131        RetBlockPHI->addIncoming(InVal, *PI);
132      RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
133    }
134
135    // Turn BB into a block that just unconditionally branches to the return
136    // block.  This handles the case when the two return blocks have a common
137    // predecessor but that return different things.
138    RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
139    BB.getTerminator()->eraseFromParent();
140    BranchInst::Create(RetBlock, &BB);
141  }
142
143  return Changed;
144}
145
146/// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
147/// iterating until no more changes are made.
148static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
149                                   const DataLayout *DL) {
150  bool Changed = false;
151  bool LocalChange = true;
152  while (LocalChange) {
153    LocalChange = false;
154
155    // Loop over all of the basic blocks and remove them if they are unneeded...
156    //
157    for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
158      if (SimplifyCFG(BBIt++, TTI, DL)) {
159        LocalChange = true;
160        ++NumSimpl;
161      }
162    }
163    Changed |= LocalChange;
164  }
165  return Changed;
166}
167
168// It is possible that we may require multiple passes over the code to fully
169// simplify the CFG.
170//
171bool CFGSimplifyPass::runOnFunction(Function &F) {
172  if (skipOptnoneFunction(F))
173    return false;
174
175  const TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
176  DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
177  const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr;
178  bool EverChanged = removeUnreachableBlocks(F);
179  EverChanged |= mergeEmptyReturnBlocks(F);
180  EverChanged |= iterativelySimplifyCFG(F, TTI, DL);
181
182  // If neither pass changed anything, we're done.
183  if (!EverChanged) return false;
184
185  // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
186  // removeUnreachableBlocks is needed to nuke them, which means we should
187  // iterate between the two optimizations.  We structure the code like this to
188  // avoid reruning iterativelySimplifyCFG if the second pass of
189  // removeUnreachableBlocks doesn't do anything.
190  if (!removeUnreachableBlocks(F))
191    return true;
192
193  do {
194    EverChanged = iterativelySimplifyCFG(F, TTI, DL);
195    EverChanged |= removeUnreachableBlocks(F);
196  } while (EverChanged);
197
198  return true;
199}
200