Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/PowerPC/PPCReduceCRLogicals.cpp
Line
Count
Source (jump to first uncovered line)
1
//===---- PPCReduceCRLogicals.cpp - Reduce CR Bit Logical operations ------===//
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 pass aims to reduce the number of logical operations on bits in the CR
10
// register. These instructions have a fairly high latency and only a single
11
// pipeline at their disposal in modern PPC cores. Furthermore, they have a
12
// tendency to occur in fairly small blocks where there's little opportunity
13
// to hide the latency between the CR logical operation and its user.
14
//
15
//===---------------------------------------------------------------------===//
16
17
#include "PPC.h"
18
#include "PPCInstrInfo.h"
19
#include "PPCTargetMachine.h"
20
#include "llvm/ADT/Statistic.h"
21
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
22
#include "llvm/CodeGen/MachineDominators.h"
23
#include "llvm/CodeGen/MachineFunctionPass.h"
24
#include "llvm/CodeGen/MachineInstrBuilder.h"
25
#include "llvm/CodeGen/MachineRegisterInfo.h"
26
#include "llvm/Config/llvm-config.h"
27
#include "llvm/Support/Debug.h"
28
29
using namespace llvm;
30
31
#define DEBUG_TYPE "ppc-reduce-cr-ops"
32
33
STATISTIC(NumContainedSingleUseBinOps,
34
          "Number of single-use binary CR logical ops contained in a block");
35
STATISTIC(NumToSplitBlocks,
36
          "Number of binary CR logical ops that can be used to split blocks");
37
STATISTIC(TotalCRLogicals, "Number of CR logical ops.");
38
STATISTIC(TotalNullaryCRLogicals,
39
          "Number of nullary CR logical ops (CRSET/CRUNSET).");
40
STATISTIC(TotalUnaryCRLogicals, "Number of unary CR logical ops.");
41
STATISTIC(TotalBinaryCRLogicals, "Number of CR logical ops.");
42
STATISTIC(NumBlocksSplitOnBinaryCROp,
43
          "Number of blocks split on CR binary logical ops.");
44
STATISTIC(NumNotSplitIdenticalOperands,
45
          "Number of blocks not split due to operands being identical.");
46
STATISTIC(NumNotSplitChainCopies,
47
          "Number of blocks not split due to operands being chained copies.");
48
STATISTIC(NumNotSplitWrongOpcode,
49
          "Number of blocks not split due to the wrong opcode.");
50
51
/// Given a basic block \p Successor that potentially contains PHIs, this
52
/// function will look for any incoming values in the PHIs that are supposed to
53
/// be coming from \p OrigMBB but whose definition is actually in \p NewMBB.
54
/// Any such PHIs will be updated to reflect reality.
55
static void updatePHIs(MachineBasicBlock *Successor, MachineBasicBlock *OrigMBB,
56
234
                       MachineBasicBlock *NewMBB, MachineRegisterInfo *MRI) {
57
384
  for (auto &MI : Successor->instrs()) {
58
384
    if (!MI.isPHI())
59
272
      continue;
60
112
    // This is a really ugly-looking loop, but it was pillaged directly from
61
112
    // MachineBasicBlock::transferSuccessorsAndUpdatePHIs().
62
240
    
for (unsigned i = 2, e = MI.getNumOperands() + 1; 112
i != e;
i += 2128
) {
63
184
      MachineOperand &MO = MI.getOperand(i);
64
184
      if (MO.getMBB() == OrigMBB) {
65
112
        // Check if the instruction is actually defined in NewMBB.
66
112
        if (MI.getOperand(i - 1).isReg()) {
67
112
          MachineInstr *DefMI = MRI->getVRegDef(MI.getOperand(i - 1).getReg());
68
112
          if (DefMI->getParent() == NewMBB ||
69
112
              !OrigMBB->isSuccessor(Successor)) {
70
56
            MO.setMBB(NewMBB);
71
56
            break;
72
56
          }
73
112
        }
74
112
      }
75
184
    }
76
112
  }
77
234
}
78
79
/// Given a basic block \p Successor that potentially contains PHIs, this
80
/// function will look for PHIs that have an incoming value from \p OrigMBB
81
/// and will add the same incoming value from \p NewMBB.
82
/// NOTE: This should only be used if \p NewMBB is an immediate dominator of
83
/// \p OrigMBB.
84
static void addIncomingValuesToPHIs(MachineBasicBlock *Successor,
85
                                    MachineBasicBlock *OrigMBB,
86
                                    MachineBasicBlock *NewMBB,
87
117
                                    MachineRegisterInfo *MRI) {
88
117
  assert(OrigMBB->isSuccessor(NewMBB) &&
89
117
         "NewMBB must be a successor of OrigMBB");
90
195
  for (auto &MI : Successor->instrs()) {
91
195
    if (!MI.isPHI())
92
139
      continue;
93
56
    // This is a really ugly-looking loop, but it was pillaged directly from
94
56
    // MachineBasicBlock::transferSuccessorsAndUpdatePHIs().
95
72
    
for (unsigned i = 2, e = MI.getNumOperands() + 1; 56
i != e;
i += 216
) {
96
72
      MachineOperand &MO = MI.getOperand(i);
97
72
      if (MO.getMBB() == OrigMBB) {
98
56
        MachineInstrBuilder MIB(*MI.getParent()->getParent(), &MI);
99
56
        MIB.addReg(MI.getOperand(i - 1).getReg()).addMBB(NewMBB);
100
56
        break;
101
56
      }
102
72
    }
103
56
  }
104
117
}
105
106
struct BlockSplitInfo {
107
  MachineInstr *OrigBranch;
108
  MachineInstr *SplitBefore;
109
  MachineInstr *SplitCond;
110
  bool InvertNewBranch;
111
  bool InvertOrigBranch;
112
  bool BranchToFallThrough;
113
  const MachineBranchProbabilityInfo *MBPI;
114
  MachineInstr *MIToDelete;
115
  MachineInstr *NewCond;
116
0
  bool allInstrsInSameMBB() {
117
0
    if (!OrigBranch || !SplitBefore || !SplitCond)
118
0
      return false;
119
0
    MachineBasicBlock *MBB = OrigBranch->getParent();
120
0
    if (SplitBefore->getParent() != MBB || SplitCond->getParent() != MBB)
121
0
      return false;
122
0
    if (MIToDelete && MIToDelete->getParent() != MBB)
123
0
      return false;
124
0
    if (NewCond && NewCond->getParent() != MBB)
125
0
      return false;
126
0
    return true;
127
0
  }
128
};
129
130
/// Splits a MachineBasicBlock to branch before \p SplitBefore. The original
131
/// branch is \p OrigBranch. The target of the new branch can either be the same
132
/// as the target of the original branch or the fallthrough successor of the
133
/// original block as determined by \p BranchToFallThrough. The branch
134
/// conditions will be inverted according to \p InvertNewBranch and
135
/// \p InvertOrigBranch. If an instruction that previously fed the branch is to
136
/// be deleted, it is provided in \p MIToDelete and \p NewCond will be used as
137
/// the branch condition. The branch probabilities will be set if the
138
/// MachineBranchProbabilityInfo isn't null.
139
117
static bool splitMBB(BlockSplitInfo &BSI) {
140
117
  assert(BSI.allInstrsInSameMBB() &&
141
117
         "All instructions must be in the same block.");
142
117
143
117
  MachineBasicBlock *ThisMBB = BSI.OrigBranch->getParent();
144
117
  MachineFunction *MF = ThisMBB->getParent();
145
117
  MachineRegisterInfo *MRI = &MF->getRegInfo();
146
117
  assert(MRI->isSSA() && "Can only do this while the function is in SSA form.");
147
117
  if (ThisMBB->succ_size() != 2) {
148
0
    LLVM_DEBUG(
149
0
        dbgs() << "Don't know how to handle blocks that don't have exactly"
150
0
               << " two successors.\n");
151
0
    return false;
152
0
  }
153
117
154
117
  const PPCInstrInfo *TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
155
117
  unsigned OrigBROpcode = BSI.OrigBranch->getOpcode();
156
117
  unsigned InvertedOpcode =
157
117
      OrigBROpcode == PPC::BC
158
117
          ? PPC::BCn
159
117
          : OrigBROpcode == PPC::BCn
160
0
                ? PPC::BC
161
0
                : OrigBROpcode == PPC::BCLR ? PPC::BCLRn : PPC::BCLR;
162
117
  unsigned NewBROpcode = BSI.InvertNewBranch ? 
InvertedOpcode56
:
OrigBROpcode61
;
163
117
  MachineBasicBlock *OrigTarget = BSI.OrigBranch->getOperand(1).getMBB();
164
117
  MachineBasicBlock *OrigFallThrough = OrigTarget == *ThisMBB->succ_begin()
165
117
                                           ? 
*ThisMBB->succ_rbegin()81
166
117
                                           : 
*ThisMBB->succ_begin()36
;
167
117
  MachineBasicBlock *NewBRTarget =
168
117
      BSI.BranchToFallThrough ? 
OrigFallThrough56
:
OrigTarget61
;
169
117
170
117
  // It's impossible to know the precise branch probability after the split.
171
117
  // But it still needs to be reasonable, the whole probability to original
172
117
  // targets should not be changed.
173
117
  // After split NewBRTarget will get two incoming edges. Assume P0 is the
174
117
  // original branch probability to NewBRTarget, P1 and P2 are new branch
175
117
  // probabilies to NewBRTarget after split. If the two edge frequencies are
176
117
  // same, then
177
117
  //      F * P1 = F * P0 / 2            ==>  P1 = P0 / 2
178
117
  //      F * (1 - P1) * P2 = F * P1     ==>  P2 = P1 / (1 - P1)
179
117
  BranchProbability ProbToNewTarget, ProbFallThrough;     // Prob for new Br.
180
117
  BranchProbability ProbOrigTarget, ProbOrigFallThrough;  // Prob for orig Br.
181
117
  ProbToNewTarget = ProbFallThrough = BranchProbability::getUnknown();
182
117
  ProbOrigTarget = ProbOrigFallThrough = BranchProbability::getUnknown();
183
117
  if (BSI.MBPI) {
184
117
    if (BSI.BranchToFallThrough) {
185
56
      ProbToNewTarget = BSI.MBPI->getEdgeProbability(ThisMBB, OrigFallThrough) / 2;
186
56
      ProbFallThrough = ProbToNewTarget.getCompl();
187
56
      ProbOrigFallThrough = ProbToNewTarget / ProbToNewTarget.getCompl();
188
56
      ProbOrigTarget = ProbOrigFallThrough.getCompl();
189
61
    } else {
190
61
      ProbToNewTarget = BSI.MBPI->getEdgeProbability(ThisMBB, OrigTarget) / 2;
191
61
      ProbFallThrough = ProbToNewTarget.getCompl();
192
61
      ProbOrigTarget = ProbToNewTarget / ProbToNewTarget.getCompl();
193
61
      ProbOrigFallThrough = ProbOrigTarget.getCompl();
194
61
    }
195
117
  }
196
117
197
117
  // Create a new basic block.
198
117
  MachineBasicBlock::iterator InsertPoint = BSI.SplitBefore;
199
117
  const BasicBlock *LLVM_BB = ThisMBB->getBasicBlock();
200
117
  MachineFunction::iterator It = ThisMBB->getIterator();
201
117
  MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(LLVM_BB);
202
117
  MF->insert(++It, NewMBB);
203
117
204
117
  // Move everything after SplitBefore into the new block.
205
117
  NewMBB->splice(NewMBB->end(), ThisMBB, InsertPoint, ThisMBB->end());
206
117
  NewMBB->transferSuccessors(ThisMBB);
207
117
  if (!ProbOrigTarget.isUnknown()) {
208
117
    auto MBBI = std::find(NewMBB->succ_begin(), NewMBB->succ_end(), OrigTarget);
209
117
    NewMBB->setSuccProbability(MBBI, ProbOrigTarget);
210
117
    MBBI = std::find(NewMBB->succ_begin(), NewMBB->succ_end(), OrigFallThrough);
211
117
    NewMBB->setSuccProbability(MBBI, ProbOrigFallThrough);
212
117
  }
213
117
214
117
  // Add the two successors to ThisMBB.
215
117
  ThisMBB->addSuccessor(NewBRTarget, ProbToNewTarget);
216
117
  ThisMBB->addSuccessor(NewMBB, ProbFallThrough);
217
117
218
117
  // Add the branches to ThisMBB.
219
117
  BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(),
220
117
          TII->get(NewBROpcode))
221
117
      .addReg(BSI.SplitCond->getOperand(0).getReg())
222
117
      .addMBB(NewBRTarget);
223
117
  BuildMI(*ThisMBB, ThisMBB->end(), BSI.SplitBefore->getDebugLoc(),
224
117
          TII->get(PPC::B))
225
117
      .addMBB(NewMBB);
226
117
  if (BSI.MIToDelete)
227
117
    BSI.MIToDelete->eraseFromParent();
228
117
229
117
  // Change the condition on the original branch and invert it if requested.
230
117
  auto FirstTerminator = NewMBB->getFirstTerminator();
231
117
  if (BSI.NewCond) {
232
117
    assert(FirstTerminator->getOperand(0).isReg() &&
233
117
           "Can't update condition of unconditional branch.");
234
117
    FirstTerminator->getOperand(0).setReg(BSI.NewCond->getOperand(0).getReg());
235
117
  }
236
117
  if (BSI.InvertOrigBranch)
237
59
    FirstTerminator->setDesc(TII->get(InvertedOpcode));
238
117
239
117
  // If any of the PHIs in the successors of NewMBB reference values that
240
117
  // now come from NewMBB, they need to be updated.
241
234
  for (auto *Succ : NewMBB->successors()) {
242
234
    updatePHIs(Succ, ThisMBB, NewMBB, MRI);
243
234
  }
244
117
  addIncomingValuesToPHIs(NewBRTarget, ThisMBB, NewMBB, MRI);
245
117
246
117
  LLVM_DEBUG(dbgs() << "After splitting, ThisMBB:\n"; ThisMBB->dump());
247
117
  LLVM_DEBUG(dbgs() << "NewMBB:\n"; NewMBB->dump());
248
117
  LLVM_DEBUG(dbgs() << "New branch-to block:\n"; NewBRTarget->dump());
249
117
  return true;
250
117
}
251
252
192
static bool isBinary(MachineInstr &MI) {
253
192
  return MI.getNumOperands() == 3;
254
192
}
255
256
192
static bool isNullary(MachineInstr &MI) {
257
192
  return MI.getNumOperands() == 1;
258
192
}
259
260
/// Given a CR logical operation \p CROp, branch opcode \p BROp as well as
261
/// a flag to indicate if the first operand of \p CROp is used as the
262
/// SplitBefore operand, determines whether either of the branches are to be
263
/// inverted as well as whether the new target should be the original
264
/// fall-through block.
265
static void
266
computeBranchTargetAndInversion(unsigned CROp, unsigned BROp, bool UsingDef1,
267
                                bool &InvertNewBranch, bool &InvertOrigBranch,
268
117
                                bool &TargetIsFallThrough) {
269
117
  // The conditions under which each of the output operands should be [un]set
270
117
  // can certainly be written much more concisely with just 3 if statements or
271
117
  // ternary expressions. However, this provides a much clearer overview to the
272
117
  // reader as to what is set for each <CROp, BROp, OpUsed> combination.
273
117
  if (BROp == PPC::BC || 
BROp == PPC::BCLR0
) {
274
117
    // Regular branches.
275
117
    switch (CROp) {
276
117
    default:
277
0
      llvm_unreachable("Don't know how to handle this CR logical.");
278
117
    case PPC::CROR:
279
2
      InvertNewBranch = false;
280
2
      InvertOrigBranch = false;
281
2
      TargetIsFallThrough = false;
282
2
      return;
283
117
    case PPC::CRAND:
284
0
      InvertNewBranch = true;
285
0
      InvertOrigBranch = false;
286
0
      TargetIsFallThrough = true;
287
0
      return;
288
117
    case PPC::CRNAND:
289
0
      InvertNewBranch = true;
290
0
      InvertOrigBranch = true;
291
0
      TargetIsFallThrough = false;
292
0
      return;
293
117
    case PPC::CRNOR:
294
0
      InvertNewBranch = false;
295
0
      InvertOrigBranch = true;
296
0
      TargetIsFallThrough = true;
297
0
      return;
298
117
    case PPC::CRORC:
299
59
      InvertNewBranch = UsingDef1;
300
59
      InvertOrigBranch = !UsingDef1;
301
59
      TargetIsFallThrough = false;
302
59
      return;
303
117
    case PPC::CRANDC:
304
56
      InvertNewBranch = !UsingDef1;
305
56
      InvertOrigBranch = !UsingDef1;
306
56
      TargetIsFallThrough = true;
307
56
      return;
308
0
    }
309
0
  } else if (BROp == PPC::BCn || BROp == PPC::BCLRn) {
310
0
    // Negated branches.
311
0
    switch (CROp) {
312
0
    default:
313
0
      llvm_unreachable("Don't know how to handle this CR logical.");
314
0
    case PPC::CROR:
315
0
      InvertNewBranch = true;
316
0
      InvertOrigBranch = false;
317
0
      TargetIsFallThrough = true;
318
0
      return;
319
0
    case PPC::CRAND:
320
0
      InvertNewBranch = false;
321
0
      InvertOrigBranch = false;
322
0
      TargetIsFallThrough = false;
323
0
      return;
324
0
    case PPC::CRNAND:
325
0
      InvertNewBranch = false;
326
0
      InvertOrigBranch = true;
327
0
      TargetIsFallThrough = true;
328
0
      return;
329
0
    case PPC::CRNOR:
330
0
      InvertNewBranch = true;
331
0
      InvertOrigBranch = true;
332
0
      TargetIsFallThrough = false;
333
0
      return;
334
0
    case PPC::CRORC:
335
0
      InvertNewBranch = !UsingDef1;
336
0
      InvertOrigBranch = !UsingDef1;
337
0
      TargetIsFallThrough = true;
338
0
      return;
339
0
    case PPC::CRANDC:
340
0
      InvertNewBranch = UsingDef1;
341
0
      InvertOrigBranch = !UsingDef1;
342
0
      TargetIsFallThrough = false;
343
0
      return;
344
0
    }
345
0
  } else
346
0
    llvm_unreachable("Don't know how to handle this branch.");
347
117
}
348
349
namespace {
350
351
class PPCReduceCRLogicals : public MachineFunctionPass {
352
353
public:
354
  static char ID;
355
  struct CRLogicalOpInfo {
356
    MachineInstr *MI;
357
    // FIXME: If chains of copies are to be handled, this should be a vector.
358
    std::pair<MachineInstr*, MachineInstr*> CopyDefs;
359
    std::pair<MachineInstr*, MachineInstr*> TrueDefs;
360
    unsigned IsBinary : 1;
361
    unsigned IsNullary : 1;
362
    unsigned ContainedInBlock : 1;
363
    unsigned FeedsISEL : 1;
364
    unsigned FeedsBR : 1;
365
    unsigned FeedsLogical : 1;
366
    unsigned SingleUse : 1;
367
    unsigned DefsSingleUse : 1;
368
    unsigned SubregDef1;
369
    unsigned SubregDef2;
370
    CRLogicalOpInfo() : MI(nullptr), IsBinary(0), IsNullary(0),
371
                        ContainedInBlock(0), FeedsISEL(0), FeedsBR(0),
372
                        FeedsLogical(0), SingleUse(0), DefsSingleUse(1),
373
192
                        SubregDef1(0), SubregDef2(0) { }
374
    void dump();
375
  };
376
377
private:
378
  const PPCInstrInfo *TII;
379
  MachineFunction *MF;
380
  MachineRegisterInfo *MRI;
381
  const MachineBranchProbabilityInfo *MBPI;
382
383
  // A vector to contain all the CR logical operations
384
  std::vector<CRLogicalOpInfo> AllCRLogicalOps;
385
  void initialize(MachineFunction &MFParm);
386
  void collectCRLogicals();
387
  bool handleCROp(CRLogicalOpInfo &CRI);
388
  bool splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI);
389
4.46k
  static bool isCRLogical(MachineInstr &MI) {
390
4.46k
    unsigned Opc = MI.getOpcode();
391
4.46k
    return Opc == PPC::CRAND || 
Opc == PPC::CRNAND4.45k
||
Opc == PPC::CROR4.45k
||
392
4.46k
      
Opc == PPC::CRXOR4.45k
||
Opc == PPC::CRNOR4.43k
||
Opc == PPC::CREQV4.43k
||
393
4.46k
      
Opc == PPC::CRANDC4.41k
||
Opc == PPC::CRORC4.34k
||
Opc == PPC::CRSET4.26k
||
394
4.46k
      
Opc == PPC::CRUNSET4.26k
||
Opc == PPC::CR6SET4.26k
||
Opc == PPC::CR6UNSET4.26k
;
395
4.46k
  }
396
200
  bool simplifyCode() {
397
200
    bool Changed = false;
398
200
    // Not using a range-based for loop here as the vector may grow while being
399
200
    // operated on.
400
392
    for (unsigned i = 0; i < AllCRLogicalOps.size(); 
i++192
)
401
192
      Changed |= handleCROp(AllCRLogicalOps[i]);
402
200
    return Changed;
403
200
  }
404
405
public:
406
8
  PPCReduceCRLogicals() : MachineFunctionPass(ID) {
407
8
    initializePPCReduceCRLogicalsPass(*PassRegistry::getPassRegistry());
408
8
  }
409
410
  MachineInstr *lookThroughCRCopy(unsigned Reg, unsigned &Subreg,
411
                                  MachineInstr *&CpDef);
412
200
  bool runOnMachineFunction(MachineFunction &MF) override {
413
200
    if (skipFunction(MF.getFunction()))
414
0
      return false;
415
200
416
200
    // If the subtarget doesn't use CR bits, there's nothing to do.
417
200
    const PPCSubtarget &STI = MF.getSubtarget<PPCSubtarget>();
418
200
    if (!STI.useCRBits())
419
0
      return false;
420
200
421
200
    initialize(MF);
422
200
    collectCRLogicals();
423
200
    return simplifyCode();
424
200
  }
425
  CRLogicalOpInfo createCRLogicalOpInfo(MachineInstr &MI);
426
7
  void getAnalysisUsage(AnalysisUsage &AU) const override {
427
7
    AU.addRequired<MachineBranchProbabilityInfo>();
428
7
    AU.addRequired<MachineDominatorTree>();
429
7
    MachineFunctionPass::getAnalysisUsage(AU);
430
7
  }
431
};
432
433
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
434
LLVM_DUMP_METHOD void PPCReduceCRLogicals::CRLogicalOpInfo::dump() {
435
  dbgs() << "CRLogicalOpMI: ";
436
  MI->dump();
437
  dbgs() << "IsBinary: " << IsBinary << ", FeedsISEL: " << FeedsISEL;
438
  dbgs() << ", FeedsBR: " << FeedsBR << ", FeedsLogical: ";
439
  dbgs() << FeedsLogical << ", SingleUse: " << SingleUse;
440
  dbgs() << ", DefsSingleUse: " << DefsSingleUse;
441
  dbgs() << ", SubregDef1: " << SubregDef1 << ", SubregDef2: ";
442
  dbgs() << SubregDef2 << ", ContainedInBlock: " << ContainedInBlock;
443
  if (!IsNullary) {
444
    dbgs() << "\nDefs:\n";
445
    TrueDefs.first->dump();
446
  }
447
  if (IsBinary)
448
    TrueDefs.second->dump();
449
  dbgs() << "\n";
450
  if (CopyDefs.first) {
451
    dbgs() << "CopyDef1: ";
452
    CopyDefs.first->dump();
453
  }
454
  if (CopyDefs.second) {
455
    dbgs() << "CopyDef2: ";
456
    CopyDefs.second->dump();
457
  }
458
}
459
#endif
460
461
PPCReduceCRLogicals::CRLogicalOpInfo
462
192
PPCReduceCRLogicals::createCRLogicalOpInfo(MachineInstr &MIParam) {
463
192
  CRLogicalOpInfo Ret;
464
192
  Ret.MI = &MIParam;
465
192
  // Get the defs
466
192
  if (isNullary(MIParam)) {
467
0
    Ret.IsNullary = 1;
468
0
    Ret.TrueDefs = std::make_pair(nullptr, nullptr);
469
0
    Ret.CopyDefs = std::make_pair(nullptr, nullptr);
470
192
  } else {
471
192
    MachineInstr *Def1 = lookThroughCRCopy(MIParam.getOperand(1).getReg(),
472
192
                                           Ret.SubregDef1, Ret.CopyDefs.first);
473
192
    Ret.DefsSingleUse &=
474
192
      MRI->hasOneNonDBGUse(Def1->getOperand(0).getReg());
475
192
    Ret.DefsSingleUse &=
476
192
      MRI->hasOneNonDBGUse(Ret.CopyDefs.first->getOperand(0).getReg());
477
192
    assert(Def1 && "Must be able to find a definition of operand 1.");
478
192
    if (isBinary(MIParam)) {
479
192
      Ret.IsBinary = 1;
480
192
      MachineInstr *Def2 = lookThroughCRCopy(MIParam.getOperand(2).getReg(),
481
192
                                             Ret.SubregDef2,
482
192
                                             Ret.CopyDefs.second);
483
192
      Ret.DefsSingleUse &=
484
192
        MRI->hasOneNonDBGUse(Def2->getOperand(0).getReg());
485
192
      Ret.DefsSingleUse &=
486
192
        MRI->hasOneNonDBGUse(Ret.CopyDefs.second->getOperand(0).getReg());
487
192
      assert(Def2 && "Must be able to find a definition of operand 2.");
488
192
      Ret.TrueDefs = std::make_pair(Def1, Def2);
489
192
    } else {
490
0
      Ret.TrueDefs = std::make_pair(Def1, nullptr);
491
0
      Ret.CopyDefs.second = nullptr;
492
0
    }
493
192
  }
494
192
495
192
  Ret.ContainedInBlock = 1;
496
192
  // Get the uses
497
192
  for (MachineInstr &UseMI :
498
194
       MRI->use_nodbg_instructions(MIParam.getOperand(0).getReg())) {
499
194
    unsigned Opc = UseMI.getOpcode();
500
194
    if (Opc == PPC::ISEL || Opc == PPC::ISEL8)
501
40
      Ret.FeedsISEL = 1;
502
194
    if (Opc == PPC::BC || 
Opc == PPC::BCn45
||
Opc == PPC::BCLR45
||
503
194
        
Opc == PPC::BCLRn45
)
504
149
      Ret.FeedsBR = 1;
505
194
    Ret.FeedsLogical = isCRLogical(UseMI);
506
194
    if (UseMI.getParent() != MIParam.getParent())
507
2
      Ret.ContainedInBlock = 0;
508
194
  }
509
192
  Ret.SingleUse = MRI->hasOneNonDBGUse(MIParam.getOperand(0).getReg()) ? 
1190
:
02
;
510
192
511
192
  // We now know whether all the uses of the CR logical are in the same block.
512
192
  if (!Ret.IsNullary) {
513
192
    Ret.ContainedInBlock &=
514
192
      (MIParam.getParent() == Ret.TrueDefs.first->getParent());
515
192
    if (Ret.IsBinary)
516
192
      Ret.ContainedInBlock &=
517
192
        (MIParam.getParent() == Ret.TrueDefs.second->getParent());
518
192
  }
519
192
  LLVM_DEBUG(Ret.dump());
520
192
  if (Ret.IsBinary && Ret.ContainedInBlock && 
Ret.SingleUse190
) {
521
190
    NumContainedSingleUseBinOps++;
522
190
    if (Ret.FeedsBR && 
Ret.DefsSingleUse145
)
523
145
      NumToSplitBlocks++;
524
190
  }
525
192
  return Ret;
526
192
}
527
528
/// Looks through a COPY instruction to the actual definition of the CR-bit
529
/// register and returns the instruction that defines it.
530
/// FIXME: This currently handles what is by-far the most common case:
531
/// an instruction that defines a CR field followed by a single copy of a bit
532
/// from that field into a virtual register. If chains of copies need to be
533
/// handled, this should have a loop until a non-copy instruction is found.
534
MachineInstr *PPCReduceCRLogicals::lookThroughCRCopy(unsigned Reg,
535
                                                     unsigned &Subreg,
536
384
                                                     MachineInstr *&CpDef) {
537
384
  Subreg = -1;
538
384
  if (!TargetRegisterInfo::isVirtualRegister(Reg))
539
0
    return nullptr;
540
384
  MachineInstr *Copy = MRI->getVRegDef(Reg);
541
384
  CpDef = Copy;
542
384
  if (!Copy->isCopy())
543
5
    return Copy;
544
379
  unsigned CopySrc = Copy->getOperand(1).getReg();
545
379
  Subreg = Copy->getOperand(1).getSubReg();
546
379
  if (!TargetRegisterInfo::isVirtualRegister(CopySrc)) {
547
0
    const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
548
0
    // Set the Subreg
549
0
    if (CopySrc == PPC::CR0EQ || CopySrc == PPC::CR6EQ)
550
0
      Subreg = PPC::sub_eq;
551
0
    if (CopySrc == PPC::CR0LT || CopySrc == PPC::CR6LT)
552
0
      Subreg = PPC::sub_lt;
553
0
    if (CopySrc == PPC::CR0GT || CopySrc == PPC::CR6GT)
554
0
      Subreg = PPC::sub_gt;
555
0
    if (CopySrc == PPC::CR0UN || CopySrc == PPC::CR6UN)
556
0
      Subreg = PPC::sub_un;
557
0
    // Loop backwards and return the first MI that modifies the physical CR Reg.
558
0
    MachineBasicBlock::iterator Me = Copy, B = Copy->getParent()->begin();
559
0
    while (Me != B)
560
0
      if ((--Me)->modifiesRegister(CopySrc, TRI))
561
0
        return &*Me;
562
0
    return nullptr;
563
379
  }
564
379
  return MRI->getVRegDef(CopySrc);
565
379
}
566
567
200
void PPCReduceCRLogicals::initialize(MachineFunction &MFParam) {
568
200
  MF = &MFParam;
569
200
  MRI = &MF->getRegInfo();
570
200
  TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
571
200
  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
572
200
573
200
  AllCRLogicalOps.clear();
574
200
}
575
576
/// Contains all the implemented transformations on CR logical operations.
577
/// For example, a binary CR logical can be used to split a block on its inputs,
578
/// a unary CR logical might be used to change the condition code on a
579
/// comparison feeding it. A nullary CR logical might simply be removable
580
/// if the user of the bit it [un]sets can be transformed.
581
192
bool PPCReduceCRLogicals::handleCROp(CRLogicalOpInfo &CRI) {
582
192
  // We can definitely split a block on the inputs to a binary CR operation
583
192
  // whose defs and (single) use are within the same block.
584
192
  bool Changed = false;
585
192
  if (CRI.IsBinary && CRI.ContainedInBlock && 
CRI.SingleUse190
&&
CRI.FeedsBR190
&&
586
192
      
CRI.DefsSingleUse145
) {
587
145
    Changed = splitBlockOnBinaryCROp(CRI);
588
145
    if (Changed)
589
117
      NumBlocksSplitOnBinaryCROp++;
590
145
  }
591
192
  return Changed;
592
192
}
593
594
/// Splits a block that contains a CR-logical operation that feeds a branch
595
/// and whose operands are produced within the block.
596
/// Example:
597
///    %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2
598
///    %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5
599
///    %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3
600
///    %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7
601
///    %vr9<def> = CROR %vr6<kill>, %vr8<kill>; CRBITRC:%vr9,%vr6,%vr8
602
///    BC %vr9<kill>, <BB#2>; CRBITRC:%vr9
603
/// Becomes:
604
///    %vr5<def> = CMPDI %vr2, 0; CRRC:%vr5 G8RC:%vr2
605
///    %vr6<def> = COPY %vr5:sub_eq; CRBITRC:%vr6 CRRC:%vr5
606
///    BC %vr6<kill>, <BB#2>; CRBITRC:%vr6
607
///
608
///    %vr7<def> = CMPDI %vr3, 0; CRRC:%vr7 G8RC:%vr3
609
///    %vr8<def> = COPY %vr7:sub_eq; CRBITRC:%vr8 CRRC:%vr7
610
///    BC %vr9<kill>, <BB#2>; CRBITRC:%vr9
611
145
bool PPCReduceCRLogicals::splitBlockOnBinaryCROp(CRLogicalOpInfo &CRI) {
612
145
  if (CRI.CopyDefs.first == CRI.CopyDefs.second) {
613
0
    LLVM_DEBUG(dbgs() << "Unable to split as the two operands are the same\n");
614
0
    NumNotSplitIdenticalOperands++;
615
0
    return false;
616
0
  }
617
145
  if (CRI.TrueDefs.first->isCopy() || CRI.TrueDefs.second->isCopy() ||
618
145
      CRI.TrueDefs.first->isPHI() || CRI.TrueDefs.second->isPHI()) {
619
0
    LLVM_DEBUG(
620
0
        dbgs() << "Unable to split because one of the operands is a PHI or "
621
0
                  "chain of copies.\n");
622
0
    NumNotSplitChainCopies++;
623
0
    return false;
624
0
  }
625
145
  // Note: keep in sync with computeBranchTargetAndInversion().
626
145
  if (CRI.MI->getOpcode() != PPC::CROR &&
627
145
      
CRI.MI->getOpcode() != PPC::CRAND143
&&
628
145
      
CRI.MI->getOpcode() != PPC::CRNOR143
&&
629
145
      
CRI.MI->getOpcode() != PPC::CRNAND143
&&
630
145
      
CRI.MI->getOpcode() != PPC::CRORC143
&&
631
145
      
CRI.MI->getOpcode() != PPC::CRANDC84
) {
632
28
    LLVM_DEBUG(dbgs() << "Unable to split blocks on this opcode.\n");
633
28
    NumNotSplitWrongOpcode++;
634
28
    return false;
635
28
  }
636
117
  LLVM_DEBUG(dbgs() << "Splitting the following CR op:\n"; CRI.dump());
637
117
  MachineBasicBlock::iterator Def1It = CRI.TrueDefs.first;
638
117
  MachineBasicBlock::iterator Def2It = CRI.TrueDefs.second;
639
117
640
117
  bool UsingDef1 = false;
641
117
  MachineInstr *SplitBefore = &*Def2It;
642
518
  for (auto E = CRI.MI->getParent()->end(); Def2It != E; 
++Def2It401
) {
643
457
    if (Def1It == Def2It) { // Def2 comes before Def1.
644
56
      SplitBefore = &*Def1It;
645
56
      UsingDef1 = true;
646
56
      break;
647
56
    }
648
457
  }
649
117
650
117
  LLVM_DEBUG(dbgs() << "We will split the following block:\n";);
651
117
  LLVM_DEBUG(CRI.MI->getParent()->dump());
652
117
  LLVM_DEBUG(dbgs() << "Before instruction:\n"; SplitBefore->dump());
653
117
654
117
  // Get the branch instruction.
655
117
  MachineInstr *Branch =
656
117
    MRI->use_nodbg_begin(CRI.MI->getOperand(0).getReg())->getParent();
657
117
658
117
  // We want the new block to have no code in it other than the definition
659
117
  // of the input to the CR logical and the CR logical itself. So we move
660
117
  // those to the bottom of the block (just before the branch). Then we
661
117
  // will split before the CR logical.
662
117
  MachineBasicBlock *MBB = SplitBefore->getParent();
663
117
  auto FirstTerminator = MBB->getFirstTerminator();
664
117
  MachineBasicBlock::iterator FirstInstrToMove =
665
117
    UsingDef1 ? 
CRI.TrueDefs.first56
:
CRI.TrueDefs.second61
;
666
117
  MachineBasicBlock::iterator SecondInstrToMove =
667
117
    UsingDef1 ? 
CRI.CopyDefs.first56
:
CRI.CopyDefs.second61
;
668
117
669
117
  // The instructions that need to be moved are not guaranteed to be
670
117
  // contiguous. Move them individually.
671
117
  // FIXME: If one of the operands is a chain of (single use) copies, they
672
117
  // can all be moved and we can still split.
673
117
  MBB->splice(FirstTerminator, MBB, FirstInstrToMove);
674
117
  if (FirstInstrToMove != SecondInstrToMove)
675
117
    MBB->splice(FirstTerminator, MBB, SecondInstrToMove);
676
117
  MBB->splice(FirstTerminator, MBB, CRI.MI);
677
117
678
117
  unsigned Opc = CRI.MI->getOpcode();
679
117
  bool InvertOrigBranch, InvertNewBranch, TargetIsFallThrough;
680
117
  computeBranchTargetAndInversion(Opc, Branch->getOpcode(), UsingDef1,
681
117
                                  InvertNewBranch, InvertOrigBranch,
682
117
                                  TargetIsFallThrough);
683
117
  MachineInstr *SplitCond =
684
117
    UsingDef1 ? 
CRI.CopyDefs.second56
:
CRI.CopyDefs.first61
;
685
117
  LLVM_DEBUG(dbgs() << "We will " << (InvertNewBranch ? "invert" : "copy"));
686
117
  LLVM_DEBUG(dbgs() << " the original branch and the target is the "
687
117
                    << (TargetIsFallThrough ? "fallthrough block\n"
688
117
                                            : "orig. target block\n"));
689
117
  LLVM_DEBUG(dbgs() << "Original branch instruction: "; Branch->dump());
690
117
  BlockSplitInfo BSI { Branch, SplitBefore, SplitCond, InvertNewBranch,
691
117
    InvertOrigBranch, TargetIsFallThrough, MBPI, CRI.MI,
692
117
    UsingDef1 ? 
CRI.CopyDefs.first56
:
CRI.CopyDefs.second61
};
693
117
  bool Changed = splitMBB(BSI);
694
117
  // If we've split on a CR logical that is fed by a CR logical,
695
117
  // recompute the source CR logical as it may be usable for splitting.
696
117
  if (Changed) {
697
117
    bool Input1CRlogical =
698
117
      CRI.TrueDefs.first && isCRLogical(*CRI.TrueDefs.first);
699
117
    bool Input2CRlogical =
700
117
      CRI.TrueDefs.second && isCRLogical(*CRI.TrueDefs.second);
701
117
    if (Input1CRlogical)
702
1
      AllCRLogicalOps.push_back(createCRLogicalOpInfo(*CRI.TrueDefs.first));
703
117
    if (Input2CRlogical)
704
0
      AllCRLogicalOps.push_back(createCRLogicalOpInfo(*CRI.TrueDefs.second));
705
117
  }
706
117
  return Changed;
707
117
}
708
709
200
void PPCReduceCRLogicals::collectCRLogicals() {
710
651
  for (MachineBasicBlock &MBB : *MF) {
711
4.03k
    for (MachineInstr &MI : MBB) {
712
4.03k
      if (isCRLogical(MI)) {
713
191
        AllCRLogicalOps.push_back(createCRLogicalOpInfo(MI));
714
191
        TotalCRLogicals++;
715
191
        if (AllCRLogicalOps.back().IsNullary)
716
0
          TotalNullaryCRLogicals++;
717
191
        else if (AllCRLogicalOps.back().IsBinary)
718
191
          TotalBinaryCRLogicals++;
719
0
        else
720
0
          TotalUnaryCRLogicals++;
721
191
      }
722
4.03k
    }
723
651
  }
724
200
}
725
726
} // end anonymous namespace
727
728
101k
INITIALIZE_PASS_BEGIN(PPCReduceCRLogicals, DEBUG_TYPE,
729
101k
                      "PowerPC Reduce CR logical Operation", false, false)
730
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
731
101k
INITIALIZE_PASS_END(PPCReduceCRLogicals, DEBUG_TYPE,
732
                    "PowerPC Reduce CR logical Operation", false, false)
733
734
char PPCReduceCRLogicals::ID = 0;
735
FunctionPass*
736
8
llvm::createPPCReduceCRLogicalsPass() { return new PPCReduceCRLogicals(); }