xref: /llvm-project/llvm/lib/Target/PowerPC/PPCMIPeephole.cpp (revision 24ee4edee8e00bb7ad3d3cda17d02a442456ff3e)
1 //===-------------- PPCMIPeephole.cpp - MI Peephole Cleanups -------------===//
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 performs peephole optimizations to clean up ugly code
10 // sequences at the MachineInstruction layer.  It runs at the end of
11 // the SSA phases, following VSX swap removal.  A pass of dead code
12 // elimination follows this one for quick clean-up of any dead
13 // instructions introduced here.  Although we could do this as callbacks
14 // from the generic peephole pass, this would have a couple of bad
15 // effects:  it might remove optimization opportunities for VSX swap
16 // removal, and it would miss cleanups made possible following VSX
17 // swap removal.
18 //
19 //===---------------------------------------------------------------------===//
20 
21 #include "MCTargetDesc/PPCMCTargetDesc.h"
22 #include "MCTargetDesc/PPCPredicates.h"
23 #include "PPC.h"
24 #include "PPCInstrBuilder.h"
25 #include "PPCInstrInfo.h"
26 #include "PPCMachineFunctionInfo.h"
27 #include "PPCTargetMachine.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
30 #include "llvm/CodeGen/MachineDominators.h"
31 #include "llvm/CodeGen/MachineFunctionPass.h"
32 #include "llvm/CodeGen/MachineInstrBuilder.h"
33 #include "llvm/CodeGen/MachinePostDominators.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/InitializePasses.h"
36 #include "llvm/Support/Debug.h"
37 
38 using namespace llvm;
39 
40 #define DEBUG_TYPE "ppc-mi-peepholes"
41 
42 STATISTIC(RemoveTOCSave, "Number of TOC saves removed");
43 STATISTIC(MultiTOCSaves,
44           "Number of functions with multiple TOC saves that must be kept");
45 STATISTIC(NumTOCSavesInPrologue, "Number of TOC saves placed in the prologue");
46 STATISTIC(NumEliminatedSExt, "Number of eliminated sign-extensions");
47 STATISTIC(NumEliminatedZExt, "Number of eliminated zero-extensions");
48 STATISTIC(NumOptADDLIs, "Number of optimized ADD instruction fed by LI");
49 STATISTIC(NumConvertedToImmediateForm,
50           "Number of instructions converted to their immediate form");
51 STATISTIC(NumFunctionsEnteredInMIPeephole,
52           "Number of functions entered in PPC MI Peepholes");
53 STATISTIC(NumFixedPointIterations,
54           "Number of fixed-point iterations converting reg-reg instructions "
55           "to reg-imm ones");
56 STATISTIC(NumRotatesCollapsed,
57           "Number of pairs of rotate left, clear left/right collapsed");
58 STATISTIC(NumEXTSWAndSLDICombined,
59           "Number of pairs of EXTSW and SLDI combined as EXTSWSLI");
60 
61 static cl::opt<bool>
62 FixedPointRegToImm("ppc-reg-to-imm-fixed-point", cl::Hidden, cl::init(true),
63                    cl::desc("Iterate to a fixed point when attempting to "
64                             "convert reg-reg instructions to reg-imm"));
65 
66 static cl::opt<bool>
67 ConvertRegReg("ppc-convert-rr-to-ri", cl::Hidden, cl::init(true),
68               cl::desc("Convert eligible reg+reg instructions to reg+imm"));
69 
70 static cl::opt<bool>
71     EnableSExtElimination("ppc-eliminate-signext",
72                           cl::desc("enable elimination of sign-extensions"),
73                           cl::init(false), cl::Hidden);
74 
75 static cl::opt<bool>
76     EnableZExtElimination("ppc-eliminate-zeroext",
77                           cl::desc("enable elimination of zero-extensions"),
78                           cl::init(false), cl::Hidden);
79 
80 namespace {
81 
82 struct PPCMIPeephole : public MachineFunctionPass {
83 
84   static char ID;
85   const PPCInstrInfo *TII;
86   MachineFunction *MF;
87   MachineRegisterInfo *MRI;
88 
89   PPCMIPeephole() : MachineFunctionPass(ID) {
90     initializePPCMIPeepholePass(*PassRegistry::getPassRegistry());
91   }
92 
93 private:
94   MachineDominatorTree *MDT;
95   MachinePostDominatorTree *MPDT;
96   MachineBlockFrequencyInfo *MBFI;
97   uint64_t EntryFreq;
98 
99   // Initialize class variables.
100   void initialize(MachineFunction &MFParm);
101 
102   // Perform peepholes.
103   bool simplifyCode(void);
104 
105   // Perform peepholes.
106   bool eliminateRedundantCompare(void);
107   bool eliminateRedundantTOCSaves(std::map<MachineInstr *, bool> &TOCSaves);
108   bool combineSEXTAndSHL(MachineInstr &MI, MachineInstr *&ToErase);
109   bool emitRLDICWhenLoweringJumpTables(MachineInstr &MI);
110   void UpdateTOCSaves(std::map<MachineInstr *, bool> &TOCSaves,
111                       MachineInstr *MI);
112 
113 public:
114 
115   void getAnalysisUsage(AnalysisUsage &AU) const override {
116     AU.addRequired<MachineDominatorTree>();
117     AU.addRequired<MachinePostDominatorTree>();
118     AU.addRequired<MachineBlockFrequencyInfo>();
119     AU.addPreserved<MachineDominatorTree>();
120     AU.addPreserved<MachinePostDominatorTree>();
121     AU.addPreserved<MachineBlockFrequencyInfo>();
122     MachineFunctionPass::getAnalysisUsage(AU);
123   }
124 
125   // Main entry point for this pass.
126   bool runOnMachineFunction(MachineFunction &MF) override {
127     if (skipFunction(MF.getFunction()))
128       return false;
129     initialize(MF);
130     return simplifyCode();
131   }
132 };
133 
134 // Initialize class variables.
135 void PPCMIPeephole::initialize(MachineFunction &MFParm) {
136   MF = &MFParm;
137   MRI = &MF->getRegInfo();
138   MDT = &getAnalysis<MachineDominatorTree>();
139   MPDT = &getAnalysis<MachinePostDominatorTree>();
140   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
141   EntryFreq = MBFI->getEntryFreq();
142   TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
143   LLVM_DEBUG(dbgs() << "*** PowerPC MI peephole pass ***\n\n");
144   LLVM_DEBUG(MF->dump());
145 }
146 
147 static MachineInstr *getVRegDefOrNull(MachineOperand *Op,
148                                       MachineRegisterInfo *MRI) {
149   assert(Op && "Invalid Operand!");
150   if (!Op->isReg())
151     return nullptr;
152 
153   Register Reg = Op->getReg();
154   if (!Register::isVirtualRegister(Reg))
155     return nullptr;
156 
157   return MRI->getVRegDef(Reg);
158 }
159 
160 // This function returns number of known zero bits in output of MI
161 // starting from the most significant bit.
162 static unsigned
163 getKnownLeadingZeroCount(MachineInstr *MI, const PPCInstrInfo *TII) {
164   unsigned Opcode = MI->getOpcode();
165   if (Opcode == PPC::RLDICL || Opcode == PPC::RLDICL_rec ||
166       Opcode == PPC::RLDCL || Opcode == PPC::RLDCL_rec)
167     return MI->getOperand(3).getImm();
168 
169   if ((Opcode == PPC::RLDIC || Opcode == PPC::RLDIC_rec) &&
170       MI->getOperand(3).getImm() <= 63 - MI->getOperand(2).getImm())
171     return MI->getOperand(3).getImm();
172 
173   if ((Opcode == PPC::RLWINM || Opcode == PPC::RLWINM_rec ||
174        Opcode == PPC::RLWNM || Opcode == PPC::RLWNM_rec ||
175        Opcode == PPC::RLWINM8 || Opcode == PPC::RLWNM8) &&
176       MI->getOperand(3).getImm() <= MI->getOperand(4).getImm())
177     return 32 + MI->getOperand(3).getImm();
178 
179   if (Opcode == PPC::ANDI_rec) {
180     uint16_t Imm = MI->getOperand(2).getImm();
181     return 48 + countLeadingZeros(Imm);
182   }
183 
184   if (Opcode == PPC::CNTLZW || Opcode == PPC::CNTLZW_rec ||
185       Opcode == PPC::CNTTZW || Opcode == PPC::CNTTZW_rec ||
186       Opcode == PPC::CNTLZW8 || Opcode == PPC::CNTTZW8)
187     // The result ranges from 0 to 32.
188     return 58;
189 
190   if (Opcode == PPC::CNTLZD || Opcode == PPC::CNTLZD_rec ||
191       Opcode == PPC::CNTTZD || Opcode == PPC::CNTTZD_rec)
192     // The result ranges from 0 to 64.
193     return 57;
194 
195   if (Opcode == PPC::LHZ   || Opcode == PPC::LHZX  ||
196       Opcode == PPC::LHZ8  || Opcode == PPC::LHZX8 ||
197       Opcode == PPC::LHZU  || Opcode == PPC::LHZUX ||
198       Opcode == PPC::LHZU8 || Opcode == PPC::LHZUX8)
199     return 48;
200 
201   if (Opcode == PPC::LBZ   || Opcode == PPC::LBZX  ||
202       Opcode == PPC::LBZ8  || Opcode == PPC::LBZX8 ||
203       Opcode == PPC::LBZU  || Opcode == PPC::LBZUX ||
204       Opcode == PPC::LBZU8 || Opcode == PPC::LBZUX8)
205     return 56;
206 
207   if (TII->isZeroExtended(*MI))
208     return 32;
209 
210   return 0;
211 }
212 
213 // This function maintains a map for the pairs <TOC Save Instr, Keep>
214 // Each time a new TOC save is encountered, it checks if any of the existing
215 // ones are dominated by the new one. If so, it marks the existing one as
216 // redundant by setting it's entry in the map as false. It then adds the new
217 // instruction to the map with either true or false depending on if any
218 // existing instructions dominated the new one.
219 void PPCMIPeephole::UpdateTOCSaves(
220   std::map<MachineInstr *, bool> &TOCSaves, MachineInstr *MI) {
221   assert(TII->isTOCSaveMI(*MI) && "Expecting a TOC save instruction here");
222   assert(MF->getSubtarget<PPCSubtarget>().isELFv2ABI() &&
223          "TOC-save removal only supported on ELFv2");
224   PPCFunctionInfo *FI = MF->getInfo<PPCFunctionInfo>();
225 
226   MachineBasicBlock *Entry = &MF->front();
227   uint64_t CurrBlockFreq = MBFI->getBlockFreq(MI->getParent()).getFrequency();
228 
229   // If the block in which the TOC save resides is in a block that
230   // post-dominates Entry, or a block that is hotter than entry (keep in mind
231   // that early MachineLICM has already run so the TOC save won't be hoisted)
232   // we can just do the save in the prologue.
233   if (CurrBlockFreq > EntryFreq || MPDT->dominates(MI->getParent(), Entry))
234     FI->setMustSaveTOC(true);
235 
236   // If we are saving the TOC in the prologue, all the TOC saves can be removed
237   // from the code.
238   if (FI->mustSaveTOC()) {
239     for (auto &TOCSave : TOCSaves)
240       TOCSave.second = false;
241     // Add new instruction to map.
242     TOCSaves[MI] = false;
243     return;
244   }
245 
246   bool Keep = true;
247   for (auto It = TOCSaves.begin(); It != TOCSaves.end(); It++ ) {
248     MachineInstr *CurrInst = It->first;
249     // If new instruction dominates an existing one, mark existing one as
250     // redundant.
251     if (It->second && MDT->dominates(MI, CurrInst))
252       It->second = false;
253     // Check if the new instruction is redundant.
254     if (MDT->dominates(CurrInst, MI)) {
255       Keep = false;
256       break;
257     }
258   }
259   // Add new instruction to map.
260   TOCSaves[MI] = Keep;
261 }
262 
263 // Perform peephole optimizations.
264 bool PPCMIPeephole::simplifyCode(void) {
265   bool Simplified = false;
266   MachineInstr* ToErase = nullptr;
267   std::map<MachineInstr *, bool> TOCSaves;
268   const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
269   NumFunctionsEnteredInMIPeephole++;
270   if (ConvertRegReg) {
271     // Fixed-point conversion of reg/reg instructions fed by load-immediate
272     // into reg/imm instructions. FIXME: This is expensive, control it with
273     // an option.
274     bool SomethingChanged = false;
275     do {
276       NumFixedPointIterations++;
277       SomethingChanged = false;
278       for (MachineBasicBlock &MBB : *MF) {
279         for (MachineInstr &MI : MBB) {
280           if (MI.isDebugInstr())
281             continue;
282 
283           if (TII->convertToImmediateForm(MI)) {
284             // We don't erase anything in case the def has other uses. Let DCE
285             // remove it if it can be removed.
286             LLVM_DEBUG(dbgs() << "Converted instruction to imm form: ");
287             LLVM_DEBUG(MI.dump());
288             NumConvertedToImmediateForm++;
289             SomethingChanged = true;
290             Simplified = true;
291             continue;
292           }
293         }
294       }
295     } while (SomethingChanged && FixedPointRegToImm);
296   }
297 
298   for (MachineBasicBlock &MBB : *MF) {
299     for (MachineInstr &MI : MBB) {
300 
301       // If the previous instruction was marked for elimination,
302       // remove it now.
303       if (ToErase) {
304         ToErase->eraseFromParent();
305         ToErase = nullptr;
306       }
307 
308       // Ignore debug instructions.
309       if (MI.isDebugInstr())
310         continue;
311 
312       // Per-opcode peepholes.
313       switch (MI.getOpcode()) {
314 
315       default:
316         break;
317 
318       case PPC::STD: {
319         MachineFrameInfo &MFI = MF->getFrameInfo();
320         if (MFI.hasVarSizedObjects() ||
321             !MF->getSubtarget<PPCSubtarget>().isELFv2ABI())
322           break;
323         // When encountering a TOC save instruction, call UpdateTOCSaves
324         // to add it to the TOCSaves map and mark any existing TOC saves
325         // it dominates as redundant.
326         if (TII->isTOCSaveMI(MI))
327           UpdateTOCSaves(TOCSaves, &MI);
328         break;
329       }
330       case PPC::XXPERMDI: {
331         // Perform simplifications of 2x64 vector swaps and splats.
332         // A swap is identified by an immediate value of 2, and a splat
333         // is identified by an immediate value of 0 or 3.
334         int Immed = MI.getOperand(3).getImm();
335 
336         if (Immed == 1)
337           break;
338 
339         // For each of these simplifications, we need the two source
340         // regs to match.  Unfortunately, MachineCSE ignores COPY and
341         // SUBREG_TO_REG, so for example we can see
342         //   XXPERMDI t, SUBREG_TO_REG(s), SUBREG_TO_REG(s), immed.
343         // We have to look through chains of COPY and SUBREG_TO_REG
344         // to find the real source values for comparison.
345         unsigned TrueReg1 =
346           TRI->lookThruCopyLike(MI.getOperand(1).getReg(), MRI);
347         unsigned TrueReg2 =
348           TRI->lookThruCopyLike(MI.getOperand(2).getReg(), MRI);
349 
350         if (!(TrueReg1 == TrueReg2 && Register::isVirtualRegister(TrueReg1)))
351           break;
352 
353         MachineInstr *DefMI = MRI->getVRegDef(TrueReg1);
354 
355         if (!DefMI)
356           break;
357 
358         unsigned DefOpc = DefMI->getOpcode();
359 
360         // If this is a splat fed by a splatting load, the splat is
361         // redundant. Replace with a copy. This doesn't happen directly due
362         // to code in PPCDAGToDAGISel.cpp, but it can happen when converting
363         // a load of a double to a vector of 64-bit integers.
364         auto isConversionOfLoadAndSplat = [=]() -> bool {
365           if (DefOpc != PPC::XVCVDPSXDS && DefOpc != PPC::XVCVDPUXDS)
366             return false;
367           unsigned FeedReg1 =
368             TRI->lookThruCopyLike(DefMI->getOperand(1).getReg(), MRI);
369           if (Register::isVirtualRegister(FeedReg1)) {
370             MachineInstr *LoadMI = MRI->getVRegDef(FeedReg1);
371             if (LoadMI && LoadMI->getOpcode() == PPC::LXVDSX)
372               return true;
373           }
374           return false;
375         };
376         if ((Immed == 0 || Immed == 3) &&
377             (DefOpc == PPC::LXVDSX || isConversionOfLoadAndSplat())) {
378           LLVM_DEBUG(dbgs() << "Optimizing load-and-splat/splat "
379                                "to load-and-splat/copy: ");
380           LLVM_DEBUG(MI.dump());
381           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
382                   MI.getOperand(0).getReg())
383               .add(MI.getOperand(1));
384           ToErase = &MI;
385           Simplified = true;
386         }
387 
388         // If this is a splat or a swap fed by another splat, we
389         // can replace it with a copy.
390         if (DefOpc == PPC::XXPERMDI) {
391           unsigned DefReg1 = DefMI->getOperand(1).getReg();
392           unsigned DefReg2 = DefMI->getOperand(2).getReg();
393           unsigned DefImmed = DefMI->getOperand(3).getImm();
394 
395           // If the two inputs are not the same register, check to see if
396           // they originate from the same virtual register after only
397           // copy-like instructions.
398           if (DefReg1 != DefReg2) {
399             unsigned FeedReg1 = TRI->lookThruCopyLike(DefReg1, MRI);
400             unsigned FeedReg2 = TRI->lookThruCopyLike(DefReg2, MRI);
401 
402             if (!(FeedReg1 == FeedReg2 &&
403                   Register::isVirtualRegister(FeedReg1)))
404               break;
405           }
406 
407           if (DefImmed == 0 || DefImmed == 3) {
408             LLVM_DEBUG(dbgs() << "Optimizing splat/swap or splat/splat "
409                                  "to splat/copy: ");
410             LLVM_DEBUG(MI.dump());
411             BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
412                     MI.getOperand(0).getReg())
413                 .add(MI.getOperand(1));
414             ToErase = &MI;
415             Simplified = true;
416           }
417 
418           // If this is a splat fed by a swap, we can simplify modify
419           // the splat to splat the other value from the swap's input
420           // parameter.
421           else if ((Immed == 0 || Immed == 3) && DefImmed == 2) {
422             LLVM_DEBUG(dbgs() << "Optimizing swap/splat => splat: ");
423             LLVM_DEBUG(MI.dump());
424             MI.getOperand(1).setReg(DefReg1);
425             MI.getOperand(2).setReg(DefReg2);
426             MI.getOperand(3).setImm(3 - Immed);
427             Simplified = true;
428           }
429 
430           // If this is a swap fed by a swap, we can replace it
431           // with a copy from the first swap's input.
432           else if (Immed == 2 && DefImmed == 2) {
433             LLVM_DEBUG(dbgs() << "Optimizing swap/swap => copy: ");
434             LLVM_DEBUG(MI.dump());
435             BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
436                     MI.getOperand(0).getReg())
437                 .add(DefMI->getOperand(1));
438             ToErase = &MI;
439             Simplified = true;
440           }
441         } else if ((Immed == 0 || Immed == 3) && DefOpc == PPC::XXPERMDIs &&
442                    (DefMI->getOperand(2).getImm() == 0 ||
443                     DefMI->getOperand(2).getImm() == 3)) {
444           // Splat fed by another splat - switch the output of the first
445           // and remove the second.
446           DefMI->getOperand(0).setReg(MI.getOperand(0).getReg());
447           ToErase = &MI;
448           Simplified = true;
449           LLVM_DEBUG(dbgs() << "Removing redundant splat: ");
450           LLVM_DEBUG(MI.dump());
451         }
452         break;
453       }
454       case PPC::VSPLTB:
455       case PPC::VSPLTH:
456       case PPC::XXSPLTW: {
457         unsigned MyOpcode = MI.getOpcode();
458         unsigned OpNo = MyOpcode == PPC::XXSPLTW ? 1 : 2;
459         unsigned TrueReg =
460           TRI->lookThruCopyLike(MI.getOperand(OpNo).getReg(), MRI);
461         if (!Register::isVirtualRegister(TrueReg))
462           break;
463         MachineInstr *DefMI = MRI->getVRegDef(TrueReg);
464         if (!DefMI)
465           break;
466         unsigned DefOpcode = DefMI->getOpcode();
467         auto isConvertOfSplat = [=]() -> bool {
468           if (DefOpcode != PPC::XVCVSPSXWS && DefOpcode != PPC::XVCVSPUXWS)
469             return false;
470           Register ConvReg = DefMI->getOperand(1).getReg();
471           if (!Register::isVirtualRegister(ConvReg))
472             return false;
473           MachineInstr *Splt = MRI->getVRegDef(ConvReg);
474           return Splt && (Splt->getOpcode() == PPC::LXVWSX ||
475             Splt->getOpcode() == PPC::XXSPLTW);
476         };
477         bool AlreadySplat = (MyOpcode == DefOpcode) ||
478           (MyOpcode == PPC::VSPLTB && DefOpcode == PPC::VSPLTBs) ||
479           (MyOpcode == PPC::VSPLTH && DefOpcode == PPC::VSPLTHs) ||
480           (MyOpcode == PPC::XXSPLTW && DefOpcode == PPC::XXSPLTWs) ||
481           (MyOpcode == PPC::XXSPLTW && DefOpcode == PPC::LXVWSX) ||
482           (MyOpcode == PPC::XXSPLTW && DefOpcode == PPC::MTVSRWS)||
483           (MyOpcode == PPC::XXSPLTW && isConvertOfSplat());
484         // If the instruction[s] that feed this splat have already splat
485         // the value, this splat is redundant.
486         if (AlreadySplat) {
487           LLVM_DEBUG(dbgs() << "Changing redundant splat to a copy: ");
488           LLVM_DEBUG(MI.dump());
489           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
490                   MI.getOperand(0).getReg())
491               .add(MI.getOperand(OpNo));
492           ToErase = &MI;
493           Simplified = true;
494         }
495         // Splat fed by a shift. Usually when we align value to splat into
496         // vector element zero.
497         if (DefOpcode == PPC::XXSLDWI) {
498           Register ShiftRes = DefMI->getOperand(0).getReg();
499           Register ShiftOp1 = DefMI->getOperand(1).getReg();
500           Register ShiftOp2 = DefMI->getOperand(2).getReg();
501           unsigned ShiftImm = DefMI->getOperand(3).getImm();
502           unsigned SplatImm = MI.getOperand(2).getImm();
503           if (ShiftOp1 == ShiftOp2) {
504             unsigned NewElem = (SplatImm + ShiftImm) & 0x3;
505             if (MRI->hasOneNonDBGUse(ShiftRes)) {
506               LLVM_DEBUG(dbgs() << "Removing redundant shift: ");
507               LLVM_DEBUG(DefMI->dump());
508               ToErase = DefMI;
509             }
510             Simplified = true;
511             LLVM_DEBUG(dbgs() << "Changing splat immediate from " << SplatImm
512                               << " to " << NewElem << " in instruction: ");
513             LLVM_DEBUG(MI.dump());
514             MI.getOperand(1).setReg(ShiftOp1);
515             MI.getOperand(2).setImm(NewElem);
516           }
517         }
518         break;
519       }
520       case PPC::XVCVDPSP: {
521         // If this is a DP->SP conversion fed by an FRSP, the FRSP is redundant.
522         unsigned TrueReg =
523           TRI->lookThruCopyLike(MI.getOperand(1).getReg(), MRI);
524         if (!Register::isVirtualRegister(TrueReg))
525           break;
526         MachineInstr *DefMI = MRI->getVRegDef(TrueReg);
527 
528         // This can occur when building a vector of single precision or integer
529         // values.
530         if (DefMI && DefMI->getOpcode() == PPC::XXPERMDI) {
531           unsigned DefsReg1 =
532             TRI->lookThruCopyLike(DefMI->getOperand(1).getReg(), MRI);
533           unsigned DefsReg2 =
534             TRI->lookThruCopyLike(DefMI->getOperand(2).getReg(), MRI);
535           if (!Register::isVirtualRegister(DefsReg1) ||
536               !Register::isVirtualRegister(DefsReg2))
537             break;
538           MachineInstr *P1 = MRI->getVRegDef(DefsReg1);
539           MachineInstr *P2 = MRI->getVRegDef(DefsReg2);
540 
541           if (!P1 || !P2)
542             break;
543 
544           // Remove the passed FRSP instruction if it only feeds this MI and
545           // set any uses of that FRSP (in this MI) to the source of the FRSP.
546           auto removeFRSPIfPossible = [&](MachineInstr *RoundInstr) {
547             if (RoundInstr->getOpcode() == PPC::FRSP &&
548                 MRI->hasOneNonDBGUse(RoundInstr->getOperand(0).getReg())) {
549               Simplified = true;
550               Register ConvReg1 = RoundInstr->getOperand(1).getReg();
551               Register FRSPDefines = RoundInstr->getOperand(0).getReg();
552               MachineInstr &Use = *(MRI->use_instr_begin(FRSPDefines));
553               for (int i = 0, e = Use.getNumOperands(); i < e; ++i)
554                 if (Use.getOperand(i).isReg() &&
555                     Use.getOperand(i).getReg() == FRSPDefines)
556                   Use.getOperand(i).setReg(ConvReg1);
557               LLVM_DEBUG(dbgs() << "Removing redundant FRSP:\n");
558               LLVM_DEBUG(RoundInstr->dump());
559               LLVM_DEBUG(dbgs() << "As it feeds instruction:\n");
560               LLVM_DEBUG(MI.dump());
561               LLVM_DEBUG(dbgs() << "Through instruction:\n");
562               LLVM_DEBUG(DefMI->dump());
563               RoundInstr->eraseFromParent();
564             }
565           };
566 
567           // If the input to XVCVDPSP is a vector that was built (even
568           // partially) out of FRSP's, the FRSP(s) can safely be removed
569           // since this instruction performs the same operation.
570           if (P1 != P2) {
571             removeFRSPIfPossible(P1);
572             removeFRSPIfPossible(P2);
573             break;
574           }
575           removeFRSPIfPossible(P1);
576         }
577         break;
578       }
579       case PPC::EXTSH:
580       case PPC::EXTSH8:
581       case PPC::EXTSH8_32_64: {
582         if (!EnableSExtElimination) break;
583         Register NarrowReg = MI.getOperand(1).getReg();
584         if (!Register::isVirtualRegister(NarrowReg))
585           break;
586 
587         MachineInstr *SrcMI = MRI->getVRegDef(NarrowReg);
588         // If we've used a zero-extending load that we will sign-extend,
589         // just do a sign-extending load.
590         if (SrcMI->getOpcode() == PPC::LHZ ||
591             SrcMI->getOpcode() == PPC::LHZX) {
592           if (!MRI->hasOneNonDBGUse(SrcMI->getOperand(0).getReg()))
593             break;
594           auto is64Bit = [] (unsigned Opcode) {
595             return Opcode == PPC::EXTSH8;
596           };
597           auto isXForm = [] (unsigned Opcode) {
598             return Opcode == PPC::LHZX;
599           };
600           auto getSextLoadOp = [] (bool is64Bit, bool isXForm) {
601             if (is64Bit)
602               if (isXForm) return PPC::LHAX8;
603               else         return PPC::LHA8;
604             else
605               if (isXForm) return PPC::LHAX;
606               else         return PPC::LHA;
607           };
608           unsigned Opc = getSextLoadOp(is64Bit(MI.getOpcode()),
609                                        isXForm(SrcMI->getOpcode()));
610           LLVM_DEBUG(dbgs() << "Zero-extending load\n");
611           LLVM_DEBUG(SrcMI->dump());
612           LLVM_DEBUG(dbgs() << "and sign-extension\n");
613           LLVM_DEBUG(MI.dump());
614           LLVM_DEBUG(dbgs() << "are merged into sign-extending load\n");
615           SrcMI->setDesc(TII->get(Opc));
616           SrcMI->getOperand(0).setReg(MI.getOperand(0).getReg());
617           ToErase = &MI;
618           Simplified = true;
619           NumEliminatedSExt++;
620         }
621         break;
622       }
623       case PPC::EXTSW:
624       case PPC::EXTSW_32:
625       case PPC::EXTSW_32_64: {
626         if (!EnableSExtElimination) break;
627         Register NarrowReg = MI.getOperand(1).getReg();
628         if (!Register::isVirtualRegister(NarrowReg))
629           break;
630 
631         MachineInstr *SrcMI = MRI->getVRegDef(NarrowReg);
632         // If we've used a zero-extending load that we will sign-extend,
633         // just do a sign-extending load.
634         if (SrcMI->getOpcode() == PPC::LWZ ||
635             SrcMI->getOpcode() == PPC::LWZX) {
636           if (!MRI->hasOneNonDBGUse(SrcMI->getOperand(0).getReg()))
637             break;
638           auto is64Bit = [] (unsigned Opcode) {
639             return Opcode == PPC::EXTSW || Opcode == PPC::EXTSW_32_64;
640           };
641           auto isXForm = [] (unsigned Opcode) {
642             return Opcode == PPC::LWZX;
643           };
644           auto getSextLoadOp = [] (bool is64Bit, bool isXForm) {
645             if (is64Bit)
646               if (isXForm) return PPC::LWAX;
647               else         return PPC::LWA;
648             else
649               if (isXForm) return PPC::LWAX_32;
650               else         return PPC::LWA_32;
651           };
652           unsigned Opc = getSextLoadOp(is64Bit(MI.getOpcode()),
653                                        isXForm(SrcMI->getOpcode()));
654           LLVM_DEBUG(dbgs() << "Zero-extending load\n");
655           LLVM_DEBUG(SrcMI->dump());
656           LLVM_DEBUG(dbgs() << "and sign-extension\n");
657           LLVM_DEBUG(MI.dump());
658           LLVM_DEBUG(dbgs() << "are merged into sign-extending load\n");
659           SrcMI->setDesc(TII->get(Opc));
660           SrcMI->getOperand(0).setReg(MI.getOperand(0).getReg());
661           ToErase = &MI;
662           Simplified = true;
663           NumEliminatedSExt++;
664         } else if (MI.getOpcode() == PPC::EXTSW_32_64 &&
665                    TII->isSignExtended(*SrcMI)) {
666           // We can eliminate EXTSW if the input is known to be already
667           // sign-extended.
668           LLVM_DEBUG(dbgs() << "Removing redundant sign-extension\n");
669           Register TmpReg =
670               MF->getRegInfo().createVirtualRegister(&PPC::G8RCRegClass);
671           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::IMPLICIT_DEF),
672                   TmpReg);
673           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::INSERT_SUBREG),
674                   MI.getOperand(0).getReg())
675               .addReg(TmpReg)
676               .addReg(NarrowReg)
677               .addImm(PPC::sub_32);
678           ToErase = &MI;
679           Simplified = true;
680           NumEliminatedSExt++;
681         }
682         break;
683       }
684       case PPC::RLDICL: {
685         // We can eliminate RLDICL (e.g. for zero-extension)
686         // if all bits to clear are already zero in the input.
687         // This code assume following code sequence for zero-extension.
688         //   %6 = COPY %5:sub_32; (optional)
689         //   %8 = IMPLICIT_DEF;
690         //   %7<def,tied1> = INSERT_SUBREG %8<tied0>, %6, sub_32;
691         if (!EnableZExtElimination) break;
692 
693         if (MI.getOperand(2).getImm() != 0)
694           break;
695 
696         Register SrcReg = MI.getOperand(1).getReg();
697         if (!Register::isVirtualRegister(SrcReg))
698           break;
699 
700         MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
701         if (!(SrcMI && SrcMI->getOpcode() == PPC::INSERT_SUBREG &&
702               SrcMI->getOperand(0).isReg() && SrcMI->getOperand(1).isReg()))
703           break;
704 
705         MachineInstr *ImpDefMI, *SubRegMI;
706         ImpDefMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
707         SubRegMI = MRI->getVRegDef(SrcMI->getOperand(2).getReg());
708         if (ImpDefMI->getOpcode() != PPC::IMPLICIT_DEF) break;
709 
710         SrcMI = SubRegMI;
711         if (SubRegMI->getOpcode() == PPC::COPY) {
712           Register CopyReg = SubRegMI->getOperand(1).getReg();
713           if (Register::isVirtualRegister(CopyReg))
714             SrcMI = MRI->getVRegDef(CopyReg);
715         }
716 
717         unsigned KnownZeroCount = getKnownLeadingZeroCount(SrcMI, TII);
718         if (MI.getOperand(3).getImm() <= KnownZeroCount) {
719           LLVM_DEBUG(dbgs() << "Removing redundant zero-extension\n");
720           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
721                   MI.getOperand(0).getReg())
722               .addReg(SrcReg);
723           ToErase = &MI;
724           Simplified = true;
725           NumEliminatedZExt++;
726         }
727         break;
728       }
729 
730       // TODO: Any instruction that has an immediate form fed only by a PHI
731       // whose operands are all load immediate can be folded away. We currently
732       // do this for ADD instructions, but should expand it to arithmetic and
733       // binary instructions with immediate forms in the future.
734       case PPC::ADD4:
735       case PPC::ADD8: {
736         auto isSingleUsePHI = [&](MachineOperand *PhiOp) {
737           assert(PhiOp && "Invalid Operand!");
738           MachineInstr *DefPhiMI = getVRegDefOrNull(PhiOp, MRI);
739 
740           return DefPhiMI && (DefPhiMI->getOpcode() == PPC::PHI) &&
741                  MRI->hasOneNonDBGUse(DefPhiMI->getOperand(0).getReg());
742         };
743 
744         auto dominatesAllSingleUseLIs = [&](MachineOperand *DominatorOp,
745                                             MachineOperand *PhiOp) {
746           assert(PhiOp && "Invalid Operand!");
747           assert(DominatorOp && "Invalid Operand!");
748           MachineInstr *DefPhiMI = getVRegDefOrNull(PhiOp, MRI);
749           MachineInstr *DefDomMI = getVRegDefOrNull(DominatorOp, MRI);
750 
751           // Note: the vregs only show up at odd indices position of PHI Node,
752           // the even indices position save the BB info.
753           for (unsigned i = 1; i < DefPhiMI->getNumOperands(); i += 2) {
754             MachineInstr *LiMI =
755                 getVRegDefOrNull(&DefPhiMI->getOperand(i), MRI);
756             if (!LiMI ||
757                 (LiMI->getOpcode() != PPC::LI && LiMI->getOpcode() != PPC::LI8)
758                 || !MRI->hasOneNonDBGUse(LiMI->getOperand(0).getReg()) ||
759                 !MDT->dominates(DefDomMI, LiMI))
760               return false;
761           }
762 
763           return true;
764         };
765 
766         MachineOperand Op1 = MI.getOperand(1);
767         MachineOperand Op2 = MI.getOperand(2);
768         if (isSingleUsePHI(&Op2) && dominatesAllSingleUseLIs(&Op1, &Op2))
769           std::swap(Op1, Op2);
770         else if (!isSingleUsePHI(&Op1) || !dominatesAllSingleUseLIs(&Op2, &Op1))
771           break; // We don't have an ADD fed by LI's that can be transformed
772 
773         // Now we know that Op1 is the PHI node and Op2 is the dominator
774         Register DominatorReg = Op2.getReg();
775 
776         const TargetRegisterClass *TRC = MI.getOpcode() == PPC::ADD8
777                                              ? &PPC::G8RC_and_G8RC_NOX0RegClass
778                                              : &PPC::GPRC_and_GPRC_NOR0RegClass;
779         MRI->setRegClass(DominatorReg, TRC);
780 
781         // replace LIs with ADDIs
782         MachineInstr *DefPhiMI = getVRegDefOrNull(&Op1, MRI);
783         for (unsigned i = 1; i < DefPhiMI->getNumOperands(); i += 2) {
784           MachineInstr *LiMI = getVRegDefOrNull(&DefPhiMI->getOperand(i), MRI);
785           LLVM_DEBUG(dbgs() << "Optimizing LI to ADDI: ");
786           LLVM_DEBUG(LiMI->dump());
787 
788           // There could be repeated registers in the PHI, e.g: %1 =
789           // PHI %6, <%bb.2>, %8, <%bb.3>, %8, <%bb.6>; So if we've
790           // already replaced the def instruction, skip.
791           if (LiMI->getOpcode() == PPC::ADDI || LiMI->getOpcode() == PPC::ADDI8)
792             continue;
793 
794           assert((LiMI->getOpcode() == PPC::LI ||
795                   LiMI->getOpcode() == PPC::LI8) &&
796                  "Invalid Opcode!");
797           auto LiImm = LiMI->getOperand(1).getImm(); // save the imm of LI
798           LiMI->RemoveOperand(1);                    // remove the imm of LI
799           LiMI->setDesc(TII->get(LiMI->getOpcode() == PPC::LI ? PPC::ADDI
800                                                               : PPC::ADDI8));
801           MachineInstrBuilder(*LiMI->getParent()->getParent(), *LiMI)
802               .addReg(DominatorReg)
803               .addImm(LiImm); // restore the imm of LI
804           LLVM_DEBUG(LiMI->dump());
805         }
806 
807         // Replace ADD with COPY
808         LLVM_DEBUG(dbgs() << "Optimizing ADD to COPY: ");
809         LLVM_DEBUG(MI.dump());
810         BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
811                 MI.getOperand(0).getReg())
812             .add(Op1);
813         ToErase = &MI;
814         Simplified = true;
815         NumOptADDLIs++;
816         break;
817       }
818       case PPC::RLDICR: {
819         Simplified |= emitRLDICWhenLoweringJumpTables(MI) ||
820                       combineSEXTAndSHL(MI, ToErase);
821         break;
822       }
823       case PPC::RLWINM:
824       case PPC::RLWINM_rec:
825       case PPC::RLWINM8:
826       case PPC::RLWINM8_rec: {
827         unsigned FoldingReg = MI.getOperand(1).getReg();
828         if (!Register::isVirtualRegister(FoldingReg))
829           break;
830 
831         MachineInstr *SrcMI = MRI->getVRegDef(FoldingReg);
832         if (SrcMI->getOpcode() != PPC::RLWINM &&
833             SrcMI->getOpcode() != PPC::RLWINM_rec &&
834             SrcMI->getOpcode() != PPC::RLWINM8 &&
835             SrcMI->getOpcode() != PPC::RLWINM8_rec)
836           break;
837         assert((MI.getOperand(2).isImm() && MI.getOperand(3).isImm() &&
838                 MI.getOperand(4).isImm() && SrcMI->getOperand(2).isImm() &&
839                 SrcMI->getOperand(3).isImm() && SrcMI->getOperand(4).isImm()) &&
840                "Invalid PPC::RLWINM Instruction!");
841         uint64_t SHSrc = SrcMI->getOperand(2).getImm();
842         uint64_t SHMI = MI.getOperand(2).getImm();
843         uint64_t MBSrc = SrcMI->getOperand(3).getImm();
844         uint64_t MBMI = MI.getOperand(3).getImm();
845         uint64_t MESrc = SrcMI->getOperand(4).getImm();
846         uint64_t MEMI = MI.getOperand(4).getImm();
847 
848         assert((MEMI < 32 && MESrc < 32 && MBMI < 32 && MBSrc < 32) &&
849                "Invalid PPC::RLWINM Instruction!");
850 
851         // If MBMI is bigger than MEMI, we always can not get run of ones.
852         // RotatedSrcMask non-wrap:
853         //                 0........31|32........63
854         // RotatedSrcMask:   B---E        B---E
855         // MaskMI:         -----------|--E  B------
856         // Result:           -----          ---      (Bad candidate)
857         //
858         // RotatedSrcMask wrap:
859         //                 0........31|32........63
860         // RotatedSrcMask: --E   B----|--E    B----
861         // MaskMI:         -----------|--E  B------
862         // Result:         ---   -----|---    -----  (Bad candidate)
863         //
864         // One special case is RotatedSrcMask is a full set mask.
865         // RotatedSrcMask full:
866         //                 0........31|32........63
867         // RotatedSrcMask: ------EB---|-------EB---
868         // MaskMI:         -----------|--E  B------
869         // Result:         -----------|---  -------  (Good candidate)
870 
871         // Mark special case.
872         bool SrcMaskFull = (MBSrc - MESrc == 1) || (MBSrc == 0 && MESrc == 31);
873 
874         // For other MBMI > MEMI cases, just return.
875         if ((MBMI > MEMI) && !SrcMaskFull)
876           break;
877 
878         // Handle MBMI <= MEMI cases.
879         APInt MaskMI = APInt::getBitsSetWithWrap(32, 32 - MEMI - 1, 32 - MBMI);
880         // In MI, we only need low 32 bits of SrcMI, just consider about low 32
881         // bit of SrcMI mask. Note that in APInt, lowerest bit is at index 0,
882         // while in PowerPC ISA, lowerest bit is at index 63.
883         APInt MaskSrc =
884             APInt::getBitsSetWithWrap(32, 32 - MESrc - 1, 32 - MBSrc);
885         // Current APInt::getBitsSetWithWrap sets all bits to 0 if loBit is
886         // equal to highBit.
887         // If MBSrc - MESrc == 1, we expect a full set mask instead of Null.
888         if (SrcMaskFull && (MBSrc - MESrc == 1))
889           MaskSrc.setAllBits();
890 
891         APInt RotatedSrcMask = MaskSrc.rotl(SHMI);
892         APInt FinalMask = RotatedSrcMask & MaskMI;
893         uint32_t NewMB, NewME;
894 
895         // If final mask is 0, MI result should be 0 too.
896         if (FinalMask.isNullValue()) {
897           bool Is64Bit = (MI.getOpcode() == PPC::RLWINM8 ||
898                           MI.getOpcode() == PPC::RLWINM8_rec);
899 
900           LLVM_DEBUG(dbgs() << "Replace Instr: ");
901           LLVM_DEBUG(MI.dump());
902 
903           if (MI.getOpcode() == PPC::RLWINM || MI.getOpcode() == PPC::RLWINM8) {
904             // Replace MI with "LI 0"
905             MI.RemoveOperand(4);
906             MI.RemoveOperand(3);
907             MI.RemoveOperand(2);
908             MI.getOperand(1).ChangeToImmediate(0);
909             MI.setDesc(TII->get(Is64Bit ? PPC::LI8 : PPC::LI));
910           } else {
911             // Replace MI with "ANDI_rec reg, 0"
912             MI.RemoveOperand(4);
913             MI.RemoveOperand(3);
914             MI.getOperand(2).setImm(0);
915             MI.setDesc(TII->get(Is64Bit ? PPC::ANDI8_rec : PPC::ANDI_rec));
916           }
917           Simplified = true;
918           NumRotatesCollapsed++;
919 
920           LLVM_DEBUG(dbgs() << "With: ");
921           LLVM_DEBUG(MI.dump());
922         } else if ((isRunOfOnes((unsigned)(FinalMask.getZExtValue()), NewMB,
923                                NewME) && NewMB <= NewME)|| SrcMaskFull) {
924           // Here we only handle MBMI <= MEMI case, so NewMB must be no bigger
925           // than NewME. Otherwise we get a 64 bit value after folding, but MI
926           // return a 32 bit value.
927 
928           // If FoldingReg has only one use and it it not RLWINM_rec and
929           // RLWINM8_rec, safe to delete its def SrcMI. Otherwise keep it.
930           if (MRI->hasOneNonDBGUse(FoldingReg) &&
931               (SrcMI->getOpcode() == PPC::RLWINM ||
932                SrcMI->getOpcode() == PPC::RLWINM8)) {
933             ToErase = SrcMI;
934             LLVM_DEBUG(dbgs() << "Delete dead instruction: ");
935             LLVM_DEBUG(SrcMI->dump());
936           }
937 
938           LLVM_DEBUG(dbgs() << "Converting Instr: ");
939           LLVM_DEBUG(MI.dump());
940 
941           uint16_t NewSH = (SHSrc + SHMI) % 32;
942           MI.getOperand(2).setImm(NewSH);
943           // If SrcMI mask is full, no need to update MBMI and MEMI.
944           if (!SrcMaskFull) {
945             MI.getOperand(3).setImm(NewMB);
946             MI.getOperand(4).setImm(NewME);
947           }
948           MI.getOperand(1).setReg(SrcMI->getOperand(1).getReg());
949           if (SrcMI->getOperand(1).isKill()) {
950             MI.getOperand(1).setIsKill(true);
951             SrcMI->getOperand(1).setIsKill(false);
952           } else
953             // About to replace MI.getOperand(1), clear its kill flag.
954             MI.getOperand(1).setIsKill(false);
955 
956           Simplified = true;
957           NumRotatesCollapsed++;
958 
959           LLVM_DEBUG(dbgs() << "To: ");
960           LLVM_DEBUG(MI.dump());
961         }
962         break;
963       }
964       }
965     }
966 
967     // If the last instruction was marked for elimination,
968     // remove it now.
969     if (ToErase) {
970       ToErase->eraseFromParent();
971       ToErase = nullptr;
972     }
973   }
974 
975   // Eliminate all the TOC save instructions which are redundant.
976   Simplified |= eliminateRedundantTOCSaves(TOCSaves);
977   PPCFunctionInfo *FI = MF->getInfo<PPCFunctionInfo>();
978   if (FI->mustSaveTOC())
979     NumTOCSavesInPrologue++;
980 
981   // We try to eliminate redundant compare instruction.
982   Simplified |= eliminateRedundantCompare();
983 
984   return Simplified;
985 }
986 
987 // helper functions for eliminateRedundantCompare
988 static bool isEqOrNe(MachineInstr *BI) {
989   PPC::Predicate Pred = (PPC::Predicate)BI->getOperand(0).getImm();
990   unsigned PredCond = PPC::getPredicateCondition(Pred);
991   return (PredCond == PPC::PRED_EQ || PredCond == PPC::PRED_NE);
992 }
993 
994 static bool isSupportedCmpOp(unsigned opCode) {
995   return (opCode == PPC::CMPLD  || opCode == PPC::CMPD  ||
996           opCode == PPC::CMPLW  || opCode == PPC::CMPW  ||
997           opCode == PPC::CMPLDI || opCode == PPC::CMPDI ||
998           opCode == PPC::CMPLWI || opCode == PPC::CMPWI);
999 }
1000 
1001 static bool is64bitCmpOp(unsigned opCode) {
1002   return (opCode == PPC::CMPLD  || opCode == PPC::CMPD ||
1003           opCode == PPC::CMPLDI || opCode == PPC::CMPDI);
1004 }
1005 
1006 static bool isSignedCmpOp(unsigned opCode) {
1007   return (opCode == PPC::CMPD  || opCode == PPC::CMPW ||
1008           opCode == PPC::CMPDI || opCode == PPC::CMPWI);
1009 }
1010 
1011 static unsigned getSignedCmpOpCode(unsigned opCode) {
1012   if (opCode == PPC::CMPLD)  return PPC::CMPD;
1013   if (opCode == PPC::CMPLW)  return PPC::CMPW;
1014   if (opCode == PPC::CMPLDI) return PPC::CMPDI;
1015   if (opCode == PPC::CMPLWI) return PPC::CMPWI;
1016   return opCode;
1017 }
1018 
1019 // We can decrement immediate x in (GE x) by changing it to (GT x-1) or
1020 // (LT x) to (LE x-1)
1021 static unsigned getPredicateToDecImm(MachineInstr *BI, MachineInstr *CMPI) {
1022   uint64_t Imm = CMPI->getOperand(2).getImm();
1023   bool SignedCmp = isSignedCmpOp(CMPI->getOpcode());
1024   if ((!SignedCmp && Imm == 0) || (SignedCmp && Imm == 0x8000))
1025     return 0;
1026 
1027   PPC::Predicate Pred = (PPC::Predicate)BI->getOperand(0).getImm();
1028   unsigned PredCond = PPC::getPredicateCondition(Pred);
1029   unsigned PredHint = PPC::getPredicateHint(Pred);
1030   if (PredCond == PPC::PRED_GE)
1031     return PPC::getPredicate(PPC::PRED_GT, PredHint);
1032   if (PredCond == PPC::PRED_LT)
1033     return PPC::getPredicate(PPC::PRED_LE, PredHint);
1034 
1035   return 0;
1036 }
1037 
1038 // We can increment immediate x in (GT x) by changing it to (GE x+1) or
1039 // (LE x) to (LT x+1)
1040 static unsigned getPredicateToIncImm(MachineInstr *BI, MachineInstr *CMPI) {
1041   uint64_t Imm = CMPI->getOperand(2).getImm();
1042   bool SignedCmp = isSignedCmpOp(CMPI->getOpcode());
1043   if ((!SignedCmp && Imm == 0xFFFF) || (SignedCmp && Imm == 0x7FFF))
1044     return 0;
1045 
1046   PPC::Predicate Pred = (PPC::Predicate)BI->getOperand(0).getImm();
1047   unsigned PredCond = PPC::getPredicateCondition(Pred);
1048   unsigned PredHint = PPC::getPredicateHint(Pred);
1049   if (PredCond == PPC::PRED_GT)
1050     return PPC::getPredicate(PPC::PRED_GE, PredHint);
1051   if (PredCond == PPC::PRED_LE)
1052     return PPC::getPredicate(PPC::PRED_LT, PredHint);
1053 
1054   return 0;
1055 }
1056 
1057 // This takes a Phi node and returns a register value for the specified BB.
1058 static unsigned getIncomingRegForBlock(MachineInstr *Phi,
1059                                        MachineBasicBlock *MBB) {
1060   for (unsigned I = 2, E = Phi->getNumOperands() + 1; I != E; I += 2) {
1061     MachineOperand &MO = Phi->getOperand(I);
1062     if (MO.getMBB() == MBB)
1063       return Phi->getOperand(I-1).getReg();
1064   }
1065   llvm_unreachable("invalid src basic block for this Phi node\n");
1066   return 0;
1067 }
1068 
1069 // This function tracks the source of the register through register copy.
1070 // If BB1 and BB2 are non-NULL, we also track PHI instruction in BB2
1071 // assuming that the control comes from BB1 into BB2.
1072 static unsigned getSrcVReg(unsigned Reg, MachineBasicBlock *BB1,
1073                            MachineBasicBlock *BB2, MachineRegisterInfo *MRI) {
1074   unsigned SrcReg = Reg;
1075   while (1) {
1076     unsigned NextReg = SrcReg;
1077     MachineInstr *Inst = MRI->getVRegDef(SrcReg);
1078     if (BB1 && Inst->getOpcode() == PPC::PHI && Inst->getParent() == BB2) {
1079       NextReg = getIncomingRegForBlock(Inst, BB1);
1080       // We track through PHI only once to avoid infinite loop.
1081       BB1 = nullptr;
1082     }
1083     else if (Inst->isFullCopy())
1084       NextReg = Inst->getOperand(1).getReg();
1085     if (NextReg == SrcReg || !Register::isVirtualRegister(NextReg))
1086       break;
1087     SrcReg = NextReg;
1088   }
1089   return SrcReg;
1090 }
1091 
1092 static bool eligibleForCompareElimination(MachineBasicBlock &MBB,
1093                                           MachineBasicBlock *&PredMBB,
1094                                           MachineBasicBlock *&MBBtoMoveCmp,
1095                                           MachineRegisterInfo *MRI) {
1096 
1097   auto isEligibleBB = [&](MachineBasicBlock &BB) {
1098     auto BII = BB.getFirstInstrTerminator();
1099     // We optimize BBs ending with a conditional branch.
1100     // We check only for BCC here, not BCCLR, because BCCLR
1101     // will be formed only later in the pipeline.
1102     if (BB.succ_size() == 2 &&
1103         BII != BB.instr_end() &&
1104         (*BII).getOpcode() == PPC::BCC &&
1105         (*BII).getOperand(1).isReg()) {
1106       // We optimize only if the condition code is used only by one BCC.
1107       Register CndReg = (*BII).getOperand(1).getReg();
1108       if (!Register::isVirtualRegister(CndReg) || !MRI->hasOneNonDBGUse(CndReg))
1109         return false;
1110 
1111       MachineInstr *CMPI = MRI->getVRegDef(CndReg);
1112       // We assume compare and branch are in the same BB for ease of analysis.
1113       if (CMPI->getParent() != &BB)
1114         return false;
1115 
1116       // We skip this BB if a physical register is used in comparison.
1117       for (MachineOperand &MO : CMPI->operands())
1118         if (MO.isReg() && !Register::isVirtualRegister(MO.getReg()))
1119           return false;
1120 
1121       return true;
1122     }
1123     return false;
1124   };
1125 
1126   // If this BB has more than one successor, we can create a new BB and
1127   // move the compare instruction in the new BB.
1128   // So far, we do not move compare instruction to a BB having multiple
1129   // successors to avoid potentially increasing code size.
1130   auto isEligibleForMoveCmp = [](MachineBasicBlock &BB) {
1131     return BB.succ_size() == 1;
1132   };
1133 
1134   if (!isEligibleBB(MBB))
1135     return false;
1136 
1137   unsigned NumPredBBs = MBB.pred_size();
1138   if (NumPredBBs == 1) {
1139     MachineBasicBlock *TmpMBB = *MBB.pred_begin();
1140     if (isEligibleBB(*TmpMBB)) {
1141       PredMBB = TmpMBB;
1142       MBBtoMoveCmp = nullptr;
1143       return true;
1144     }
1145   }
1146   else if (NumPredBBs == 2) {
1147     // We check for partially redundant case.
1148     // So far, we support cases with only two predecessors
1149     // to avoid increasing the number of instructions.
1150     MachineBasicBlock::pred_iterator PI = MBB.pred_begin();
1151     MachineBasicBlock *Pred1MBB = *PI;
1152     MachineBasicBlock *Pred2MBB = *(PI+1);
1153 
1154     if (isEligibleBB(*Pred1MBB) && isEligibleForMoveCmp(*Pred2MBB)) {
1155       // We assume Pred1MBB is the BB containing the compare to be merged and
1156       // Pred2MBB is the BB to which we will append a compare instruction.
1157       // Hence we can proceed as is.
1158     }
1159     else if (isEligibleBB(*Pred2MBB) && isEligibleForMoveCmp(*Pred1MBB)) {
1160       // We need to swap Pred1MBB and Pred2MBB to canonicalize.
1161       std::swap(Pred1MBB, Pred2MBB);
1162     }
1163     else return false;
1164 
1165     // Here, Pred2MBB is the BB to which we need to append a compare inst.
1166     // We cannot move the compare instruction if operands are not available
1167     // in Pred2MBB (i.e. defined in MBB by an instruction other than PHI).
1168     MachineInstr *BI = &*MBB.getFirstInstrTerminator();
1169     MachineInstr *CMPI = MRI->getVRegDef(BI->getOperand(1).getReg());
1170     for (int I = 1; I <= 2; I++)
1171       if (CMPI->getOperand(I).isReg()) {
1172         MachineInstr *Inst = MRI->getVRegDef(CMPI->getOperand(I).getReg());
1173         if (Inst->getParent() == &MBB && Inst->getOpcode() != PPC::PHI)
1174           return false;
1175       }
1176 
1177     PredMBB = Pred1MBB;
1178     MBBtoMoveCmp = Pred2MBB;
1179     return true;
1180   }
1181 
1182   return false;
1183 }
1184 
1185 // This function will iterate over the input map containing a pair of TOC save
1186 // instruction and a flag. The flag will be set to false if the TOC save is
1187 // proven redundant. This function will erase from the basic block all the TOC
1188 // saves marked as redundant.
1189 bool PPCMIPeephole::eliminateRedundantTOCSaves(
1190     std::map<MachineInstr *, bool> &TOCSaves) {
1191   bool Simplified = false;
1192   int NumKept = 0;
1193   for (auto TOCSave : TOCSaves) {
1194     if (!TOCSave.second) {
1195       TOCSave.first->eraseFromParent();
1196       RemoveTOCSave++;
1197       Simplified = true;
1198     } else {
1199       NumKept++;
1200     }
1201   }
1202 
1203   if (NumKept > 1)
1204     MultiTOCSaves++;
1205 
1206   return Simplified;
1207 }
1208 
1209 // If multiple conditional branches are executed based on the (essentially)
1210 // same comparison, we merge compare instructions into one and make multiple
1211 // conditional branches on this comparison.
1212 // For example,
1213 //   if (a == 0) { ... }
1214 //   else if (a < 0) { ... }
1215 // can be executed by one compare and two conditional branches instead of
1216 // two pairs of a compare and a conditional branch.
1217 //
1218 // This method merges two compare instructions in two MBBs and modifies the
1219 // compare and conditional branch instructions if needed.
1220 // For the above example, the input for this pass looks like:
1221 //   cmplwi r3, 0
1222 //   beq    0, .LBB0_3
1223 //   cmpwi  r3, -1
1224 //   bgt    0, .LBB0_4
1225 // So, before merging two compares, we need to modify these instructions as
1226 //   cmpwi  r3, 0       ; cmplwi and cmpwi yield same result for beq
1227 //   beq    0, .LBB0_3
1228 //   cmpwi  r3, 0       ; greather than -1 means greater or equal to 0
1229 //   bge    0, .LBB0_4
1230 
1231 bool PPCMIPeephole::eliminateRedundantCompare(void) {
1232   bool Simplified = false;
1233 
1234   for (MachineBasicBlock &MBB2 : *MF) {
1235     MachineBasicBlock *MBB1 = nullptr, *MBBtoMoveCmp = nullptr;
1236 
1237     // For fully redundant case, we select two basic blocks MBB1 and MBB2
1238     // as an optimization target if
1239     // - both MBBs end with a conditional branch,
1240     // - MBB1 is the only predecessor of MBB2, and
1241     // - compare does not take a physical register as a operand in both MBBs.
1242     // In this case, eligibleForCompareElimination sets MBBtoMoveCmp nullptr.
1243     //
1244     // As partially redundant case, we additionally handle if MBB2 has one
1245     // additional predecessor, which has only one successor (MBB2).
1246     // In this case, we move the compare instruction originally in MBB2 into
1247     // MBBtoMoveCmp. This partially redundant case is typically appear by
1248     // compiling a while loop; here, MBBtoMoveCmp is the loop preheader.
1249     //
1250     // Overview of CFG of related basic blocks
1251     // Fully redundant case        Partially redundant case
1252     //   --------                   ----------------  --------
1253     //   | MBB1 | (w/ 2 succ)       | MBBtoMoveCmp |  | MBB1 | (w/ 2 succ)
1254     //   --------                   ----------------  --------
1255     //      |    \                     (w/ 1 succ) \     |    \
1256     //      |     \                                 \    |     \
1257     //      |                                        \   |
1258     //   --------                                     --------
1259     //   | MBB2 | (w/ 1 pred                          | MBB2 | (w/ 2 pred
1260     //   -------- and 2 succ)                         -------- and 2 succ)
1261     //      |    \                                       |    \
1262     //      |     \                                      |     \
1263     //
1264     if (!eligibleForCompareElimination(MBB2, MBB1, MBBtoMoveCmp, MRI))
1265       continue;
1266 
1267     MachineInstr *BI1   = &*MBB1->getFirstInstrTerminator();
1268     MachineInstr *CMPI1 = MRI->getVRegDef(BI1->getOperand(1).getReg());
1269 
1270     MachineInstr *BI2   = &*MBB2.getFirstInstrTerminator();
1271     MachineInstr *CMPI2 = MRI->getVRegDef(BI2->getOperand(1).getReg());
1272     bool IsPartiallyRedundant = (MBBtoMoveCmp != nullptr);
1273 
1274     // We cannot optimize an unsupported compare opcode or
1275     // a mix of 32-bit and 64-bit comaprisons
1276     if (!isSupportedCmpOp(CMPI1->getOpcode()) ||
1277         !isSupportedCmpOp(CMPI2->getOpcode()) ||
1278         is64bitCmpOp(CMPI1->getOpcode()) != is64bitCmpOp(CMPI2->getOpcode()))
1279       continue;
1280 
1281     unsigned NewOpCode = 0;
1282     unsigned NewPredicate1 = 0, NewPredicate2 = 0;
1283     int16_t Imm1 = 0, NewImm1 = 0, Imm2 = 0, NewImm2 = 0;
1284     bool SwapOperands = false;
1285 
1286     if (CMPI1->getOpcode() != CMPI2->getOpcode()) {
1287       // Typically, unsigned comparison is used for equality check, but
1288       // we replace it with a signed comparison if the comparison
1289       // to be merged is a signed comparison.
1290       // In other cases of opcode mismatch, we cannot optimize this.
1291 
1292       // We cannot change opcode when comparing against an immediate
1293       // if the most significant bit of the immediate is one
1294       // due to the difference in sign extension.
1295       auto CmpAgainstImmWithSignBit = [](MachineInstr *I) {
1296         if (!I->getOperand(2).isImm())
1297           return false;
1298         int16_t Imm = (int16_t)I->getOperand(2).getImm();
1299         return Imm < 0;
1300       };
1301 
1302       if (isEqOrNe(BI2) && !CmpAgainstImmWithSignBit(CMPI2) &&
1303           CMPI1->getOpcode() == getSignedCmpOpCode(CMPI2->getOpcode()))
1304         NewOpCode = CMPI1->getOpcode();
1305       else if (isEqOrNe(BI1) && !CmpAgainstImmWithSignBit(CMPI1) &&
1306                getSignedCmpOpCode(CMPI1->getOpcode()) == CMPI2->getOpcode())
1307         NewOpCode = CMPI2->getOpcode();
1308       else continue;
1309     }
1310 
1311     if (CMPI1->getOperand(2).isReg() && CMPI2->getOperand(2).isReg()) {
1312       // In case of comparisons between two registers, these two registers
1313       // must be same to merge two comparisons.
1314       unsigned Cmp1Operand1 = getSrcVReg(CMPI1->getOperand(1).getReg(),
1315                                          nullptr, nullptr, MRI);
1316       unsigned Cmp1Operand2 = getSrcVReg(CMPI1->getOperand(2).getReg(),
1317                                          nullptr, nullptr, MRI);
1318       unsigned Cmp2Operand1 = getSrcVReg(CMPI2->getOperand(1).getReg(),
1319                                          MBB1, &MBB2, MRI);
1320       unsigned Cmp2Operand2 = getSrcVReg(CMPI2->getOperand(2).getReg(),
1321                                          MBB1, &MBB2, MRI);
1322 
1323       if (Cmp1Operand1 == Cmp2Operand1 && Cmp1Operand2 == Cmp2Operand2) {
1324         // Same pair of registers in the same order; ready to merge as is.
1325       }
1326       else if (Cmp1Operand1 == Cmp2Operand2 && Cmp1Operand2 == Cmp2Operand1) {
1327         // Same pair of registers in different order.
1328         // We reverse the predicate to merge compare instructions.
1329         PPC::Predicate Pred = (PPC::Predicate)BI2->getOperand(0).getImm();
1330         NewPredicate2 = (unsigned)PPC::getSwappedPredicate(Pred);
1331         // In case of partial redundancy, we need to swap operands
1332         // in another compare instruction.
1333         SwapOperands = true;
1334       }
1335       else continue;
1336     }
1337     else if (CMPI1->getOperand(2).isImm() && CMPI2->getOperand(2).isImm()) {
1338       // In case of comparisons between a register and an immediate,
1339       // the operand register must be same for two compare instructions.
1340       unsigned Cmp1Operand1 = getSrcVReg(CMPI1->getOperand(1).getReg(),
1341                                          nullptr, nullptr, MRI);
1342       unsigned Cmp2Operand1 = getSrcVReg(CMPI2->getOperand(1).getReg(),
1343                                          MBB1, &MBB2, MRI);
1344       if (Cmp1Operand1 != Cmp2Operand1)
1345         continue;
1346 
1347       NewImm1 = Imm1 = (int16_t)CMPI1->getOperand(2).getImm();
1348       NewImm2 = Imm2 = (int16_t)CMPI2->getOperand(2).getImm();
1349 
1350       // If immediate are not same, we try to adjust by changing predicate;
1351       // e.g. GT imm means GE (imm+1).
1352       if (Imm1 != Imm2 && (!isEqOrNe(BI2) || !isEqOrNe(BI1))) {
1353         int Diff = Imm1 - Imm2;
1354         if (Diff < -2 || Diff > 2)
1355           continue;
1356 
1357         unsigned PredToInc1 = getPredicateToIncImm(BI1, CMPI1);
1358         unsigned PredToDec1 = getPredicateToDecImm(BI1, CMPI1);
1359         unsigned PredToInc2 = getPredicateToIncImm(BI2, CMPI2);
1360         unsigned PredToDec2 = getPredicateToDecImm(BI2, CMPI2);
1361         if (Diff == 2) {
1362           if (PredToInc2 && PredToDec1) {
1363             NewPredicate2 = PredToInc2;
1364             NewPredicate1 = PredToDec1;
1365             NewImm2++;
1366             NewImm1--;
1367           }
1368         }
1369         else if (Diff == 1) {
1370           if (PredToInc2) {
1371             NewImm2++;
1372             NewPredicate2 = PredToInc2;
1373           }
1374           else if (PredToDec1) {
1375             NewImm1--;
1376             NewPredicate1 = PredToDec1;
1377           }
1378         }
1379         else if (Diff == -1) {
1380           if (PredToDec2) {
1381             NewImm2--;
1382             NewPredicate2 = PredToDec2;
1383           }
1384           else if (PredToInc1) {
1385             NewImm1++;
1386             NewPredicate1 = PredToInc1;
1387           }
1388         }
1389         else if (Diff == -2) {
1390           if (PredToDec2 && PredToInc1) {
1391             NewPredicate2 = PredToDec2;
1392             NewPredicate1 = PredToInc1;
1393             NewImm2--;
1394             NewImm1++;
1395           }
1396         }
1397       }
1398 
1399       // We cannot merge two compares if the immediates are not same.
1400       if (NewImm2 != NewImm1)
1401         continue;
1402     }
1403 
1404     LLVM_DEBUG(dbgs() << "Optimize two pairs of compare and branch:\n");
1405     LLVM_DEBUG(CMPI1->dump());
1406     LLVM_DEBUG(BI1->dump());
1407     LLVM_DEBUG(CMPI2->dump());
1408     LLVM_DEBUG(BI2->dump());
1409 
1410     // We adjust opcode, predicates and immediate as we determined above.
1411     if (NewOpCode != 0 && NewOpCode != CMPI1->getOpcode()) {
1412       CMPI1->setDesc(TII->get(NewOpCode));
1413     }
1414     if (NewPredicate1) {
1415       BI1->getOperand(0).setImm(NewPredicate1);
1416     }
1417     if (NewPredicate2) {
1418       BI2->getOperand(0).setImm(NewPredicate2);
1419     }
1420     if (NewImm1 != Imm1) {
1421       CMPI1->getOperand(2).setImm(NewImm1);
1422     }
1423 
1424     if (IsPartiallyRedundant) {
1425       // We touch up the compare instruction in MBB2 and move it to
1426       // a previous BB to handle partially redundant case.
1427       if (SwapOperands) {
1428         Register Op1 = CMPI2->getOperand(1).getReg();
1429         Register Op2 = CMPI2->getOperand(2).getReg();
1430         CMPI2->getOperand(1).setReg(Op2);
1431         CMPI2->getOperand(2).setReg(Op1);
1432       }
1433       if (NewImm2 != Imm2)
1434         CMPI2->getOperand(2).setImm(NewImm2);
1435 
1436       for (int I = 1; I <= 2; I++) {
1437         if (CMPI2->getOperand(I).isReg()) {
1438           MachineInstr *Inst = MRI->getVRegDef(CMPI2->getOperand(I).getReg());
1439           if (Inst->getParent() != &MBB2)
1440             continue;
1441 
1442           assert(Inst->getOpcode() == PPC::PHI &&
1443                  "We cannot support if an operand comes from this BB.");
1444           unsigned SrcReg = getIncomingRegForBlock(Inst, MBBtoMoveCmp);
1445           CMPI2->getOperand(I).setReg(SrcReg);
1446         }
1447       }
1448       auto I = MachineBasicBlock::iterator(MBBtoMoveCmp->getFirstTerminator());
1449       MBBtoMoveCmp->splice(I, &MBB2, MachineBasicBlock::iterator(CMPI2));
1450 
1451       DebugLoc DL = CMPI2->getDebugLoc();
1452       Register NewVReg = MRI->createVirtualRegister(&PPC::CRRCRegClass);
1453       BuildMI(MBB2, MBB2.begin(), DL,
1454               TII->get(PPC::PHI), NewVReg)
1455         .addReg(BI1->getOperand(1).getReg()).addMBB(MBB1)
1456         .addReg(BI2->getOperand(1).getReg()).addMBB(MBBtoMoveCmp);
1457       BI2->getOperand(1).setReg(NewVReg);
1458     }
1459     else {
1460       // We finally eliminate compare instruction in MBB2.
1461       BI2->getOperand(1).setReg(BI1->getOperand(1).getReg());
1462       CMPI2->eraseFromParent();
1463     }
1464     BI2->getOperand(1).setIsKill(true);
1465     BI1->getOperand(1).setIsKill(false);
1466 
1467     LLVM_DEBUG(dbgs() << "into a compare and two branches:\n");
1468     LLVM_DEBUG(CMPI1->dump());
1469     LLVM_DEBUG(BI1->dump());
1470     LLVM_DEBUG(BI2->dump());
1471     if (IsPartiallyRedundant) {
1472       LLVM_DEBUG(dbgs() << "The following compare is moved into "
1473                         << printMBBReference(*MBBtoMoveCmp)
1474                         << " to handle partial redundancy.\n");
1475       LLVM_DEBUG(CMPI2->dump());
1476     }
1477 
1478     Simplified = true;
1479   }
1480 
1481   return Simplified;
1482 }
1483 
1484 // We miss the opportunity to emit an RLDIC when lowering jump tables
1485 // since ISEL sees only a single basic block. When selecting, the clear
1486 // and shift left will be in different blocks.
1487 bool PPCMIPeephole::emitRLDICWhenLoweringJumpTables(MachineInstr &MI) {
1488   if (MI.getOpcode() != PPC::RLDICR)
1489     return false;
1490 
1491   Register SrcReg = MI.getOperand(1).getReg();
1492   if (!Register::isVirtualRegister(SrcReg))
1493     return false;
1494 
1495   MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
1496   if (SrcMI->getOpcode() != PPC::RLDICL)
1497     return false;
1498 
1499   MachineOperand MOpSHSrc = SrcMI->getOperand(2);
1500   MachineOperand MOpMBSrc = SrcMI->getOperand(3);
1501   MachineOperand MOpSHMI = MI.getOperand(2);
1502   MachineOperand MOpMEMI = MI.getOperand(3);
1503   if (!(MOpSHSrc.isImm() && MOpMBSrc.isImm() && MOpSHMI.isImm() &&
1504         MOpMEMI.isImm()))
1505     return false;
1506 
1507   uint64_t SHSrc = MOpSHSrc.getImm();
1508   uint64_t MBSrc = MOpMBSrc.getImm();
1509   uint64_t SHMI = MOpSHMI.getImm();
1510   uint64_t MEMI = MOpMEMI.getImm();
1511   uint64_t NewSH = SHSrc + SHMI;
1512   uint64_t NewMB = MBSrc - SHMI;
1513   if (NewMB > 63 || NewSH > 63)
1514     return false;
1515 
1516   // The bits cleared with RLDICL are [0, MBSrc).
1517   // The bits cleared with RLDICR are (MEMI, 63].
1518   // After the sequence, the bits cleared are:
1519   // [0, MBSrc-SHMI) and (MEMI, 63).
1520   //
1521   // The bits cleared with RLDIC are [0, NewMB) and (63-NewSH, 63].
1522   if ((63 - NewSH) != MEMI)
1523     return false;
1524 
1525   LLVM_DEBUG(dbgs() << "Converting pair: ");
1526   LLVM_DEBUG(SrcMI->dump());
1527   LLVM_DEBUG(MI.dump());
1528 
1529   MI.setDesc(TII->get(PPC::RLDIC));
1530   MI.getOperand(1).setReg(SrcMI->getOperand(1).getReg());
1531   MI.getOperand(2).setImm(NewSH);
1532   MI.getOperand(3).setImm(NewMB);
1533 
1534   LLVM_DEBUG(dbgs() << "To: ");
1535   LLVM_DEBUG(MI.dump());
1536   NumRotatesCollapsed++;
1537   return true;
1538 }
1539 
1540 // For case in LLVM IR
1541 // entry:
1542 //   %iconv = sext i32 %index to i64
1543 //   br i1 undef label %true, label %false
1544 // true:
1545 //   %ptr = getelementptr inbounds i32, i32* null, i64 %iconv
1546 // ...
1547 // PPCISelLowering::combineSHL fails to combine, because sext and shl are in
1548 // different BBs when conducting instruction selection. We can do a peephole
1549 // optimization to combine these two instructions into extswsli after
1550 // instruction selection.
1551 bool PPCMIPeephole::combineSEXTAndSHL(MachineInstr &MI,
1552                                       MachineInstr *&ToErase) {
1553   if (MI.getOpcode() != PPC::RLDICR)
1554     return false;
1555 
1556   if (!MF->getSubtarget<PPCSubtarget>().isISA3_0())
1557     return false;
1558 
1559   assert(MI.getNumOperands() == 4 && "RLDICR should have 4 operands");
1560 
1561   MachineOperand MOpSHMI = MI.getOperand(2);
1562   MachineOperand MOpMEMI = MI.getOperand(3);
1563   if (!(MOpSHMI.isImm() && MOpMEMI.isImm()))
1564     return false;
1565 
1566   uint64_t SHMI = MOpSHMI.getImm();
1567   uint64_t MEMI = MOpMEMI.getImm();
1568   if (SHMI + MEMI != 63)
1569     return false;
1570 
1571   Register SrcReg = MI.getOperand(1).getReg();
1572   if (!Register::isVirtualRegister(SrcReg))
1573     return false;
1574 
1575   MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
1576   if (SrcMI->getOpcode() != PPC::EXTSW &&
1577       SrcMI->getOpcode() != PPC::EXTSW_32_64)
1578     return false;
1579 
1580   // If the register defined by extsw has more than one use, combination is not
1581   // needed.
1582   if (!MRI->hasOneNonDBGUse(SrcReg))
1583     return false;
1584 
1585   assert(SrcMI->getNumOperands() == 2 && "EXTSW should have 2 operands");
1586   assert(SrcMI->getOperand(1).isReg() &&
1587          "EXTSW's second operand should be a register");
1588   if (!Register::isVirtualRegister(SrcMI->getOperand(1).getReg()))
1589     return false;
1590 
1591   LLVM_DEBUG(dbgs() << "Combining pair: ");
1592   LLVM_DEBUG(SrcMI->dump());
1593   LLVM_DEBUG(MI.dump());
1594 
1595   MachineInstr *NewInstr =
1596       BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
1597               SrcMI->getOpcode() == PPC::EXTSW ? TII->get(PPC::EXTSWSLI)
1598                                                : TII->get(PPC::EXTSWSLI_32_64),
1599               MI.getOperand(0).getReg())
1600           .add(SrcMI->getOperand(1))
1601           .add(MOpSHMI);
1602   (void)NewInstr;
1603 
1604   LLVM_DEBUG(dbgs() << "TO: ");
1605   LLVM_DEBUG(NewInstr->dump());
1606   ++NumEXTSWAndSLDICombined;
1607   ToErase = &MI;
1608   // SrcMI, which is extsw, is of no use now, erase it.
1609   SrcMI->eraseFromParent();
1610   return true;
1611 }
1612 
1613 } // end default namespace
1614 
1615 INITIALIZE_PASS_BEGIN(PPCMIPeephole, DEBUG_TYPE,
1616                       "PowerPC MI Peephole Optimization", false, false)
1617 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
1618 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
1619 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
1620 INITIALIZE_PASS_END(PPCMIPeephole, DEBUG_TYPE,
1621                     "PowerPC MI Peephole Optimization", false, false)
1622 
1623 char PPCMIPeephole::ID = 0;
1624 FunctionPass*
1625 llvm::createPPCMIPeepholePass() { return new PPCMIPeephole(); }
1626 
1627