Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/X86/X86CondBrFolding.cpp
Line
Count
Source (jump to first uncovered line)
1
//===---- X86CondBrFolding.cpp - optimize conditional branches ------------===//
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
// This file defines a pass that optimizes condition branches on x86 by taking
9
// advantage of the three-way conditional code generated by compare
10
// instructions.
11
// Currently, it tries to hoisting EQ and NE conditional branch to a dominant
12
// conditional branch condition where the same EQ/NE conditional code is
13
// computed. An example:
14
//   bb_0:
15
//     cmp %0, 19
16
//     jg bb_1
17
//     jmp bb_2
18
//   bb_1:
19
//     cmp %0, 40
20
//     jg bb_3
21
//     jmp bb_4
22
//   bb_4:
23
//     cmp %0, 20
24
//     je bb_5
25
//     jmp bb_6
26
// Here we could combine the two compares in bb_0 and bb_4 and have the
27
// following code:
28
//   bb_0:
29
//     cmp %0, 20
30
//     jg bb_1
31
//     jl bb_2
32
//     jmp bb_5
33
//   bb_1:
34
//     cmp %0, 40
35
//     jg bb_3
36
//     jmp bb_6
37
// For the case of %0 == 20 (bb_5), we eliminate two jumps, and the control
38
// height for bb_6 is also reduced. bb_4 is gone after the optimization.
39
//
40
// There are plenty of this code patterns, especially from the switch case
41
// lowing where we generate compare of "pivot-1" for the inner nodes in the
42
// binary search tree.
43
//===----------------------------------------------------------------------===//
44
45
#include "X86.h"
46
#include "X86InstrInfo.h"
47
#include "X86Subtarget.h"
48
#include "llvm/ADT/Statistic.h"
49
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
50
#include "llvm/CodeGen/MachineFunctionPass.h"
51
#include "llvm/CodeGen/MachineInstrBuilder.h"
52
#include "llvm/CodeGen/MachineRegisterInfo.h"
53
#include "llvm/Support/BranchProbability.h"
54
55
using namespace llvm;
56
57
#define DEBUG_TYPE "x86-condbr-folding"
58
59
STATISTIC(NumFixedCondBrs, "Number of x86 condbr folded");
60
61
namespace {
62
class X86CondBrFoldingPass : public MachineFunctionPass {
63
public:
64
15
  X86CondBrFoldingPass() : MachineFunctionPass(ID) { }
65
65
  StringRef getPassName() const override { return "X86 CondBr Folding"; }
66
67
  bool runOnMachineFunction(MachineFunction &MF) override;
68
69
15
  void getAnalysisUsage(AnalysisUsage &AU) const override {
70
15
    MachineFunctionPass::getAnalysisUsage(AU);
71
15
    AU.addRequired<MachineBranchProbabilityInfo>();
72
15
  }
73
74
public:
75
  static char ID;
76
};
77
} // namespace
78
79
char X86CondBrFoldingPass::ID = 0;
80
INITIALIZE_PASS(X86CondBrFoldingPass, "X86CondBrFolding", "X86CondBrFolding", false, false)
81
82
14
FunctionPass *llvm::createX86CondBrFolding() {
83
14
  return new X86CondBrFoldingPass();
84
14
}
85
86
namespace {
87
// A class the stores the auxiliary information for each MBB.
88
struct TargetMBBInfo {
89
  MachineBasicBlock *TBB;
90
  MachineBasicBlock *FBB;
91
  MachineInstr *BrInstr;
92
  MachineInstr *CmpInstr;
93
  X86::CondCode BranchCode;
94
  unsigned SrcReg;
95
  int CmpValue;
96
  bool Modified;
97
  bool CmpBrOnly;
98
};
99
100
// A class that optimizes the conditional branch by hoisting and merge CondCode.
101
class X86CondBrFolding {
102
public:
103
  X86CondBrFolding(const X86InstrInfo *TII,
104
                   const MachineBranchProbabilityInfo *MBPI,
105
                   MachineFunction &MF)
106
43
      : TII(TII), MBPI(MBPI), MF(MF) {}
107
  bool optimize();
108
109
private:
110
  const X86InstrInfo *TII;
111
  const MachineBranchProbabilityInfo *MBPI;
112
  MachineFunction &MF;
113
  std::vector<std::unique_ptr<TargetMBBInfo>> MBBInfos;
114
  SmallVector<MachineBasicBlock *, 4> RemoveList;
115
116
  void optimizeCondBr(MachineBasicBlock &MBB,
117
                      SmallVectorImpl<MachineBasicBlock *> &BranchPath);
118
  void fixBranchProb(MachineBasicBlock *NextMBB, MachineBasicBlock *RootMBB,
119
                     SmallVectorImpl<MachineBasicBlock *> &BranchPath);
120
  void replaceBrDest(MachineBasicBlock *MBB, MachineBasicBlock *OrigDest,
121
                     MachineBasicBlock *NewDest);
122
  void fixupModifiedCond(MachineBasicBlock *MBB);
123
  std::unique_ptr<TargetMBBInfo> analyzeMBB(MachineBasicBlock &MBB);
124
  static bool analyzeCompare(const MachineInstr &MI, unsigned &SrcReg,
125
                             int &CmpValue);
126
  bool findPath(MachineBasicBlock *MBB,
127
                SmallVectorImpl<MachineBasicBlock *> &BranchPath);
128
1.19k
  TargetMBBInfo *getMBBInfo(MachineBasicBlock *MBB) const {
129
1.19k
    return MBBInfos[MBB->getNumber()].get();
130
1.19k
  }
131
};
132
} // namespace
133
134
// Find a valid path that we can reuse the CondCode.
135
// The resulted path (if return true) is stored in BranchPath.
136
// Return value:
137
//  false: is no valid path is found.
138
//  true: a valid path is found and the targetBB can be reached.
139
bool X86CondBrFolding::findPath(
140
156
    MachineBasicBlock *MBB, SmallVectorImpl<MachineBasicBlock *> &BranchPath) {
141
156
  TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
142
156
  assert(MBBInfo && "Expecting a candidate MBB");
143
156
  int CmpValue = MBBInfo->CmpValue;
144
156
145
156
  MachineBasicBlock *PredMBB = *MBB->pred_begin();
146
156
  MachineBasicBlock *SaveMBB = MBB;
147
264
  while (PredMBB) {
148
264
    TargetMBBInfo *PredMBBInfo = getMBBInfo(PredMBB);
149
264
    if (!PredMBBInfo || 
PredMBBInfo->SrcReg != MBBInfo->SrcReg258
)
150
6
      return false;
151
258
152
258
    assert(SaveMBB == PredMBBInfo->TBB || SaveMBB == PredMBBInfo->FBB);
153
258
    bool IsFalseBranch = (SaveMBB == PredMBBInfo->FBB);
154
258
155
258
    X86::CondCode CC = PredMBBInfo->BranchCode;
156
258
    assert(CC == X86::COND_L || CC == X86::COND_G || CC == X86::COND_E);
157
258
    int PredCmpValue = PredMBBInfo->CmpValue;
158
258
    bool ValueCmpTrue = ((CmpValue < PredCmpValue && 
CC == X86::COND_L132
) ||
159
258
                         
(228
CmpValue > PredCmpValue228
&&
CC == X86::COND_G126
) ||
160
258
                         
(138
CmpValue == PredCmpValue138
&&
CC == X86::COND_E0
));
161
258
    // Check if both the result of value compare and the branch target match.
162
258
    if (!(ValueCmpTrue ^ IsFalseBranch)) {
163
0
      LLVM_DEBUG(dbgs() << "Dead BB detected!\n");
164
0
      return false;
165
0
    }
166
258
167
258
    BranchPath.push_back(PredMBB);
168
258
    // These are the conditions on which we could combine the compares.
169
258
    if ((CmpValue == PredCmpValue) ||
170
258
        (CmpValue == PredCmpValue - 1 && 
CC == X86::COND_L18
) ||
171
258
        
(240
CmpValue == PredCmpValue + 1240
&&
CC == X86::COND_G54
))
172
72
      return true;
173
186
174
186
    // If PredMBB has more than on preds, or not a pure cmp and br, we bailout.
175
186
    if (PredMBB->pred_size() != 1 || 
!PredMBBInfo->CmpBrOnly108
)
176
78
      return false;
177
108
178
108
    SaveMBB = PredMBB;
179
108
    PredMBB = *PredMBB->pred_begin();
180
108
  }
181
156
  
return false0
;
182
156
}
183
184
// Fix up any PHI node in the successor of MBB.
185
static void fixPHIsInSucc(MachineBasicBlock *MBB, MachineBasicBlock *OldMBB,
186
144
                          MachineBasicBlock *NewMBB) {
187
144
  if (NewMBB == OldMBB)
188
0
    return;
189
144
  for (auto MI = MBB->instr_begin(), ME = MBB->instr_end();
190
144
       MI != ME && MI->isPHI(); 
++MI0
)
191
0
    for (unsigned i = 2, e = MI->getNumOperands() + 1; i != e; i += 2) {
192
0
      MachineOperand &MO = MI->getOperand(i);
193
0
      if (MO.getMBB() == OldMBB)
194
0
        MO.setMBB(NewMBB);
195
0
    }
196
144
}
197
198
// Utility function to set branch probability for edge MBB->SuccMBB.
199
static inline bool setBranchProb(MachineBasicBlock *MBB,
200
                                 MachineBasicBlock *SuccMBB,
201
264
                                 BranchProbability Prob) {
202
264
  auto MBBI = std::find(MBB->succ_begin(), MBB->succ_end(), SuccMBB);
203
264
  if (MBBI == MBB->succ_end())
204
0
    return false;
205
264
  MBB->setSuccProbability(MBBI, Prob);
206
264
  return true;
207
264
}
208
209
// Utility function to find the unconditional br instruction in MBB.
210
static inline MachineBasicBlock::iterator
211
114
findUncondBrI(MachineBasicBlock *MBB) {
212
396
  return std::find_if(MBB->begin(), MBB->end(), [](MachineInstr &MI) -> bool {
213
396
    return MI.getOpcode() == X86::JMP_1;
214
396
  });
215
114
}
216
217
// Replace MBB's original successor, OrigDest, with NewDest.
218
// Also update the MBBInfo for MBB.
219
void X86CondBrFolding::replaceBrDest(MachineBasicBlock *MBB,
220
                                     MachineBasicBlock *OrigDest,
221
72
                                     MachineBasicBlock *NewDest) {
222
72
  TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
223
72
  MachineInstr *BrMI;
224
72
  if (MBBInfo->TBB == OrigDest) {
225
30
    BrMI = MBBInfo->BrInstr;
226
30
    MachineInstrBuilder MIB =
227
30
        BuildMI(*MBB, BrMI, MBB->findDebugLoc(BrMI), TII->get(X86::JCC_1))
228
30
            .addMBB(NewDest).addImm(MBBInfo->BranchCode);
229
30
    MBBInfo->TBB = NewDest;
230
30
    MBBInfo->BrInstr = MIB.getInstr();
231
42
  } else { // Should be the unconditional jump stmt.
232
42
    MachineBasicBlock::iterator UncondBrI = findUncondBrI(MBB);
233
42
    BuildMI(*MBB, UncondBrI, MBB->findDebugLoc(UncondBrI), TII->get(X86::JMP_1))
234
42
        .addMBB(NewDest);
235
42
    MBBInfo->FBB = NewDest;
236
42
    BrMI = &*UncondBrI;
237
42
  }
238
72
  fixPHIsInSucc(NewDest, OrigDest, MBB);
239
72
  BrMI->eraseFromParent();
240
72
  MBB->addSuccessor(NewDest);
241
72
  setBranchProb(MBB, NewDest, MBPI->getEdgeProbability(MBB, OrigDest));
242
72
  MBB->removeSuccessor(OrigDest);
243
72
}
244
245
// Change the CondCode and BrInstr according to MBBInfo.
246
0
void X86CondBrFolding::fixupModifiedCond(MachineBasicBlock *MBB) {
247
0
  TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
248
0
  if (!MBBInfo->Modified)
249
0
    return;
250
0
251
0
  MachineInstr *BrMI = MBBInfo->BrInstr;
252
0
  X86::CondCode CC = MBBInfo->BranchCode;
253
0
  MachineInstrBuilder MIB = BuildMI(*MBB, BrMI, MBB->findDebugLoc(BrMI),
254
0
                                    TII->get(X86::JCC_1))
255
0
                                .addMBB(MBBInfo->TBB).addImm(CC);
256
0
  BrMI->eraseFromParent();
257
0
  MBBInfo->BrInstr = MIB.getInstr();
258
0
259
0
  MachineBasicBlock::iterator UncondBrI = findUncondBrI(MBB);
260
0
  BuildMI(*MBB, UncondBrI, MBB->findDebugLoc(UncondBrI), TII->get(X86::JMP_1))
261
0
      .addMBB(MBBInfo->FBB);
262
0
  MBB->erase(UncondBrI);
263
0
  MBBInfo->Modified = false;
264
0
}
265
266
//
267
// Apply the transformation:
268
//  RootMBB -1-> ... PredMBB -3-> MBB -5-> TargetMBB
269
//     \-2->           \-4->       \-6-> FalseMBB
270
// ==>
271
//             RootMBB -1-> ... PredMBB -7-> FalseMBB
272
// TargetMBB <-8-/ \-2->           \-4->
273
//
274
// Note that PredMBB and RootMBB could be the same.
275
// And in the case of dead TargetMBB, we will not have TargetMBB and edge 8.
276
//
277
// There are some special handling where the RootMBB is COND_E in which case
278
// we directly short-cycle the brinstr.
279
//
280
void X86CondBrFolding::optimizeCondBr(
281
72
    MachineBasicBlock &MBB, SmallVectorImpl<MachineBasicBlock *> &BranchPath) {
282
72
283
72
  X86::CondCode CC;
284
72
  TargetMBBInfo *MBBInfo = getMBBInfo(&MBB);
285
72
  assert(MBBInfo && "Expecting a candidate MBB");
286
72
  MachineBasicBlock *TargetMBB = MBBInfo->TBB;
287
72
  BranchProbability TargetProb = MBPI->getEdgeProbability(&MBB, MBBInfo->TBB);
288
72
289
72
  // Forward the jump from MBB's predecessor to MBB's false target.
290
72
  MachineBasicBlock *PredMBB = BranchPath.front();
291
72
  TargetMBBInfo *PredMBBInfo = getMBBInfo(PredMBB);
292
72
  assert(PredMBBInfo && "Expecting a candidate MBB");
293
72
  if (PredMBBInfo->Modified)
294
0
    fixupModifiedCond(PredMBB);
295
72
  CC = PredMBBInfo->BranchCode;
296
72
  // Don't do this if depth of BranchPath is 1 and PredMBB is of COND_E.
297
72
  // We will short-cycle directly for this case.
298
72
  if (!(CC == X86::COND_E && 
BranchPath.size() == 10
))
299
72
    replaceBrDest(PredMBB, &MBB, MBBInfo->FBB);
300
72
301
72
  MachineBasicBlock *RootMBB = BranchPath.back();
302
72
  TargetMBBInfo *RootMBBInfo = getMBBInfo(RootMBB);
303
72
  assert(RootMBBInfo && "Expecting a candidate MBB");
304
72
  if (RootMBBInfo->Modified)
305
0
    fixupModifiedCond(RootMBB);
306
72
  CC = RootMBBInfo->BranchCode;
307
72
308
72
  if (CC != X86::COND_E) {
309
72
    MachineBasicBlock::iterator UncondBrI = findUncondBrI(RootMBB);
310
72
    // RootMBB: Cond jump to the original not-taken MBB.
311
72
    X86::CondCode NewCC;
312
72
    switch (CC) {
313
72
    case X86::COND_L:
314
18
      NewCC = X86::COND_G;
315
18
      break;
316
72
    case X86::COND_G:
317
54
      NewCC = X86::COND_L;
318
54
      break;
319
72
    default:
320
0
      llvm_unreachable("unexpected condtional code.");
321
72
    }
322
72
    BuildMI(*RootMBB, UncondBrI, RootMBB->findDebugLoc(UncondBrI),
323
72
            TII->get(X86::JCC_1))
324
72
        .addMBB(RootMBBInfo->FBB).addImm(NewCC);
325
72
326
72
    // RootMBB: Jump to TargetMBB
327
72
    BuildMI(*RootMBB, UncondBrI, RootMBB->findDebugLoc(UncondBrI),
328
72
            TII->get(X86::JMP_1))
329
72
        .addMBB(TargetMBB);
330
72
    RootMBB->addSuccessor(TargetMBB);
331
72
    fixPHIsInSucc(TargetMBB, &MBB, RootMBB);
332
72
    RootMBB->erase(UncondBrI);
333
72
  } else {
334
0
    replaceBrDest(RootMBB, RootMBBInfo->TBB, TargetMBB);
335
0
  }
336
72
337
72
  // Fix RootMBB's CmpValue to MBB's CmpValue to TargetMBB. Don't set Imm
338
72
  // directly. Move MBB's stmt to here as the opcode might be different.
339
72
  if (RootMBBInfo->CmpValue != MBBInfo->CmpValue) {
340
72
    MachineInstr *NewCmp = MBBInfo->CmpInstr;
341
72
    NewCmp->removeFromParent();
342
72
    RootMBB->insert(RootMBBInfo->CmpInstr, NewCmp);
343
72
    RootMBBInfo->CmpInstr->eraseFromParent();
344
72
  }
345
72
346
72
  // Fix branch Probabilities.
347
72
  auto fixBranchProb = [&](MachineBasicBlock *NextMBB) {
348
72
    BranchProbability Prob;
349
120
    for (auto &I : BranchPath) {
350
120
      MachineBasicBlock *ThisMBB = I;
351
120
      if (!ThisMBB->hasSuccessorProbabilities() ||
352
120
          !ThisMBB->isSuccessor(NextMBB))
353
0
        break;
354
120
      Prob = MBPI->getEdgeProbability(ThisMBB, NextMBB);
355
120
      if (Prob.isUnknown())
356
0
        break;
357
120
      TargetProb = Prob * TargetProb;
358
120
      Prob = Prob - TargetProb;
359
120
      setBranchProb(ThisMBB, NextMBB, Prob);
360
120
      if (ThisMBB == RootMBB) {
361
72
        setBranchProb(ThisMBB, TargetMBB, TargetProb);
362
72
      }
363
120
      ThisMBB->normalizeSuccProbs();
364
120
      if (ThisMBB == RootMBB)
365
72
        break;
366
48
      NextMBB = ThisMBB;
367
48
    }
368
72
    return true;
369
72
  };
370
72
  if (CC != X86::COND_E && !TargetProb.isUnknown())
371
72
    fixBranchProb(MBBInfo->FBB);
372
72
373
72
  if (CC != X86::COND_E)
374
72
    RemoveList.push_back(&MBB);
375
72
376
72
  // Invalidate MBBInfo just in case.
377
72
  MBBInfos[MBB.getNumber()] = nullptr;
378
72
  MBBInfos[RootMBB->getNumber()] = nullptr;
379
72
380
72
  LLVM_DEBUG(dbgs() << "After optimization:\nRootMBB is: " << *RootMBB << "\n");
381
72
  if (BranchPath.size() > 1)
382
72
    LLVM_DEBUG(dbgs() << "PredMBB is: " << *(BranchPath[0]) << "\n");
383
72
}
384
385
// Driver function for optimization: find the valid candidate and apply
386
// the transformation.
387
43
bool X86CondBrFolding::optimize() {
388
43
  bool Changed = false;
389
43
  LLVM_DEBUG(dbgs() << "***** X86CondBr Folding on Function: " << MF.getName()
390
43
                    << " *****\n");
391
43
  // Setup data structures.
392
43
  MBBInfos.resize(MF.getNumBlockIDs());
393
43
  for (auto &MBB : MF)
394
483
    MBBInfos[MBB.getNumber()] = analyzeMBB(MBB);
395
43
396
483
  for (auto &MBB : MF) {
397
483
    TargetMBBInfo *MBBInfo = getMBBInfo(&MBB);
398
483
    if (!MBBInfo || 
!MBBInfo->CmpBrOnly240
)
399
285
      continue;
400
198
    if (MBB.pred_size() != 1)
401
42
      continue;
402
156
    LLVM_DEBUG(dbgs() << "Work on MBB." << MBB.getNumber()
403
156
                      << " CmpValue: " << MBBInfo->CmpValue << "\n");
404
156
    SmallVector<MachineBasicBlock *, 4> BranchPath;
405
156
    if (!findPath(&MBB, BranchPath))
406
84
      continue;
407
72
408
#ifndef NDEBUG
409
    LLVM_DEBUG(dbgs() << "Found one path (len=" << BranchPath.size() << "):\n");
410
    int Index = 1;
411
    LLVM_DEBUG(dbgs() << "Target MBB is: " << MBB << "\n");
412
    for (auto I = BranchPath.rbegin(); I != BranchPath.rend(); ++I, ++Index) {
413
      MachineBasicBlock *PMBB = *I;
414
      TargetMBBInfo *PMBBInfo = getMBBInfo(PMBB);
415
      LLVM_DEBUG(dbgs() << "Path MBB (" << Index << " of " << BranchPath.size()
416
                        << ") is " << *PMBB);
417
      LLVM_DEBUG(dbgs() << "CC=" << PMBBInfo->BranchCode
418
                        << "  Val=" << PMBBInfo->CmpValue
419
                        << "  CmpBrOnly=" << PMBBInfo->CmpBrOnly << "\n\n");
420
    }
421
#endif
422
72
    optimizeCondBr(MBB, BranchPath);
423
72
    Changed = true;
424
72
  }
425
43
  NumFixedCondBrs += RemoveList.size();
426
72
  for (auto MBBI : RemoveList) {
427
216
    while (!MBBI->succ_empty())
428
144
      MBBI->removeSuccessor(MBBI->succ_end() - 1);
429
72
430
72
    MBBI->eraseFromParent();
431
72
  }
432
43
433
43
  return Changed;
434
43
}
435
436
// Analyze instructions that generate CondCode and extract information.
437
bool X86CondBrFolding::analyzeCompare(const MachineInstr &MI, unsigned &SrcReg,
438
283
                                      int &CmpValue) {
439
283
  unsigned SrcRegIndex = 0;
440
283
  unsigned ValueIndex = 0;
441
283
  switch (MI.getOpcode()) {
442
283
  // TODO: handle test instructions.
443
283
  default:
444
42
    return false;
445
283
  case X86::CMP64ri32:
446
0
  case X86::CMP64ri8:
447
0
  case X86::CMP32ri:
448
0
  case X86::CMP32ri8:
449
0
  case X86::CMP16ri:
450
0
  case X86::CMP16ri8:
451
0
  case X86::CMP8ri:
452
0
    SrcRegIndex = 0;
453
0
    ValueIndex = 1;
454
0
    break;
455
241
  case X86::SUB64ri32:
456
241
  case X86::SUB64ri8:
457
241
  case X86::SUB32ri:
458
241
  case X86::SUB32ri8:
459
241
  case X86::SUB16ri:
460
241
  case X86::SUB16ri8:
461
241
  case X86::SUB8ri:
462
241
    SrcRegIndex = 1;
463
241
    ValueIndex = 2;
464
241
    break;
465
241
  }
466
241
  SrcReg = MI.getOperand(SrcRegIndex).getReg();
467
241
  if (!MI.getOperand(ValueIndex).isImm())
468
1
    return false;
469
240
  CmpValue = MI.getOperand(ValueIndex).getImm();
470
240
  return true;
471
240
}
472
473
// Analyze a candidate MBB and set the extract all the information needed.
474
// The valid candidate will have two successors.
475
// It also should have a sequence of
476
//  Branch_instr,
477
//  CondBr,
478
//  UnCondBr.
479
// Return TargetMBBInfo if MBB is a valid candidate and nullptr otherwise.
480
std::unique_ptr<TargetMBBInfo>
481
483
X86CondBrFolding::analyzeMBB(MachineBasicBlock &MBB) {
482
483
  MachineBasicBlock *TBB;
483
483
  MachineBasicBlock *FBB;
484
483
  MachineInstr *BrInstr;
485
483
  MachineInstr *CmpInstr;
486
483
  X86::CondCode CC;
487
483
  unsigned SrcReg;
488
483
  int CmpValue;
489
483
  bool Modified;
490
483
  bool CmpBrOnly;
491
483
492
483
  if (MBB.succ_size() != 2)
493
242
    return nullptr;
494
241
495
241
  CmpBrOnly = true;
496
241
  FBB = TBB = nullptr;
497
241
  CmpInstr = nullptr;
498
241
  MachineBasicBlock::iterator I = MBB.end();
499
963
  while (I != MBB.begin()) {
500
765
    --I;
501
765
    if (I->isDebugValue())
502
0
      continue;
503
765
    if (I->getOpcode() == X86::JMP_1) {
504
241
      if (FBB)
505
0
        return nullptr;
506
241
      FBB = I->getOperand(0).getMBB();
507
241
      continue;
508
241
    }
509
524
    if (I->isBranch()) {
510
241
      if (TBB)
511
0
        return nullptr;
512
241
      CC = X86::getCondFromBranch(*I);
513
241
      switch (CC) {
514
241
      default:
515
0
        return nullptr;
516
241
      case X86::COND_E:
517
241
      case X86::COND_L:
518
241
      case X86::COND_G:
519
241
      case X86::COND_NE:
520
241
      case X86::COND_LE:
521
241
      case X86::COND_GE:
522
241
        break;
523
241
      }
524
241
      TBB = I->getOperand(0).getMBB();
525
241
      BrInstr = &*I;
526
241
      continue;
527
241
    }
528
283
    if (analyzeCompare(*I, SrcReg, CmpValue)) {
529
240
      if (CmpInstr)
530
0
        return nullptr;
531
240
      CmpInstr = &*I;
532
240
      continue;
533
240
    }
534
43
    CmpBrOnly = false;
535
43
    break;
536
43
  }
537
241
538
241
  if (!TBB || !FBB || !CmpInstr)
539
1
    return nullptr;
540
240
541
240
  // Simplify CondCode. Note this is only to simplify the findPath logic
542
240
  // and will not change the instruction here.
543
240
  switch (CC) {
544
240
  case X86::COND_NE:
545
30
    CC = X86::COND_E;
546
30
    std::swap(TBB, FBB);
547
30
    Modified = true;
548
30
    break;
549
240
  case X86::COND_LE:
550
0
    if (CmpValue == INT_MAX)
551
0
      return nullptr;
552
0
    CC = X86::COND_L;
553
0
    CmpValue += 1;
554
0
    Modified = true;
555
0
    break;
556
0
  case X86::COND_GE:
557
0
    if (CmpValue == INT_MIN)
558
0
      return nullptr;
559
0
    CC = X86::COND_G;
560
0
    CmpValue -= 1;
561
0
    Modified = true;
562
0
    break;
563
210
  default:
564
210
    Modified = false;
565
210
    break;
566
240
  }
567
240
  return llvm::make_unique<TargetMBBInfo>(TargetMBBInfo{
568
240
      TBB, FBB, BrInstr, CmpInstr, CC, SrcReg, CmpValue, Modified, CmpBrOnly});
569
240
}
570
571
50
bool X86CondBrFoldingPass::runOnMachineFunction(MachineFunction &MF) {
572
50
  const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
573
50
  if (!ST.threewayBranchProfitable())
574
7
    return false;
575
43
  const X86InstrInfo *TII = ST.getInstrInfo();
576
43
  const MachineBranchProbabilityInfo *MBPI =
577
43
      &getAnalysis<MachineBranchProbabilityInfo>();
578
43
579
43
  X86CondBrFolding CondBr(TII, MBPI, MF);
580
43
  return CondBr.optimize();
581
43
}