LLVM  6.0.0svn
HexagonEarlyIfConv.cpp
Go to the documentation of this file.
1 //===- HexagonEarlyIfConv.cpp ---------------------------------------------===//
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 implements a Hexagon-specific if-conversion pass that runs on the
11 // SSA form.
12 // In SSA it is not straightforward to represent instructions that condi-
13 // tionally define registers, since a conditionally-defined register may
14 // only be used under the same condition on which the definition was based.
15 // To avoid complications of this nature, this patch will only generate
16 // predicated stores, and speculate other instructions from the "if-conver-
17 // ted" block.
18 // The code will recognize CFG patterns where a block with a conditional
19 // branch "splits" into a "true block" and a "false block". Either of these
20 // could be omitted (in case of a triangle, for example).
21 // If after conversion of the side block(s) the CFG allows it, the resul-
22 // ting blocks may be merged. If the "join" block contained PHI nodes, they
23 // will be replaced with MUX (or MUX-like) instructions to maintain the
24 // semantics of the PHI.
25 //
26 // Example:
27 //
28 // %vreg40<def> = L2_loadrub_io %vreg39<kill>, 1
29 // %vreg41<def> = S2_tstbit_i %vreg40<kill>, 0
30 // J2_jumpt %vreg41<kill>, <BB#5>, %PC<imp-def,dead>
31 // J2_jump <BB#4>, %PC<imp-def,dead>
32 // Successors according to CFG: BB#4(62) BB#5(62)
33 //
34 // BB#4: derived from LLVM BB %if.then
35 // Predecessors according to CFG: BB#3
36 // %vreg11<def> = A2_addp %vreg6, %vreg10
37 // S2_storerd_io %vreg32, 16, %vreg11
38 // Successors according to CFG: BB#5
39 //
40 // BB#5: derived from LLVM BB %if.end
41 // Predecessors according to CFG: BB#3 BB#4
42 // %vreg12<def> = PHI %vreg6, <BB#3>, %vreg11, <BB#4>
43 // %vreg13<def> = A2_addp %vreg7, %vreg12
44 // %vreg42<def> = C2_cmpeqi %vreg9, 10
45 // J2_jumpf %vreg42<kill>, <BB#3>, %PC<imp-def,dead>
46 // J2_jump <BB#6>, %PC<imp-def,dead>
47 // Successors according to CFG: BB#6(4) BB#3(124)
48 //
49 // would become:
50 //
51 // %vreg40<def> = L2_loadrub_io %vreg39<kill>, 1
52 // %vreg41<def> = S2_tstbit_i %vreg40<kill>, 0
53 // spec-> %vreg11<def> = A2_addp %vreg6, %vreg10
54 // pred-> S2_pstorerdf_io %vreg41, %vreg32, 16, %vreg11
55 // %vreg46<def> = PS_pselect %vreg41, %vreg6, %vreg11
56 // %vreg13<def> = A2_addp %vreg7, %vreg46
57 // %vreg42<def> = C2_cmpeqi %vreg9, 10
58 // J2_jumpf %vreg42<kill>, <BB#3>, %PC<imp-def,dead>
59 // J2_jump <BB#6>, %PC<imp-def,dead>
60 // Successors according to CFG: BB#6 BB#3
61 
62 #include "Hexagon.h"
63 #include "HexagonInstrInfo.h"
64 #include "HexagonSubtarget.h"
65 #include "llvm/ADT/DenseSet.h"
66 #include "llvm/ADT/SmallVector.h"
67 #include "llvm/ADT/StringRef.h"
80 #include "llvm/IR/DebugLoc.h"
81 #include "llvm/Pass.h"
84 #include "llvm/Support/Compiler.h"
85 #include "llvm/Support/Debug.h"
88 #include <cassert>
89 #include <iterator>
90 
91 #define DEBUG_TYPE "hexagon-eif"
92 
93 using namespace llvm;
94 
95 namespace llvm {
96 
99 
100 } // end namespace llvm
101 
102 static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
103  cl::init(false), cl::desc("Enable branch probability info"));
104 static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
105  cl::desc("Size limit in Hexagon early if-conversion"));
106 static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false),
107  cl::Hidden, cl::desc("Do not convert branches that may exit the loop"));
108 
109 namespace {
110 
111  struct PrintMB {
112  PrintMB(const MachineBasicBlock *B) : MB(B) {}
113 
114  const MachineBasicBlock *MB;
115  };
116  raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) {
117  if (!P.MB)
118  return OS << "<none>";
119  return OS << '#' << P.MB->getNumber();
120  }
121 
122  struct FlowPattern {
123  FlowPattern() = default;
124  FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB,
126  : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {}
127 
128  MachineBasicBlock *SplitB = nullptr;
129  MachineBasicBlock *TrueB = nullptr;
130  MachineBasicBlock *FalseB = nullptr;
131  MachineBasicBlock *JoinB = nullptr;
132  unsigned PredR = 0;
133  };
134 
135  struct PrintFP {
136  PrintFP(const FlowPattern &P, const TargetRegisterInfo &T)
137  : FP(P), TRI(T) {}
138 
139  const FlowPattern &FP;
140  const TargetRegisterInfo &TRI;
141  friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P);
142  };
144  const PrintFP &P) LLVM_ATTRIBUTE_UNUSED;
145  raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) {
146  OS << "{ SplitB:" << PrintMB(P.FP.SplitB)
147  << ", PredR:" << PrintReg(P.FP.PredR, &P.TRI)
148  << ", TrueB:" << PrintMB(P.FP.TrueB)
149  << ", FalseB:" << PrintMB(P.FP.FalseB)
150  << ", JoinB:" << PrintMB(P.FP.JoinB) << " }";
151  return OS;
152  }
153 
154  class HexagonEarlyIfConversion : public MachineFunctionPass {
155  public:
156  static char ID;
157 
158  HexagonEarlyIfConversion() : MachineFunctionPass(ID) {}
159 
160  StringRef getPassName() const override {
161  return "Hexagon early if conversion";
162  }
163 
164  void getAnalysisUsage(AnalysisUsage &AU) const override {
170  }
171 
172  bool runOnMachineFunction(MachineFunction &MF) override;
173 
174  private:
175  using BlockSetType = DenseSet<MachineBasicBlock *>;
176 
177  bool isPreheader(const MachineBasicBlock *B) const;
178  bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L,
179  FlowPattern &FP);
180  bool visitBlock(MachineBasicBlock *B, MachineLoop *L);
181  bool visitLoop(MachineLoop *L);
182 
183  bool hasEHLabel(const MachineBasicBlock *B) const;
184  bool hasUncondBranch(const MachineBasicBlock *B) const;
185  bool isValidCandidate(const MachineBasicBlock *B) const;
186  bool usesUndefVReg(const MachineInstr *MI) const;
187  bool isValid(const FlowPattern &FP) const;
188  unsigned countPredicateDefs(const MachineBasicBlock *B) const;
189  unsigned computePhiCost(const MachineBasicBlock *B,
190  const FlowPattern &FP) const;
191  bool isProfitable(const FlowPattern &FP) const;
192  bool isPredicableStore(const MachineInstr *MI) const;
193  bool isSafeToSpeculate(const MachineInstr *MI) const;
194 
195  unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const;
196  void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At,
197  MachineInstr *MI, unsigned PredR, bool IfTrue);
198  void predicateBlockNB(MachineBasicBlock *ToB,
200  unsigned PredR, bool IfTrue);
201 
202  unsigned buildMux(MachineBasicBlock *B, MachineBasicBlock::iterator At,
203  const TargetRegisterClass *DRC, unsigned PredR, unsigned TR,
204  unsigned TSR, unsigned FR, unsigned FSR);
205  void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP);
206  void convert(const FlowPattern &FP);
207 
208  void removeBlock(MachineBasicBlock *B);
209  void eliminatePhis(MachineBasicBlock *B);
210  void replacePhiEdges(MachineBasicBlock *OldB, MachineBasicBlock *NewB);
211  void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB);
212  void simplifyFlowGraph(const FlowPattern &FP);
213 
214  const HexagonInstrInfo *HII = nullptr;
215  const TargetRegisterInfo *TRI = nullptr;
216  MachineFunction *MFN = nullptr;
217  MachineRegisterInfo *MRI = nullptr;
218  MachineDominatorTree *MDT = nullptr;
219  MachineLoopInfo *MLI = nullptr;
220  BlockSetType Deleted;
221  const MachineBranchProbabilityInfo *MBPI;
222  };
223 
224 } // end anonymous namespace
225 
227 
228 INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-early-if",
229  "Hexagon early if conversion", false, false)
230 
231 bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const {
232  if (B->succ_size() != 1)
233  return false;
234  MachineBasicBlock *SB = *B->succ_begin();
235  MachineLoop *L = MLI->getLoopFor(SB);
236  return L && SB == L->getHeader() && MDT->dominates(B, SB);
237 }
238 
239 bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
240  MachineLoop *L, FlowPattern &FP) {
241  DEBUG(dbgs() << "Checking flow pattern at BB#" << B->getNumber() << "\n");
242 
243  // Interested only in conditional branches, no .new, no new-value, etc.
244  // Check the terminators directly, it's easier than handling all responses
245  // from AnalyzeBranch.
246  MachineBasicBlock *TB = nullptr, *FB = nullptr;
248  if (T1I == B->end())
249  return false;
250  unsigned Opc = T1I->getOpcode();
251  if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
252  return false;
253  unsigned PredR = T1I->getOperand(0).getReg();
254 
255  // Get the layout successor, or 0 if B does not have one.
257  MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : nullptr;
258 
259  MachineBasicBlock *T1B = T1I->getOperand(1).getMBB();
260  MachineBasicBlock::const_iterator T2I = std::next(T1I);
261  // The second terminator should be an unconditional branch.
262  assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump);
263  MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
264  : T2I->getOperand(0).getMBB();
265  if (T1B == T2B) {
266  // XXX merge if T1B == NextB, or convert branch to unconditional.
267  // mark as diamond with both sides equal?
268  return false;
269  }
270 
271  // Record the true/false blocks in such a way that "true" means "if (PredR)",
272  // and "false" means "if (!PredR)".
273  if (Opc == Hexagon::J2_jumpt)
274  TB = T1B, FB = T2B;
275  else
276  TB = T2B, FB = T1B;
277 
278  if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
279  return false;
280 
281  // Detect triangle first. In case of a triangle, one of the blocks TB/FB
282  // can fall through into the other, in other words, it will be executed
283  // in both cases. We only want to predicate the block that is executed
284  // conditionally.
285  unsigned TNP = TB->pred_size(), FNP = FB->pred_size();
286  unsigned TNS = TB->succ_size(), FNS = FB->succ_size();
287 
288  // A block is predicable if it has one predecessor (it must be B), and
289  // it has a single successor. In fact, the block has to end either with
290  // an unconditional branch (which can be predicated), or with a fall-
291  // through.
292  // Also, skip blocks that do not belong to the same loop.
293  bool TOk = (TNP == 1 && TNS == 1 && MLI->getLoopFor(TB) == L);
294  bool FOk = (FNP == 1 && FNS == 1 && MLI->getLoopFor(FB) == L);
295 
296  // If requested (via an option), do not consider branches where the
297  // true and false targets do not belong to the same loop.
298  if (SkipExitBranches && MLI->getLoopFor(TB) != MLI->getLoopFor(FB))
299  return false;
300 
301  // If neither is predicable, there is nothing interesting.
302  if (!TOk && !FOk)
303  return false;
304 
305  MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : nullptr;
306  MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : nullptr;
307  MachineBasicBlock *JB = nullptr;
308 
309  if (TOk) {
310  if (FOk) {
311  if (TSB == FSB)
312  JB = TSB;
313  // Diamond: "if (P) then TB; else FB;".
314  } else {
315  // TOk && !FOk
316  if (TSB == FB)
317  JB = FB;
318  FB = nullptr;
319  }
320  } else {
321  // !TOk && FOk (at least one must be true by now).
322  if (FSB == TB)
323  JB = TB;
324  TB = nullptr;
325  }
326  // Don't try to predicate loop preheaders.
327  if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) {
328  DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB)
329  << " is a loop preheader. Skipping.\n");
330  return false;
331  }
332 
333  FP = FlowPattern(B, PredR, TB, FB, JB);
334  DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n");
335  return true;
336 }
337 
338 // KLUDGE: HexagonInstrInfo::AnalyzeBranch won't work on a block that
339 // contains EH_LABEL.
340 bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const {
341  for (auto &I : *B)
342  if (I.isEHLabel())
343  return true;
344  return false;
345 }
346 
347 // KLUDGE: HexagonInstrInfo::AnalyzeBranch may be unable to recognize
348 // that a block can never fall-through.
349 bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B)
350  const {
352  while (I != E) {
353  if (I->isBarrier())
354  return true;
355  ++I;
356  }
357  return false;
358 }
359 
360 bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B)
361  const {
362  if (!B)
363  return true;
364  if (B->isEHPad() || B->hasAddressTaken())
365  return false;
366  if (B->succ_size() == 0)
367  return false;
368 
369  for (auto &MI : *B) {
370  if (MI.isDebugValue())
371  continue;
372  if (MI.isConditionalBranch())
373  return false;
374  unsigned Opc = MI.getOpcode();
375  bool IsJMP = (Opc == Hexagon::J2_jump);
376  if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI))
377  return false;
378  // Look for predicate registers defined by this instruction. It's ok
379  // to speculate such an instruction, but the predicate register cannot
380  // be used outside of this block (or else it won't be possible to
381  // update the use of it after predication). PHI uses will be updated
382  // to use a result of a MUX, and a MUX cannot be created for predicate
383  // registers.
384  for (const MachineOperand &MO : MI.operands()) {
385  if (!MO.isReg() || !MO.isDef())
386  continue;
387  unsigned R = MO.getReg();
389  continue;
390  switch (MRI->getRegClass(R)->getID()) {
391  case Hexagon::PredRegsRegClassID:
392  case Hexagon::HvxQRRegClassID:
393  break;
394  default:
395  continue;
396  }
397  for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U)
398  if (U->getParent()->isPHI())
399  return false;
400  }
401  }
402  return true;
403 }
404 
405 bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const {
406  for (const MachineOperand &MO : MI->operands()) {
407  if (!MO.isReg() || !MO.isUse())
408  continue;
409  unsigned R = MO.getReg();
411  continue;
412  const MachineInstr *DefI = MRI->getVRegDef(R);
413  // "Undefined" virtual registers are actually defined via IMPLICIT_DEF.
414  assert(DefI && "Expecting a reaching def in MRI");
415  if (DefI->isImplicitDef())
416  return true;
417  }
418  return false;
419 }
420 
421 bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const {
422  if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition
423  return false;
424  if (FP.TrueB && !isValidCandidate(FP.TrueB))
425  return false;
426  if (FP.FalseB && !isValidCandidate(FP.FalseB))
427  return false;
428  // Check the PHIs in the join block. If any of them use a register
429  // that is defined as IMPLICIT_DEF, do not convert this. This can
430  // legitimately happen if one side of the split never executes, but
431  // the compiler is unable to prove it. That side may then seem to
432  // provide an "undef" value to the join block, however it will never
433  // execute at run-time. If we convert this case, the "undef" will
434  // be used in a MUX instruction, and that may seem like actually
435  // using an undefined value to other optimizations. This could lead
436  // to trouble further down the optimization stream, cause assertions
437  // to fail, etc.
438  if (FP.JoinB) {
439  const MachineBasicBlock &B = *FP.JoinB;
440  for (auto &MI : B) {
441  if (!MI.isPHI())
442  break;
443  if (usesUndefVReg(&MI))
444  return false;
445  unsigned DefR = MI.getOperand(0).getReg();
446  const TargetRegisterClass *RC = MRI->getRegClass(DefR);
447  if (RC == &Hexagon::PredRegsRegClass)
448  return false;
449  }
450  }
451  return true;
452 }
453 
454 unsigned HexagonEarlyIfConversion::computePhiCost(const MachineBasicBlock *B,
455  const FlowPattern &FP) const {
456  if (B->pred_size() < 2)
457  return 0;
458 
459  unsigned Cost = 0;
460  for (const MachineInstr &MI : *B) {
461  if (!MI.isPHI())
462  break;
463  // If both incoming blocks are one of the TrueB/FalseB/SplitB, then
464  // a MUX may be needed. Otherwise the PHI will need to be updated at
465  // no extra cost.
466  // Find the interesting PHI operands for further checks.
468  for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
469  const MachineBasicBlock *BB = MI.getOperand(i+1).getMBB();
470  if (BB == FP.SplitB || BB == FP.TrueB || BB == FP.FalseB)
471  Inc.push_back(i);
472  }
473  assert(Inc.size() <= 2);
474  if (Inc.size() < 2)
475  continue;
476 
477  const MachineOperand &RA = MI.getOperand(1);
478  const MachineOperand &RB = MI.getOperand(3);
479  assert(RA.isReg() && RB.isReg());
480  // Must have a MUX if the phi uses a subregister.
481  if (RA.getSubReg() != 0 || RB.getSubReg() != 0) {
482  Cost++;
483  continue;
484  }
485  const MachineInstr *Def1 = MRI->getVRegDef(RA.getReg());
486  const MachineInstr *Def3 = MRI->getVRegDef(RB.getReg());
487  if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3))
488  Cost++;
489  }
490  return Cost;
491 }
492 
493 unsigned HexagonEarlyIfConversion::countPredicateDefs(
494  const MachineBasicBlock *B) const {
495  unsigned PredDefs = 0;
496  for (auto &MI : *B) {
497  for (const MachineOperand &MO : MI.operands()) {
498  if (!MO.isReg() || !MO.isDef())
499  continue;
500  unsigned R = MO.getReg();
502  continue;
503  if (MRI->getRegClass(R) == &Hexagon::PredRegsRegClass)
504  PredDefs++;
505  }
506  }
507  return PredDefs;
508 }
509 
510 bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const {
511  if (FP.TrueB && FP.FalseB) {
512  // Do not IfCovert if the branch is one sided.
513  if (MBPI) {
514  BranchProbability Prob(9, 10);
515  if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)
516  return false;
517  if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)
518  return false;
519  }
520 
521  // If both sides are predicable, convert them if they join, and the
522  // join block has no other predecessors.
523  MachineBasicBlock *TSB = *FP.TrueB->succ_begin();
524  MachineBasicBlock *FSB = *FP.FalseB->succ_begin();
525  if (TSB != FSB)
526  return false;
527  if (TSB->pred_size() != 2)
528  return false;
529  }
530 
531  // Calculate the total size of the predicated blocks.
532  // Assume instruction counts without branches to be the approximation of
533  // the code size. If the predicated blocks are smaller than a packet size,
534  // approximate the spare room in the packet that could be filled with the
535  // predicated/speculated instructions.
536  auto TotalCount = [] (const MachineBasicBlock *B, unsigned &Spare) {
537  if (!B)
538  return 0u;
539  unsigned T = std::count_if(B->begin(), B->getFirstTerminator(),
540  [](const MachineInstr &MI) {
541  return !MI.isMetaInstruction();
542  });
543  if (T < HEXAGON_PACKET_SIZE)
544  Spare += HEXAGON_PACKET_SIZE-T;
545  return T;
546  };
547  unsigned Spare = 0;
548  unsigned TotalIn = TotalCount(FP.TrueB, Spare) + TotalCount(FP.FalseB, Spare);
549  DEBUG(dbgs() << "Total number of instructions to be predicated/speculated: "
550  << TotalIn << ", spare room: " << Spare << "\n");
551  if (TotalIn >= SizeLimit+Spare)
552  return false;
553 
554  // Count the number of PHI nodes that will need to be updated (converted
555  // to MUX). Those can be later converted to predicated instructions, so
556  // they aren't always adding extra cost.
557  // KLUDGE: Also, count the number of predicate register definitions in
558  // each block. The scheduler may increase the pressure of these and cause
559  // expensive spills (e.g. bitmnp01).
560  unsigned TotalPh = 0;
561  unsigned PredDefs = countPredicateDefs(FP.SplitB);
562  if (FP.JoinB) {
563  TotalPh = computePhiCost(FP.JoinB, FP);
564  PredDefs += countPredicateDefs(FP.JoinB);
565  } else {
566  if (FP.TrueB && FP.TrueB->succ_size() > 0) {
567  MachineBasicBlock *SB = *FP.TrueB->succ_begin();
568  TotalPh += computePhiCost(SB, FP);
569  PredDefs += countPredicateDefs(SB);
570  }
571  if (FP.FalseB && FP.FalseB->succ_size() > 0) {
572  MachineBasicBlock *SB = *FP.FalseB->succ_begin();
573  TotalPh += computePhiCost(SB, FP);
574  PredDefs += countPredicateDefs(SB);
575  }
576  }
577  DEBUG(dbgs() << "Total number of extra muxes from converted phis: "
578  << TotalPh << "\n");
579  if (TotalIn+TotalPh >= SizeLimit+Spare)
580  return false;
581 
582  DEBUG(dbgs() << "Total number of predicate registers: " << PredDefs << "\n");
583  if (PredDefs > 4)
584  return false;
585 
586  return true;
587 }
588 
589 bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B,
590  MachineLoop *L) {
591  bool Changed = false;
592 
593  // Visit all dominated blocks from the same loop first, then process B.
594  MachineDomTreeNode *N = MDT->getNode(B);
595 
597 
598  // We will change CFG/DT during this traversal, so take precautions to
599  // avoid problems related to invalidated iterators. In fact, processing
600  // a child C of B cannot cause another child to be removed, but it can
601  // cause a new child to be added (which was a child of C before C itself
602  // was removed. This new child C, however, would have been processed
603  // prior to processing B, so there is no need to process it again.
604  // Simply keep a list of children of B, and traverse that list.
605  using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
606  DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
607  for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
608  MachineBasicBlock *SB = (*I)->getBlock();
609  if (!Deleted.count(SB))
610  Changed |= visitBlock(SB, L);
611  }
612  // When walking down the dominator tree, we want to traverse through
613  // blocks from nested (other) loops, because they can dominate blocks
614  // that are in L. Skip the non-L blocks only after the tree traversal.
615  if (MLI->getLoopFor(B) != L)
616  return Changed;
617 
618  FlowPattern FP;
619  if (!matchFlowPattern(B, L, FP))
620  return Changed;
621 
622  if (!isValid(FP)) {
623  DEBUG(dbgs() << "Conversion is not valid\n");
624  return Changed;
625  }
626  if (!isProfitable(FP)) {
627  DEBUG(dbgs() << "Conversion is not profitable\n");
628  return Changed;
629  }
630 
631  convert(FP);
632  simplifyFlowGraph(FP);
633  return true;
634 }
635 
636 bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) {
637  MachineBasicBlock *HB = L ? L->getHeader() : nullptr;
638  DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)
639  : dbgs() << "Visiting function") << "\n");
640  bool Changed = false;
641  if (L) {
642  for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
643  Changed |= visitLoop(*I);
644  }
645 
647  Changed |= visitBlock(L ? HB : EntryB, L);
648  return Changed;
649 }
650 
651 bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
652  const {
653  // HexagonInstrInfo::isPredicable will consider these stores are non-
654  // -predicable if the offset would become constant-extended after
655  // predication.
656  unsigned Opc = MI->getOpcode();
657  switch (Opc) {
658  case Hexagon::S2_storerb_io:
659  case Hexagon::S2_storerbnew_io:
660  case Hexagon::S2_storerh_io:
661  case Hexagon::S2_storerhnew_io:
662  case Hexagon::S2_storeri_io:
663  case Hexagon::S2_storerinew_io:
664  case Hexagon::S2_storerd_io:
665  case Hexagon::S4_storeirb_io:
666  case Hexagon::S4_storeirh_io:
667  case Hexagon::S4_storeiri_io:
668  return true;
669  }
670 
671  // TargetInstrInfo::isPredicable takes a non-const pointer.
672  return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI));
673 }
674 
675 bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
676  const {
677  if (MI->mayLoad() || MI->mayStore())
678  return false;
679  if (MI->isCall() || MI->isBarrier() || MI->isBranch())
680  return false;
681  if (MI->hasUnmodeledSideEffects())
682  return false;
683 
684  return true;
685 }
686 
687 unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
688  bool IfTrue) const {
689  return HII->getCondOpcode(Opc, !IfTrue);
690 }
691 
692 void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
694  unsigned PredR, bool IfTrue) {
695  DebugLoc DL;
696  if (At != ToB->end())
697  DL = At->getDebugLoc();
698  else if (!ToB->empty())
699  DL = ToB->back().getDebugLoc();
700 
701  unsigned Opc = MI->getOpcode();
702 
703  if (isPredicableStore(MI)) {
704  unsigned COpc = getCondStoreOpcode(Opc, IfTrue);
705  assert(COpc);
706  MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc));
708  if (HII->isPostIncrement(*MI)) {
709  MIB.add(*MOI);
710  ++MOI;
711  }
712  MIB.addReg(PredR);
713  for (const MachineOperand &MO : make_range(MOI, MI->operands_end()))
714  MIB.add(MO);
715 
716  // Set memory references.
719  MIB.setMemRefs(MMOBegin, MMOEnd);
720 
721  MI->eraseFromParent();
722  return;
723  }
724 
725  if (Opc == Hexagon::J2_jump) {
727  const MCInstrDesc &D = HII->get(IfTrue ? Hexagon::J2_jumpt
728  : Hexagon::J2_jumpf);
729  BuildMI(*ToB, At, DL, D)
730  .addReg(PredR)
731  .addMBB(TB);
732  MI->eraseFromParent();
733  return;
734  }
735 
736  // Print the offending instruction unconditionally as we are about to
737  // abort.
738  dbgs() << *MI;
739  llvm_unreachable("Unexpected instruction");
740 }
741 
742 // Predicate/speculate non-branch instructions from FromB into block ToB.
743 // Leave the branches alone, they will be handled later. Btw, at this point
744 // FromB should have at most one branch, and it should be unconditional.
745 void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB,
747  unsigned PredR, bool IfTrue) {
748  DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n");
751 
752  for (I = FromB->begin(); I != End; I = NextI) {
753  assert(!I->isPHI());
754  NextI = std::next(I);
755  if (isSafeToSpeculate(&*I))
756  ToB->splice(At, FromB, I);
757  else
758  predicateInstr(ToB, At, &*I, PredR, IfTrue);
759  }
760 }
761 
762 unsigned HexagonEarlyIfConversion::buildMux(MachineBasicBlock *B,
764  unsigned PredR, unsigned TR, unsigned TSR, unsigned FR, unsigned FSR) {
765  unsigned Opc = 0;
766  switch (DRC->getID()) {
767  case Hexagon::IntRegsRegClassID:
768  Opc = Hexagon::C2_mux;
769  break;
770  case Hexagon::DoubleRegsRegClassID:
771  Opc = Hexagon::PS_pselect;
772  break;
773  case Hexagon::HvxVRRegClassID:
774  Opc = Hexagon::PS_vselect;
775  break;
776  case Hexagon::HvxWRRegClassID:
777  Opc = Hexagon::PS_wselect;
778  break;
779  default:
780  llvm_unreachable("unexpected register type");
781  }
782  const MCInstrDesc &D = HII->get(Opc);
783 
784  DebugLoc DL = B->findBranchDebugLoc();
785  unsigned MuxR = MRI->createVirtualRegister(DRC);
786  BuildMI(*B, At, DL, D, MuxR)
787  .addReg(PredR)
788  .addReg(TR, 0, TSR)
789  .addReg(FR, 0, FSR);
790  return MuxR;
791 }
792 
794  const FlowPattern &FP) {
795  // Visit all PHI nodes in the WhereB block and generate MUX instructions
796  // in the split block. Update the PHI nodes with the values of the MUX.
797  auto NonPHI = WhereB->getFirstNonPHI();
798  for (auto I = WhereB->begin(); I != NonPHI; ++I) {
799  MachineInstr *PN = &*I;
800  // Registers and subregisters corresponding to TrueB, FalseB and SplitB.
801  unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0;
802  for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
803  const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1);
804  if (BO.getMBB() == FP.SplitB)
805  SR = RO.getReg(), SSR = RO.getSubReg();
806  else if (BO.getMBB() == FP.TrueB)
807  TR = RO.getReg(), TSR = RO.getSubReg();
808  else if (BO.getMBB() == FP.FalseB)
809  FR = RO.getReg(), FSR = RO.getSubReg();
810  else
811  continue;
812  PN->RemoveOperand(i+1);
813  PN->RemoveOperand(i);
814  }
815  if (TR == 0)
816  TR = SR, TSR = SSR;
817  else if (FR == 0)
818  FR = SR, FSR = SSR;
819 
820  assert(TR || FR);
821  unsigned MuxR = 0, MuxSR = 0;
822 
823  if (TR && FR) {
824  unsigned DR = PN->getOperand(0).getReg();
825  const TargetRegisterClass *RC = MRI->getRegClass(DR);
826  MuxR = buildMux(FP.SplitB, FP.SplitB->getFirstTerminator(), RC,
827  FP.PredR, TR, TSR, FR, FSR);
828  } else if (TR) {
829  MuxR = TR;
830  MuxSR = TSR;
831  } else {
832  MuxR = FR;
833  MuxSR = FSR;
834  }
835 
836  PN->addOperand(MachineOperand::CreateReg(MuxR, false, false, false, false,
837  false, false, MuxSR));
838  PN->addOperand(MachineOperand::CreateMBB(FP.SplitB));
839  }
840 }
841 
842 void HexagonEarlyIfConversion::convert(const FlowPattern &FP) {
843  MachineBasicBlock *TSB = nullptr, *FSB = nullptr;
844  MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator();
845  assert(OldTI != FP.SplitB->end());
846  DebugLoc DL = OldTI->getDebugLoc();
847 
848  if (FP.TrueB) {
849  TSB = *FP.TrueB->succ_begin();
850  predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true);
851  }
852  if (FP.FalseB) {
853  FSB = *FP.FalseB->succ_begin();
854  MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator();
855  predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false);
856  }
857 
858  // Regenerate new terminators in the split block and update the successors.
859  // First, remember any information that may be needed later and remove the
860  // existing terminators/successors from the split block.
861  MachineBasicBlock *SSB = nullptr;
862  FP.SplitB->erase(OldTI, FP.SplitB->end());
863  while (FP.SplitB->succ_size() > 0) {
864  MachineBasicBlock *T = *FP.SplitB->succ_begin();
865  // It's possible that the split block had a successor that is not a pre-
866  // dicated block. This could only happen if there was only one block to
867  // be predicated. Example:
868  // split_b:
869  // if (p) jump true_b
870  // jump unrelated2_b
871  // unrelated1_b:
872  // ...
873  // unrelated2_b: ; can have other predecessors, so it's not "false_b"
874  // jump other_b
875  // true_b: ; only reachable from split_b, can be predicated
876  // ...
877  //
878  // Find this successor (SSB) if it exists.
879  if (T != FP.TrueB && T != FP.FalseB) {
880  assert(!SSB);
881  SSB = T;
882  }
883  FP.SplitB->removeSuccessor(FP.SplitB->succ_begin());
884  }
885 
886  // Insert new branches and update the successors of the split block. This
887  // may create unconditional branches to the layout successor, etc., but
888  // that will be cleaned up later. For now, make sure that correct code is
889  // generated.
890  if (FP.JoinB) {
891  assert(!SSB || SSB == FP.JoinB);
892  BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
893  .addMBB(FP.JoinB);
894  FP.SplitB->addSuccessor(FP.JoinB);
895  } else {
896  bool HasBranch = false;
897  if (TSB) {
898  BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jumpt))
899  .addReg(FP.PredR)
900  .addMBB(TSB);
901  FP.SplitB->addSuccessor(TSB);
902  HasBranch = true;
903  }
904  if (FSB) {
905  const MCInstrDesc &D = HasBranch ? HII->get(Hexagon::J2_jump)
906  : HII->get(Hexagon::J2_jumpf);
907  MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D);
908  if (!HasBranch)
909  MIB.addReg(FP.PredR);
910  MIB.addMBB(FSB);
911  FP.SplitB->addSuccessor(FSB);
912  }
913  if (SSB) {
914  // This cannot happen if both TSB and FSB are set. [TF]SB are the
915  // successor blocks of the TrueB and FalseB (or null of the TrueB
916  // or FalseB block is null). SSB is the potential successor block
917  // of the SplitB that is neither TrueB nor FalseB.
918  BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
919  .addMBB(SSB);
920  FP.SplitB->addSuccessor(SSB);
921  }
922  }
923 
924  // What is left to do is to update the PHI nodes that could have entries
925  // referring to predicated blocks.
926  if (FP.JoinB) {
927  updatePhiNodes(FP.JoinB, FP);
928  } else {
929  if (TSB)
930  updatePhiNodes(TSB, FP);
931  if (FSB)
932  updatePhiNodes(FSB, FP);
933  // Nothing to update in SSB, since SSB's predecessors haven't changed.
934  }
935 }
936 
937 void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) {
938  DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n");
939 
940  // Transfer the immediate dominator information from B to its descendants.
941  MachineDomTreeNode *N = MDT->getNode(B);
942  MachineDomTreeNode *IDN = N->getIDom();
943  if (IDN) {
944  MachineBasicBlock *IDB = IDN->getBlock();
945 
947  using DTNodeVectType = SmallVector<MachineDomTreeNode *, 4>;
948 
949  DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
950  for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
951  MachineBasicBlock *SB = (*I)->getBlock();
952  MDT->changeImmediateDominator(SB, IDB);
953  }
954  }
955 
956  while (B->succ_size() > 0)
957  B->removeSuccessor(B->succ_begin());
958 
959  for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
960  (*I)->removeSuccessor(B, true);
961 
962  Deleted.insert(B);
963  MDT->eraseNode(B);
964  MFN->erase(B->getIterator());
965 }
966 
967 void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) {
968  DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n");
969  MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI();
970  for (I = B->begin(); I != NonPHI; I = NextI) {
971  NextI = std::next(I);
972  MachineInstr *PN = &*I;
973  assert(PN->getNumOperands() == 3 && "Invalid phi node");
974  MachineOperand &UO = PN->getOperand(1);
975  unsigned UseR = UO.getReg(), UseSR = UO.getSubReg();
976  unsigned DefR = PN->getOperand(0).getReg();
977  unsigned NewR = UseR;
978  if (UseSR) {
979  // MRI.replaceVregUsesWith does not allow to update the subregister,
980  // so instead of doing the use-iteration here, create a copy into a
981  // "non-subregistered" register.
982  const DebugLoc &DL = PN->getDebugLoc();
983  const TargetRegisterClass *RC = MRI->getRegClass(DefR);
984  NewR = MRI->createVirtualRegister(RC);
985  NonPHI = BuildMI(*B, NonPHI, DL, HII->get(TargetOpcode::COPY), NewR)
986  .addReg(UseR, 0, UseSR);
987  }
988  MRI->replaceRegWith(DefR, NewR);
989  B->erase(I);
990  }
991 }
992 
993 void HexagonEarlyIfConversion::replacePhiEdges(MachineBasicBlock *OldB,
994  MachineBasicBlock *NewB) {
995  for (auto I = OldB->succ_begin(), E = OldB->succ_end(); I != E; ++I) {
996  MachineBasicBlock *SB = *I;
998  for (P = SB->begin(); P != N; ++P) {
999  MachineInstr &PN = *P;
1000  for (MachineOperand &MO : PN.operands())
1001  if (MO.isMBB() && MO.getMBB() == OldB)
1002  MO.setMBB(NewB);
1003  }
1004  }
1005 }
1006 
1007 void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
1008  MachineBasicBlock *SuccB) {
1009  DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "
1010  << PrintMB(SuccB) << "\n");
1011  bool TermOk = hasUncondBranch(SuccB);
1012  eliminatePhis(SuccB);
1013  HII->removeBranch(*PredB);
1014  PredB->removeSuccessor(SuccB);
1015  PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end());
1017  for (I = SuccB->succ_begin(); I != E; ++I)
1018  PredB->addSuccessor(*I);
1019  PredB->normalizeSuccProbs();
1020  replacePhiEdges(SuccB, PredB);
1021  removeBlock(SuccB);
1022  if (!TermOk)
1023  PredB->updateTerminator();
1024 }
1025 
1026 void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) {
1027  if (FP.TrueB)
1028  removeBlock(FP.TrueB);
1029  if (FP.FalseB)
1030  removeBlock(FP.FalseB);
1031 
1032  FP.SplitB->updateTerminator();
1033  if (FP.SplitB->succ_size() != 1)
1034  return;
1035 
1036  MachineBasicBlock *SB = *FP.SplitB->succ_begin();
1037  if (SB->pred_size() != 1)
1038  return;
1039 
1040  // By now, the split block has only one successor (SB), and SB has only
1041  // one predecessor. We can try to merge them. We will need to update ter-
1042  // minators in FP.Split+SB, and that requires working AnalyzeBranch, which
1043  // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends
1044  // with an unconditional branch, we won't need to touch the terminators.
1045  if (!hasEHLabel(SB) || hasUncondBranch(SB))
1046  mergeBlocks(FP.SplitB, SB);
1047 }
1048 
1049 bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) {
1050  if (skipFunction(*MF.getFunction()))
1051  return false;
1052 
1053  auto &ST = MF.getSubtarget<HexagonSubtarget>();
1054  HII = ST.getInstrInfo();
1055  TRI = ST.getRegisterInfo();
1056  MFN = &MF;
1057  MRI = &MF.getRegInfo();
1058  MDT = &getAnalysis<MachineDominatorTree>();
1059  MLI = &getAnalysis<MachineLoopInfo>();
1060  MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() :
1061  nullptr;
1062 
1063  Deleted.clear();
1064  bool Changed = false;
1065 
1066  for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
1067  Changed |= visitLoop(*I);
1068  Changed |= visitLoop(nullptr);
1069 
1070  return Changed;
1071 }
1072 
1073 //===----------------------------------------------------------------------===//
1074 // Public Constructor Functions
1075 //===----------------------------------------------------------------------===//
1077  return new HexagonEarlyIfConversion();
1078 }
void push_back(const T &Elt)
Definition: SmallVector.h:212
const MachineInstrBuilder & add(const MachineOperand &MO) const
mop_iterator operands_end()
Definition: MachineInstr.h:327
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:458
MachineBasicBlock * getMBB() const
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:268
static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *LandingPadReplacement)
Definition: CoroFrame.cpp:534
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:45
unsigned getSubReg() const
A debug info location.
Definition: DebugLoc.h:34
static cl::opt< bool > SkipExitBranches("eif-no-loop-exit", cl::init(false), cl::Hidden, cl::desc("Do not convert branches that may exit the loop"))
bool isMetaInstruction() const
Return true if this instruction doesn&#39;t produce any output in the form of executable instructions...
Definition: MachineInstr.h:883
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
bool isPHI() const
Definition: MachineInstr.h:826
SI optimize exec mask operations pre RA
AnalysisUsage & addRequired()
A description of a memory reference used in the backend.
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...
static MachineOperand CreateReg(unsigned Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false)
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
#define HEXAGON_PACKET_SIZE
Definition: Hexagon.h:33
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:290
unsigned getID() const
Return the register class ID number.
BlockT * getHeader() const
Definition: LoopInfo.h:100
std::vector< MachineLoop *>::const_iterator iterator
Definition: LoopInfo.h:139
void RemoveOperand(unsigned i)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
#define T
Base class for the actual dominator tree node.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:482
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.
NodeT * getBlock() const
static cl::opt< bool > EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden, cl::init(false), cl::desc("Enable branch probability info"))
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:639
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
FunctionPass * createHexagonEarlyIfConversion()
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
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.
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:144
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
self_iterator getIterator()
Definition: ilist_node.h:82
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
bool isImplicitDef() const
Definition: MachineInstr.h:831
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void initializeHexagonEarlyIfConversionPass(PassRegistry &Registry)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Iterator for intrusive lists based on ilist_node.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:389
MachineOperand class - Representation of each machine instruction operand.
iterator begin() const
Definition: LoopInfo.h:142
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
unsigned succ_size() const
static cl::opt< unsigned > SizeLimit("eif-limit", cl::init(6), cl::Hidden, cl::desc("Size limit in Hexagon early if-conversion"))
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:59
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0)
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
LoopInfoBase< MachineBasicBlock, MachineLoop >::iterator iterator
The iterator interface to the top-level loops in the current function.
iterator end() const
Definition: LoopInfo.h:143
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:626
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
mop_iterator operands_begin()
Definition: MachineInstr.h:326
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:465
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-early-if", "Hexagon early if conversion", false, false) bool HexagonEarlyIfConversion
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0) const
const MachineInstrBuilder & setMemRefs(MachineInstr::mmo_iterator b, MachineInstr::mmo_iterator e) const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
std::vector< MachineBasicBlock * >::iterator succ_iterator
auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< decltype(std::begin(Range))>::difference_type
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:837
mmo_iterator memoperands_end() const
Definition: MachineInstr.h:390