Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/PowerPC/PPCExpandISEL.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------------- PPCExpandISEL.cpp - Expand ISEL instruction ------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// A pass that expands the ISEL instruction into an if-then-else sequence.
11
// This pass must be run post-RA since all operands must be physical registers.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "PPC.h"
16
#include "PPCInstrInfo.h"
17
#include "PPCSubtarget.h"
18
#include "llvm/ADT/DenseMap.h"
19
#include "llvm/ADT/Statistic.h"
20
#include "llvm/CodeGen/LivePhysRegs.h"
21
#include "llvm/CodeGen/MachineFunctionPass.h"
22
#include "llvm/CodeGen/MachineInstrBuilder.h"
23
#include "llvm/CodeGen/MachineRegisterInfo.h"
24
#include "llvm/Support/CommandLine.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/raw_ostream.h"
27
28
using namespace llvm;
29
30
#define DEBUG_TYPE "ppc-expand-isel"
31
32
STATISTIC(NumExpanded, "Number of ISEL instructions expanded");
33
STATISTIC(NumRemoved, "Number of ISEL instructions removed");
34
STATISTIC(NumFolded, "Number of ISEL instructions folded");
35
36
// If -ppc-gen-isel=false is set, we will disable generating the ISEL
37
// instruction on all PPC targets. Otherwise, if the user set option
38
// -misel or the platform supports ISEL by default, still generate the
39
// ISEL instruction, else expand it.
40
static cl::opt<bool>
41
    GenerateISEL("ppc-gen-isel",
42
                 cl::desc("Enable generating the ISEL instruction."),
43
                 cl::init(true), cl::Hidden);
44
45
namespace {
46
class PPCExpandISEL : public MachineFunctionPass {
47
  DebugLoc dl;
48
  MachineFunction *MF;
49
  const TargetInstrInfo *TII;
50
  bool IsTrueBlockRequired;
51
  bool IsFalseBlockRequired;
52
  MachineBasicBlock *TrueBlock;
53
  MachineBasicBlock *FalseBlock;
54
  MachineBasicBlock *NewSuccessor;
55
  MachineBasicBlock::iterator TrueBlockI;
56
  MachineBasicBlock::iterator FalseBlockI;
57
58
  typedef SmallVector<MachineInstr *, 4> BlockISELList;
59
  typedef SmallDenseMap<int, BlockISELList> ISELInstructionList;
60
61
  // A map of MBB numbers to their lists of contained ISEL instructions.
62
  ISELInstructionList ISELInstructions;
63
64
  /// Initialize the object.
65
  void initialize(MachineFunction &MFParam);
66
67
  void handleSpecialCases(BlockISELList &BIL, MachineBasicBlock *MBB);
68
  void reorganizeBlockLayout(BlockISELList &BIL, MachineBasicBlock *MBB);
69
  void populateBlocks(BlockISELList &BIL);
70
  void expandMergeableISELs(BlockISELList &BIL);
71
  void expandAndMergeISELs();
72
73
  bool canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI);
74
75
  ///  Is this instruction an ISEL or ISEL8?
76
20.8k
  static bool isISEL(const MachineInstr &MI) {
77
20.7k
    return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8);
78
20.8k
  }
79
80
  ///  Is this instruction an ISEL8?
81
267
  static bool isISEL8(const MachineInstr &MI) {
82
267
    return (MI.getOpcode() == PPC::ISEL8);
83
267
  }
84
85
  /// Are the two operands using the same register?
86
1.08k
  bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) {
87
1.08k
    return (Op1.getReg() == Op2.getReg());
88
1.08k
  }
89
90
  ///
91
  ///  Collect all ISEL instructions from the current function.
92
  ///
93
  /// Walk the current function and collect all the ISEL instructions that are
94
  /// found. The instructions are placed in the ISELInstructions vector.
95
  ///
96
  /// \return true if any ISEL instructions were found, false otherwise
97
  ///
98
  bool collectISELInstructions();
99
100
public:
101
  static char ID;
102
1.37k
  PPCExpandISEL() : MachineFunctionPass(ID) {
103
1.37k
    initializePPCExpandISELPass(*PassRegistry::getPassRegistry());
104
1.37k
  }
105
106
  ///
107
  ///  Determine whether to generate the ISEL instruction or expand it.
108
  ///
109
  /// Expand ISEL instruction into if-then-else sequence when one of
110
  /// the following two conditions hold:
111
  /// (1) -ppc-gen-isel=false
112
  /// (2) hasISEL() return false
113
  /// Otherwise, still generate ISEL instruction.
114
  /// The -ppc-gen-isel option is set to true by default. Which means the ISEL
115
  /// instruction is still generated by default on targets that support them.
116
  ///
117
  /// \return true if ISEL should be expanded into if-then-else code sequence;
118
  ///         false if ISEL instruction should be generated, i.e. not expaned.
119
  ///
120
  static bool isExpandISELEnabled(const MachineFunction &MF);
121
122
#ifndef NDEBUG
123
  void DumpISELInstructions() const;
124
#endif
125
126
7.49k
  bool runOnMachineFunction(MachineFunction &MF) override {
127
7.49k
    if (!isExpandISELEnabled(MF))
128
5.66k
      return false;
129
1.83k
130
1.83k
    
DEBUG1.83k
(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
131
1.83k
    initialize(MF);
132
1.83k
133
1.83k
    if (
!collectISELInstructions()1.83k
) {
134
1.71k
      DEBUG(dbgs() << "No ISEL instructions in this function\n");
135
1.71k
      return false;
136
1.71k
    }
137
114
138
#ifndef NDEBUG
139
    DumpISELInstructions();
140
#endif
141
142
114
    expandAndMergeISELs();
143
114
144
114
    return true;
145
114
  }
146
};
147
} // end anonymous namespace
148
149
1.83k
void PPCExpandISEL::initialize(MachineFunction &MFParam) {
150
1.83k
  MF = &MFParam;
151
1.83k
  TII = MF->getSubtarget().getInstrInfo();
152
1.83k
  ISELInstructions.clear();
153
1.83k
}
154
155
7.49k
bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) {
156
7.36k
  return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL();
157
7.49k
}
158
159
1.83k
bool PPCExpandISEL::collectISELInstructions() {
160
3.00k
  for (MachineBasicBlock &MBB : *MF) {
161
3.00k
    BlockISELList thisBlockISELs;
162
3.00k
    for (MachineInstr &MI : MBB)
163
20.8k
      
if (20.8k
isISEL(MI)20.8k
)
164
202
        thisBlockISELs.push_back(&MI);
165
3.00k
    if (!thisBlockISELs.empty())
166
122
      ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs));
167
3.00k
  }
168
1.83k
  return !ISELInstructions.empty();
169
1.83k
}
170
171
#ifndef NDEBUG
172
void PPCExpandISEL::DumpISELInstructions() const {
173
  for (const auto &I : ISELInstructions) {
174
    DEBUG(dbgs() << "BB#" << I.first << ":\n");
175
    for (const auto &VI : I.second)
176
      DEBUG(dbgs() << "    "; VI->print(dbgs()));
177
  }
178
}
179
#endif
180
181
/// Contiguous ISELs that have the same condition can be merged.
182
80
bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) {
183
80
  // Same Condition Register?
184
80
  if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3)))
185
36
    return false;
186
44
187
44
  MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI;
188
44
  MachineBasicBlock::iterator MBBI = *MI;
189
44
  return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs?
190
44
}
191
192
114
void PPCExpandISEL::expandAndMergeISELs() {
193
122
  for (auto &BlockList : ISELInstructions) {
194
122
    DEBUG(dbgs() << "Expanding ISEL instructions in BB#" << BlockList.first
195
122
                 << "\n");
196
122
197
122
    BlockISELList &CurrentISELList = BlockList.second;
198
122
    auto I = CurrentISELList.begin();
199
122
    auto E = CurrentISELList.end();
200
122
201
303
    while (
I != E303
) {
202
181
      BlockISELList SubISELList;
203
181
204
181
      SubISELList.push_back(*I++);
205
181
206
181
      // Collect the ISELs that can be merged together.
207
202
      while (
I != E && 202
canMerge(SubISELList.back(), *I)80
)
208
21
        SubISELList.push_back(*I++);
209
181
210
181
      expandMergeableISELs(SubISELList);
211
181
    }
212
122
  }
213
114
}
214
215
void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
216
181
                                       MachineBasicBlock *MBB) {
217
181
  IsTrueBlockRequired = false;
218
181
  IsFalseBlockRequired = false;
219
181
220
181
  auto MI = BIL.begin();
221
383
  while (
MI != BIL.end()383
) {
222
202
    assert(isISEL(**MI) && "Expecting an ISEL instruction");
223
202
    DEBUG(dbgs() << "ISEL: " << **MI << "\n");
224
202
225
202
    MachineOperand &Dest = (*MI)->getOperand(0);
226
202
    MachineOperand &TrueValue = (*MI)->getOperand(1);
227
202
    MachineOperand &FalseValue = (*MI)->getOperand(2);
228
202
229
202
    // If at least one of the ISEL instructions satisfy the following
230
202
    // condition, we need the True Block:
231
202
    // The Dest Register and True Value Register are not the same
232
202
    // Similarly, if at least one of the ISEL instructions satisfy the
233
202
    // following condition, we need the False Block:
234
202
    // The Dest Register and False Value Register are not the same.
235
202
236
202
    bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
237
202
    bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
238
202
239
202
    // Special case 1, all registers used by ISEL are the same one.
240
202
    if (
!IsADDIInstRequired && 202
!IsORIInstRequired42
) {
241
1
      DEBUG(dbgs() << "Remove redudant ISEL instruction.");
242
1
      NumRemoved++;
243
1
      (*MI)->eraseFromParent();
244
1
      // Setting MI to the erase result keeps the iterator valid and increased.
245
1
      MI = BIL.erase(MI);
246
1
      continue;
247
1
    }
248
201
249
201
    // Special case 2, the two input registers used by ISEL are the same.
250
201
    // Note 1: We favor merging ISEL expansions over folding a single one. If
251
201
    // the passed list has multiple merge-able ISEL's, we won't fold any.
252
201
    // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
253
201
    // PPC::ZERO8 will be used for the first operand if the value is meant to
254
201
    // be zero. In this case, the useSameRegister method will return false,
255
201
    // thereby preventing this ISEL from being folded.
256
201
257
201
    
if (201
useSameRegister(TrueValue, FalseValue) && 201
(BIL.size() == 1)0
) {
258
0
      DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy.");
259
0
      NumFolded++;
260
0
      BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? 
PPC::ADDI80
:
PPC::ADDI0
))
261
0
          .add(Dest)
262
0
          .add(TrueValue)
263
0
          .add(MachineOperand::CreateImm(0));
264
0
      (*MI)->eraseFromParent();
265
0
      // Setting MI to the erase result keeps the iterator valid and increased.
266
0
      MI = BIL.erase(MI);
267
0
      continue;
268
0
    }
269
201
270
201
    IsTrueBlockRequired |= IsADDIInstRequired;
271
201
    IsFalseBlockRequired |= IsORIInstRequired;
272
201
    MI++;
273
201
  }
274
181
}
275
276
void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
277
181
                                          MachineBasicBlock *MBB) {
278
181
  if (BIL.empty())
279
0
    return;
280
181
281
181
  assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
282
181
         "Should have been handled by special cases earlier!");
283
181
284
181
  MachineBasicBlock *Successor = nullptr;
285
181
  const BasicBlock *LLVM_BB = MBB->getBasicBlock();
286
181
  MachineBasicBlock::iterator MBBI = (*BIL.back());
287
3
  NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
288
181
                     // Another BB is needed to move the instructions that
289
181
                     // follow this ISEL.  If the ISEL is the last instruction
290
181
                     // in a block that can't fall through, we also need a block
291
181
                     // to branch to.
292
179
                     ? MF->CreateMachineBasicBlock(LLVM_BB)
293
2
                     : nullptr;
294
181
295
181
  MachineFunction::iterator It = MBB->getIterator();
296
181
  ++It; // Point to the successor block of MBB.
297
181
298
181
  // If NewSuccessor is NULL then the last ISEL in this group is the last
299
181
  // non-debug instruction in this block. Find the fall-through successor
300
181
  // of this block to use when updating the CFG below.
301
181
  if (
!NewSuccessor181
) {
302
2
    for (auto &Succ : MBB->successors()) {
303
2
      if (
MBB->isLayoutSuccessor(Succ)2
) {
304
2
        Successor = Succ;
305
2
        break;
306
2
      }
307
181
    }
308
2
  } else
309
179
    Successor = NewSuccessor;
310
181
311
181
  // The FalseBlock and TrueBlock are inserted after the MBB block but before
312
181
  // its successor.
313
181
  // Note this need to be done *after* the above setting the Successor code.
314
181
  if (
IsFalseBlockRequired181
) {
315
94
    FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
316
94
    MF->insert(It, FalseBlock);
317
94
  }
318
181
319
181
  if (
IsTrueBlockRequired181
) {
320
147
    TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
321
147
    MF->insert(It, TrueBlock);
322
147
  }
323
181
324
181
  if (
NewSuccessor181
) {
325
179
    MF->insert(It, NewSuccessor);
326
179
327
179
    // Transfer the rest of this block into the new successor block.
328
179
    NewSuccessor->splice(NewSuccessor->end(), MBB,
329
179
                         std::next(MachineBasicBlock::iterator(BIL.back())),
330
179
                         MBB->end());
331
179
    NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
332
179
333
179
    // Copy the original liveIns of MBB to NewSuccessor.
334
179
    for (auto &LI : MBB->liveins())
335
8.35k
      NewSuccessor->addLiveIn(LI);
336
179
337
179
    // After splitting the NewSuccessor block, Regs defined but not killed
338
179
    // in MBB should be treated as liveins of NewSuccessor.
339
179
    // Note: Cannot use stepBackward instead since we are using the Reg
340
179
    // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
341
179
    // NewSuccessor. Otherwise, will cause cyclic dependence.
342
179
    LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
343
179
    SmallVector<std::pair<unsigned, const MachineOperand *>, 2> Clobbers;
344
179
    for (MachineInstr &MI : *MBB)
345
1.38k
      LPR.stepForward(MI, Clobbers);
346
179
    for (auto &LI : LPR)
347
1.63k
      NewSuccessor->addLiveIn(LI);
348
181
  } else {
349
2
    // Remove successor from MBB.
350
2
    MBB->removeSuccessor(Successor);
351
2
  }
352
181
353
181
  // Note that this needs to be done *after* transfering the successors from MBB
354
181
  // to the NewSuccessor block, otherwise these blocks will also be transferred
355
181
  // as successors!
356
181
  MBB->addSuccessor(IsTrueBlockRequired ? 
TrueBlock147
:
Successor34
);
357
181
  MBB->addSuccessor(IsFalseBlockRequired ? 
FalseBlock94
:
Successor87
);
358
181
359
181
  if (
IsTrueBlockRequired181
) {
360
147
    TrueBlockI = TrueBlock->begin();
361
147
    TrueBlock->addSuccessor(Successor);
362
147
  }
363
181
364
181
  if (
IsFalseBlockRequired181
) {
365
94
    FalseBlockI = FalseBlock->begin();
366
94
    FalseBlock->addSuccessor(Successor);
367
94
  }
368
181
369
181
  // Conditional branch to the TrueBlock or Successor
370
181
  BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
371
181
      .add(BIL.back()->getOperand(3))
372
181
      .addMBB(IsTrueBlockRequired ? 
TrueBlock147
:
Successor34
);
373
181
374
181
  // Jump over the true block to the new successor if the condition is false.
375
181
  BuildMI(*(IsFalseBlockRequired ? 
FalseBlock94
:
MBB87
),
376
181
          (IsFalseBlockRequired ? 
FalseBlockI94
:
BIL.back()87
), dl,
377
181
          TII->get(PPC::B))
378
181
      .addMBB(Successor);
379
181
380
181
  if (IsFalseBlockRequired)
381
94
    FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
382
181
}
383
384
181
void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
385
201
  for (auto &MI : BIL) {
386
201
    assert(isISEL(*MI) && "Expecting an ISEL instruction");
387
201
388
201
    MachineOperand &Dest = MI->getOperand(0);       // location to store to
389
201
    MachineOperand &TrueValue = MI->getOperand(1);  // Value to store if
390
201
                                                       // condition is true
391
201
    MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
392
201
                                                       // condition is false
393
201
    MachineOperand &ConditionRegister = MI->getOperand(3); // Condition
394
201
395
201
    DEBUG(dbgs() << "Dest: " << Dest << "\n");
396
201
    DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
397
201
    DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
398
201
    DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
399
201
400
201
401
201
    // If the Dest Register and True Value Register are not the same one, we
402
201
    // need the True Block.
403
201
    bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
404
201
    bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
405
201
406
201
    if (
IsADDIInstRequired201
) {
407
160
      // Copy the result into the destination if the condition is true.
408
160
      BuildMI(*TrueBlock, TrueBlockI, dl,
409
160
              TII->get(isISEL8(*MI) ? 
PPC::ADDI859
:
PPC::ADDI101
))
410
160
          .add(Dest)
411
160
          .add(TrueValue)
412
160
          .add(MachineOperand::CreateImm(0));
413
160
414
160
      // Add the LiveIn registers required by true block.
415
160
      TrueBlock->addLiveIn(TrueValue.getReg());
416
160
    }
417
201
418
201
    if (
IsORIInstRequired201
) {
419
107
      // Add the LiveIn registers required by false block.
420
107
      FalseBlock->addLiveIn(FalseValue.getReg());
421
107
    }
422
201
423
201
    if (
NewSuccessor201
) {
424
199
      // Add the LiveIn registers required by NewSuccessor block.
425
199
      NewSuccessor->addLiveIn(Dest.getReg());
426
199
      NewSuccessor->addLiveIn(TrueValue.getReg());
427
199
      NewSuccessor->addLiveIn(FalseValue.getReg());
428
199
      NewSuccessor->addLiveIn(ConditionRegister.getReg());
429
199
    }
430
201
431
201
    // Copy the value into the destination if the condition is false.
432
201
    if (IsORIInstRequired)
433
107
      BuildMI(*FalseBlock, FalseBlockI, dl,
434
107
              TII->get(isISEL8(*MI) ? 
PPC::ORI852
:
PPC::ORI55
))
435
107
          .add(Dest)
436
107
          .add(FalseValue)
437
107
          .add(MachineOperand::CreateImm(0));
438
201
439
201
    MI->eraseFromParent(); // Remove the ISEL instruction.
440
201
441
201
    NumExpanded++;
442
201
  }
443
181
}
444
445
181
void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
446
181
  // At this stage all the ISELs of BIL are in the same MBB.
447
181
  MachineBasicBlock *MBB = BIL.back()->getParent();
448
181
449
181
  handleSpecialCases(BIL, MBB);
450
181
  reorganizeBlockLayout(BIL, MBB);
451
181
  populateBlocks(BIL);
452
181
}
453
454
INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
455
                false, false)
456
char PPCExpandISEL::ID = 0;
457
458
1.36k
FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }