Coverage Report

Created: 2019-07-24 05:18

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