contrib/llvm/lib/Target/PowerPC/PPCMIPeephole.cpp

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