Coverage Report

Created: 2017-10-03 07:32

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