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> = MUX64_rr %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#define DEBUG_TYPE "hexagon-eif"
63
64#include "llvm/ADT/DenseSet.h"
65#include "llvm/ADT/SetVector.h"
66#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
67#include "llvm/CodeGen/MachineDominators.h"
68#include "llvm/CodeGen/MachineFunctionPass.h"
69#include "llvm/CodeGen/MachineInstrBuilder.h"
70#include "llvm/CodeGen/MachineLoopInfo.h"
71#include "llvm/CodeGen/MachineRegisterInfo.h"
72#include "llvm/CodeGen/Passes.h"
73#include "llvm/Support/CommandLine.h"
74#include "llvm/Support/Debug.h"
75#include "llvm/Support/raw_ostream.h"
76#include "llvm/Target/TargetInstrInfo.h"
77#include "llvm/Target/TargetMachine.h"
78#include "HexagonTargetMachine.h"
79
80#include <functional>
81
82using namespace llvm;
83
84namespace llvm {
85  FunctionPass *createHexagonEarlyIfConversion();
86  void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry);
87}
88
89namespace {
90  cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
91    cl::init(false), cl::desc("Enable branch probability info"));
92  cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
93    cl::desc("Size limit in Hexagon early if-conversion"));
94
95  struct PrintMB {
96    PrintMB(const MachineBasicBlock *B) : MB(B) {}
97    const MachineBasicBlock *MB;
98  };
99  raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) {
100    if (!P.MB)
101      return OS << "<none>";
102    return OS << '#' << P.MB->getNumber();
103  }
104
105  struct FlowPattern {
106    FlowPattern() : SplitB(0), TrueB(0), FalseB(0), JoinB(0), PredR(0) {}
107    FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB,
108          MachineBasicBlock *FB, MachineBasicBlock *JB)
109      : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {}
110
111    MachineBasicBlock *SplitB;
112    MachineBasicBlock *TrueB, *FalseB, *JoinB;
113    unsigned PredR;
114  };
115  struct PrintFP {
116    PrintFP(const FlowPattern &P, const TargetRegisterInfo &T)
117      : FP(P), TRI(T) {}
118    const FlowPattern &FP;
119    const TargetRegisterInfo &TRI;
120    friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P);
121  };
122  raw_ostream &operator<<(raw_ostream &OS,
123                          const PrintFP &P) LLVM_ATTRIBUTE_UNUSED;
124  raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) {
125    OS << "{ SplitB:" << PrintMB(P.FP.SplitB)
126       << ", PredR:" << PrintReg(P.FP.PredR, &P.TRI)
127       << ", TrueB:" << PrintMB(P.FP.TrueB) << ", FalseB:"
128       << PrintMB(P.FP.FalseB)
129       << ", JoinB:" << PrintMB(P.FP.JoinB) << " }";
130    return OS;
131  }
132
133  class HexagonEarlyIfConversion : public MachineFunctionPass {
134  public:
135    static char ID;
136    HexagonEarlyIfConversion() : MachineFunctionPass(ID),
137        TII(0), TRI(0), MFN(0), MRI(0), MDT(0), MLI(0) {
138      initializeHexagonEarlyIfConversionPass(*PassRegistry::getPassRegistry());
139    }
140    const char *getPassName() const override {
141      return "Hexagon early if conversion";
142    }
143    void getAnalysisUsage(AnalysisUsage &AU) const override {
144      AU.addRequired<MachineBranchProbabilityInfo>();
145      AU.addRequired<MachineDominatorTree>();
146      AU.addPreserved<MachineDominatorTree>();
147      AU.addRequired<MachineLoopInfo>();
148      MachineFunctionPass::getAnalysisUsage(AU);
149    }
150    bool runOnMachineFunction(MachineFunction &MF) override;
151
152  private:
153    typedef DenseSet<MachineBasicBlock*> BlockSetType;
154
155    bool isPreheader(const MachineBasicBlock *B) const;
156    bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L,
157          FlowPattern &FP);
158    bool visitBlock(MachineBasicBlock *B, MachineLoop *L);
159    bool visitLoop(MachineLoop *L);
160
161    bool hasEHLabel(const MachineBasicBlock *B) const;
162    bool hasUncondBranch(const MachineBasicBlock *B) const;
163    bool isValidCandidate(const MachineBasicBlock *B) const;
164    bool usesUndefVReg(const MachineInstr *MI) const;
165    bool isValid(const FlowPattern &FP) const;
166    unsigned countPredicateDefs(const MachineBasicBlock *B) const;
167    unsigned computePhiCost(MachineBasicBlock *B) const;
168    bool isProfitable(const FlowPattern &FP) const;
169    bool isPredicableStore(const MachineInstr *MI) const;
170    bool isSafeToSpeculate(const MachineInstr *MI) const;
171
172    unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const;
173    void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At,
174          MachineInstr *MI, unsigned PredR, bool IfTrue);
175    void predicateBlockNB(MachineBasicBlock *ToB,
176          MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
177          unsigned PredR, bool IfTrue);
178
179    void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP);
180    void convert(const FlowPattern &FP);
181
182    void removeBlock(MachineBasicBlock *B);
183    void eliminatePhis(MachineBasicBlock *B);
184    void replacePhiEdges(MachineBasicBlock *OldB, MachineBasicBlock *NewB);
185    void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB);
186    void simplifyFlowGraph(const FlowPattern &FP);
187
188    const TargetInstrInfo *TII;
189    const TargetRegisterInfo *TRI;
190    MachineFunction *MFN;
191    MachineRegisterInfo *MRI;
192    MachineDominatorTree *MDT;
193    MachineLoopInfo *MLI;
194    BlockSetType Deleted;
195    const MachineBranchProbabilityInfo *MBPI;
196  };
197
198  char HexagonEarlyIfConversion::ID = 0;
199}
200
201INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-eif",
202  "Hexagon early if conversion", false, false)
203
204bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const {
205  if (B->succ_size() != 1)
206    return false;
207  MachineBasicBlock *SB = *B->succ_begin();
208  MachineLoop *L = MLI->getLoopFor(SB);
209  return L && SB == L->getHeader();
210}
211
212
213bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
214    MachineLoop *L, FlowPattern &FP) {
215  DEBUG(dbgs() << "Checking flow pattern at BB#" << B->getNumber() << "\n");
216
217  // Interested only in conditional branches, no .new, no new-value, etc.
218  // Check the terminators directly, it's easier than handling all responses
219  // from AnalyzeBranch.
220  MachineBasicBlock *TB = 0, *FB = 0;
221  MachineBasicBlock::const_iterator T1I = B->getFirstTerminator();
222  if (T1I == B->end())
223    return false;
224  unsigned Opc = T1I->getOpcode();
225  if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
226    return false;
227  unsigned PredR = T1I->getOperand(0).getReg();
228
229  // Get the layout successor, or 0 if B does not have one.
230  MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B));
231  MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : 0;
232
233  MachineBasicBlock *T1B = T1I->getOperand(1).getMBB();
234  MachineBasicBlock::const_iterator T2I = std::next(T1I);
235  // The second terminator should be an unconditional branch.
236  assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump);
237  MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
238                                             : T2I->getOperand(0).getMBB();
239  if (T1B == T2B) {
240    // XXX merge if T1B == NextB, or convert branch to unconditional.
241    // mark as diamond with both sides equal?
242    return false;
243  }
244  // Loop could be null for both.
245  if (MLI->getLoopFor(T1B) != L || MLI->getLoopFor(T2B) != L)
246    return false;
247
248  // Record the true/false blocks in such a way that "true" means "if (PredR)",
249  // and "false" means "if (!PredR)".
250  if (Opc == Hexagon::J2_jumpt)
251    TB = T1B, FB = T2B;
252  else
253    TB = T2B, FB = T1B;
254
255  if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
256    return false;
257
258  // Detect triangle first. In case of a triangle, one of the blocks TB/FB
259  // can fall through into the other, in other words, it will be executed
260  // in both cases. We only want to predicate the block that is executed
261  // conditionally.
262  unsigned TNP = TB->pred_size(), FNP = FB->pred_size();
263  unsigned TNS = TB->succ_size(), FNS = FB->succ_size();
264
265  // A block is predicable if it has one predecessor (it must be B), and
266  // it has a single successor. In fact, the block has to end either with
267  // an unconditional branch (which can be predicated), or with a fall-
268  // through.
269  bool TOk = (TNP == 1) && (TNS == 1);
270  bool FOk = (FNP == 1) && (FNS == 1);
271
272  // If neither is predicable, there is nothing interesting.
273  if (!TOk && !FOk)
274    return false;
275
276  MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : 0;
277  MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : 0;
278  MachineBasicBlock *JB = 0;
279
280  if (TOk) {
281    if (FOk) {
282      if (TSB == FSB)
283        JB = TSB;
284      // Diamond: "if (P) then TB; else FB;".
285    } else {
286      // TOk && !FOk
287      if (TSB == FB) {
288        JB = FB;
289        FB = 0;
290      }
291    }
292  } else {
293    // !TOk && FOk  (at least one must be true by now).
294    if (FSB == TB) {
295      JB = TB;
296      TB = 0;
297    }
298  }
299  // Don't try to predicate loop preheaders.
300  if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) {
301    DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB)
302                 << " is a loop preheader. Skipping.\n");
303    return false;
304  }
305
306  FP = FlowPattern(B, PredR, TB, FB, JB);
307  DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n");
308  return true;
309}
310
311
312// KLUDGE: HexagonInstrInfo::AnalyzeBranch won't work on a block that
313// contains EH_LABEL.
314bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const {
315  for (auto &I : *B)
316    if (I.isEHLabel())
317      return true;
318  return false;
319}
320
321
322// KLUDGE: HexagonInstrInfo::AnalyzeBranch may be unable to recognize
323// that a block can never fall-through.
324bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B)
325      const {
326  MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end();
327  while (I != E) {
328    if (I->isBarrier())
329      return true;
330    ++I;
331  }
332  return false;
333}
334
335
336bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B)
337      const {
338  if (!B)
339    return true;
340  if (B->isEHPad() || B->hasAddressTaken())
341    return false;
342  if (B->succ_size() == 0)
343    return false;
344
345  for (auto &MI : *B) {
346    if (MI.isDebugValue())
347      continue;
348    if (MI.isConditionalBranch())
349      return false;
350    unsigned Opc = MI.getOpcode();
351    bool IsJMP = (Opc == Hexagon::J2_jump);
352    if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI))
353      return false;
354    // Look for predicate registers defined by this instruction. It's ok
355    // to speculate such an instruction, but the predicate register cannot
356    // be used outside of this block (or else it won't be possible to
357    // update the use of it after predication). PHI uses will be updated
358    // to use a result of a MUX, and a MUX cannot be created for predicate
359    // registers.
360    for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
361      if (!MO->isReg() || !MO->isDef())
362        continue;
363      unsigned R = MO->getReg();
364      if (!TargetRegisterInfo::isVirtualRegister(R))
365        continue;
366      if (MRI->getRegClass(R) != &Hexagon::PredRegsRegClass)
367        continue;
368      for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U)
369        if (U->getParent()->isPHI())
370          return false;
371    }
372  }
373  return true;
374}
375
376
377bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const {
378  for (ConstMIOperands MO(*MI); MO.isValid(); ++MO) {
379    if (!MO->isReg() || !MO->isUse())
380      continue;
381    unsigned R = MO->getReg();
382    if (!TargetRegisterInfo::isVirtualRegister(R))
383      continue;
384    const MachineInstr *DefI = MRI->getVRegDef(R);
385    // "Undefined" virtual registers are actually defined via IMPLICIT_DEF.
386    assert(DefI && "Expecting a reaching def in MRI");
387    if (DefI->isImplicitDef())
388      return true;
389  }
390  return false;
391}
392
393
394bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const {
395  if (hasEHLabel(FP.SplitB))  // KLUDGE: see function definition
396    return false;
397  if (FP.TrueB && !isValidCandidate(FP.TrueB))
398    return false;
399  if (FP.FalseB && !isValidCandidate(FP.FalseB))
400    return false;
401  // Check the PHIs in the join block. If any of them use a register
402  // that is defined as IMPLICIT_DEF, do not convert this. This can
403  // legitimately happen if one side of the split never executes, but
404  // the compiler is unable to prove it. That side may then seem to
405  // provide an "undef" value to the join block, however it will never
406  // execute at run-time. If we convert this case, the "undef" will
407  // be used in a MUX instruction, and that may seem like actually
408  // using an undefined value to other optimizations. This could lead
409  // to trouble further down the optimization stream, cause assertions
410  // to fail, etc.
411  if (FP.JoinB) {
412    const MachineBasicBlock &B = *FP.JoinB;
413    for (auto &MI : B) {
414      if (!MI.isPHI())
415        break;
416      if (usesUndefVReg(&MI))
417        return false;
418      unsigned DefR = MI.getOperand(0).getReg();
419      const TargetRegisterClass *RC = MRI->getRegClass(DefR);
420      if (RC == &Hexagon::PredRegsRegClass)
421        return false;
422    }
423  }
424  return true;
425}
426
427
428unsigned HexagonEarlyIfConversion::computePhiCost(MachineBasicBlock *B) const {
429  assert(B->pred_size() <= 2);
430  if (B->pred_size() < 2)
431    return 0;
432
433  unsigned Cost = 0;
434  MachineBasicBlock::const_iterator I, E = B->getFirstNonPHI();
435  for (I = B->begin(); I != E; ++I) {
436    const MachineOperand &RO1 = I->getOperand(1);
437    const MachineOperand &RO3 = I->getOperand(3);
438    assert(RO1.isReg() && RO3.isReg());
439    // Must have a MUX if the phi uses a subregister.
440    if (RO1.getSubReg() != 0 || RO3.getSubReg() != 0) {
441      Cost++;
442      continue;
443    }
444    MachineInstr *Def1 = MRI->getVRegDef(RO1.getReg());
445    MachineInstr *Def3 = MRI->getVRegDef(RO3.getReg());
446    if (!TII->isPredicable(*Def1) || !TII->isPredicable(*Def3))
447      Cost++;
448  }
449  return Cost;
450}
451
452
453unsigned HexagonEarlyIfConversion::countPredicateDefs(
454      const MachineBasicBlock *B) const {
455  unsigned PredDefs = 0;
456  for (auto &MI : *B) {
457    for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
458      if (!MO->isReg() || !MO->isDef())
459        continue;
460      unsigned R = MO->getReg();
461      if (!TargetRegisterInfo::isVirtualRegister(R))
462        continue;
463      if (MRI->getRegClass(R) == &Hexagon::PredRegsRegClass)
464        PredDefs++;
465    }
466  }
467  return PredDefs;
468}
469
470
471bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const {
472  if (FP.TrueB && FP.FalseB) {
473
474    // Do not IfCovert if the branch is one sided.
475    if (MBPI) {
476      BranchProbability Prob(9, 10);
477      if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)
478        return false;
479      if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)
480        return false;
481    }
482
483    // If both sides are predicable, convert them if they join, and the
484    // join block has no other predecessors.
485    MachineBasicBlock *TSB = *FP.TrueB->succ_begin();
486    MachineBasicBlock *FSB = *FP.FalseB->succ_begin();
487    if (TSB != FSB)
488      return false;
489    if (TSB->pred_size() != 2)
490      return false;
491  }
492
493  // Calculate the total size of the predicated blocks.
494  // Assume instruction counts without branches to be the approximation of
495  // the code size. If the predicated blocks are smaller than a packet size,
496  // approximate the spare room in the packet that could be filled with the
497  // predicated/speculated instructions.
498  unsigned TS = 0, FS = 0, Spare = 0;
499  if (FP.TrueB) {
500    TS = std::distance(FP.TrueB->begin(), FP.TrueB->getFirstTerminator());
501    if (TS < HEXAGON_PACKET_SIZE)
502      Spare += HEXAGON_PACKET_SIZE-TS;
503  }
504  if (FP.FalseB) {
505    FS = std::distance(FP.FalseB->begin(), FP.FalseB->getFirstTerminator());
506    if (FS < HEXAGON_PACKET_SIZE)
507      Spare += HEXAGON_PACKET_SIZE-TS;
508  }
509  unsigned TotalIn = TS+FS;
510  DEBUG(dbgs() << "Total number of instructions to be predicated/speculated: "
511               << TotalIn << ", spare room: " << Spare << "\n");
512  if (TotalIn >= SizeLimit+Spare)
513    return false;
514
515  // Count the number of PHI nodes that will need to be updated (converted
516  // to MUX). Those can be later converted to predicated instructions, so
517  // they aren't always adding extra cost.
518  // KLUDGE: Also, count the number of predicate register definitions in
519  // each block. The scheduler may increase the pressure of these and cause
520  // expensive spills (e.g. bitmnp01).
521  unsigned TotalPh = 0;
522  unsigned PredDefs = countPredicateDefs(FP.SplitB);
523  if (FP.JoinB) {
524    TotalPh = computePhiCost(FP.JoinB);
525    PredDefs += countPredicateDefs(FP.JoinB);
526  } else {
527    if (FP.TrueB && FP.TrueB->succ_size() > 0) {
528      MachineBasicBlock *SB = *FP.TrueB->succ_begin();
529      TotalPh += computePhiCost(SB);
530      PredDefs += countPredicateDefs(SB);
531    }
532    if (FP.FalseB && FP.FalseB->succ_size() > 0) {
533      MachineBasicBlock *SB = *FP.FalseB->succ_begin();
534      TotalPh += computePhiCost(SB);
535      PredDefs += countPredicateDefs(SB);
536    }
537  }
538  DEBUG(dbgs() << "Total number of extra muxes from converted phis: "
539               << TotalPh << "\n");
540  if (TotalIn+TotalPh >= SizeLimit+Spare)
541    return false;
542
543  DEBUG(dbgs() << "Total number of predicate registers: " << PredDefs << "\n");
544  if (PredDefs > 4)
545    return false;
546
547  return true;
548}
549
550
551bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B,
552      MachineLoop *L) {
553  bool Changed = false;
554
555  // Visit all dominated blocks from the same loop first, then process B.
556  MachineDomTreeNode *N = MDT->getNode(B);
557  typedef GraphTraits<MachineDomTreeNode*> GTN;
558  // We will change CFG/DT during this traversal, so take precautions to
559  // avoid problems related to invalidated iterators. In fact, processing
560  // a child C of B cannot cause another child to be removed, but it can
561  // cause a new child to be added (which was a child of C before C itself
562  // was removed. This new child C, however, would have been processed
563  // prior to processing B, so there is no need to process it again.
564  // Simply keep a list of children of B, and traverse that list.
565  typedef SmallVector<MachineDomTreeNode*,4> DTNodeVectType;
566  DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
567  for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
568    MachineBasicBlock *SB = (*I)->getBlock();
569    if (!Deleted.count(SB))
570      Changed |= visitBlock(SB, L);
571  }
572  // When walking down the dominator tree, we want to traverse through
573  // blocks from nested (other) loops, because they can dominate blocks
574  // that are in L. Skip the non-L blocks only after the tree traversal.
575  if (MLI->getLoopFor(B) != L)
576    return Changed;
577
578  FlowPattern FP;
579  if (!matchFlowPattern(B, L, FP))
580    return Changed;
581
582  if (!isValid(FP)) {
583    DEBUG(dbgs() << "Conversion is not valid\n");
584    return Changed;
585  }
586  if (!isProfitable(FP)) {
587    DEBUG(dbgs() << "Conversion is not profitable\n");
588    return Changed;
589  }
590
591  convert(FP);
592  simplifyFlowGraph(FP);
593  return true;
594}
595
596
597bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) {
598  MachineBasicBlock *HB = L ? L->getHeader() : 0;
599  DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)
600           : dbgs() << "Visiting function") << "\n");
601  bool Changed = false;
602  if (L) {
603    for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
604      Changed |= visitLoop(*I);
605  }
606
607  MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN);
608  Changed |= visitBlock(L ? HB : EntryB, L);
609  return Changed;
610}
611
612
613bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
614      const {
615  // Exclude post-increment stores. Those return a value, so we cannot
616  // predicate them.
617  unsigned Opc = MI->getOpcode();
618  using namespace Hexagon;
619  switch (Opc) {
620    // Store byte:
621    case S2_storerb_io: case S4_storerb_rr:
622    case S2_storerbabs: case S4_storeirb_io:  case S2_storerbgp:
623    // Store halfword:
624    case S2_storerh_io: case S4_storerh_rr:
625    case S2_storerhabs: case S4_storeirh_io:  case S2_storerhgp:
626    // Store upper halfword:
627    case S2_storerf_io: case S4_storerf_rr:
628    case S2_storerfabs: case S2_storerfgp:
629    // Store word:
630    case S2_storeri_io: case S4_storeri_rr:
631    case S2_storeriabs: case S4_storeiri_io:  case S2_storerigp:
632    // Store doubleword:
633    case S2_storerd_io: case S4_storerd_rr:
634    case S2_storerdabs: case S2_storerdgp:
635      return true;
636  }
637  return false;
638}
639
640
641bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
642      const {
643  if (MI->mayLoad() || MI->mayStore())
644    return false;
645  if (MI->isCall() || MI->isBarrier() || MI->isBranch())
646    return false;
647  if (MI->hasUnmodeledSideEffects())
648    return false;
649
650  return true;
651}
652
653
654unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
655      bool IfTrue) const {
656  // Exclude post-increment stores.
657  using namespace Hexagon;
658  switch (Opc) {
659    case S2_storerb_io:
660      return IfTrue ? S2_pstorerbt_io : S2_pstorerbf_io;
661    case S4_storerb_rr:
662      return IfTrue ? S4_pstorerbt_rr : S4_pstorerbf_rr;
663    case S2_storerbabs:
664    case S2_storerbgp:
665      return IfTrue ? S4_pstorerbt_abs : S4_pstorerbf_abs;
666    case S4_storeirb_io:
667      return IfTrue ? S4_storeirbt_io : S4_storeirbf_io;
668    case S2_storerh_io:
669      return IfTrue ? S2_pstorerht_io : S2_pstorerhf_io;
670    case S4_storerh_rr:
671      return IfTrue ? S4_pstorerht_rr : S4_pstorerhf_rr;
672    case S2_storerhabs:
673    case S2_storerhgp:
674      return IfTrue ? S4_pstorerht_abs : S4_pstorerhf_abs;
675    case S2_storerf_io:
676      return IfTrue ? S2_pstorerft_io : S2_pstorerff_io;
677    case S4_storerf_rr:
678      return IfTrue ? S4_pstorerft_rr : S4_pstorerff_rr;
679    case S2_storerfabs:
680    case S2_storerfgp:
681      return IfTrue ? S4_pstorerft_abs : S4_pstorerff_abs;
682    case S4_storeirh_io:
683      return IfTrue ? S4_storeirht_io : S4_storeirhf_io;
684    case S2_storeri_io:
685      return IfTrue ? S2_pstorerit_io : S2_pstorerif_io;
686    case S4_storeri_rr:
687      return IfTrue ? S4_pstorerit_rr : S4_pstorerif_rr;
688    case S2_storeriabs:
689    case S2_storerigp:
690      return IfTrue ? S4_pstorerit_abs : S4_pstorerif_abs;
691    case S4_storeiri_io:
692      return IfTrue ? S4_storeirit_io : S4_storeirif_io;
693    case S2_storerd_io:
694      return IfTrue ? S2_pstorerdt_io : S2_pstorerdf_io;
695    case S4_storerd_rr:
696      return IfTrue ? S4_pstorerdt_rr : S4_pstorerdf_rr;
697    case S2_storerdabs:
698    case S2_storerdgp:
699      return IfTrue ? S4_pstorerdt_abs : S4_pstorerdf_abs;
700  }
701  llvm_unreachable("Unexpected opcode");
702  return 0;
703}
704
705
706void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
707      MachineBasicBlock::iterator At, MachineInstr *MI,
708      unsigned PredR, bool IfTrue) {
709  DebugLoc DL;
710  if (At != ToB->end())
711    DL = At->getDebugLoc();
712  else if (!ToB->empty())
713    DL = ToB->back().getDebugLoc();
714
715  unsigned Opc = MI->getOpcode();
716
717  if (isPredicableStore(MI)) {
718    unsigned COpc = getCondStoreOpcode(Opc, IfTrue);
719    assert(COpc);
720    MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, TII->get(COpc))
721      .addReg(PredR);
722    for (MIOperands MO(*MI); MO.isValid(); ++MO)
723      MIB.addOperand(*MO);
724
725    // Set memory references.
726    MachineInstr::mmo_iterator MMOBegin = MI->memoperands_begin();
727    MachineInstr::mmo_iterator MMOEnd = MI->memoperands_end();
728    MIB.setMemRefs(MMOBegin, MMOEnd);
729
730    MI->eraseFromParent();
731    return;
732  }
733
734  if (Opc == Hexagon::J2_jump) {
735    MachineBasicBlock *TB = MI->getOperand(0).getMBB();
736    const MCInstrDesc &D = TII->get(IfTrue ? Hexagon::J2_jumpt
737                                           : Hexagon::J2_jumpf);
738    BuildMI(*ToB, At, DL, D)
739      .addReg(PredR)
740      .addMBB(TB);
741    MI->eraseFromParent();
742    return;
743  }
744
745  // Print the offending instruction unconditionally as we are about to
746  // abort.
747  dbgs() << *MI;
748  llvm_unreachable("Unexpected instruction");
749}
750
751
752// Predicate/speculate non-branch instructions from FromB into block ToB.
753// Leave the branches alone, they will be handled later. Btw, at this point
754// FromB should have at most one branch, and it should be unconditional.
755void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB,
756      MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
757      unsigned PredR, bool IfTrue) {
758  DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n");
759  MachineBasicBlock::iterator End = FromB->getFirstTerminator();
760  MachineBasicBlock::iterator I, NextI;
761
762  for (I = FromB->begin(); I != End; I = NextI) {
763    assert(!I->isPHI());
764    NextI = std::next(I);
765    if (isSafeToSpeculate(&*I))
766      ToB->splice(At, FromB, I);
767    else
768      predicateInstr(ToB, At, &*I, PredR, IfTrue);
769  }
770}
771
772
773void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB,
774      const FlowPattern &FP) {
775  // Visit all PHI nodes in the WhereB block and generate MUX instructions
776  // in the split block. Update the PHI nodes with the values of the MUX.
777  auto NonPHI = WhereB->getFirstNonPHI();
778  for (auto I = WhereB->begin(); I != NonPHI; ++I) {
779    MachineInstr *PN = &*I;
780    // Registers and subregisters corresponding to TrueB, FalseB and SplitB.
781    unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0;
782    for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
783      const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1);
784      if (BO.getMBB() == FP.SplitB)
785        SR = RO.getReg(), SSR = RO.getSubReg();
786      else if (BO.getMBB() == FP.TrueB)
787        TR = RO.getReg(), TSR = RO.getSubReg();
788      else if (BO.getMBB() == FP.FalseB)
789        FR = RO.getReg(), FSR = RO.getSubReg();
790      else
791        continue;
792      PN->RemoveOperand(i+1);
793      PN->RemoveOperand(i);
794    }
795    if (TR == 0)
796      TR = SR, TSR = SSR;
797    else if (FR == 0)
798      FR = SR, FSR = SSR;
799    assert(TR && FR);
800
801    using namespace Hexagon;
802    unsigned DR = PN->getOperand(0).getReg();
803    const TargetRegisterClass *RC = MRI->getRegClass(DR);
804    const MCInstrDesc &D = RC == &IntRegsRegClass ? TII->get(C2_mux)
805                                                  : TII->get(MUX64_rr);
806
807    MachineBasicBlock::iterator MuxAt = FP.SplitB->getFirstTerminator();
808    DebugLoc DL;
809    if (MuxAt != FP.SplitB->end())
810      DL = MuxAt->getDebugLoc();
811    unsigned MuxR = MRI->createVirtualRegister(RC);
812    BuildMI(*FP.SplitB, MuxAt, DL, D, MuxR)
813      .addReg(FP.PredR)
814      .addReg(TR, 0, TSR)
815      .addReg(FR, 0, FSR);
816
817    PN->addOperand(MachineOperand::CreateReg(MuxR, false));
818    PN->addOperand(MachineOperand::CreateMBB(FP.SplitB));
819  }
820}
821
822
823void HexagonEarlyIfConversion::convert(const FlowPattern &FP) {
824  MachineBasicBlock *TSB = 0, *FSB = 0;
825  MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator();
826  assert(OldTI != FP.SplitB->end());
827  DebugLoc DL = OldTI->getDebugLoc();
828
829  if (FP.TrueB) {
830    TSB = *FP.TrueB->succ_begin();
831    predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true);
832  }
833  if (FP.FalseB) {
834    FSB = *FP.FalseB->succ_begin();
835    MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator();
836    predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false);
837  }
838
839  // Regenerate new terminators in the split block and update the successors.
840  // First, remember any information that may be needed later and remove the
841  // existing terminators/successors from the split block.
842  MachineBasicBlock *SSB = 0;
843  FP.SplitB->erase(OldTI, FP.SplitB->end());
844  while (FP.SplitB->succ_size() > 0) {
845    MachineBasicBlock *T = *FP.SplitB->succ_begin();
846    // It's possible that the split block had a successor that is not a pre-
847    // dicated block. This could only happen if there was only one block to
848    // be predicated. Example:
849    //   split_b:
850    //     if (p) jump true_b
851    //     jump unrelated2_b
852    //   unrelated1_b:
853    //     ...
854    //   unrelated2_b:  ; can have other predecessors, so it's not "false_b"
855    //     jump other_b
856    //   true_b:        ; only reachable from split_b, can be predicated
857    //     ...
858    //
859    // Find this successor (SSB) if it exists.
860    if (T != FP.TrueB && T != FP.FalseB) {
861      assert(!SSB);
862      SSB = T;
863    }
864    FP.SplitB->removeSuccessor(FP.SplitB->succ_begin());
865  }
866
867  // Insert new branches and update the successors of the split block. This
868  // may create unconditional branches to the layout successor, etc., but
869  // that will be cleaned up later. For now, make sure that correct code is
870  // generated.
871  if (FP.JoinB) {
872    assert(!SSB || SSB == FP.JoinB);
873    BuildMI(*FP.SplitB, FP.SplitB->end(), DL, TII->get(Hexagon::J2_jump))
874      .addMBB(FP.JoinB);
875    FP.SplitB->addSuccessor(FP.JoinB);
876  } else {
877    bool HasBranch = false;
878    if (TSB) {
879      BuildMI(*FP.SplitB, FP.SplitB->end(), DL, TII->get(Hexagon::J2_jumpt))
880        .addReg(FP.PredR)
881        .addMBB(TSB);
882      FP.SplitB->addSuccessor(TSB);
883      HasBranch = true;
884    }
885    if (FSB) {
886      const MCInstrDesc &D = HasBranch ? TII->get(Hexagon::J2_jump)
887                                       : TII->get(Hexagon::J2_jumpf);
888      MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D);
889      if (!HasBranch)
890        MIB.addReg(FP.PredR);
891      MIB.addMBB(FSB);
892      FP.SplitB->addSuccessor(FSB);
893    }
894    if (SSB) {
895      // This cannot happen if both TSB and FSB are set. [TF]SB are the
896      // successor blocks of the TrueB and FalseB (or null of the TrueB
897      // or FalseB block is null). SSB is the potential successor block
898      // of the SplitB that is neither TrueB nor FalseB.
899      BuildMI(*FP.SplitB, FP.SplitB->end(), DL, TII->get(Hexagon::J2_jump))
900        .addMBB(SSB);
901      FP.SplitB->addSuccessor(SSB);
902    }
903  }
904
905  // What is left to do is to update the PHI nodes that could have entries
906  // referring to predicated blocks.
907  if (FP.JoinB) {
908    updatePhiNodes(FP.JoinB, FP);
909  } else {
910    if (TSB)
911      updatePhiNodes(TSB, FP);
912    if (FSB)
913      updatePhiNodes(FSB, FP);
914    // Nothing to update in SSB, since SSB's predecessors haven't changed.
915  }
916}
917
918
919void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) {
920  DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n");
921
922  // Transfer the immediate dominator information from B to its descendants.
923  MachineDomTreeNode *N = MDT->getNode(B);
924  MachineDomTreeNode *IDN = N->getIDom();
925  if (IDN) {
926    MachineBasicBlock *IDB = IDN->getBlock();
927    typedef GraphTraits<MachineDomTreeNode*> GTN;
928    typedef SmallVector<MachineDomTreeNode*,4> DTNodeVectType;
929    DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
930    for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
931      MachineBasicBlock *SB = (*I)->getBlock();
932      MDT->changeImmediateDominator(SB, IDB);
933    }
934  }
935
936  while (B->succ_size() > 0)
937    B->removeSuccessor(B->succ_begin());
938
939  for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
940    (*I)->removeSuccessor(B, true);
941
942  Deleted.insert(B);
943  MDT->eraseNode(B);
944  MFN->erase(B->getIterator());
945}
946
947
948void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) {
949  DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n");
950  MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI();
951  for (I = B->begin(); I != NonPHI; I = NextI) {
952    NextI = std::next(I);
953    MachineInstr *PN = &*I;
954    assert(PN->getNumOperands() == 3 && "Invalid phi node");
955    MachineOperand &UO = PN->getOperand(1);
956    unsigned UseR = UO.getReg(), UseSR = UO.getSubReg();
957    unsigned DefR = PN->getOperand(0).getReg();
958    unsigned NewR = UseR;
959    if (UseSR) {
960      // MRI.replaceVregUsesWith does not allow to update the subregister,
961      // so instead of doing the use-iteration here, create a copy into a
962      // "non-subregistered" register.
963      const DebugLoc &DL = PN->getDebugLoc();
964      const TargetRegisterClass *RC = MRI->getRegClass(DefR);
965      NewR = MRI->createVirtualRegister(RC);
966      NonPHI = BuildMI(*B, NonPHI, DL, TII->get(TargetOpcode::COPY), NewR)
967        .addReg(UseR, 0, UseSR);
968    }
969    MRI->replaceRegWith(DefR, NewR);
970    B->erase(I);
971  }
972}
973
974
975void HexagonEarlyIfConversion::replacePhiEdges(MachineBasicBlock *OldB,
976      MachineBasicBlock *NewB) {
977  for (auto I = OldB->succ_begin(), E = OldB->succ_end(); I != E; ++I) {
978    MachineBasicBlock *SB = *I;
979    MachineBasicBlock::iterator P, N = SB->getFirstNonPHI();
980    for (P = SB->begin(); P != N; ++P) {
981      MachineInstr &PN = *P;
982      for (MIOperands MO(PN); MO.isValid(); ++MO)
983        if (MO->isMBB() && MO->getMBB() == OldB)
984          MO->setMBB(NewB);
985    }
986  }
987}
988
989
990void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
991      MachineBasicBlock *SuccB) {
992  DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "
993               << PrintMB(SuccB) << "\n");
994  bool TermOk = hasUncondBranch(SuccB);
995  eliminatePhis(SuccB);
996  TII->RemoveBranch(*PredB);
997  PredB->removeSuccessor(SuccB);
998  PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end());
999  MachineBasicBlock::succ_iterator I, E = SuccB->succ_end();
1000  for (I = SuccB->succ_begin(); I != E; ++I)
1001    PredB->addSuccessor(*I);
1002  PredB->normalizeSuccProbs();
1003  replacePhiEdges(SuccB, PredB);
1004  removeBlock(SuccB);
1005  if (!TermOk)
1006    PredB->updateTerminator();
1007}
1008
1009
1010void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) {
1011  if (FP.TrueB)
1012    removeBlock(FP.TrueB);
1013  if (FP.FalseB)
1014    removeBlock(FP.FalseB);
1015
1016  FP.SplitB->updateTerminator();
1017  if (FP.SplitB->succ_size() != 1)
1018    return;
1019
1020  MachineBasicBlock *SB = *FP.SplitB->succ_begin();
1021  if (SB->pred_size() != 1)
1022    return;
1023
1024  // By now, the split block has only one successor (SB), and SB has only
1025  // one predecessor. We can try to merge them. We will need to update ter-
1026  // minators in FP.Split+SB, and that requires working AnalyzeBranch, which
1027  // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends
1028  // with an unconditional branch, we won't need to touch the terminators.
1029  if (!hasEHLabel(SB) || hasUncondBranch(SB))
1030    mergeBlocks(FP.SplitB, SB);
1031}
1032
1033
1034bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) {
1035  if (skipFunction(*MF.getFunction()))
1036    return false;
1037
1038  auto &ST = MF.getSubtarget();
1039  TII = ST.getInstrInfo();
1040  TRI = ST.getRegisterInfo();
1041  MFN = &MF;
1042  MRI = &MF.getRegInfo();
1043  MDT = &getAnalysis<MachineDominatorTree>();
1044  MLI = &getAnalysis<MachineLoopInfo>();
1045  MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() :
1046    nullptr;
1047
1048  Deleted.clear();
1049  bool Changed = false;
1050
1051  for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
1052    Changed |= visitLoop(*I);
1053  Changed |= visitLoop(0);
1054
1055  return Changed;
1056}
1057
1058//===----------------------------------------------------------------------===//
1059//                         Public Constructor Functions
1060//===----------------------------------------------------------------------===//
1061FunctionPass *llvm::createHexagonEarlyIfConversion() {
1062  return new HexagonEarlyIfConversion();
1063}
1064
1065