LLVM  10.0.0svn
X86CondBrFolding.cpp
Go to the documentation of this file.
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"
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  X86CondBrFoldingPass() : MachineFunctionPass(ID) { }
65  StringRef getPassName() const override { return "X86 CondBr Folding"; }
66 
67  bool runOnMachineFunction(MachineFunction &MF) override;
68 
69  void getAnalysisUsage(AnalysisUsage &AU) const override {
72  }
73 
74 public:
75  static char ID;
76 };
77 } // namespace
78 
80 INITIALIZE_PASS(X86CondBrFoldingPass, "X86CondBrFolding", "X86CondBrFolding", false, false)
81 
83  return new X86CondBrFoldingPass();
84 }
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  : 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;
115 
116  void optimizeCondBr(MachineBasicBlock &MBB,
118  void fixBranchProb(MachineBasicBlock *NextMBB, MachineBasicBlock *RootMBB,
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,
128  TargetMBBInfo *getMBBInfo(MachineBasicBlock *MBB) const {
129  return MBBInfos[MBB->getNumber()].get();
130  }
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(
141  TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
142  assert(MBBInfo && "Expecting a candidate MBB");
143  int CmpValue = MBBInfo->CmpValue;
144 
145  MachineBasicBlock *PredMBB = *MBB->pred_begin();
146  MachineBasicBlock *SaveMBB = MBB;
147  while (PredMBB) {
148  TargetMBBInfo *PredMBBInfo = getMBBInfo(PredMBB);
149  if (!PredMBBInfo || PredMBBInfo->SrcReg != MBBInfo->SrcReg)
150  return false;
151 
152  assert(SaveMBB == PredMBBInfo->TBB || SaveMBB == PredMBBInfo->FBB);
153  bool IsFalseBranch = (SaveMBB == PredMBBInfo->FBB);
154 
155  X86::CondCode CC = PredMBBInfo->BranchCode;
156  assert(CC == X86::COND_L || CC == X86::COND_G || CC == X86::COND_E);
157  int PredCmpValue = PredMBBInfo->CmpValue;
158  bool ValueCmpTrue = ((CmpValue < PredCmpValue && CC == X86::COND_L) ||
159  (CmpValue > PredCmpValue && CC == X86::COND_G) ||
160  (CmpValue == PredCmpValue && CC == X86::COND_E));
161  // Check if both the result of value compare and the branch target match.
162  if (!(ValueCmpTrue ^ IsFalseBranch)) {
163  LLVM_DEBUG(dbgs() << "Dead BB detected!\n");
164  return false;
165  }
166 
167  BranchPath.push_back(PredMBB);
168  // These are the conditions on which we could combine the compares.
169  if ((CmpValue == PredCmpValue) ||
170  (CmpValue == PredCmpValue - 1 && CC == X86::COND_L) ||
171  (CmpValue == PredCmpValue + 1 && CC == X86::COND_G))
172  return true;
173 
174  // If PredMBB has more than on preds, or not a pure cmp and br, we bailout.
175  if (PredMBB->pred_size() != 1 || !PredMBBInfo->CmpBrOnly)
176  return false;
177 
178  SaveMBB = PredMBB;
179  PredMBB = *PredMBB->pred_begin();
180  }
181  return false;
182 }
183 
184 // Fix up any PHI node in the successor of MBB.
186  MachineBasicBlock *NewMBB) {
187  if (NewMBB == OldMBB)
188  return;
189  for (auto MI = MBB->instr_begin(), ME = MBB->instr_end();
190  MI != ME && MI->isPHI(); ++MI)
191  for (unsigned i = 2, e = MI->getNumOperands() + 1; i != e; i += 2) {
192  MachineOperand &MO = MI->getOperand(i);
193  if (MO.getMBB() == OldMBB)
194  MO.setMBB(NewMBB);
195  }
196 }
197 
198 // Utility function to set branch probability for edge MBB->SuccMBB.
199 static inline bool setBranchProb(MachineBasicBlock *MBB,
200  MachineBasicBlock *SuccMBB,
201  BranchProbability Prob) {
202  auto MBBI = std::find(MBB->succ_begin(), MBB->succ_end(), SuccMBB);
203  if (MBBI == MBB->succ_end())
204  return false;
205  MBB->setSuccProbability(MBBI, Prob);
206  return true;
207 }
208 
209 // Utility function to find the unconditional br instruction in MBB.
210 static inline MachineBasicBlock::iterator
212  return std::find_if(MBB->begin(), MBB->end(), [](MachineInstr &MI) -> bool {
213  return MI.getOpcode() == X86::JMP_1;
214  });
215 }
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  MachineBasicBlock *NewDest) {
222  TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
223  MachineInstr *BrMI;
224  if (MBBInfo->TBB == OrigDest) {
225  BrMI = MBBInfo->BrInstr;
226  MachineInstrBuilder MIB =
227  BuildMI(*MBB, BrMI, MBB->findDebugLoc(BrMI), TII->get(X86::JCC_1))
228  .addMBB(NewDest).addImm(MBBInfo->BranchCode);
229  MBBInfo->TBB = NewDest;
230  MBBInfo->BrInstr = MIB.getInstr();
231  } else { // Should be the unconditional jump stmt.
233  BuildMI(*MBB, UncondBrI, MBB->findDebugLoc(UncondBrI), TII->get(X86::JMP_1))
234  .addMBB(NewDest);
235  MBBInfo->FBB = NewDest;
236  BrMI = &*UncondBrI;
237  }
238  fixPHIsInSucc(NewDest, OrigDest, MBB);
239  BrMI->eraseFromParent();
240  MBB->addSuccessor(NewDest);
241  setBranchProb(MBB, NewDest, MBPI->getEdgeProbability(MBB, OrigDest));
242  MBB->removeSuccessor(OrigDest);
243 }
244 
245 // Change the CondCode and BrInstr according to MBBInfo.
246 void X86CondBrFolding::fixupModifiedCond(MachineBasicBlock *MBB) {
247  TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
248  if (!MBBInfo->Modified)
249  return;
250 
251  MachineInstr *BrMI = MBBInfo->BrInstr;
252  X86::CondCode CC = MBBInfo->BranchCode;
253  MachineInstrBuilder MIB = BuildMI(*MBB, BrMI, MBB->findDebugLoc(BrMI),
254  TII->get(X86::JCC_1))
255  .addMBB(MBBInfo->TBB).addImm(CC);
256  BrMI->eraseFromParent();
257  MBBInfo->BrInstr = MIB.getInstr();
258 
260  BuildMI(*MBB, UncondBrI, MBB->findDebugLoc(UncondBrI), TII->get(X86::JMP_1))
261  .addMBB(MBBInfo->FBB);
262  MBB->erase(UncondBrI);
263  MBBInfo->Modified = false;
264 }
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(
282 
283  X86::CondCode CC;
284  TargetMBBInfo *MBBInfo = getMBBInfo(&MBB);
285  assert(MBBInfo && "Expecting a candidate MBB");
286  MachineBasicBlock *TargetMBB = MBBInfo->TBB;
287  BranchProbability TargetProb = MBPI->getEdgeProbability(&MBB, MBBInfo->TBB);
288 
289  // Forward the jump from MBB's predecessor to MBB's false target.
290  MachineBasicBlock *PredMBB = BranchPath.front();
291  TargetMBBInfo *PredMBBInfo = getMBBInfo(PredMBB);
292  assert(PredMBBInfo && "Expecting a candidate MBB");
293  if (PredMBBInfo->Modified)
294  fixupModifiedCond(PredMBB);
295  CC = PredMBBInfo->BranchCode;
296  // Don't do this if depth of BranchPath is 1 and PredMBB is of COND_E.
297  // We will short-cycle directly for this case.
298  if (!(CC == X86::COND_E && BranchPath.size() == 1))
299  replaceBrDest(PredMBB, &MBB, MBBInfo->FBB);
300 
301  MachineBasicBlock *RootMBB = BranchPath.back();
302  TargetMBBInfo *RootMBBInfo = getMBBInfo(RootMBB);
303  assert(RootMBBInfo && "Expecting a candidate MBB");
304  if (RootMBBInfo->Modified)
305  fixupModifiedCond(RootMBB);
306  CC = RootMBBInfo->BranchCode;
307 
308  if (CC != X86::COND_E) {
309  MachineBasicBlock::iterator UncondBrI = findUncondBrI(RootMBB);
310  // RootMBB: Cond jump to the original not-taken MBB.
311  X86::CondCode NewCC;
312  switch (CC) {
313  case X86::COND_L:
314  NewCC = X86::COND_G;
315  break;
316  case X86::COND_G:
317  NewCC = X86::COND_L;
318  break;
319  default:
320  llvm_unreachable("unexpected condtional code.");
321  }
322  BuildMI(*RootMBB, UncondBrI, RootMBB->findDebugLoc(UncondBrI),
323  TII->get(X86::JCC_1))
324  .addMBB(RootMBBInfo->FBB).addImm(NewCC);
325 
326  // RootMBB: Jump to TargetMBB
327  BuildMI(*RootMBB, UncondBrI, RootMBB->findDebugLoc(UncondBrI),
328  TII->get(X86::JMP_1))
329  .addMBB(TargetMBB);
330  RootMBB->addSuccessor(TargetMBB);
331  fixPHIsInSucc(TargetMBB, &MBB, RootMBB);
332  RootMBB->erase(UncondBrI);
333  } else {
334  replaceBrDest(RootMBB, RootMBBInfo->TBB, TargetMBB);
335  }
336 
337  // Fix RootMBB's CmpValue to MBB's CmpValue to TargetMBB. Don't set Imm
338  // directly. Move MBB's stmt to here as the opcode might be different.
339  if (RootMBBInfo->CmpValue != MBBInfo->CmpValue) {
340  MachineInstr *NewCmp = MBBInfo->CmpInstr;
341  NewCmp->removeFromParent();
342  RootMBB->insert(RootMBBInfo->CmpInstr, NewCmp);
343  RootMBBInfo->CmpInstr->eraseFromParent();
344  }
345 
346  // Fix branch Probabilities.
347  auto fixBranchProb = [&](MachineBasicBlock *NextMBB) {
348  BranchProbability Prob;
349  for (auto &I : BranchPath) {
350  MachineBasicBlock *ThisMBB = I;
351  if (!ThisMBB->hasSuccessorProbabilities() ||
352  !ThisMBB->isSuccessor(NextMBB))
353  break;
354  Prob = MBPI->getEdgeProbability(ThisMBB, NextMBB);
355  if (Prob.isUnknown())
356  break;
357  TargetProb = Prob * TargetProb;
358  Prob = Prob - TargetProb;
359  setBranchProb(ThisMBB, NextMBB, Prob);
360  if (ThisMBB == RootMBB) {
361  setBranchProb(ThisMBB, TargetMBB, TargetProb);
362  }
363  ThisMBB->normalizeSuccProbs();
364  if (ThisMBB == RootMBB)
365  break;
366  NextMBB = ThisMBB;
367  }
368  return true;
369  };
370  if (CC != X86::COND_E && !TargetProb.isUnknown())
371  fixBranchProb(MBBInfo->FBB);
372 
373  if (CC != X86::COND_E)
374  RemoveList.push_back(&MBB);
375 
376  // Invalidate MBBInfo just in case.
377  MBBInfos[MBB.getNumber()] = nullptr;
378  MBBInfos[RootMBB->getNumber()] = nullptr;
379 
380  LLVM_DEBUG(dbgs() << "After optimization:\nRootMBB is: " << *RootMBB << "\n");
381  if (BranchPath.size() > 1)
382  LLVM_DEBUG(dbgs() << "PredMBB is: " << *(BranchPath[0]) << "\n");
383 }
384 
385 // Driver function for optimization: find the valid candidate and apply
386 // the transformation.
387 bool X86CondBrFolding::optimize() {
388  bool Changed = false;
389  LLVM_DEBUG(dbgs() << "***** X86CondBr Folding on Function: " << MF.getName()
390  << " *****\n");
391  // Setup data structures.
392  MBBInfos.resize(MF.getNumBlockIDs());
393  for (auto &MBB : MF)
394  MBBInfos[MBB.getNumber()] = analyzeMBB(MBB);
395 
396  for (auto &MBB : MF) {
397  TargetMBBInfo *MBBInfo = getMBBInfo(&MBB);
398  if (!MBBInfo || !MBBInfo->CmpBrOnly)
399  continue;
400  if (MBB.pred_size() != 1)
401  continue;
402  LLVM_DEBUG(dbgs() << "Work on MBB." << MBB.getNumber()
403  << " CmpValue: " << MBBInfo->CmpValue << "\n");
405  if (!findPath(&MBB, BranchPath))
406  continue;
407 
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  optimizeCondBr(MBB, BranchPath);
423  Changed = true;
424  }
425  NumFixedCondBrs += RemoveList.size();
426  for (auto MBBI : RemoveList) {
427  while (!MBBI->succ_empty())
428  MBBI->removeSuccessor(MBBI->succ_end() - 1);
429 
430  MBBI->eraseFromParent();
431  }
432 
433  return Changed;
434 }
435 
436 // Analyze instructions that generate CondCode and extract information.
437 bool X86CondBrFolding::analyzeCompare(const MachineInstr &MI, unsigned &SrcReg,
438  int &CmpValue) {
439  unsigned SrcRegIndex = 0;
440  unsigned ValueIndex = 0;
441  switch (MI.getOpcode()) {
442  // TODO: handle test instructions.
443  default:
444  return false;
445  case X86::CMP64ri32:
446  case X86::CMP64ri8:
447  case X86::CMP32ri:
448  case X86::CMP32ri8:
449  case X86::CMP16ri:
450  case X86::CMP16ri8:
451  case X86::CMP8ri:
452  SrcRegIndex = 0;
453  ValueIndex = 1;
454  break;
455  case X86::SUB64ri32:
456  case X86::SUB64ri8:
457  case X86::SUB32ri:
458  case X86::SUB32ri8:
459  case X86::SUB16ri:
460  case X86::SUB16ri8:
461  case X86::SUB8ri:
462  SrcRegIndex = 1;
463  ValueIndex = 2;
464  break;
465  }
466  SrcReg = MI.getOperand(SrcRegIndex).getReg();
467  if (!MI.getOperand(ValueIndex).isImm())
468  return false;
469  CmpValue = MI.getOperand(ValueIndex).getImm();
470  return true;
471 }
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 X86CondBrFolding::analyzeMBB(MachineBasicBlock &MBB) {
482  MachineBasicBlock *TBB;
483  MachineBasicBlock *FBB;
484  MachineInstr *BrInstr;
485  MachineInstr *CmpInstr;
486  X86::CondCode CC;
487  unsigned SrcReg;
488  int CmpValue;
489  bool Modified;
490  bool CmpBrOnly;
491 
492  if (MBB.succ_size() != 2)
493  return nullptr;
494 
495  CmpBrOnly = true;
496  FBB = TBB = nullptr;
497  CmpInstr = nullptr;
499  while (I != MBB.begin()) {
500  --I;
501  if (I->isDebugValue())
502  continue;
503  if (I->getOpcode() == X86::JMP_1) {
504  if (FBB)
505  return nullptr;
506  FBB = I->getOperand(0).getMBB();
507  continue;
508  }
509  if (I->isBranch()) {
510  if (TBB)
511  return nullptr;
512  CC = X86::getCondFromBranch(*I);
513  switch (CC) {
514  default:
515  return nullptr;
516  case X86::COND_E:
517  case X86::COND_L:
518  case X86::COND_G:
519  case X86::COND_NE:
520  case X86::COND_LE:
521  case X86::COND_GE:
522  break;
523  }
524  TBB = I->getOperand(0).getMBB();
525  BrInstr = &*I;
526  continue;
527  }
528  if (analyzeCompare(*I, SrcReg, CmpValue)) {
529  if (CmpInstr)
530  return nullptr;
531  CmpInstr = &*I;
532  continue;
533  }
534  CmpBrOnly = false;
535  break;
536  }
537 
538  if (!TBB || !FBB || !CmpInstr)
539  return nullptr;
540 
541  // Simplify CondCode. Note this is only to simplify the findPath logic
542  // and will not change the instruction here.
543  switch (CC) {
544  case X86::COND_NE:
545  CC = X86::COND_E;
546  std::swap(TBB, FBB);
547  Modified = true;
548  break;
549  case X86::COND_LE:
550  if (CmpValue == INT_MAX)
551  return nullptr;
552  CC = X86::COND_L;
553  CmpValue += 1;
554  Modified = true;
555  break;
556  case X86::COND_GE:
557  if (CmpValue == INT_MIN)
558  return nullptr;
559  CC = X86::COND_G;
560  CmpValue -= 1;
561  Modified = true;
562  break;
563  default:
564  Modified = false;
565  break;
566  }
567  return std::make_unique<TargetMBBInfo>(TargetMBBInfo{
568  TBB, FBB, BrInstr, CmpInstr, CC, SrcReg, CmpValue, Modified, CmpBrOnly});
569 }
570 
571 bool X86CondBrFoldingPass::runOnMachineFunction(MachineFunction &MF) {
572  const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
573  if (!ST.threewayBranchProfitable())
574  return false;
575  const X86InstrInfo *TII = ST.getInstrInfo();
576  const MachineBranchProbabilityInfo *MBPI =
577  &getAnalysis<MachineBranchProbabilityInfo>();
578 
579  X86CondBrFolding CondBr(TII, MBPI, MF);
580  return CondBr.optimize();
581 }
bool hasSuccessorProbabilities() const
Return true if any of the successors have probabilities attached to them.
instr_iterator instr_begin()
instr_iterator instr_end()
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool setBranchProb(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, BranchProbability Prob)
const X86InstrInfo * getInstrInfo() const override
Definition: X86Subtarget.h:501
STATISTIC(NumFunctions, "Total number of functions")
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
AnalysisUsage & addRequired()
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
void setMBB(MachineBasicBlock *MBB)
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1205
size_t size() const
Definition: SmallVector.h:52
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1198
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
CondCode getCondFromBranch(const MachineInstr &MI)
bool threewayBranchProfitable() const
Definition: X86Subtarget.h:696
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly. ...
int64_t getImm() const
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
static MachineBasicBlock::iterator findUncondBrI(MachineBasicBlock *MBB)
unsigned succ_size() const
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
static void fixPHIsInSucc(MachineBasicBlock *MBB, MachineBasicBlock *OldMBB, MachineBasicBlock *NewMBB)
void push_back(MachineInstr *MI)
#define I(x, y, z)
Definition: MD5.cpp:58
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
FunctionPass * createX86CondBrFolding()
Return a pass that folds conditional branch jumps.
MachineInstr * removeFromParent()
Unlink &#39;this&#39; from the containing basic block, and return it without deleting it. ...
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416