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