Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/PowerPC/PPCBranchCoalescing.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- CoalesceBranches.cpp - Coalesce blocks with the same condition ---===//
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
/// \file
10
/// Coalesce basic blocks guarded by the same branch condition into a single
11
/// basic block.
12
///
13
//===----------------------------------------------------------------------===//
14
15
#include "PPC.h"
16
#include "llvm/ADT/BitVector.h"
17
#include "llvm/ADT/Statistic.h"
18
#include "llvm/CodeGen/MachineDominators.h"
19
#include "llvm/CodeGen/MachineFunctionPass.h"
20
#include "llvm/CodeGen/MachinePostDominators.h"
21
#include "llvm/CodeGen/MachineRegisterInfo.h"
22
#include "llvm/CodeGen/Passes.h"
23
#include "llvm/CodeGen/TargetFrameLowering.h"
24
#include "llvm/CodeGen/TargetInstrInfo.h"
25
#include "llvm/CodeGen/TargetSubtargetInfo.h"
26
#include "llvm/Support/Debug.h"
27
28
using namespace llvm;
29
30
#define DEBUG_TYPE "ppc-branch-coalescing"
31
32
STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
33
STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
34
STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");
35
36
//===----------------------------------------------------------------------===//
37
//                               PPCBranchCoalescing
38
//===----------------------------------------------------------------------===//
39
///
40
/// Improve scheduling by coalescing branches that depend on the same condition.
41
/// This pass looks for blocks that are guarded by the same branch condition
42
/// and attempts to merge the blocks together. Such opportunities arise from
43
/// the expansion of select statements in the IR.
44
///
45
/// This pass does not handle implicit operands on branch statements. In order
46
/// to run on targets that use implicit operands, changes need to be made in the
47
/// canCoalesceBranch and canMerge methods.
48
///
49
/// Example: the following LLVM IR
50
///
51
///     %test = icmp eq i32 %x 0
52
///     %tmp1 = select i1 %test, double %a, double 2.000000e-03
53
///     %tmp2 = select i1 %test, double %b, double 5.000000e-03
54
///
55
/// expands to the following machine code:
56
///
57
/// %bb.0: derived from LLVM BB %entry
58
///    liveins: %f1 %f3 %x6
59
///        <SNIP1>
60
///        %0 = COPY %f1; F8RC:%0
61
///        %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
62
///        %8 = LXSDX %zero8, killed %7, implicit %rm;
63
///                    mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
64
///        BCC 76, %5, <%bb.2>; CRRC:%5
65
///    Successors according to CFG: %bb.1(?%) %bb.2(?%)
66
///
67
/// %bb.1: derived from LLVM BB %entry
68
///    Predecessors according to CFG: %bb.0
69
///    Successors according to CFG: %bb.2(?%)
70
///
71
/// %bb.2: derived from LLVM BB %entry
72
///    Predecessors according to CFG: %bb.0 %bb.1
73
///        %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
74
///                    F8RC:%9,%8,%0
75
///        <SNIP2>
76
///        BCC 76, %5, <%bb.4>; CRRC:%5
77
///    Successors according to CFG: %bb.3(?%) %bb.4(?%)
78
///
79
/// %bb.3: derived from LLVM BB %entry
80
///    Predecessors according to CFG: %bb.2
81
///    Successors according to CFG: %bb.4(?%)
82
///
83
/// %bb.4: derived from LLVM BB %entry
84
///    Predecessors according to CFG: %bb.2 %bb.3
85
///        %13 = PHI %12, <%bb.3>, %2, <%bb.2>;
86
///                     F8RC:%13,%12,%2
87
///        <SNIP3>
88
///        BLR8 implicit %lr8, implicit %rm, implicit %f1
89
///
90
/// When this pattern is detected, branch coalescing will try to collapse
91
/// it by moving code in %bb.2 to %bb.0 and/or %bb.4 and removing %bb.3.
92
///
93
/// If all conditions are meet, IR should collapse to:
94
///
95
/// %bb.0: derived from LLVM BB %entry
96
///    liveins: %f1 %f3 %x6
97
///        <SNIP1>
98
///        %0 = COPY %f1; F8RC:%0
99
///        %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
100
///        %8 = LXSDX %zero8, killed %7, implicit %rm;
101
///                     mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
102
///        <SNIP2>
103
///        BCC 76, %5, <%bb.4>; CRRC:%5
104
///    Successors according to CFG: %bb.1(0x2aaaaaaa / 0x80000000 = 33.33%)
105
///      %bb.4(0x55555554 / 0x80000000 = 66.67%)
106
///
107
/// %bb.1: derived from LLVM BB %entry
108
///    Predecessors according to CFG: %bb.0
109
///    Successors according to CFG: %bb.4(0x40000000 / 0x80000000 = 50.00%)
110
///
111
/// %bb.4: derived from LLVM BB %entry
112
///    Predecessors according to CFG: %bb.0 %bb.1
113
///        %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
114
///                    F8RC:%9,%8,%0
115
///        %13 = PHI %12, <%bb.1>, %2, <%bb.0>;
116
///                     F8RC:%13,%12,%2
117
///        <SNIP3>
118
///        BLR8 implicit %lr8, implicit %rm, implicit %f1
119
///
120
/// Branch Coalescing does not split blocks, it moves everything in the same
121
/// direction ensuring it does not break use/definition semantics.
122
///
123
/// PHI nodes and its corresponding use instructions are moved to its successor
124
/// block if there are no uses within the successor block PHI nodes.  PHI
125
/// node ordering cannot be assumed.
126
///
127
/// Non-PHI can be moved up to the predecessor basic block or down to the
128
/// successor basic block following any PHI instructions. Whether it moves
129
/// up or down depends on whether the register(s) defined in the instructions
130
/// are used in current block or in any PHI instructions at the beginning of
131
/// the successor block.
132
133
namespace {
134
135
class PPCBranchCoalescing : public MachineFunctionPass {
136
  struct CoalescingCandidateInfo {
137
    MachineBasicBlock *BranchBlock;       // Block containing the branch
138
    MachineBasicBlock *BranchTargetBlock; // Block branched to
139
    MachineBasicBlock *FallThroughBlock;  // Fall-through if branch not taken
140
    SmallVector<MachineOperand, 4> Cond;
141
    bool MustMoveDown;
142
    bool MustMoveUp;
143
144
    CoalescingCandidateInfo();
145
    void clear();
146
  };
147
148
  MachineDominatorTree *MDT;
149
  MachinePostDominatorTree *MPDT;
150
  const TargetInstrInfo *TII;
151
  MachineRegisterInfo *MRI;
152
153
  void initialize(MachineFunction &F);
154
  bool canCoalesceBranch(CoalescingCandidateInfo &Cand);
155
  bool identicalOperands(ArrayRef<MachineOperand> OperandList1,
156
                         ArrayRef<MachineOperand> OperandList2) const;
157
  bool validateCandidates(CoalescingCandidateInfo &SourceRegion,
158
                          CoalescingCandidateInfo &TargetRegion) const;
159
160
public:
161
  static char ID;
162
163
4
  PPCBranchCoalescing() : MachineFunctionPass(ID) {
164
4
    initializePPCBranchCoalescingPass(*PassRegistry::getPassRegistry());
165
4
  }
166
167
3
  void getAnalysisUsage(AnalysisUsage &AU) const override {
168
3
    AU.addRequired<MachineDominatorTree>();
169
3
    AU.addRequired<MachinePostDominatorTree>();
170
3
    MachineFunctionPass::getAnalysisUsage(AU);
171
3
  }
172
173
6
  StringRef getPassName() const override { return "Branch Coalescing"; }
174
175
  bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
176
                       CoalescingCandidateInfo &TargetRegion);
177
  bool canMoveToBeginning(const MachineInstr &MI,
178
                          const MachineBasicBlock &MBB) const;
179
  bool canMoveToEnd(const MachineInstr &MI,
180
                    const MachineBasicBlock &MBB) const;
181
  bool canMerge(CoalescingCandidateInfo &SourceRegion,
182
                CoalescingCandidateInfo &TargetRegion) const;
183
  void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB,
184
                         MachineBasicBlock *TargetRegionMBB);
185
  bool runOnMachineFunction(MachineFunction &MF) override;
186
};
187
} // End anonymous namespace.
188
189
char PPCBranchCoalescing::ID = 0;
190
/// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
191
/// Pass
192
4
FunctionPass *llvm::createPPCBranchCoalescingPass() {
193
4
  return new PPCBranchCoalescing();
194
4
}
195
196
101k
INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
197
101k
                      "Branch Coalescing", false, false)
198
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
199
101k
INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
200
101k
INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
201
                    false, false)
202
203
PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
204
    : BranchBlock(nullptr), BranchTargetBlock(nullptr),
205
4
      FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
206
207
20
void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {
208
20
  BranchBlock = nullptr;
209
20
  BranchTargetBlock = nullptr;
210
20
  FallThroughBlock = nullptr;
211
20
  Cond.clear();
212
20
  MustMoveDown = false;
213
20
  MustMoveUp = false;
214
20
}
215
216
2
void PPCBranchCoalescing::initialize(MachineFunction &MF) {
217
2
  MDT = &getAnalysis<MachineDominatorTree>();
218
2
  MPDT = &getAnalysis<MachinePostDominatorTree>();
219
2
  TII = MF.getSubtarget().getInstrInfo();
220
2
  MRI = &MF.getRegInfo();
221
2
}
222
223
///
224
/// Analyze the branch statement to determine if it can be coalesced. This
225
/// method analyses the branch statement for the given candidate to determine
226
/// if it can be coalesced. If the branch can be coalesced, then the
227
/// BranchTargetBlock and the FallThroughBlock are recorded in the specified
228
/// Candidate.
229
///
230
///\param[in,out] Cand The coalescing candidate to analyze
231
///\return true if and only if the branch can be coalesced, false otherwise
232
///
233
16
bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
234
16
  LLVM_DEBUG(dbgs() << "Determine if branch block "
235
16
                    << Cand.BranchBlock->getNumber() << " can be coalesced:");
236
16
  MachineBasicBlock *FalseMBB = nullptr;
237
16
238
16
  if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,
239
16
                         Cand.Cond)) {
240
4
    LLVM_DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");
241
4
    return false;
242
4
  }
243
12
244
12
  for (auto &I : Cand.BranchBlock->terminators()) {
245
10
    LLVM_DEBUG(dbgs() << "Looking at terminator : " << I << "\n");
246
10
    if (!I.isBranch())
247
0
      continue;
248
10
249
10
    // The analyzeBranch method does not include any implicit operands.
250
10
    // This is not an issue on PPC but must be handled on other targets.
251
10
    // For this pass to be made target-independent, the analyzeBranch API
252
10
    // need to be updated to support implicit operands and there would
253
10
    // need to be a way to verify that any implicit operands would not be
254
10
    // clobbered by merging blocks.  This would include identifying the
255
10
    // implicit operands as well as the basic block they are defined in.
256
10
    // This could be done by changing the analyzeBranch API to have it also
257
10
    // record and return the implicit operands and the blocks where they are
258
10
    // defined. Alternatively, the BranchCoalescing code would need to be
259
10
    // extended to identify the implicit operands.  The analysis in canMerge
260
10
    // must then be extended to prove that none of the implicit operands are
261
10
    // changed in the blocks that are combined during coalescing.
262
10
    if (I.getNumOperands() != I.getNumExplicitOperands()) {
263
0
      LLVM_DEBUG(dbgs() << "Terminator contains implicit operands - skip : "
264
0
                        << I << "\n");
265
0
      return false;
266
0
    }
267
10
  }
268
12
269
12
  if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
270
0
    LLVM_DEBUG(dbgs() << "EH Pad - skip\n");
271
0
    return false;
272
0
  }
273
12
274
12
  // For now only consider triangles (i.e, BranchTargetBlock is set,
275
12
  // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)
276
12
  if (!Cand.BranchTargetBlock || 
FalseMBB10
||
277
12
      
!Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)10
) {
278
2
    LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n");
279
2
    return false;
280
2
  }
281
10
282
10
  // Ensure there are only two successors
283
10
  if (Cand.BranchBlock->succ_size() != 2) {
284
0
    LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n");
285
0
    return false;
286
0
  }
287
10
288
10
  // Sanity check - the block must be able to fall through
289
10
  assert(Cand.BranchBlock->canFallThrough() &&
290
10
         "Expecting the block to fall through!");
291
10
292
10
  // We have already ensured there are exactly two successors to
293
10
  // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.
294
10
  // Ensure the single fall though block is empty.
295
10
  MachineBasicBlock *Succ =
296
10
    (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
297
10
    ? 
*Cand.BranchBlock->succ_rbegin()0
298
10
    : *Cand.BranchBlock->succ_begin();
299
10
300
10
  assert(Succ && "Expecting a valid fall-through block\n");
301
10
302
10
  if (!Succ->empty()) {
303
0
    LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n");
304
0
    return false;
305
0
  }
306
10
307
10
  if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {
308
0
    LLVM_DEBUG(
309
0
        dbgs()
310
0
        << "Successor of fall through block is not branch taken block\n");
311
0
    return false;
312
0
  }
313
10
314
10
  Cand.FallThroughBlock = Succ;
315
10
  LLVM_DEBUG(dbgs() << "Valid Candidate\n");
316
10
  return true;
317
10
}
318
319
///
320
/// Determine if the two operand lists are identical
321
///
322
/// \param[in] OpList1 operand list
323
/// \param[in] OpList2 operand list
324
/// \return true if and only if the operands lists are identical
325
///
326
bool PPCBranchCoalescing::identicalOperands(
327
4
    ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {
328
4
329
4
  if (OpList1.size() != OpList2.size()) {
330
0
    LLVM_DEBUG(dbgs() << "Operand list is different size\n");
331
0
    return false;
332
0
  }
333
4
334
12
  
for (unsigned i = 0; 4
i < OpList1.size();
++i8
) {
335
8
    const MachineOperand &Op1 = OpList1[i];
336
8
    const MachineOperand &Op2 = OpList2[i];
337
8
338
8
    LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n"
339
8
                      << "Op2: " << Op2 << "\n");
340
8
341
8
    if (Op1.isIdenticalTo(Op2)) {
342
8
      // filter out instructions with physical-register uses
343
8
      if (Op1.isReg() && 
TargetRegisterInfo::isPhysicalRegister(Op1.getReg())4
344
8
        // If the physical register is constant then we can assume the value
345
8
        // has not changed between uses.
346
8
          && 
!(0
Op1.isUse()0
&&
MRI->isConstantPhysReg(Op1.getReg())0
)) {
347
0
        LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
348
0
        return false;
349
0
      }
350
8
      LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
351
8
      continue;
352
8
    }
353
0
354
0
    // If the operands are not identical, but are registers, check to see if the
355
0
    // definition of the register produces the same value. If they produce the
356
0
    // same value, consider them to be identical.
357
0
    if (Op1.isReg() && Op2.isReg() &&
358
0
        TargetRegisterInfo::isVirtualRegister(Op1.getReg()) &&
359
0
        TargetRegisterInfo::isVirtualRegister(Op2.getReg())) {
360
0
      MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
361
0
      MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
362
0
      if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
363
0
        LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
364
0
                          << " produce the same value!\n");
365
0
      } else {
366
0
        LLVM_DEBUG(dbgs() << "Operands produce different values\n");
367
0
        return false;
368
0
      }
369
0
    } else {
370
0
      LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
371
0
      return false;
372
0
    }
373
0
  }
374
4
375
4
  return true;
376
4
}
377
378
///
379
/// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
380
/// and update them to refer to the new block.  PHI node ordering
381
/// cannot be assumed so it does not matter where the PHI instructions
382
/// are moved to in TargetMBB.
383
///
384
/// \param[in] SourceMBB block to move PHI instructions from
385
/// \param[in] TargetMBB block to move PHI instructions to
386
///
387
void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
388
4
                                         MachineBasicBlock *TargetMBB) {
389
4
390
4
  MachineBasicBlock::iterator MI = SourceMBB->begin();
391
4
  MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI();
392
4
393
4
  if (MI == ME) {
394
0
    LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
395
0
    return;
396
0
  }
397
4
398
4
  // Update all PHI instructions in SourceMBB and move to top of TargetMBB
399
10
  
for (MachineBasicBlock::iterator Iter = MI; 4
Iter != ME;
Iter++6
) {
400
6
    MachineInstr &PHIInst = *Iter;
401
18
    for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; 
i += 212
) {
402
12
      MachineOperand &MO = PHIInst.getOperand(i);
403
12
      if (MO.getMBB() == SourceMBB)
404
0
        MO.setMBB(TargetMBB);
405
12
    }
406
6
  }
407
4
  TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
408
4
}
409
410
///
411
/// This function checks if MI can be moved to the beginning of the TargetMBB
412
/// following PHI instructions. A MI instruction can be moved to beginning of
413
/// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
414
///
415
/// \param[in] MI the machine instruction to move.
416
/// \param[in] TargetMBB the machine basic block to move to
417
/// \return true if it is safe to move MI to beginning of TargetMBB,
418
///         false otherwise.
419
///
420
bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
421
                                          const MachineBasicBlock &TargetMBB
422
12
                                          ) const {
423
12
424
12
  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
425
12
                    << TargetMBB.getNumber() << "\n");
426
12
427
12
  for (auto &Def : MI.defs()) { // Looking at Def
428
8
    for (auto &Use : MRI->use_instructions(Def.getReg())) {
429
8
      if (Use.isPHI() && 
Use.getParent() == &TargetMBB4
) {
430
4
        LLVM_DEBUG(dbgs() << "    *** used in a PHI -- cannot move ***\n");
431
4
        return false;
432
4
      }
433
8
    }
434
8
  }
435
12
436
12
  
LLVM_DEBUG8
(dbgs() << " Safe to move to the beginning.\n");
437
8
  return true;
438
12
}
439
440
///
441
/// This function checks if MI can be moved to the end of the TargetMBB,
442
/// immediately before the first terminator.  A MI instruction can be moved
443
/// to then end of the TargetMBB if no PHI node defines what MI uses within
444
/// it's own MBB.
445
///
446
/// \param[in] MI the machine instruction to move.
447
/// \param[in] TargetMBB the machine basic block to move to
448
/// \return true if it is safe to move MI to end of TargetMBB,
449
///         false otherwise.
450
///
451
bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
452
                                    const MachineBasicBlock &TargetMBB
453
12
                                    ) const {
454
12
455
12
  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
456
12
                    << TargetMBB.getNumber() << "\n");
457
12
458
26
  for (auto &Use : MI.uses()) {
459
26
    if (Use.isReg() && 
TargetRegisterInfo::isVirtualRegister(Use.getReg())14
) {
460
8
      MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
461
8
      if (DefInst->isPHI() && 
DefInst->getParent() == MI.getParent()0
) {
462
0
        LLVM_DEBUG(dbgs() << "    *** Cannot move this instruction ***\n");
463
0
        return false;
464
8
      } else {
465
8
        LLVM_DEBUG(
466
8
            dbgs() << "    *** def is in another block -- safe to move!\n");
467
8
      }
468
8
    }
469
26
  }
470
12
471
12
  LLVM_DEBUG(dbgs() << "  Safe to move to the end.\n");
472
12
  return true;
473
12
}
474
475
///
476
/// This method checks to ensure the two coalescing candidates follows the
477
/// expected pattern required for coalescing.
478
///
479
/// \param[in] SourceRegion The candidate to move statements from
480
/// \param[in] TargetRegion The candidate to move statements to
481
/// \return true if all instructions in SourceRegion.BranchBlock can be merged
482
/// into a block in TargetRegion; false otherwise.
483
///
484
bool PPCBranchCoalescing::validateCandidates(
485
    CoalescingCandidateInfo &SourceRegion,
486
8
    CoalescingCandidateInfo &TargetRegion) const {
487
8
488
8
  if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
489
8
    
llvm_unreachable0
("Expecting SourceRegion to immediately follow TargetRegion");
490
8
  else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
491
8
    
llvm_unreachable0
("Expecting TargetRegion to dominate SourceRegion");
492
8
  else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
493
8
    
llvm_unreachable0
("Expecting SourceRegion to post-dominate TargetRegion");
494
8
  else if (!TargetRegion.FallThroughBlock->empty() ||
495
8
           !SourceRegion.FallThroughBlock->empty())
496
8
    
llvm_unreachable0
("Expecting fall-through blocks to be empty");
497
8
498
8
  return true;
499
8
}
500
501
///
502
/// This method determines whether the two coalescing candidates can be merged.
503
/// In order to be merged, all instructions must be able to
504
///   1. Move to the beginning of the SourceRegion.BranchTargetBlock;
505
///   2. Move to the end of the TargetRegion.BranchBlock.
506
/// Merging involves moving the instructions in the
507
/// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
508
///
509
/// This function first try to move instructions from the
510
/// TargetRegion.BranchTargetBlock down, to the beginning of the
511
/// SourceRegion.BranchTargetBlock. This is not possible if any register defined
512
/// in TargetRegion.BranchTargetBlock is used in a PHI node in the
513
/// SourceRegion.BranchTargetBlock. In this case, check whether the statement
514
/// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
515
/// before the branch statement). If it cannot move, then these blocks cannot
516
/// be merged.
517
///
518
/// Note that there is no analysis for moving instructions past the fall-through
519
/// blocks because they are confirmed to be empty. An assert is thrown if they
520
/// are not.
521
///
522
/// \param[in] SourceRegion The candidate to move statements from
523
/// \param[in] TargetRegion The candidate to move statements to
524
/// \return true if all instructions in SourceRegion.BranchBlock can be merged
525
///         into a block in TargetRegion, false otherwise.
526
///
527
bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
528
4
                                CoalescingCandidateInfo &TargetRegion) const {
529
4
  if (!validateCandidates(SourceRegion, TargetRegion))
530
0
    return false;
531
4
532
4
  // Walk through PHI nodes first and see if they force the merge into the
533
4
  // SourceRegion.BranchTargetBlock.
534
4
  for (MachineBasicBlock::iterator
535
4
           I = SourceRegion.BranchBlock->instr_begin(),
536
4
           E = SourceRegion.BranchBlock->getFirstNonPHI();
537
10
       I != E; 
++I6
) {
538
6
    for (auto &Def : I->defs())
539
6
      for (auto &Use : MRI->use_instructions(Def.getReg())) {
540
6
        if (Use.isPHI() && 
Use.getParent() == SourceRegion.BranchTargetBlock0
) {
541
0
          LLVM_DEBUG(dbgs()
542
0
                     << "PHI " << *I
543
0
                     << " defines register used in another "
544
0
                        "PHI within branch target block -- can't merge\n");
545
0
          NumPHINotMoved++;
546
0
          return false;
547
0
        }
548
6
        if (Use.getParent() == SourceRegion.BranchBlock) {
549
0
          LLVM_DEBUG(dbgs() << "PHI " << *I
550
0
                            << " defines register used in this "
551
0
                               "block -- all must move down\n");
552
0
          SourceRegion.MustMoveDown = true;
553
0
        }
554
6
      }
555
6
  }
556
4
557
4
  // Walk through the MI to see if they should be merged into
558
4
  // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
559
4
  for (MachineBasicBlock::iterator
560
4
           I = SourceRegion.BranchBlock->getFirstNonPHI(),
561
4
           E = SourceRegion.BranchBlock->end();
562
16
       I != E; 
++I12
) {
563
12
    if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
564
4
      LLVM_DEBUG(dbgs() << "Instruction " << *I
565
4
                        << " cannot move down - must move up!\n");
566
4
      SourceRegion.MustMoveUp = true;
567
4
    }
568
12
    if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
569
0
      LLVM_DEBUG(dbgs() << "Instruction " << *I
570
0
                        << " cannot move up - must move down!\n");
571
0
      SourceRegion.MustMoveDown = true;
572
0
    }
573
12
  }
574
4
575
4
  return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? 
false0
: true;
576
4
}
577
578
/// Merge the instructions from SourceRegion.BranchBlock,
579
/// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
580
/// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
581
/// TargetRegion.FallThroughBlock respectively.
582
///
583
/// The successors for blocks in TargetRegion will be updated to use the
584
/// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
585
/// will be removed from the function.
586
///
587
/// A region consists of a BranchBlock, a FallThroughBlock, and a
588
/// BranchTargetBlock. Branch coalesce works on patterns where the
589
/// TargetRegion's BranchTargetBlock must also be the SourceRegions's
590
/// BranchBlock.
591
///
592
///  Before mergeCandidates:
593
///
594
///  +---------------------------+
595
///  |  TargetRegion.BranchBlock |
596
///  +---------------------------+
597
///     /        |
598
///    /   +--------------------------------+
599
///   |    |  TargetRegion.FallThroughBlock |
600
///    \   +--------------------------------+
601
///     \        |
602
///  +----------------------------------+
603
///  |  TargetRegion.BranchTargetBlock  |
604
///  |  SourceRegion.BranchBlock        |
605
///  +----------------------------------+
606
///     /        |
607
///    /   +--------------------------------+
608
///   |    |  SourceRegion.FallThroughBlock |
609
///    \   +--------------------------------+
610
///     \        |
611
///  +----------------------------------+
612
///  |  SourceRegion.BranchTargetBlock  |
613
///  +----------------------------------+
614
///
615
///  After mergeCandidates:
616
///
617
///  +-----------------------------+
618
///  |  TargetRegion.BranchBlock   |
619
///  |  SourceRegion.BranchBlock   |
620
///  +-----------------------------+
621
///     /        |
622
///    /   +---------------------------------+
623
///   |    |  TargetRegion.FallThroughBlock  |
624
///   |    |  SourceRegion.FallThroughBlock  |
625
///    \   +---------------------------------+
626
///     \        |
627
///  +----------------------------------+
628
///  |  SourceRegion.BranchTargetBlock  |
629
///  +----------------------------------+
630
///
631
/// \param[in] SourceRegion The candidate to move blocks from
632
/// \param[in] TargetRegion The candidate to move blocks to
633
///
634
bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
635
4
                                       CoalescingCandidateInfo &TargetRegion) {
636
4
637
4
  if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
638
0
    llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
639
0
    return false;
640
4
  }
641
4
642
4
  if (!validateCandidates(SourceRegion, TargetRegion))
643
0
    return false;
644
4
645
4
  // Start the merging process by first handling the BranchBlock.
646
4
  // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
647
4
  moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
648
4
649
4
  // Move remaining instructions in SourceRegion.BranchBlock into
650
4
  // TargetRegion.BranchBlock
651
4
  MachineBasicBlock::iterator firstInstr =
652
4
      SourceRegion.BranchBlock->getFirstNonPHI();
653
4
  MachineBasicBlock::iterator lastInstr =
654
4
      SourceRegion.BranchBlock->getFirstTerminator();
655
4
656
4
  MachineBasicBlock *Source = SourceRegion.MustMoveDown
657
4
                                  ? 
SourceRegion.BranchTargetBlock0
658
4
                                  : TargetRegion.BranchBlock;
659
4
660
4
  MachineBasicBlock::iterator Target =
661
4
      SourceRegion.MustMoveDown
662
4
          ? 
SourceRegion.BranchTargetBlock->getFirstNonPHI()0
663
4
          : TargetRegion.BranchBlock->getFirstTerminator();
664
4
665
4
  Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
666
4
667
4
  // Once PHI and instructions have been moved we need to clean up the
668
4
  // control flow.
669
4
670
4
  // Remove SourceRegion.FallThroughBlock before transferring successors of
671
4
  // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
672
4
  SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
673
4
  TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
674
4
      SourceRegion.BranchBlock);
675
4
  // Update branch in TargetRegion.BranchBlock to jump to
676
4
  // SourceRegion.BranchTargetBlock
677
4
  // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
678
4
  TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
679
4
      SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
680
4
  // Remove the branch statement(s) in SourceRegion.BranchBlock
681
4
  MachineBasicBlock::iterator I =
682
4
      SourceRegion.BranchBlock->terminators().begin();
683
8
  while (I != SourceRegion.BranchBlock->terminators().end()) {
684
4
    MachineInstr &CurrInst = *I;
685
4
    ++I;
686
4
    if (CurrInst.isBranch())
687
4
      CurrInst.eraseFromParent();
688
4
  }
689
4
690
4
  // Fall-through block should be empty since this is part of the condition
691
4
  // to coalesce the branches.
692
4
  assert(TargetRegion.FallThroughBlock->empty() &&
693
4
         "FallThroughBlocks should be empty!");
694
4
695
4
  // Transfer successor information and move PHIs down to the
696
4
  // branch-taken block.
697
4
  TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
698
4
      SourceRegion.FallThroughBlock);
699
4
  TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
700
4
701
4
  // Remove the blocks from the function.
702
4
  assert(SourceRegion.BranchBlock->empty() &&
703
4
         "Expecting branch block to be empty!");
704
4
  SourceRegion.BranchBlock->eraseFromParent();
705
4
706
4
  assert(SourceRegion.FallThroughBlock->empty() &&
707
4
         "Expecting fall-through block to be empty!\n");
708
4
  SourceRegion.FallThroughBlock->eraseFromParent();
709
4
710
4
  NumBlocksCoalesced++;
711
4
  return true;
712
4
}
713
714
2
bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
715
2
716
2
  if (skipFunction(MF.getFunction()) || MF.empty())
717
0
    return false;
718
2
719
2
  bool didSomething = false;
720
2
721
2
  LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");
722
2
  initialize(MF);
723
2
724
2
  LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
725
2
726
2
  CoalescingCandidateInfo Cand1, Cand2;
727
2
  // Walk over blocks and find candidates to merge
728
2
  // Continue trying to merge with the first candidate found, as long as merging
729
2
  // is successfull.
730
6
  for (MachineBasicBlock &MBB : MF) {
731
6
    bool MergedCandidates = false;
732
10
    do {
733
10
      MergedCandidates = false;
734
10
      Cand1.clear();
735
10
      Cand2.clear();
736
10
737
10
      Cand1.BranchBlock = &MBB;
738
10
739
10
      // If unable to coalesce the branch, then continue to next block
740
10
      if (!canCoalesceBranch(Cand1))
741
4
        break;
742
6
743
6
      Cand2.BranchBlock = Cand1.BranchTargetBlock;
744
6
      if (!canCoalesceBranch(Cand2))
745
2
        break;
746
4
747
4
      // Sanity check
748
4
      // The branch-taken block of the second candidate should post-dominate the
749
4
      // first candidate
750
4
      assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
751
4
             "Branch-taken block should post-dominate first candidate");
752
4
753
4
      if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
754
0
        LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()
755
0
                          << " and " << Cand2.BranchBlock->getNumber()
756
0
                          << " have different branches\n");
757
0
        break;
758
0
      }
759
4
      if (!canMerge(Cand2, Cand1)) {
760
0
        LLVM_DEBUG(dbgs() << "Cannot merge blocks "
761
0
                          << Cand1.BranchBlock->getNumber() << " and "
762
0
                          << Cand2.BranchBlock->getNumber() << "\n");
763
0
        NumBlocksNotCoalesced++;
764
0
        continue;
765
0
      }
766
4
      LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
767
4
                        << " and " << Cand1.BranchTargetBlock->getNumber()
768
4
                        << "\n");
769
4
      MergedCandidates = mergeCandidates(Cand2, Cand1);
770
4
      if (MergedCandidates)
771
4
        didSomething = true;
772
4
773
4
      LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();
774
4
                 dbgs() << "\n");
775
4
    } while (MergedCandidates);
776
6
  }
777
2
778
#ifndef NDEBUG
779
  // Verify MF is still valid after branch coalescing
780
  if (didSomething)
781
    MF.verify(nullptr, "Error in code produced by branch coalescing");
782
#endif // NDEBUG
783
784
2
  LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");
785
2
  return didSomething;
786
2
}