Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/IndirectBrExpandPass.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- IndirectBrExpandPass.cpp - Expand indirectbr to switch -------------===//
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
/// \file
9
///
10
/// Implements an expansion pass to turn `indirectbr` instructions in the IR
11
/// into `switch` instructions. This works by enumerating the basic blocks in
12
/// a dense range of integers, replacing each `blockaddr` constant with the
13
/// corresponding integer constant, and then building a switch that maps from
14
/// the integers to the actual blocks. All of the indirectbr instructions in the
15
/// function are redirected to this common switch.
16
///
17
/// While this is generically useful if a target is unable to codegen
18
/// `indirectbr` natively, it is primarily useful when there is some desire to
19
/// get the builtin non-jump-table lowering of a switch even when the input
20
/// source contained an explicit indirect branch construct.
21
///
22
/// Note that it doesn't make any sense to enable this pass unless a target also
23
/// disables jump-table lowering of switches. Doing that is likely to pessimize
24
/// the code.
25
///
26
//===----------------------------------------------------------------------===//
27
28
#include "llvm/ADT/STLExtras.h"
29
#include "llvm/ADT/Sequence.h"
30
#include "llvm/ADT/SmallVector.h"
31
#include "llvm/CodeGen/TargetPassConfig.h"
32
#include "llvm/CodeGen/TargetSubtargetInfo.h"
33
#include "llvm/IR/BasicBlock.h"
34
#include "llvm/IR/Function.h"
35
#include "llvm/IR/IRBuilder.h"
36
#include "llvm/IR/InstIterator.h"
37
#include "llvm/IR/Instruction.h"
38
#include "llvm/IR/Instructions.h"
39
#include "llvm/Pass.h"
40
#include "llvm/Support/Debug.h"
41
#include "llvm/Support/ErrorHandling.h"
42
#include "llvm/Support/raw_ostream.h"
43
#include "llvm/Target/TargetMachine.h"
44
45
using namespace llvm;
46
47
#define DEBUG_TYPE "indirectbr-expand"
48
49
namespace {
50
51
class IndirectBrExpandPass : public FunctionPass {
52
  const TargetLowering *TLI = nullptr;
53
54
public:
55
  static char ID; // Pass identification, replacement for typeid
56
57
12.6k
  IndirectBrExpandPass() : FunctionPass(ID) {
58
12.6k
    initializeIndirectBrExpandPassPass(*PassRegistry::getPassRegistry());
59
12.6k
  }
60
61
  bool runOnFunction(Function &F) override;
62
};
63
64
} // end anonymous namespace
65
66
char IndirectBrExpandPass::ID = 0;
67
68
INITIALIZE_PASS(IndirectBrExpandPass, DEBUG_TYPE,
69
                "Expand indirectbr instructions", false, false)
70
71
12.6k
FunctionPass *llvm::createIndirectBrExpandPass() {
72
12.6k
  return new IndirectBrExpandPass();
73
12.6k
}
74
75
142k
bool IndirectBrExpandPass::runOnFunction(Function &F) {
76
142k
  auto &DL = F.getParent()->getDataLayout();
77
142k
  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
78
142k
  if (!TPC)
79
0
    return false;
80
142k
81
142k
  auto &TM = TPC->getTM<TargetMachine>();
82
142k
  auto &STI = *TM.getSubtargetImpl(F);
83
142k
  if (!STI.enableIndirectBrExpand())
84
137k
    return false;
85
4.51k
  TLI = STI.getTargetLowering();
86
4.51k
87
4.51k
  SmallVector<IndirectBrInst *, 1> IndirectBrs;
88
4.51k
89
4.51k
  // Set of all potential successors for indirectbr instructions.
90
4.51k
  SmallPtrSet<BasicBlock *, 4> IndirectBrSuccs;
91
4.51k
92
4.51k
  // Build a list of indirectbrs that we want to rewrite.
93
4.51k
  for (BasicBlock &BB : F)
94
5.32k
    if (auto *IBr = dyn_cast<IndirectBrInst>(BB.getTerminator())) {
95
14
      // Handle the degenerate case of no successors by replacing the indirectbr
96
14
      // with unreachable as there is no successor available.
97
14
      if (IBr->getNumSuccessors() == 0) {
98
0
        (void)new UnreachableInst(F.getContext(), IBr);
99
0
        IBr->eraseFromParent();
100
0
        continue;
101
0
      }
102
14
103
14
      IndirectBrs.push_back(IBr);
104
14
      for (BasicBlock *SuccBB : IBr->successors())
105
64
        IndirectBrSuccs.insert(SuccBB);
106
14
    }
107
4.51k
108
4.51k
  if (IndirectBrs.empty())
109
4.50k
    return false;
110
5
111
5
  // If we need to replace any indirectbrs we need to establish integer
112
5
  // constants that will correspond to each of the basic blocks in the function
113
5
  // whose address escapes. We do that here and rewrite all the blockaddress
114
5
  // constants to just be those integer constants cast to a pointer type.
115
5
  SmallVector<BasicBlock *, 4> BBs;
116
5
117
73
  for (BasicBlock &BB : F) {
118
73
    // Skip blocks that aren't successors to an indirectbr we're going to
119
73
    // rewrite.
120
73
    if (!IndirectBrSuccs.count(&BB))
121
19
      continue;
122
54
123
114
    
auto IsBlockAddressUse = [&](const Use &U) 54
{
124
114
      return isa<BlockAddress>(U.getUser());
125
114
    };
126
54
    auto BlockAddressUseIt = llvm::find_if(BB.uses(), IsBlockAddressUse);
127
54
    if (BlockAddressUseIt == BB.use_end())
128
4
      continue;
129
50
130
50
    assert(std::find_if(std::next(BlockAddressUseIt), BB.use_end(),
131
50
                        IsBlockAddressUse) == BB.use_end() &&
132
50
           "There should only ever be a single blockaddress use because it is "
133
50
           "a constant and should be uniqued.");
134
50
135
50
    auto *BA = cast<BlockAddress>(BlockAddressUseIt->getUser());
136
50
137
50
    // Skip if the constant was formed but ended up not being used (due to DCE
138
50
    // or whatever).
139
50
    if (!BA->isConstantUsed())
140
0
      continue;
141
50
142
50
    // Compute the index we want to use for this basic block. We can't use zero
143
50
    // because null can be compared with block addresses.
144
50
    int BBIndex = BBs.size() + 1;
145
50
    BBs.push_back(&BB);
146
50
147
50
    auto *ITy = cast<IntegerType>(DL.getIntPtrType(BA->getType()));
148
50
    ConstantInt *BBIndexC = ConstantInt::get(ITy, BBIndex);
149
50
150
50
    // Now rewrite the blockaddress to an integer constant based on the index.
151
50
    // FIXME: This part doesn't properly recognize other uses of blockaddress
152
50
    // expressions, for instance, where they are used to pass labels to
153
50
    // asm-goto. This part of the pass needs a rework.
154
50
    BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(BBIndexC, BA->getType()));
155
50
  }
156
5
157
5
  if (BBs.empty()) {
158
1
    // There are no blocks whose address is taken, so any indirectbr instruction
159
1
    // cannot get a valid input and we can replace all of them with unreachable.
160
1
    for (auto *IBr : IndirectBrs) {
161
1
      (void)new UnreachableInst(F.getContext(), IBr);
162
1
      IBr->eraseFromParent();
163
1
    }
164
1
    return true;
165
1
  }
166
4
167
4
  BasicBlock *SwitchBB;
168
4
  Value *SwitchValue;
169
4
170
4
  // Compute a common integer type across all the indirectbr instructions.
171
4
  IntegerType *CommonITy = nullptr;
172
13
  for (auto *IBr : IndirectBrs) {
173
13
    auto *ITy =
174
13
        cast<IntegerType>(DL.getIntPtrType(IBr->getAddress()->getType()));
175
13
    if (!CommonITy || 
ITy->getBitWidth() > CommonITy->getBitWidth()6
)
176
7
      CommonITy = ITy;
177
13
  }
178
4
179
13
  auto GetSwitchValue = [DL, CommonITy](IndirectBrInst *IBr) {
180
13
    return CastInst::CreatePointerCast(
181
13
        IBr->getAddress(), CommonITy,
182
13
        Twine(IBr->getAddress()->getName()) + ".switch_cast", IBr);
183
13
  };
184
4
185
4
  if (IndirectBrs.size() == 1) {
186
1
    // If we only have one indirectbr, we can just directly replace it within
187
1
    // its block.
188
1
    SwitchBB = IndirectBrs[0]->getParent();
189
1
    SwitchValue = GetSwitchValue(IndirectBrs[0]);
190
1
    IndirectBrs[0]->eraseFromParent();
191
3
  } else {
192
3
    // Otherwise we need to create a new block to hold the switch across BBs,
193
3
    // jump to that block instead of each indirectbr, and phi together the
194
3
    // values for the switch.
195
3
    SwitchBB = BasicBlock::Create(F.getContext(), "switch_bb", &F);
196
3
    auto *SwitchPN = PHINode::Create(CommonITy, IndirectBrs.size(),
197
3
                                     "switch_value_phi", SwitchBB);
198
3
    SwitchValue = SwitchPN;
199
3
200
3
    // Now replace the indirectbr instructions with direct branches to the
201
3
    // switch block and fill out the PHI operands.
202
12
    for (auto *IBr : IndirectBrs) {
203
12
      SwitchPN->addIncoming(GetSwitchValue(IBr), IBr->getParent());
204
12
      BranchInst::Create(SwitchBB, IBr);
205
12
      IBr->eraseFromParent();
206
12
    }
207
3
  }
208
4
209
4
  // Now build the switch in the block. The block will have no terminator
210
4
  // already.
211
4
  auto *SI = SwitchInst::Create(SwitchValue, BBs[0], BBs.size(), SwitchBB);
212
4
213
4
  // Add a case for each block.
214
4
  for (int i : llvm::seq<int>(1, BBs.size()))
215
43
    SI->addCase(ConstantInt::get(CommonITy, i + 1), BBs[i]);
216
4
217
4
  return true;
218
4
}