lib/CodeGen/PeepholeOptimizer.cpp

   1 //===-- PeepholeOptimizer.cpp - Peephole Optimizations --------------------===//
   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 // Perform peephole optimizations on the machine code:
  11 //
  12 // - Optimize Extensions
  13 //
  14 //     Optimization of sign / zero extension instructions. It may be extended to
  15 //     handle other instructions with similar properties.
  16 //
  17 //     On some targets, some instructions, e.g. X86 sign / zero extension, may
  18 //     leave the source value in the lower part of the result. This optimization
  19 //     will replace some uses of the pre-extension value with uses of the
  20 //     sub-register of the results.
  21 //
  22 // - Optimize Comparisons
  23 //
  24 //     Optimization of comparison instructions. For instance, in this code:
  25 //
  26 //       sub r1, 1
  27 //       cmp r1, 0
  28 //       bz  L1
  29 //
  30 //     If the "sub" instruction all ready sets (or could be modified to set) the
  31 //     same flag that the "cmp" instruction sets and that "bz" uses, then we can
  32 //     eliminate the "cmp" instruction.
  33 //
  34 //     Another instance, in this code:
  35 //
  36 //       sub r1, r3 | sub r1, imm
  37 //       cmp r3, r1 or cmp r1, r3 | cmp r1, imm
  38 //       bge L1
  39 //
  40 //     If the branch instruction can use flag from "sub", then we can replace
  41 //     "sub" with "subs" and eliminate the "cmp" instruction.
  42 //
  43 // - Optimize Loads:
  44 //
  45 //     Loads that can be folded into a later instruction. A load is foldable
  46 //     if it loads to virtual registers and the virtual register defined has
  47 //     a single use.
  48 //
  49 // - Optimize Copies and Bitcast:
  50 //
  51 //     Rewrite copies and bitcasts to avoid cross register bank copies
  52 //     when possible.
  53 //     E.g., Consider the following example, where capital and lower
  54 //     letters denote different register file:
  55 //     b = copy A <-- cross-bank copy
  56 //     C = copy b <-- cross-bank copy
  57 //   =>
  58 //     b = copy A <-- cross-bank copy
  59 //     C = copy A <-- same-bank copy
  60 //
  61 //     E.g., for bitcast:
  62 //     b = bitcast A <-- cross-bank copy
  63 //     C = bitcast b <-- cross-bank copy
  64 //   =>
  65 //     b = bitcast A <-- cross-bank copy
  66 //     C = copy A    <-- same-bank copy
  67 //===----------------------------------------------------------------------===//
  68
  69 #include "llvm/CodeGen/Passes.h"
  70 #include "llvm/ADT/DenseMap.h"
  71 #include "llvm/ADT/SmallPtrSet.h"
  72 #include "llvm/ADT/SmallSet.h"
  73 #include "llvm/ADT/Statistic.h"
  74 #include "llvm/CodeGen/MachineDominators.h"
  75 #include "llvm/CodeGen/MachineInstrBuilder.h"
  76 #include "llvm/CodeGen/MachineRegisterInfo.h"
  77 #include "llvm/Support/CommandLine.h"
  78 #include "llvm/Support/Debug.h"
  79 #include "llvm/Target/TargetInstrInfo.h"
  80 #include "llvm/Target/TargetRegisterInfo.h"
  81 using namespace llvm;
  82
  83 #define DEBUG_TYPE "peephole-opt"
  84
  85 // Optimize Extensions
  86 static cl::opt<bool>
  87 Aggressive("aggressive-ext-opt", cl::Hidden,
  88            cl::desc("Aggressive extension optimization"));
  89
  90 static cl::opt<bool>
  91 DisablePeephole("disable-peephole", cl::Hidden, cl::init(false),
  92                 cl::desc("Disable the peephole optimizer"));
  93
  94 static cl::opt<bool>
  95 DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(true),
  96                   cl::desc("Disable advanced copy optimization"));
  97
  98 STATISTIC(NumReuse,      "Number of extension results reused");
  99 STATISTIC(NumCmps,       "Number of compares eliminated");
 100 STATISTIC(NumImmFold,    "Number of move immediate folded");
 101 STATISTIC(NumLoadFold,   "Number of loads folded");
 102 STATISTIC(NumSelects,    "Number of selects optimized");
 103 STATISTIC(NumCopiesBitcasts, "Number of copies/bitcasts optimized");
 104
 105 namespace {
 106   class PeepholeOptimizer : public MachineFunctionPass {
 107     const TargetMachine   *TM;
 108     const TargetInstrInfo *TII;
 109     MachineRegisterInfo   *MRI;
 110     MachineDominatorTree  *DT;  // Machine dominator tree
 111
 112   public:
 113     static char ID; // Pass identification
 114     PeepholeOptimizer() : MachineFunctionPass(ID) {
 115       initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry());
 116     }
 117
 118     bool runOnMachineFunction(MachineFunction &MF) override;
 119
 120     void getAnalysisUsage(AnalysisUsage &AU) const override {
 121       AU.setPreservesCFG();
 122       MachineFunctionPass::getAnalysisUsage(AU);
 123       if (Aggressive) {
 124         AU.addRequired<MachineDominatorTree>();
 125         AU.addPreserved<MachineDominatorTree>();
 126       }
 127     }
 128
 129   private:
 130     bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB);
 131     bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
 132                           SmallPtrSet<MachineInstr*, 8> &LocalMIs);
 133     bool optimizeSelect(MachineInstr *MI);
 134     bool optimizeCopyOrBitcast(MachineInstr *MI);
 135     bool isMoveImmediate(MachineInstr *MI,
 136                          SmallSet<unsigned, 4> &ImmDefRegs,
 137                          DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
 138     bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
 139                        SmallSet<unsigned, 4> &ImmDefRegs,
 140                        DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
 141     bool isLoadFoldable(MachineInstr *MI,
 142                         SmallSet<unsigned, 16> &FoldAsLoadDefCandidates);
 143   };
 144
 145   /// \brief Helper class to track the possible sources of a value defined by
 146   /// a (chain of) copy related instructions.
 147   /// Given a definition (instruction and definition index), this class
 148   /// follows the use-def chain to find successive suitable sources.
 149   /// The given source can be used to rewrite the definition into
 150   /// def = COPY src.
 151   ///
 152   /// For instance, let us consider the following snippet:
 153   /// v0 =
 154   /// v2 = INSERT_SUBREG v1, v0, sub0
 155   /// def = COPY v2.sub0
 156   ///
 157   /// Using a ValueTracker for def = COPY v2.sub0 will give the following
 158   /// suitable sources:
 159   /// v2.sub0 and v0.
 160   /// Then, def can be rewritten into def = COPY v0.
 161   class ValueTracker {
 162   private:
 163     /// The current point into the use-def chain.
 164     const MachineInstr *Def;
 165     /// The index of the definition in Def.
 166     unsigned DefIdx;
 167     /// The sub register index of the definition.
 168     unsigned DefSubReg;
 169     /// The register where the value can be found.
 170     unsigned Reg;
 171     /// Specifiy whether or not the value tracking looks through
 172     /// complex instructions. When this is false, the value tracker
 173     /// bails on everything that is not a copy or a bitcast.
 174     ///
 175     /// Note: This could have been implemented as a specialized version of
 176     /// the ValueTracker class but that would have complicated the code of
 177     /// the users of this class.
 178     bool UseAdvancedTracking;
 179     /// Optional MachineRegisterInfo used to perform some complex
 180     /// tracking.
 181     const MachineRegisterInfo *MRI;
 182
 183     /// \brief Dispatcher to the right underlying implementation of
 184     /// getNextSource.
 185     bool getNextSourceImpl(unsigned &SrcIdx, unsigned &SrcSubReg);
 186     /// \brief Specialized version of getNextSource for Copy instructions.
 187     bool getNextSourceFromCopy(unsigned &SrcIdx, unsigned &SrcSubReg);
 188     /// \brief Specialized version of getNextSource for Bitcast instructions.
 189     bool getNextSourceFromBitcast(unsigned &SrcIdx, unsigned &SrcSubReg);
 190     /// \brief Specialized version of getNextSource for RegSequence
 191     /// instructions.
 192     bool getNextSourceFromRegSequence(unsigned &SrcIdx, unsigned &SrcSubReg);
 193     /// \brief Specialized version of getNextSource for InsertSubreg
 194     /// instructions.
 195     bool getNextSourceFromInsertSubreg(unsigned &SrcIdx, unsigned &SrcSubReg);
 196     /// \brief Specialized version of getNextSource for ExtractSubreg
 197     /// instructions.
 198     bool getNextSourceFromExtractSubreg(unsigned &SrcIdx, unsigned &SrcSubReg);
 199     /// \brief Specialized version of getNextSource for SubregToReg
 200     /// instructions.
 201     bool getNextSourceFromSubregToReg(unsigned &SrcIdx, unsigned &SrcSubReg);
 202
 203   public:
 204     /// \brief Create a ValueTracker instance for the value defines by \p MI
 205     /// at the operand index \p DefIdx.
 206     /// \p DefSubReg represents the sub register index the value tracker will
 207     /// track. It does not need to match the sub register index used in \p MI.
 208     /// \p UseAdvancedTracking specifies whether or not the value tracker looks
 209     /// through complex instructions. By default (false), it handles only copy
 210     /// and bitcast instructions.
 211     /// \p MRI useful to perform some complex checks.
 212     ValueTracker(const MachineInstr &MI, unsigned DefIdx, unsigned DefSubReg,
 213                  bool UseAdvancedTracking = false,
 214                  const MachineRegisterInfo *MRI = nullptr)
 215         : Def(&MI), DefIdx(DefIdx), DefSubReg(DefSubReg),
 216           UseAdvancedTracking(UseAdvancedTracking), MRI(MRI) {
 217       assert(Def->getOperand(DefIdx).isDef() &&
 218              Def->getOperand(DefIdx).isReg() &&
 219              "Definition does not match machine instruction");
 220       // Initially the value is in the defined register.
 221       Reg = Def->getOperand(DefIdx).getReg();
 222     }
 223
 224     /// \brief Following the use-def chain, get the next available source
 225     /// for the tracked value.
 226     /// When the returned value is not nullptr, getReg() gives the register
 227     /// that contain the tracked value.
 228     /// \note The sub register index returned in \p SrcSubReg must be used
 229     /// on that getReg() to access the actual value.
 230     /// \return Unless the returned value is nullptr (i.e., no source found),
 231     /// \p SrcIdx gives the index of the next source in the returned
 232     /// instruction and \p SrcSubReg the index to be used on that source to
 233     /// get the tracked value. When nullptr is returned, no alternative source
 234     /// has been found.
 235     const MachineInstr *getNextSource(unsigned &SrcIdx, unsigned &SrcSubReg);
 236
 237     /// \brief Get the last register where the initial value can be found.
 238     /// Initially this is the register of the definition.
 239     /// Then, after each successful call to getNextSource, this is the
 240     /// register of the last source.
 241     unsigned getReg() const { return Reg; }
 242   };
 243 }
 244
 245 char PeepholeOptimizer::ID = 0;
 246 char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID;
 247 INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts",
 248                 "Peephole Optimizations", false, false)
 249 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 250 INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts",
 251                 "Peephole Optimizations", false, false)
 252
 253 /// optimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads
 254 /// a single register and writes a single register and it does not modify the
 255 /// source, and if the source value is preserved as a sub-register of the
 256 /// result, then replace all reachable uses of the source with the subreg of the
 257 /// result.
 258 ///
 259 /// Do not generate an EXTRACT that is used only in a debug use, as this changes
 260 /// the code. Since this code does not currently share EXTRACTs, just ignore all
 261 /// debug uses.
 262 bool PeepholeOptimizer::
 263 optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
 264                  SmallPtrSet<MachineInstr*, 8> &LocalMIs) {
 265   unsigned SrcReg, DstReg, SubIdx;
 266   if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx))
 267     return false;
 268
 269   if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
 270       TargetRegisterInfo::isPhysicalRegister(SrcReg))
 271     return false;
 272
 273   if (MRI->hasOneNonDBGUse(SrcReg))
 274     // No other uses.
 275     return false;
 276
 277   // Ensure DstReg can get a register class that actually supports
 278   // sub-registers. Don't change the class until we commit.
 279   const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
 280   DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx);
 281   if (!DstRC)
 282     return false;
 283
 284   // The ext instr may be operating on a sub-register of SrcReg as well.
 285   // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit
 286   // register.
 287   // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of
 288   // SrcReg:SubIdx should be replaced.
 289   bool UseSrcSubIdx = TM->getRegisterInfo()->
 290     getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr;
 291
 292   // The source has other uses. See if we can replace the other uses with use of
 293   // the result of the extension.
 294   SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
 295   for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
 296     ReachedBBs.insert(UI.getParent());
 297
 298   // Uses that are in the same BB of uses of the result of the instruction.
 299   SmallVector<MachineOperand*, 8> Uses;
 300
 301   // Uses that the result of the instruction can reach.
 302   SmallVector<MachineOperand*, 8> ExtendedUses;
 303
 304   bool ExtendLife = true;
 305   for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {
 306     MachineInstr *UseMI = UseMO.getParent();
 307     if (UseMI == MI)
 308       continue;
 309
 310     if (UseMI->isPHI()) {
 311       ExtendLife = false;
 312       continue;
 313     }
 314
 315     // Only accept uses of SrcReg:SubIdx.
 316     if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx)
 317       continue;
 318
 319     // It's an error to translate this:
 320     //
 321     //    %reg1025 = <sext> %reg1024
 322     //     ...
 323     //    %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
 324     //
 325     // into this:
 326     //
 327     //    %reg1025 = <sext> %reg1024
 328     //     ...
 329     //    %reg1027 = COPY %reg1025:4
 330     //    %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
 331     //
 332     // The problem here is that SUBREG_TO_REG is there to assert that an
 333     // implicit zext occurs. It doesn't insert a zext instruction. If we allow
 334     // the COPY here, it will give us the value after the <sext>, not the
 335     // original value of %reg1024 before <sext>.
 336     if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
 337       continue;
 338
 339     MachineBasicBlock *UseMBB = UseMI->getParent();
 340     if (UseMBB == MBB) {
 341       // Local uses that come after the extension.
 342       if (!LocalMIs.count(UseMI))
 343         Uses.push_back(&UseMO);
 344     } else if (ReachedBBs.count(UseMBB)) {
 345       // Non-local uses where the result of the extension is used. Always
 346       // replace these unless it's a PHI.
 347       Uses.push_back(&UseMO);
 348     } else if (Aggressive && DT->dominates(MBB, UseMBB)) {
 349       // We may want to extend the live range of the extension result in order
 350       // to replace these uses.
 351       ExtendedUses.push_back(&UseMO);
 352     } else {
 353       // Both will be live out of the def MBB anyway. Don't extend live range of
 354       // the extension result.
 355       ExtendLife = false;
 356       break;
 357     }
 358   }
 359
 360   if (ExtendLife && !ExtendedUses.empty())
 361     // Extend the liveness of the extension result.
 362     std::copy(ExtendedUses.begin(), ExtendedUses.end(),
 363               std::back_inserter(Uses));
 364
 365   // Now replace all uses.
 366   bool Changed = false;
 367   if (!Uses.empty()) {
 368     SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
 369
 370     // Look for PHI uses of the extended result, we don't want to extend the
 371     // liveness of a PHI input. It breaks all kinds of assumptions down
 372     // stream. A PHI use is expected to be the kill of its source values.
 373     for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
 374       if (UI.isPHI())
 375         PHIBBs.insert(UI.getParent());
 376
 377     const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
 378     for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
 379       MachineOperand *UseMO = Uses[i];
 380       MachineInstr *UseMI = UseMO->getParent();
 381       MachineBasicBlock *UseMBB = UseMI->getParent();
 382       if (PHIBBs.count(UseMBB))
 383         continue;
 384
 385       // About to add uses of DstReg, clear DstReg's kill flags.
 386       if (!Changed) {
 387         MRI->clearKillFlags(DstReg);
 388         MRI->constrainRegClass(DstReg, DstRC);
 389       }
 390
 391       unsigned NewVR = MRI->createVirtualRegister(RC);
 392       MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
 393                                    TII->get(TargetOpcode::COPY), NewVR)
 394         .addReg(DstReg, 0, SubIdx);
 395       // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set.
 396       if (UseSrcSubIdx) {
 397         Copy->getOperand(0).setSubReg(SubIdx);
 398         Copy->getOperand(0).setIsUndef();
 399       }
 400       UseMO->setReg(NewVR);
 401       ++NumReuse;
 402       Changed = true;
 403     }
 404   }
 405
 406   return Changed;
 407 }
 408
 409 /// optimizeCmpInstr - If the instruction is a compare and the previous
 410 /// instruction it's comparing against all ready sets (or could be modified to
 411 /// set) the same flag as the compare, then we can remove the comparison and use
 412 /// the flag from the previous instruction.
 413 bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI,
 414                                          MachineBasicBlock *MBB) {
 415   // If this instruction is a comparison against zero and isn't comparing a
 416   // physical register, we can try to optimize it.
 417   unsigned SrcReg, SrcReg2;
 418   int CmpMask, CmpValue;
 419   if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) ||
 420       TargetRegisterInfo::isPhysicalRegister(SrcReg) ||
 421       (SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2)))
 422     return false;
 423
 424   // Attempt to optimize the comparison instruction.
 425   if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) {
 426     ++NumCmps;
 427     return true;
 428   }
 429
 430   return false;
 431 }
 432
 433 /// Optimize a select instruction.
 434 bool PeepholeOptimizer::optimizeSelect(MachineInstr *MI) {
 435   unsigned TrueOp = 0;
 436   unsigned FalseOp = 0;
 437   bool Optimizable = false;
 438   SmallVector<MachineOperand, 4> Cond;
 439   if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable))
 440     return false;
 441   if (!Optimizable)
 442     return false;
 443   if (!TII->optimizeSelect(MI))
 444     return false;
 445   MI->eraseFromParent();
 446   ++NumSelects;
 447   return true;
 448 }
 449
 450 /// \brief Check if the registers defined by the pair (RegisterClass, SubReg)
 451 /// share the same register file.
 452 static bool shareSameRegisterFile(const TargetRegisterInfo &TRI,
 453                                   const TargetRegisterClass *DefRC,
 454                                   unsigned DefSubReg,
 455                                   const TargetRegisterClass *SrcRC,
 456                                   unsigned SrcSubReg) {
 457   // Same register class.
 458   if (DefRC == SrcRC)
 459     return true;
 460
 461   // Both operands are sub registers. Check if they share a register class.
 462   unsigned SrcIdx, DefIdx;
 463   if (SrcSubReg && DefSubReg)
 464     return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg,
 465                                       SrcIdx, DefIdx) != nullptr;
 466   // At most one of the register is a sub register, make it Src to avoid
 467   // duplicating the test.
 468   if (!SrcSubReg) {
 469     std::swap(DefSubReg, SrcSubReg);
 470     std::swap(DefRC, SrcRC);
 471   }
 472
 473   // One of the register is a sub register, check if we can get a superclass.
 474   if (SrcSubReg)
 475     return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr;
 476   // Plain copy.
 477   return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr;
 478 }
 479
 480 /// \brief Get the index of the definition and source for \p Copy
 481 /// instruction.
 482 /// \pre Copy.isCopy() or Copy.isBitcast().
 483 /// \return True if the Copy instruction has only one register source
 484 /// and one register definition. Otherwise, \p DefIdx and \p SrcIdx
 485 /// are invalid.
 486 static bool getCopyOrBitcastDefUseIdx(const MachineInstr &Copy,
 487                                       unsigned &DefIdx, unsigned &SrcIdx) {
 488   assert((Copy.isCopy() || Copy.isBitcast()) && "Wrong operation type.");
 489   if (Copy.isCopy()) {
 490     // Copy instruction are supposed to be: Def = Src.
 491      if (Copy.getDesc().getNumOperands() != 2)
 492        return false;
 493      DefIdx = 0;
 494      SrcIdx = 1;
 495      assert(Copy.getOperand(DefIdx).isDef() && "Use comes before def!");
 496      return true;
 497   }
 498   // Bitcast case.
 499   // Bitcasts with more than one def are not supported.
 500   if (Copy.getDesc().getNumDefs() != 1)
 501     return false;
 502   // Initialize SrcIdx to an undefined operand.
 503   SrcIdx = Copy.getDesc().getNumOperands();
 504   for (unsigned OpIdx = 0, EndOpIdx = SrcIdx; OpIdx != EndOpIdx; ++OpIdx) {
 505     const MachineOperand &MO = Copy.getOperand(OpIdx);
 506     if (!MO.isReg() || !MO.getReg())
 507       continue;
 508     if (MO.isDef())
 509       DefIdx = OpIdx;
 510     else if (SrcIdx != EndOpIdx)
 511       // Multiple sources?
 512       return false;
 513     SrcIdx = OpIdx;
 514   }
 515   return true;
 516 }
 517
 518 /// \brief Optimize a copy or bitcast instruction to avoid cross
 519 /// register bank copy. The optimization looks through a chain of
 520 /// copies and try to find a source that has a compatible register
 521 /// class.
 522 /// Two register classes are considered to be compatible if they share
 523 /// the same register bank.
 524 /// New copies issued by this optimization are register allocator
 525 /// friendly. This optimization does not remove any copy as it may
 526 /// overconstraint the register allocator, but replaces some when
 527 /// possible.
 528 /// \pre \p MI is a Copy (MI->isCopy() is true)
 529 /// \return True, when \p MI has been optimized. In that case, \p MI has
 530 /// been removed from its parent.
 531 bool PeepholeOptimizer::optimizeCopyOrBitcast(MachineInstr *MI) {
 532   unsigned DefIdx, SrcIdx;
 533   if (!MI || !getCopyOrBitcastDefUseIdx(*MI, DefIdx, SrcIdx))
 534     return false;
 535
 536   const MachineOperand &MODef = MI->getOperand(DefIdx);
 537   assert(MODef.isReg() && "Copies must be between registers.");
 538   unsigned Def = MODef.getReg();
 539
 540   if (TargetRegisterInfo::isPhysicalRegister(Def))
 541     return false;
 542
 543   const TargetRegisterClass *DefRC = MRI->getRegClass(Def);
 544   unsigned DefSubReg = MODef.getSubReg();
 545
 546   unsigned Src;
 547   unsigned SrcSubReg;
 548   bool ShouldRewrite = false;
 549   const TargetRegisterInfo &TRI = *TM->getRegisterInfo();
 550
 551   // Follow the chain of copies until we reach the top of the use-def chain
 552   // or find a more suitable source.
 553   ValueTracker ValTracker(*MI, DefIdx, DefSubReg, !DisableAdvCopyOpt, MRI);
 554   do {
 555     unsigned CopySrcIdx, CopySrcSubReg;
 556     if (!ValTracker.getNextSource(CopySrcIdx, CopySrcSubReg))
 557       break;
 558     Src = ValTracker.getReg();
 559     SrcSubReg = CopySrcSubReg;
 560
 561     // Do not extend the live-ranges of physical registers as they add
 562     // constraints to the register allocator.
 563     // Moreover, if we want to extend the live-range of a physical register,
 564     // unlike SSA virtual register, we will have to check that they are not
 565     // redefine before the related use.
 566     if (TargetRegisterInfo::isPhysicalRegister(Src))
 567       break;
 568
 569     const TargetRegisterClass *SrcRC = MRI->getRegClass(Src);
 570
 571     // If this source does not incur a cross register bank copy, use it.
 572     ShouldRewrite = shareSameRegisterFile(TRI, DefRC, DefSubReg, SrcRC,
 573                                           SrcSubReg);
 574   } while (!ShouldRewrite);
 575
 576   // If we did not find a more suitable source, there is nothing to optimize.
 577   if (!ShouldRewrite || Src == MI->getOperand(SrcIdx).getReg())
 578     return false;
 579
 580   // Rewrite the copy to avoid a cross register bank penalty.
 581   unsigned NewVR = TargetRegisterInfo::isPhysicalRegister(Def) ? Def :
 582     MRI->createVirtualRegister(DefRC);
 583   MachineInstr *NewCopy = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
 584                                   TII->get(TargetOpcode::COPY), NewVR)
 585     .addReg(Src, 0, SrcSubReg);
 586   NewCopy->getOperand(0).setSubReg(DefSubReg);
 587
 588   MRI->replaceRegWith(Def, NewVR);
 589   MRI->clearKillFlags(NewVR);
 590   // We extended the lifetime of Src.
 591   // Clear the kill flags to account for that.
 592   MRI->clearKillFlags(Src);
 593   MI->eraseFromParent();
 594   ++NumCopiesBitcasts;
 595   return true;
 596 }
 597
 598 /// isLoadFoldable - Check whether MI is a candidate for folding into a later
 599 /// instruction. We only fold loads to virtual registers and the virtual
 600 /// register defined has a single use.
 601 bool PeepholeOptimizer::isLoadFoldable(
 602                               MachineInstr *MI,
 603                               SmallSet<unsigned, 16> &FoldAsLoadDefCandidates) {
 604   if (!MI->canFoldAsLoad() || !MI->mayLoad())
 605     return false;
 606   const MCInstrDesc &MCID = MI->getDesc();
 607   if (MCID.getNumDefs() != 1)
 608     return false;
 609
 610   unsigned Reg = MI->getOperand(0).getReg();
 611   // To reduce compilation time, we check MRI->hasOneNonDBGUse when inserting
 612   // loads. It should be checked when processing uses of the load, since
 613   // uses can be removed during peephole.
 614   if (!MI->getOperand(0).getSubReg() &&
 615       TargetRegisterInfo::isVirtualRegister(Reg) &&
 616       MRI->hasOneNonDBGUse(Reg)) {
 617     FoldAsLoadDefCandidates.insert(Reg);
 618     return true;
 619   }
 620   return false;
 621 }
 622
 623 bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI,
 624                                         SmallSet<unsigned, 4> &ImmDefRegs,
 625                                  DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
 626   const MCInstrDesc &MCID = MI->getDesc();
 627   if (!MI->isMoveImmediate())
 628     return false;
 629   if (MCID.getNumDefs() != 1)
 630     return false;
 631   unsigned Reg = MI->getOperand(0).getReg();
 632   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 633     ImmDefMIs.insert(std::make_pair(Reg, MI));
 634     ImmDefRegs.insert(Reg);
 635     return true;
 636   }
 637
 638   return false;
 639 }
 640
 641 /// foldImmediate - Try folding register operands that are defined by move
 642 /// immediate instructions, i.e. a trivial constant folding optimization, if
 643 /// and only if the def and use are in the same BB.
 644 bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
 645                                       SmallSet<unsigned, 4> &ImmDefRegs,
 646                                  DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
 647   for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
 648     MachineOperand &MO = MI->getOperand(i);
 649     if (!MO.isReg() || MO.isDef())
 650       continue;
 651     unsigned Reg = MO.getReg();
 652     if (!TargetRegisterInfo::isVirtualRegister(Reg))
 653       continue;
 654     if (ImmDefRegs.count(Reg) == 0)
 655       continue;
 656     DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg);
 657     assert(II != ImmDefMIs.end());
 658     if (TII->FoldImmediate(MI, II->second, Reg, MRI)) {
 659       ++NumImmFold;
 660       return true;
 661     }
 662   }
 663   return false;
 664 }
 665
 666 bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) {
 667   if (skipOptnoneFunction(*MF.getFunction()))
 668     return false;
 669
 670   DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
 671   DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n');
 672
 673   if (DisablePeephole)
 674     return false;
 675
 676   TM  = &MF.getTarget();
 677   TII = TM->getInstrInfo();
 678   MRI = &MF.getRegInfo();
 679   DT  = Aggressive ? &getAnalysis<MachineDominatorTree>() : nullptr;
 680
 681   bool Changed = false;
 682
 683   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 684     MachineBasicBlock *MBB = &*I;
 685
 686     bool SeenMoveImm = false;
 687     SmallPtrSet<MachineInstr*, 8> LocalMIs;
 688     SmallSet<unsigned, 4> ImmDefRegs;
 689     DenseMap<unsigned, MachineInstr*> ImmDefMIs;
 690     SmallSet<unsigned, 16> FoldAsLoadDefCandidates;
 691
 692     for (MachineBasicBlock::iterator
 693            MII = I->begin(), MIE = I->end(); MII != MIE; ) {
 694       MachineInstr *MI = &*MII;
 695       // We may be erasing MI below, increment MII now.
 696       ++MII;
 697       LocalMIs.insert(MI);
 698
 699       // Skip debug values. They should not affect this peephole optimization.
 700       if (MI->isDebugValue())
 701           continue;
 702
 703       // If there exists an instruction which belongs to the following
 704       // categories, we will discard the load candidates.
 705       if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() ||
 706           MI->isKill() || MI->isInlineAsm() ||
 707           MI->hasUnmodeledSideEffects()) {
 708         FoldAsLoadDefCandidates.clear();
 709         continue;
 710       }
 711       if (MI->mayStore() || MI->isCall())
 712         FoldAsLoadDefCandidates.clear();
 713
 714       if (((MI->isBitcast() || MI->isCopy()) && optimizeCopyOrBitcast(MI)) ||
 715           (MI->isCompare() && optimizeCmpInstr(MI, MBB)) ||
 716           (MI->isSelect() && optimizeSelect(MI))) {
 717         // MI is deleted.
 718         LocalMIs.erase(MI);
 719         Changed = true;
 720         continue;
 721       }
 722
 723       if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
 724         SeenMoveImm = true;
 725       } else {
 726         Changed |= optimizeExtInstr(MI, MBB, LocalMIs);
 727         // optimizeExtInstr might have created new instructions after MI
 728         // and before the already incremented MII. Adjust MII so that the
 729         // next iteration sees the new instructions.
 730         MII = MI;
 731         ++MII;
 732         if (SeenMoveImm)
 733           Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs);
 734       }
 735
 736       // Check whether MI is a load candidate for folding into a later
 737       // instruction. If MI is not a candidate, check whether we can fold an
 738       // earlier load into MI.
 739       if (!isLoadFoldable(MI, FoldAsLoadDefCandidates) &&
 740           !FoldAsLoadDefCandidates.empty()) {
 741         const MCInstrDesc &MIDesc = MI->getDesc();
 742         for (unsigned i = MIDesc.getNumDefs(); i != MIDesc.getNumOperands();
 743              ++i) {
 744           const MachineOperand &MOp = MI->getOperand(i);
 745           if (!MOp.isReg())
 746             continue;
 747           unsigned FoldAsLoadDefReg = MOp.getReg();
 748           if (FoldAsLoadDefCandidates.count(FoldAsLoadDefReg)) {
 749             // We need to fold load after optimizeCmpInstr, since
 750             // optimizeCmpInstr can enable folding by converting SUB to CMP.
 751             // Save FoldAsLoadDefReg because optimizeLoadInstr() resets it and
 752             // we need it for markUsesInDebugValueAsUndef().
 753             unsigned FoldedReg = FoldAsLoadDefReg;
 754             MachineInstr *DefMI = nullptr;
 755             MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI,
 756                                                           FoldAsLoadDefReg,
 757                                                           DefMI);
 758             if (FoldMI) {
 759               // Update LocalMIs since we replaced MI with FoldMI and deleted
 760               // DefMI.
 761               DEBUG(dbgs() << "Replacing: " << *MI);
 762               DEBUG(dbgs() << "     With: " << *FoldMI);
 763               LocalMIs.erase(MI);
 764               LocalMIs.erase(DefMI);
 765               LocalMIs.insert(FoldMI);
 766               MI->eraseFromParent();
 767               DefMI->eraseFromParent();
 768               MRI->markUsesInDebugValueAsUndef(FoldedReg);
 769               FoldAsLoadDefCandidates.erase(FoldedReg);
 770               ++NumLoadFold;
 771               // MI is replaced with FoldMI.
 772               Changed = true;
 773               break;
 774             }
 775           }
 776         }
 777       }
 778     }
 779   }
 780
 781   return Changed;
 782 }
 783
 784 bool ValueTracker::getNextSourceFromCopy(unsigned &SrcIdx,
 785                                          unsigned &SrcSubReg) {
 786   assert(Def->isCopy() && "Invalid definition");
 787   // Copy instruction are supposed to be: Def = Src.
 788   // If someone breaks this assumption, bad things will happen everywhere.
 789   assert(Def->getDesc().getNumOperands() == 2 && "Invalid number of operands");
 790
 791   if (Def->getOperand(DefIdx).getSubReg() != DefSubReg)
 792     // If we look for a different subreg, it means we want a subreg of src.
 793     // Bails as we do not support composing subreg yet.
 794     return false;
 795   // Otherwise, we want the whole source.
 796   SrcIdx = 1;
 797   SrcSubReg = Def->getOperand(SrcIdx).getSubReg();
 798   return true;
 799 }
 800
 801 bool ValueTracker::getNextSourceFromBitcast(unsigned &SrcIdx,
 802                                             unsigned &SrcSubReg) {
 803   assert(Def->isBitcast() && "Invalid definition");
 804
 805   // Bail if there are effects that a plain copy will not expose.
 806   if (Def->hasUnmodeledSideEffects())
 807     return false;
 808
 809   // Bitcasts with more than one def are not supported.
 810   if (Def->getDesc().getNumDefs() != 1)
 811     return false;
 812   if (Def->getOperand(DefIdx).getSubReg() != DefSubReg)
 813     // If we look for a different subreg, it means we want a subreg of the src.
 814     // Bails as we do not support composing subreg yet.
 815     return false;
 816
 817   SrcIdx = Def->getDesc().getNumOperands();
 818   for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx;
 819        ++OpIdx) {
 820     const MachineOperand &MO = Def->getOperand(OpIdx);
 821     if (!MO.isReg() || !MO.getReg())
 822       continue;
 823     assert(!MO.isDef() && "We should have skipped all the definitions by now");
 824     if (SrcIdx != EndOpIdx)
 825       // Multiple sources?
 826       return false;
 827     SrcIdx = OpIdx;
 828   }
 829   SrcSubReg = Def->getOperand(SrcIdx).getSubReg();
 830   return true;
 831 }
 832
 833 bool ValueTracker::getNextSourceFromRegSequence(unsigned &SrcIdx,
 834                                                 unsigned &SrcSubReg) {
 835   assert(Def->isRegSequence() && "Invalid definition");
 836
 837   if (Def->getOperand(DefIdx).getSubReg())
 838     // If we are composing subreg, bails out.
 839     // The case we are checking is Def.<subreg> = REG_SEQUENCE.
 840     // This should almost never happen as the SSA property is tracked at
 841     // the register level (as opposed to the subreg level).
 842     // I.e.,
 843     // Def.sub0 =
 844     // Def.sub1 =
 845     // is a valid SSA representation for Def.sub0 and Def.sub1, but not for
 846     // Def. Thus, it must not be generated.
 847     // However, some code could theoretically generates a single
 848     // Def.sub0 (i.e, not defining the other subregs) and we would
 849     // have this case.
 850     // If we can ascertain (or force) that this never happens, we could
 851     // turn that into an assertion.
 852     return false;
 853
 854   // We are looking at:
 855   // Def = REG_SEQUENCE v0, sub0, v1, sub1, ...
 856   // Check if one of the operand defines the subreg we are interested in.
 857   for (unsigned OpIdx = DefIdx + 1, EndOpIdx = Def->getNumOperands();
 858        OpIdx != EndOpIdx; OpIdx += 2) {
 859     const MachineOperand &MOSubIdx = Def->getOperand(OpIdx + 1);
 860     assert(MOSubIdx.isImm() &&
 861            "One of the subindex of the reg_sequence is not an immediate");
 862     if (MOSubIdx.getImm() == DefSubReg) {
 863       assert(Def->getOperand(OpIdx).isReg() &&
 864              "One of the source of the reg_sequence is not a register");
 865       SrcIdx = OpIdx;
 866       SrcSubReg = Def->getOperand(SrcIdx).getSubReg();
 867       return true;
 868     }
 869   }
 870
 871   // If the subreg we are tracking is super-defined by another subreg,
 872   // we could follow this value. However, this would require to compose
 873   // the subreg and we do not do that for now.
 874   return false;
 875 }
 876
 877 bool ValueTracker::getNextSourceFromInsertSubreg(unsigned &SrcIdx,
 878                                                  unsigned &SrcSubReg) {
 879   assert(Def->isInsertSubreg() && "Invalid definition");
 880   if (Def->getOperand(DefIdx).getSubReg())
 881     // If we are composing subreg, bails out.
 882     // Same remark as getNextSourceFromRegSequence.
 883     // I.e., this may be turned into an assert.
 884     return false;
 885
 886   // We are looking at:
 887   // Def = INSERT_SUBREG v0, v1, sub1
 888   // There are two cases:
 889   // 1. DefSubReg == sub1, get v1.
 890   // 2. DefSubReg != sub1, the value may be available through v0.
 891
 892   // #1 Check if the inserted register matches the require sub index.
 893   unsigned InsertedSubReg = Def->getOperand(3).getImm();
 894   if (InsertedSubReg == DefSubReg) {
 895     SrcIdx = 2;
 896     SrcSubReg = Def->getOperand(SrcIdx).getSubReg();
 897     return true;
 898   }
 899   // #2 Otherwise, if the sub register we are looking for is not partial
 900   // defined by the inserted element, we can look through the main
 901   // register (v0).
 902   // To check the overlapping we need a MRI and a TRI.
 903   if (!MRI)
 904     return false;
 905
 906   const MachineOperand &MODef = Def->getOperand(DefIdx);
 907   const MachineOperand &MOBase = Def->getOperand(1);
 908   // If the result register (Def) and the base register (v0) do not
 909   // have the same register class or if we have to compose
 910   // subregisters, bails out.
 911   if (MRI->getRegClass(MODef.getReg()) != MRI->getRegClass(MOBase.getReg()) ||
 912       MOBase.getSubReg())
 913     return false;
 914
 915   // Get the TRI and check if inserted sub register overlaps with the
 916   // sub register we are tracking.
 917   const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
 918   if (!TRI ||
 919       (TRI->getSubRegIndexLaneMask(DefSubReg) &
 920        TRI->getSubRegIndexLaneMask(InsertedSubReg)) != 0)
 921     return false;
 922   // At this point, the value is available in v0 via the same subreg
 923   // we used for Def.
 924   SrcIdx = 1;
 925   SrcSubReg = DefSubReg;
 926   return true;
 927 }
 928
 929 bool ValueTracker::getNextSourceFromExtractSubreg(unsigned &SrcIdx,
 930                                                   unsigned &SrcSubReg) {
 931   assert(Def->isExtractSubreg() && "Invalid definition");
 932   // We are looking at:
 933   // Def = EXTRACT_SUBREG v0, sub0
 934
 935   // Bails if we have to compose sub registers.
 936   // Indeed, if DefSubReg != 0, we would have to compose it with sub0.
 937   if (DefSubReg)
 938     return false;
 939
 940   // Bails if we have to compose sub registers.
 941   // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0.
 942   if (Def->getOperand(1).getSubReg())
 943     return false;
 944   // Otherwise, the value is available in the v0.sub0.
 945   SrcIdx = 1;
 946   SrcSubReg = Def->getOperand(2).getImm();
 947   return true;
 948 }
 949
 950 bool ValueTracker::getNextSourceFromSubregToReg(unsigned &SrcIdx,
 951                                                 unsigned &SrcSubReg) {
 952   assert(Def->isSubregToReg() && "Invalid definition");
 953   // We are looking at:
 954   // Def = SUBREG_TO_REG Imm, v0, sub0
 955
 956   // Bails if we have to compose sub registers.
 957   // If DefSubReg != sub0, we would have to check that all the bits
 958   // we track are included in sub0 and if yes, we would have to
 959   // determine the right subreg in v0.
 960   if (DefSubReg != Def->getOperand(3).getImm())
 961     return false;
 962   // Bails if we have to compose sub registers.
 963   // Likewise, if v0.subreg != 0, we would have to compose it with sub0.
 964   if (Def->getOperand(2).getSubReg())
 965     return false;
 966
 967   SrcIdx = 2;
 968   SrcSubReg = Def->getOperand(3).getImm();
 969   return true;
 970 }
 971
 972 bool ValueTracker::getNextSourceImpl(unsigned &SrcIdx, unsigned &SrcSubReg) {
 973   assert(Def && "This method needs a valid definition");
 974
 975   assert(
 976       (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic()) &&
 977       Def->getOperand(DefIdx).isDef() && "Invalid DefIdx");
 978   if (Def->isCopy())
 979     return getNextSourceFromCopy(SrcIdx, SrcSubReg);
 980   if (Def->isBitcast())
 981     return getNextSourceFromBitcast(SrcIdx, SrcSubReg);
 982   // All the remaining cases involve "complex" instructions.
 983   // Bails if we did not ask for the advanced tracking.
 984   if (!UseAdvancedTracking)
 985     return false;
 986   if (Def->isRegSequence())
 987     return getNextSourceFromRegSequence(SrcIdx, SrcSubReg);
 988   if (Def->isInsertSubreg())
 989     return getNextSourceFromInsertSubreg(SrcIdx, SrcSubReg);
 990   if (Def->isExtractSubreg())
 991     return getNextSourceFromExtractSubreg(SrcIdx, SrcSubReg);
 992   if (Def->isSubregToReg())
 993     return getNextSourceFromSubregToReg(SrcIdx, SrcSubReg);
 994   return false;
 995 }
 996
 997 const MachineInstr *ValueTracker::getNextSource(unsigned &SrcIdx,
 998                                                 unsigned &SrcSubReg) {
 999   // If we reach a point where we cannot move up in the use-def chain,
1000   // there is nothing we can get.
1001   if (!Def)
1002     return nullptr;
1003
1004   const MachineInstr *PrevDef = nullptr;
1005   // Try to find the next source.
1006   if (getNextSourceImpl(SrcIdx, SrcSubReg)) {
1007     // Update definition, definition index, and subregister for the
1008     // next call of getNextSource.
1009     const MachineOperand &MO = Def->getOperand(SrcIdx);
1010     assert(MO.isReg() && !MO.isDef() && "Source is invalid");
1011     // Update the current register.
1012     Reg = MO.getReg();
1013     // Update the return value before moving up in the use-def chain.
1014     PrevDef = Def;
1015     // If we can still move up in the use-def chain, move to the next
1016     // defintion.
1017     if (!TargetRegisterInfo::isPhysicalRegister(Reg)) {
1018       Def = MRI->getVRegDef(Reg);
1019       DefIdx = MRI->def_begin(Reg).getOperandNo();
1020       DefSubReg = SrcSubReg;
1021       return PrevDef;
1022     }
1023   }
1024   // If we end up here, this means we will not be able to find another source
1025   // for the next iteration.
1026   // Make sure any new call to getNextSource bails out early by cutting the
1027   // use-def chain.
1028   Def = nullptr;
1029   return PrevDef;
1030 }