contrib/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp

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