121
|
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 static bool isISEL(const MachineInstr &MI) {
|
|
77 return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8);
|
|
78 }
|
|
79
|
|
80 /// Is this instruction an ISEL8?
|
|
81 static bool isISEL8(const MachineInstr &MI) {
|
|
82 return (MI.getOpcode() == PPC::ISEL8);
|
|
83 }
|
|
84
|
|
85 /// Are the two operands using the same register?
|
|
86 bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) {
|
|
87 return (Op1.getReg() == Op2.getReg());
|
|
88 }
|
|
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 PPCExpandISEL() : MachineFunctionPass(ID) {
|
|
103 initializePPCExpandISELPass(*PassRegistry::getPassRegistry());
|
|
104 }
|
|
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 bool runOnMachineFunction(MachineFunction &MF) override {
|
|
127 if (!isExpandISELEnabled(MF))
|
|
128 return false;
|
|
129
|
|
130 DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
|
|
131 initialize(MF);
|
|
132
|
|
133 if (!collectISELInstructions()) {
|
|
134 DEBUG(dbgs() << "No ISEL instructions in this function\n");
|
|
135 return false;
|
|
136 }
|
|
137
|
|
138 #ifndef NDEBUG
|
|
139 DumpISELInstructions();
|
|
140 #endif
|
|
141
|
|
142 expandAndMergeISELs();
|
|
143
|
|
144 return true;
|
|
145 }
|
|
146 };
|
|
147 } // end anonymous namespace
|
|
148
|
|
149 void PPCExpandISEL::initialize(MachineFunction &MFParam) {
|
|
150 MF = &MFParam;
|
|
151 TII = MF->getSubtarget().getInstrInfo();
|
|
152 ISELInstructions.clear();
|
|
153 }
|
|
154
|
|
155 bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) {
|
|
156 return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL();
|
|
157 }
|
|
158
|
|
159 bool PPCExpandISEL::collectISELInstructions() {
|
|
160 for (MachineBasicBlock &MBB : *MF) {
|
|
161 BlockISELList thisBlockISELs;
|
|
162 for (MachineInstr &MI : MBB)
|
|
163 if (isISEL(MI))
|
|
164 thisBlockISELs.push_back(&MI);
|
|
165 if (!thisBlockISELs.empty())
|
|
166 ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs));
|
|
167 }
|
|
168 return !ISELInstructions.empty();
|
|
169 }
|
|
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 bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) {
|
|
183 // Same Condition Register?
|
|
184 if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3)))
|
|
185 return false;
|
|
186
|
|
187 MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI;
|
|
188 MachineBasicBlock::iterator MBBI = *MI;
|
|
189 return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs?
|
|
190 }
|
|
191
|
|
192 void PPCExpandISEL::expandAndMergeISELs() {
|
|
193 for (auto &BlockList : ISELInstructions) {
|
|
194 DEBUG(dbgs() << "Expanding ISEL instructions in BB#" << BlockList.first
|
|
195 << "\n");
|
|
196
|
|
197 BlockISELList &CurrentISELList = BlockList.second;
|
|
198 auto I = CurrentISELList.begin();
|
|
199 auto E = CurrentISELList.end();
|
|
200
|
|
201 while (I != E) {
|
|
202 BlockISELList SubISELList;
|
|
203
|
|
204 SubISELList.push_back(*I++);
|
|
205
|
|
206 // Collect the ISELs that can be merged together.
|
|
207 while (I != E && canMerge(SubISELList.back(), *I))
|
|
208 SubISELList.push_back(*I++);
|
|
209
|
|
210 expandMergeableISELs(SubISELList);
|
|
211 }
|
|
212 }
|
|
213 }
|
|
214
|
|
215 void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
|
|
216 MachineBasicBlock *MBB) {
|
|
217 IsTrueBlockRequired = false;
|
|
218 IsFalseBlockRequired = false;
|
|
219
|
|
220 auto MI = BIL.begin();
|
|
221 while (MI != BIL.end()) {
|
|
222 assert(isISEL(**MI) && "Expecting an ISEL instruction");
|
|
223 DEBUG(dbgs() << "ISEL: " << **MI << "\n");
|
|
224
|
|
225 MachineOperand &Dest = (*MI)->getOperand(0);
|
|
226 MachineOperand &TrueValue = (*MI)->getOperand(1);
|
|
227 MachineOperand &FalseValue = (*MI)->getOperand(2);
|
|
228
|
|
229 // If at least one of the ISEL instructions satisfy the following
|
|
230 // condition, we need the True Block:
|
|
231 // The Dest Register and True Value Register are not the same
|
|
232 // Similarly, if at least one of the ISEL instructions satisfy the
|
|
233 // following condition, we need the False Block:
|
|
234 // The Dest Register and False Value Register are not the same.
|
|
235
|
|
236 bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
|
|
237 bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
|
|
238
|
|
239 // Special case 1, all registers used by ISEL are the same one.
|
|
240 if (!IsADDIInstRequired && !IsORIInstRequired) {
|
|
241 DEBUG(dbgs() << "Remove redudant ISEL instruction.");
|
|
242 NumRemoved++;
|
|
243 (*MI)->eraseFromParent();
|
|
244 // Setting MI to the erase result keeps the iterator valid and increased.
|
|
245 MI = BIL.erase(MI);
|
|
246 continue;
|
|
247 }
|
|
248
|
|
249 // Special case 2, the two input registers used by ISEL are the same.
|
|
250 // Note 1: We favor merging ISEL expansions over folding a single one. If
|
|
251 // the passed list has multiple merge-able ISEL's, we won't fold any.
|
|
252 // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
|
|
253 // PPC::ZERO8 will be used for the first operand if the value is meant to
|
|
254 // be zero. In this case, the useSameRegister method will return false,
|
|
255 // thereby preventing this ISEL from being folded.
|
|
256
|
|
257 if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) {
|
|
258 DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy.");
|
|
259 NumFolded++;
|
|
260 BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::ADDI8 : PPC::ADDI))
|
|
261 .add(Dest)
|
|
262 .add(TrueValue)
|
|
263 .add(MachineOperand::CreateImm(0));
|
|
264 (*MI)->eraseFromParent();
|
|
265 // Setting MI to the erase result keeps the iterator valid and increased.
|
|
266 MI = BIL.erase(MI);
|
|
267 continue;
|
|
268 }
|
|
269
|
|
270 IsTrueBlockRequired |= IsADDIInstRequired;
|
|
271 IsFalseBlockRequired |= IsORIInstRequired;
|
|
272 MI++;
|
|
273 }
|
|
274 }
|
|
275
|
|
276 void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
|
|
277 MachineBasicBlock *MBB) {
|
|
278 if (BIL.empty())
|
|
279 return;
|
|
280
|
|
281 assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
|
|
282 "Should have been handled by special cases earlier!");
|
|
283
|
|
284 MachineBasicBlock *Successor = nullptr;
|
|
285 const BasicBlock *LLVM_BB = MBB->getBasicBlock();
|
|
286 MachineBasicBlock::iterator MBBI = (*BIL.back());
|
|
287 NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
|
|
288 // Another BB is needed to move the instructions that
|
|
289 // follow this ISEL. If the ISEL is the last instruction
|
|
290 // in a block that can't fall through, we also need a block
|
|
291 // to branch to.
|
|
292 ? MF->CreateMachineBasicBlock(LLVM_BB)
|
|
293 : nullptr;
|
|
294
|
|
295 MachineFunction::iterator It = MBB->getIterator();
|
|
296 ++It; // Point to the successor block of MBB.
|
|
297
|
|
298 // If NewSuccessor is NULL then the last ISEL in this group is the last
|
|
299 // non-debug instruction in this block. Find the fall-through successor
|
|
300 // of this block to use when updating the CFG below.
|
|
301 if (!NewSuccessor) {
|
|
302 for (auto &Succ : MBB->successors()) {
|
|
303 if (MBB->isLayoutSuccessor(Succ)) {
|
|
304 Successor = Succ;
|
|
305 break;
|
|
306 }
|
|
307 }
|
|
308 } else
|
|
309 Successor = NewSuccessor;
|
|
310
|
|
311 // The FalseBlock and TrueBlock are inserted after the MBB block but before
|
|
312 // its successor.
|
|
313 // Note this need to be done *after* the above setting the Successor code.
|
|
314 if (IsFalseBlockRequired) {
|
|
315 FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
|
|
316 MF->insert(It, FalseBlock);
|
|
317 }
|
|
318
|
|
319 if (IsTrueBlockRequired) {
|
|
320 TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
|
|
321 MF->insert(It, TrueBlock);
|
|
322 }
|
|
323
|
|
324 if (NewSuccessor) {
|
|
325 MF->insert(It, NewSuccessor);
|
|
326
|
|
327 // Transfer the rest of this block into the new successor block.
|
|
328 NewSuccessor->splice(NewSuccessor->end(), MBB,
|
|
329 std::next(MachineBasicBlock::iterator(BIL.back())),
|
|
330 MBB->end());
|
|
331 NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
|
|
332
|
|
333 // Copy the original liveIns of MBB to NewSuccessor.
|
|
334 for (auto &LI : MBB->liveins())
|
|
335 NewSuccessor->addLiveIn(LI);
|
|
336
|
|
337 // After splitting the NewSuccessor block, Regs defined but not killed
|
|
338 // in MBB should be treated as liveins of NewSuccessor.
|
|
339 // Note: Cannot use stepBackward instead since we are using the Reg
|
|
340 // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
|
|
341 // NewSuccessor. Otherwise, will cause cyclic dependence.
|
|
342 LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
|
|
343 SmallVector<std::pair<unsigned, const MachineOperand *>, 2> Clobbers;
|
|
344 for (MachineInstr &MI : *MBB)
|
|
345 LPR.stepForward(MI, Clobbers);
|
|
346 for (auto &LI : LPR)
|
|
347 NewSuccessor->addLiveIn(LI);
|
|
348 } else {
|
|
349 // Remove successor from MBB.
|
|
350 MBB->removeSuccessor(Successor);
|
|
351 }
|
|
352
|
|
353 // Note that this needs to be done *after* transfering the successors from MBB
|
|
354 // to the NewSuccessor block, otherwise these blocks will also be transferred
|
|
355 // as successors!
|
|
356 MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor);
|
|
357 MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor);
|
|
358
|
|
359 if (IsTrueBlockRequired) {
|
|
360 TrueBlockI = TrueBlock->begin();
|
|
361 TrueBlock->addSuccessor(Successor);
|
|
362 }
|
|
363
|
|
364 if (IsFalseBlockRequired) {
|
|
365 FalseBlockI = FalseBlock->begin();
|
|
366 FalseBlock->addSuccessor(Successor);
|
|
367 }
|
|
368
|
|
369 // Conditional branch to the TrueBlock or Successor
|
|
370 BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
|
|
371 .add(BIL.back()->getOperand(3))
|
|
372 .addMBB(IsTrueBlockRequired ? TrueBlock : Successor);
|
|
373
|
|
374 // Jump over the true block to the new successor if the condition is false.
|
|
375 BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB),
|
|
376 (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl,
|
|
377 TII->get(PPC::B))
|
|
378 .addMBB(Successor);
|
|
379
|
|
380 if (IsFalseBlockRequired)
|
|
381 FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
|
|
382 }
|
|
383
|
|
384 void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
|
|
385 for (auto &MI : BIL) {
|
|
386 assert(isISEL(*MI) && "Expecting an ISEL instruction");
|
|
387
|
|
388 MachineOperand &Dest = MI->getOperand(0); // location to store to
|
|
389 MachineOperand &TrueValue = MI->getOperand(1); // Value to store if
|
|
390 // condition is true
|
|
391 MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
|
|
392 // condition is false
|
|
393 MachineOperand &ConditionRegister = MI->getOperand(3); // Condition
|
|
394
|
|
395 DEBUG(dbgs() << "Dest: " << Dest << "\n");
|
|
396 DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
|
|
397 DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
|
|
398 DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
|
|
399
|
|
400
|
|
401 // If the Dest Register and True Value Register are not the same one, we
|
|
402 // need the True Block.
|
|
403 bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
|
|
404 bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
|
|
405
|
|
406 if (IsADDIInstRequired) {
|
|
407 // Copy the result into the destination if the condition is true.
|
|
408 BuildMI(*TrueBlock, TrueBlockI, dl,
|
|
409 TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
|
|
410 .add(Dest)
|
|
411 .add(TrueValue)
|
|
412 .add(MachineOperand::CreateImm(0));
|
|
413
|
|
414 // Add the LiveIn registers required by true block.
|
|
415 TrueBlock->addLiveIn(TrueValue.getReg());
|
|
416 }
|
|
417
|
|
418 if (IsORIInstRequired) {
|
|
419 // Add the LiveIn registers required by false block.
|
|
420 FalseBlock->addLiveIn(FalseValue.getReg());
|
|
421 }
|
|
422
|
|
423 if (NewSuccessor) {
|
|
424 // Add the LiveIn registers required by NewSuccessor block.
|
|
425 NewSuccessor->addLiveIn(Dest.getReg());
|
|
426 NewSuccessor->addLiveIn(TrueValue.getReg());
|
|
427 NewSuccessor->addLiveIn(FalseValue.getReg());
|
|
428 NewSuccessor->addLiveIn(ConditionRegister.getReg());
|
|
429 }
|
|
430
|
|
431 // Copy the value into the destination if the condition is false.
|
|
432 if (IsORIInstRequired)
|
|
433 BuildMI(*FalseBlock, FalseBlockI, dl,
|
|
434 TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
|
|
435 .add(Dest)
|
|
436 .add(FalseValue)
|
|
437 .add(MachineOperand::CreateImm(0));
|
|
438
|
|
439 MI->eraseFromParent(); // Remove the ISEL instruction.
|
|
440
|
|
441 NumExpanded++;
|
|
442 }
|
|
443 }
|
|
444
|
|
445 void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
|
|
446 // At this stage all the ISELs of BIL are in the same MBB.
|
|
447 MachineBasicBlock *MBB = BIL.back()->getParent();
|
|
448
|
|
449 handleSpecialCases(BIL, MBB);
|
|
450 reorganizeBlockLayout(BIL, MBB);
|
|
451 populateBlocks(BIL);
|
|
452 }
|
|
453
|
|
454 INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
|
|
455 false, false)
|
|
456 char PPCExpandISEL::ID = 0;
|
|
457
|
|
458 FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }
|