Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CallSiteSplitting.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 a transformation that tries to split a call-site to pass
10
// more constrained arguments if its argument is predicated in the control flow
11
// so that we can expose better context to the later passes (e.g, inliner, jump
12
// threading, or IPA-CP based function cloning, etc.).
13
// As of now we support two cases :
14
//
15
// 1) Try to a split call-site with constrained arguments, if any constraints
16
// on any argument can be found by following the single predecessors of the
17
// all site's predecessors. Currently this pass only handles call-sites with 2
18
// predecessors. For example, in the code below, we try to split the call-site
19
// since we can predicate the argument(ptr) based on the OR condition.
20
//
21
// Split from :
22
//   if (!ptr || c)
23
//     callee(ptr);
24
// to :
25
//   if (!ptr)
26
//     callee(null)         // set the known constant value
27
//   else if (c)
28
//     callee(nonnull ptr)  // set non-null attribute in the argument
29
//
30
// 2) We can also split a call-site based on constant incoming values of a PHI
31
// For example,
32
// from :
33
//   Header:
34
//    %c = icmp eq i32 %i1, %i2
35
//    br i1 %c, label %Tail, label %TBB
36
//   TBB:
37
//    br label Tail%
38
//   Tail:
39
//    %p = phi i32 [ 0, %Header], [ 1, %TBB]
40
//    call void @bar(i32 %p)
41
// to
42
//   Header:
43
//    %c = icmp eq i32 %i1, %i2
44
//    br i1 %c, label %Tail-split0, label %TBB
45
//   TBB:
46
//    br label %Tail-split1
47
//   Tail-split0:
48
//    call void @bar(i32 0)
49
//    br label %Tail
50
//   Tail-split1:
51
//    call void @bar(i32 1)
52
//    br label %Tail
53
//   Tail:
54
//    %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ]
55
//
56
//===----------------------------------------------------------------------===//
57
58
#include "llvm/Transforms/Scalar/CallSiteSplitting.h"
59
#include "llvm/ADT/Statistic.h"
60
#include "llvm/Analysis/TargetLibraryInfo.h"
61
#include "llvm/Analysis/TargetTransformInfo.h"
62
#include "llvm/Transforms/Utils/Local.h"
63
#include "llvm/IR/IntrinsicInst.h"
64
#include "llvm/IR/PatternMatch.h"
65
#include "llvm/Support/Debug.h"
66
#include "llvm/Transforms/Scalar.h"
67
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
68
#include "llvm/Transforms/Utils/Cloning.h"
69
70
using namespace llvm;
71
using namespace PatternMatch;
72
73
#define DEBUG_TYPE "callsite-splitting"
74
75
STATISTIC(NumCallSiteSplit, "Number of call-site split");
76
77
/// Only allow instructions before a call, if their CodeSize cost is below
78
/// DuplicationThreshold. Those instructions need to be duplicated in all
79
/// split blocks.
80
static cl::opt<unsigned>
81
    DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,
82
                         cl::desc("Only allow instructions before a call, if "
83
                                  "their cost is below DuplicationThreshold"),
84
                         cl::init(5));
85
86
110
static void addNonNullAttribute(CallSite CS, Value *Op) {
87
110
  unsigned ArgNo = 0;
88
263
  for (auto &I : CS.args()) {
89
263
    if (&*I == Op)
90
113
      CS.addParamAttr(ArgNo, Attribute::NonNull);
91
263
    ++ArgNo;
92
263
  }
93
110
}
94
95
static void setConstantInArgument(CallSite CS, Value *Op,
96
254
                                  Constant *ConstValue) {
97
254
  unsigned ArgNo = 0;
98
688
  for (auto &I : CS.args()) {
99
688
    if (&*I == Op) {
100
257
      // It is possible we have already added the non-null attribute to the
101
257
      // parameter by using an earlier constraining condition.
102
257
      CS.removeParamAttr(ArgNo, Attribute::NonNull);
103
257
      CS.setArgument(ArgNo, ConstValue);
104
257
    }
105
688
    ++ArgNo;
106
688
  }
107
254
}
108
109
84.4k
static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallSite CS) {
110
84.4k
  assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");
111
84.4k
  Value *Op0 = Cmp->getOperand(0);
112
84.4k
  unsigned ArgNo = 0;
113
237k
  for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E;
114
153k
       
++I, ++ArgNo152k
) {
115
153k
    // Don't consider constant or arguments that are already known non-null.
116
153k
    if (isa<Constant>(*I) || 
CS.paramHasAttr(ArgNo, Attribute::NonNull)122k
)
117
60.4k
      continue;
118
92.9k
119
92.9k
    if (*I == Op0)
120
477
      return true;
121
92.9k
  }
122
84.4k
  
return false83.9k
;
123
84.4k
}
124
125
typedef std::pair<ICmpInst *, unsigned> ConditionTy;
126
typedef SmallVector<ConditionTy, 2> ConditionsTy;
127
128
/// If From has a conditional jump to To, add the condition to Conditions,
129
/// if it is relevant to any argument at CS.
130
static void recordCondition(CallSite CS, BasicBlock *From, BasicBlock *To,
131
345k
                            ConditionsTy &Conditions) {
132
345k
  auto *BI = dyn_cast<BranchInst>(From->getTerminator());
133
345k
  if (!BI || 
!BI->isConditional()339k
)
134
96.0k
    return;
135
249k
136
249k
  CmpInst::Predicate Pred;
137
249k
  Value *Cond = BI->getCondition();
138
249k
  if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant())))
139
106k
    return;
140
142k
141
142k
  ICmpInst *Cmp = cast<ICmpInst>(Cond);
142
142k
  if (Pred == ICmpInst::ICMP_EQ || 
Pred == ICmpInst::ICMP_NE72.7k
)
143
84.4k
    if (isCondRelevantToAnyCallArgument(Cmp, CS))
144
477
      Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To
145
477
                                     ? 
Pred251
146
477
                                     : 
Cmp->getInversePredicate()226
});
147
142k
}
148
149
/// Record ICmp conditions relevant to any argument in CS following Pred's
150
/// single predecessors. If there are conflicting conditions along a path, like
151
/// x == 1 and x == 0, the first condition will be used. We stop once we reach
152
/// an edge to StopAt.
153
static void recordConditions(CallSite CS, BasicBlock *Pred,
154
263k
                             ConditionsTy &Conditions, BasicBlock *StopAt) {
155
263k
  BasicBlock *From = Pred;
156
263k
  BasicBlock *To = Pred;
157
263k
  SmallPtrSet<BasicBlock *, 4> Visited;
158
345k
  while (To != StopAt && 
!Visited.count(From->getSinglePredecessor())164k
&&
159
345k
         
(From = From->getSinglePredecessor())164k
) {
160
81.5k
    recordCondition(CS, From, To, Conditions);
161
81.5k
    Visited.insert(From);
162
81.5k
    To = From;
163
81.5k
  }
164
263k
}
165
166
528
static void addConditions(CallSite CS, const ConditionsTy &Conditions) {
167
528
  for (auto &Cond : Conditions) {
168
477
    Value *Arg = Cond.first->getOperand(0);
169
477
    Constant *ConstVal = cast<Constant>(Cond.first->getOperand(1));
170
477
    if (Cond.second == ICmpInst::ICMP_EQ)
171
254
      setConstantInArgument(CS, Arg, ConstVal);
172
223
    else if (ConstVal->getType()->isPointerTy() && 
ConstVal->isNullValue()115
) {
173
110
      assert(Cond.second == ICmpInst::ICMP_NE);
174
110
      addNonNullAttribute(CS, Arg);
175
110
    }
176
477
  }
177
528
}
178
179
132k
static SmallVector<BasicBlock *, 2> getTwoPredecessors(BasicBlock *BB) {
180
132k
  SmallVector<BasicBlock *, 2> Preds(predecessors((BB)));
181
132k
  assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
182
132k
  return Preds;
183
132k
}
184
185
1.19M
static bool canSplitCallSite(CallSite CS, TargetTransformInfo &TTI) {
186
1.19M
  if (CS.isConvergent() || 
CS.cannotDuplicate()1.19M
)
187
3
    return false;
188
1.19M
189
1.19M
  // FIXME: As of now we handle only CallInst. InvokeInst could be handled
190
1.19M
  // without too much effort.
191
1.19M
  Instruction *Instr = CS.getInstruction();
192
1.19M
  if (!isa<CallInst>(Instr))
193
0
    return false;
194
1.19M
195
1.19M
  BasicBlock *CallSiteBB = Instr->getParent();
196
1.19M
  // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
197
1.19M
  SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
198
1.19M
  if (Preds.size() != 2 || 
isa<IndirectBrInst>(Preds[0]->getTerminator())193k
||
199
1.19M
      
isa<IndirectBrInst>(Preds[1]->getTerminator())193k
)
200
998k
    return false;
201
193k
202
193k
  // BasicBlock::canSplitPredecessors is more aggressive, so checking for
203
193k
  // BasicBlock::isEHPad as well.
204
193k
  if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())
205
898
    return false;
206
192k
207
192k
  // Allow splitting a call-site only when the CodeSize cost of the
208
192k
  // instructions before the call is less then DuplicationThreshold. The
209
192k
  // instructions before the call will be duplicated in the split blocks and
210
192k
  // corresponding uses will be updated.
211
192k
  unsigned Cost = 0;
212
192k
  for (auto &InstBeforeCall :
213
565k
       llvm::make_range(CallSiteBB->begin(), Instr->getIterator())) {
214
565k
    Cost += TTI.getInstructionCost(&InstBeforeCall,
215
565k
                                   TargetTransformInfo::TCK_CodeSize);
216
565k
    if (Cost >= DuplicationThreshold)
217
60.1k
      return false;
218
565k
  }
219
192k
220
192k
  
return true132k
;
221
192k
}
222
223
static Instruction *cloneInstForMustTail(Instruction *I, Instruction *Before,
224
10
                                         Value *V) {
225
10
  Instruction *Copy = I->clone();
226
10
  Copy->setName(I->getName());
227
10
  Copy->insertBefore(Before);
228
10
  if (V)
229
8
    Copy->setOperand(0, V);
230
10
  return Copy;
231
10
}
232
233
/// Copy mandatory `musttail` return sequence that follows original `CI`, and
234
/// link it up to `NewCI` value instead:
235
///
236
///   * (optional) `bitcast NewCI to ...`
237
///   * `ret bitcast or NewCI`
238
///
239
/// Insert this sequence right before `SplitBB`'s terminator, which will be
240
/// cleaned up later in `splitCallSite` below.
241
static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
242
8
                               Instruction *NewCI) {
243
8
  bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();
244
8
  auto II = std::next(CI->getIterator());
245
8
246
8
  BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);
247
8
  if (BCI)
248
2
    ++II;
249
8
250
8
  ReturnInst* RI = dyn_cast<ReturnInst>(&*II);
251
8
  assert(RI && "`musttail` call must be followed by `ret` instruction");
252
8
253
8
  Instruction *TI = SplitBB->getTerminator();
254
8
  Value *V = NewCI;
255
8
  if (BCI)
256
2
    V = cloneInstForMustTail(BCI, TI, V);
257
8
  cloneInstForMustTail(RI, TI, IsVoid ? 
nullptr2
:
V6
);
258
8
259
8
  // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug
260
8
  // that prevents doing this now.
261
8
}
262
263
/// For each (predecessor, conditions from predecessors) pair, it will split the
264
/// basic block containing the call site, hook it up to the predecessor and
265
/// replace the call instruction with new call instructions, which contain
266
/// constraints based on the conditions from their predecessors.
267
/// For example, in the IR below with an OR condition, the call-site can
268
/// be split. In this case, Preds for Tail is [(Header, a == null),
269
/// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
270
/// CallInst1, which has constraints based on the conditions from Head and
271
/// CallInst2, which has constraints based on the conditions coming from TBB.
272
///
273
/// From :
274
///
275
///   Header:
276
///     %c = icmp eq i32* %a, null
277
///     br i1 %c %Tail, %TBB
278
///   TBB:
279
///     %c2 = icmp eq i32* %b, null
280
///     br i1 %c %Tail, %End
281
///   Tail:
282
///     %ca = call i1  @callee (i32* %a, i32* %b)
283
///
284
///  to :
285
///
286
///   Header:                          // PredBB1 is Header
287
///     %c = icmp eq i32* %a, null
288
///     br i1 %c %Tail-split1, %TBB
289
///   TBB:                             // PredBB2 is TBB
290
///     %c2 = icmp eq i32* %b, null
291
///     br i1 %c %Tail-split2, %End
292
///   Tail-split1:
293
///     %ca1 = call @callee (i32* null, i32* %b)         // CallInst1
294
///    br %Tail
295
///   Tail-split2:
296
///     %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
297
///    br %Tail
298
///   Tail:
299
///    %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
300
///
301
/// Note that in case any arguments at the call-site are constrained by its
302
/// predecessors, new call-sites with more constrained arguments will be
303
/// created in createCallSitesOnPredicatedArgument().
304
static void splitCallSite(
305
    CallSite CS,
306
    const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
307
264
    DomTreeUpdater &DTU) {
308
264
  Instruction *Instr = CS.getInstruction();
309
264
  BasicBlock *TailBB = Instr->getParent();
310
264
  bool IsMustTailCall = CS.isMustTailCall();
311
264
312
264
  PHINode *CallPN = nullptr;
313
264
314
264
  // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
315
264
  // split blocks will be terminated right after that so there're no users for
316
264
  // this phi in a `TailBB`.
317
264
  if (!IsMustTailCall && 
!Instr->use_empty()260
) {
318
158
    CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
319
158
    CallPN->setDebugLoc(Instr->getDebugLoc());
320
158
  }
321
264
322
264
  LLVM_DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
323
264
324
264
  assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
325
264
  // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
326
264
  // here.
327
264
  ValueToValueMapTy ValueToValueMaps[2];
328
792
  for (unsigned i = 0; i < Preds.size(); 
i++528
) {
329
528
    BasicBlock *PredBB = Preds[i].first;
330
528
    BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween(
331
528
        TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i],
332
528
        DTU);
333
528
    assert(SplitBlock && "Unexpected new basic block split.");
334
528
335
528
    Instruction *NewCI =
336
528
        &*std::prev(SplitBlock->getTerminator()->getIterator());
337
528
    CallSite NewCS(NewCI);
338
528
    addConditions(NewCS, Preds[i].second);
339
528
340
528
    // Handle PHIs used as arguments in the call-site.
341
528
    for (PHINode &PN : TailBB->phis()) {
342
200
      unsigned ArgNo = 0;
343
642
      for (auto &CI : CS.args()) {
344
642
        if (&*CI == &PN) {
345
154
          NewCS.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock));
346
154
        }
347
642
        ++ArgNo;
348
642
      }
349
200
    }
350
528
    LLVM_DEBUG(dbgs() << "    " << *NewCI << " in " << SplitBlock->getName()
351
528
                      << "\n");
352
528
    if (CallPN)
353
316
      CallPN->addIncoming(NewCI, SplitBlock);
354
528
355
528
    // Clone and place bitcast and return instructions before `TI`
356
528
    if (IsMustTailCall)
357
8
      copyMustTailReturn(SplitBlock, Instr, NewCI);
358
528
  }
359
264
360
264
  NumCallSiteSplit++;
361
264
362
264
  // FIXME: remove TI in `copyMustTailReturn`
363
264
  if (IsMustTailCall) {
364
4
    // Remove superfluous `br` terminators from the end of the Split blocks
365
4
    // NOTE: Removing terminator removes the SplitBlock from the TailBB's
366
4
    // predecessors. Therefore we must get complete list of Splits before
367
4
    // attempting removal.
368
4
    SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));
369
4
    assert(Splits.size() == 2 && "Expected exactly 2 splits!");
370
12
    for (unsigned i = 0; i < Splits.size(); 
i++8
) {
371
8
      Splits[i]->getTerminator()->eraseFromParent();
372
8
      DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}});
373
8
    }
374
4
375
4
    // Erase the tail block once done with musttail patching
376
4
    DTU.deleteBB(TailBB);
377
4
    return;
378
4
  }
379
260
380
260
  auto *OriginalBegin = &*TailBB->begin();
381
260
  // Replace users of the original call with a PHI mering call-sites split.
382
260
  if (CallPN) {
383
158
    CallPN->insertBefore(OriginalBegin);
384
158
    Instr->replaceAllUsesWith(CallPN);
385
158
  }
386
260
387
260
  // Remove instructions moved to split blocks from TailBB, from the duplicated
388
260
  // call instruction to the beginning of the basic block. If an instruction
389
260
  // has any uses, add a new PHI node to combine the values coming from the
390
260
  // split blocks. The new PHI nodes are placed before the first original
391
260
  // instruction, so we do not end up deleting them. By using reverse-order, we
392
260
  // do not introduce unnecessary PHI nodes for def-use chains from the call
393
260
  // instruction to the beginning of the block.
394
260
  auto I = Instr->getReverseIterator();
395
485
  while (I != TailBB->rend()) {
396
472
    Instruction *CurrentI = &*I++;
397
472
    if (!CurrentI->use_empty()) {
398
48
      // If an existing PHI has users after the call, there is no need to create
399
48
      // a new one.
400
48
      if (isa<PHINode>(CurrentI))
401
27
        continue;
402
21
      PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
403
21
      NewPN->setDebugLoc(CurrentI->getDebugLoc());
404
21
      for (auto &Mapping : ValueToValueMaps)
405
42
        NewPN->addIncoming(Mapping[CurrentI],
406
42
                           cast<Instruction>(Mapping[CurrentI])->getParent());
407
21
      NewPN->insertBefore(&*TailBB->begin());
408
21
      CurrentI->replaceAllUsesWith(NewPN);
409
21
    }
410
472
    CurrentI->eraseFromParent();
411
445
    // We are done once we handled the first original instruction in TailBB.
412
445
    if (CurrentI == OriginalBegin)
413
247
      break;
414
445
  }
415
260
}
416
417
// Return true if the call-site has an argument which is a PHI with only
418
// constant incoming values.
419
131k
static bool isPredicatedOnPHI(CallSite CS) {
420
131k
  Instruction *Instr = CS.getInstruction();
421
131k
  BasicBlock *Parent = Instr->getParent();
422
131k
  if (Instr != Parent->getFirstNonPHIOrDbg())
423
66.6k
    return false;
424
65.1k
425
65.1k
  for (auto &BI : *Parent) {
426
65.1k
    if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
427
38.0k
      for (auto &I : CS.args())
428
79.4k
        if (&*I == PN) {
429
23.4k
          assert(PN->getNumIncomingValues() == 2 &&
430
23.4k
                 "Unexpected number of incoming values");
431
23.4k
          if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
432
0
            return false;
433
23.4k
          if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
434
0
            continue;
435
23.4k
          if (isa<Constant>(PN->getIncomingValue(0)) &&
436
23.4k
              
isa<Constant>(PN->getIncomingValue(1))228
)
437
32
            return true;
438
23.4k
        }
439
38.0k
    }
440
65.1k
    
break65.0k
;
441
65.1k
  }
442
65.1k
  
return false65.0k
;
443
65.1k
}
444
445
using PredsWithCondsTy = SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2>;
446
447
// Check if any of the arguments in CS are predicated on a PHI node and return
448
// the set of predecessors we should use for splitting.
449
131k
static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallSite CS) {
450
131k
  if (!isPredicatedOnPHI(CS))
451
131k
    return {};
452
32
453
32
  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
454
32
  return {{Preds[0], {}}, {Preds[1], {}}};
455
32
}
456
457
// Checks if any of the arguments in CS are predicated in a predecessor and
458
// returns a list of predecessors with the conditions that hold on their edges
459
// to CS.
460
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallSite CS,
461
132k
                                                        DomTreeUpdater &DTU) {
462
132k
  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
463
132k
  if (Preds[0] == Preds[1])
464
177
    return {};
465
131k
466
131k
  // We can stop recording conditions once we reached the immediate dominator
467
131k
  // for the block containing the call site. Conditions in predecessors of the
468
131k
  // that node will be the same for all paths to the call site and splitting
469
131k
  // is not beneficial.
470
131k
  assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
471
131k
  auto *CSDTNode = DTU.getDomTree().getNode(CS.getInstruction()->getParent());
472
131k
  BasicBlock *StopAt = CSDTNode ? 
CSDTNode->getIDom()->getBlock()131k
:
nullptr4
;
473
131k
474
131k
  SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2> PredsCS;
475
263k
  for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
476
263k
    ConditionsTy Conditions;
477
263k
    // Record condition on edge BB(CS) <- Pred
478
263k
    recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
479
263k
    // Record conditions following Pred's single predecessors.
480
263k
    recordConditions(CS, Pred, Conditions, StopAt);
481
263k
    PredsCS.push_back({Pred, Conditions});
482
263k
  }
483
131k
484
263k
  if (
all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) 131k
{
485
263k
        return P.second.empty();
486
263k
      }))
487
131k
    return {};
488
232
489
232
  return PredsCS;
490
232
}
491
492
static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI,
493
1.25M
                               DomTreeUpdater &DTU) {
494
1.25M
  // Check if we can split the call site.
495
1.25M
  if (!CS.arg_size() || 
!canSplitCallSite(CS, TTI)1.19M
)
496
1.12M
    return false;
497
132k
498
132k
  auto PredsWithConds = shouldSplitOnPredicatedArgument(CS, DTU);
499
132k
  if (PredsWithConds.empty())
500
131k
    PredsWithConds = shouldSplitOnPHIPredicatedArgument(CS);
501
132k
  if (PredsWithConds.empty())
502
131k
    return false;
503
264
504
264
  splitCallSite(CS, PredsWithConds, DTU);
505
264
  return true;
506
264
}
507
508
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI,
509
578k
                                TargetTransformInfo &TTI, DominatorTree &DT) {
510
578k
511
578k
  DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
512
578k
  bool Changed = false;
513
2.97M
  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
514
2.39M
    BasicBlock &BB = *BI++;
515
2.39M
    auto II = BB.getFirstNonPHIOrDbg()->getIterator();
516
2.39M
    auto IE = BB.getTerminator()->getIterator();
517
2.39M
    // Iterate until we reach the terminator instruction. tryToSplitCallSite
518
2.39M
    // can replace BB's terminator in case BB is a successor of itself. In that
519
2.39M
    // case, IE will be invalidated and we also have to check the current
520
2.39M
    // terminator.
521
12.4M
    while (II != IE && 
&*II != BB.getTerminator()10.0M
) {
522
10.0M
      Instruction *I = &*II++;
523
10.0M
      CallSite CS(cast<Value>(I));
524
10.0M
      if (!CS || 
isa<IntrinsicInst>(I)2.16M
||
isInstructionTriviallyDead(I, &TLI)1.81M
)
525
8.22M
        continue;
526
1.81M
527
1.81M
      Function *Callee = CS.getCalledFunction();
528
1.81M
      if (!Callee || 
Callee->isDeclaration()1.75M
)
529
564k
        continue;
530
1.25M
531
1.25M
      // Successful musttail call-site splits result in erased CI and erased BB.
532
1.25M
      // Check if such path is possible before attempting the splitting.
533
1.25M
      bool IsMustTail = CS.isMustTailCall();
534
1.25M
535
1.25M
      Changed |= tryToSplitCallSite(CS, TTI, DTU);
536
1.25M
537
1.25M
      // There're no interesting instructions after this. The call site
538
1.25M
      // itself might have been erased on splitting.
539
1.25M
      if (IsMustTail)
540
4
        break;
541
1.25M
    }
542
2.39M
  }
543
578k
  return Changed;
544
578k
}
545
546
namespace {
547
struct CallSiteSplittingLegacyPass : public FunctionPass {
548
  static char ID;
549
11.3k
  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
550
11.3k
    initializeCallSiteSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
551
11.3k
  }
552
553
11.3k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
554
11.3k
    AU.addRequired<TargetLibraryInfoWrapperPass>();
555
11.3k
    AU.addRequired<TargetTransformInfoWrapperPass>();
556
11.3k
    AU.addRequired<DominatorTreeWrapperPass>();
557
11.3k
    AU.addPreserved<DominatorTreeWrapperPass>();
558
11.3k
    FunctionPass::getAnalysisUsage(AU);
559
11.3k
  }
560
561
578k
  bool runOnFunction(Function &F) override {
562
578k
    if (skipFunction(F))
563
16
      return false;
564
578k
565
578k
    auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
566
578k
    auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
567
578k
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
568
578k
    return doCallSiteSplitting(F, TLI, TTI, DT);
569
578k
  }
570
};
571
} // namespace
572
573
char CallSiteSplittingLegacyPass::ID = 0;
574
47.2k
INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
575
47.2k
                      "Call-site splitting", false, false)
576
47.2k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
577
47.2k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
578
47.2k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
579
47.2k
INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
580
                    "Call-site splitting", false, false)
581
11.3k
FunctionPass *llvm::createCallSiteSplittingPass() {
582
11.3k
  return new CallSiteSplittingLegacyPass();
583
11.3k
}
584
585
PreservedAnalyses CallSiteSplittingPass::run(Function &F,
586
89
                                             FunctionAnalysisManager &AM) {
587
89
  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
588
89
  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
589
89
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
590
89
591
89
  if (!doCallSiteSplitting(F, TLI, TTI, DT))
592
66
    return PreservedAnalyses::all();
593
23
  PreservedAnalyses PA;
594
23
  PA.preserve<DominatorTreeAnalysis>();
595
23
  return PA;
596
23
}