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