lib/Target/PowerPC/PPCPreEmitPeephole.cpp

   1 //===--------- PPCPreEmitPeephole.cpp - Late peephole optimizations -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // A pre-emit peephole for catching opportunities introduced by late passes such
  10 // as MachineBlockPlacement.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "PPC.h"
  15 #include "PPCInstrInfo.h"
  16 #include "PPCSubtarget.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/CodeGen/LivePhysRegs.h"
  20 #include "llvm/CodeGen/MachineBasicBlock.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Support/Debug.h"
  27
  28 using namespace llvm;
  29
  30 #define DEBUG_TYPE "ppc-pre-emit-peephole"
  31
  32 STATISTIC(NumRRConvertedInPreEmit,
  33           "Number of r+r instructions converted to r+i in pre-emit peephole");
  34 STATISTIC(NumRemovedInPreEmit,
  35           "Number of instructions deleted in pre-emit peephole");
  36 STATISTIC(NumberOfSelfCopies,
  37           "Number of self copy instructions eliminated");
  38
  39 static cl::opt<bool>
  40 RunPreEmitPeephole("ppc-late-peephole", cl::Hidden, cl::init(true),
  41                    cl::desc("Run pre-emit peephole optimizations."));
  42
  43 namespace {
  44   class PPCPreEmitPeephole : public MachineFunctionPass {
  45   public:
  46     static char ID;
  47     PPCPreEmitPeephole() : MachineFunctionPass(ID) {
  48       initializePPCPreEmitPeepholePass(*PassRegistry::getPassRegistry());
  49     }
  50
  51     void getAnalysisUsage(AnalysisUsage &AU) const override {
  52       MachineFunctionPass::getAnalysisUsage(AU);
  53     }
  54
  55     MachineFunctionProperties getRequiredProperties() const override {
  56       return MachineFunctionProperties().set(
  57           MachineFunctionProperties::Property::NoVRegs);
  58     }
  59
  60     // This function removes any redundant load immediates. It has two level
  61     // loops - The outer loop finds the load immediates BBI that could be used
  62     // to replace following redundancy. The inner loop scans instructions that
  63     // after BBI to find redundancy and update kill/dead flags accordingly. If
  64     // AfterBBI is the same as BBI, it is redundant, otherwise any instructions
  65     // that modify the def register of BBI would break the scanning.
  66     // DeadOrKillToUnset is a pointer to the previous operand that had the
  67     // kill/dead flag set. It keeps track of the def register of BBI, the use
  68     // registers of AfterBBIs and the def registers of AfterBBIs.
  69     bool removeRedundantLIs(MachineBasicBlock &MBB,
  70                             const TargetRegisterInfo *TRI) {
  71       LLVM_DEBUG(dbgs() << "Remove redundant load immediates from MBB:\n";
  72                  MBB.dump(); dbgs() << "\n");
  73
  74       DenseSet<MachineInstr *> InstrsToErase;
  75       for (auto BBI = MBB.instr_begin(); BBI != MBB.instr_end(); ++BBI) {
  76         // Skip load immediate that is marked to be erased later because it
  77         // cannot be used to replace any other instructions.
  78         if (InstrsToErase.find(&*BBI) != InstrsToErase.end())
  79           continue;
  80         // Skip non-load immediate.
  81         unsigned Opc = BBI->getOpcode();
  82         if (Opc != PPC::LI && Opc != PPC::LI8 && Opc != PPC::LIS &&
  83             Opc != PPC::LIS8)
  84           continue;
  85         // Skip load immediate, where the operand is a relocation (e.g., $r3 =
  86         // LI target-flags(ppc-lo) %const.0).
  87         if (!BBI->getOperand(1).isImm())
  88           continue;
  89         assert(BBI->getOperand(0).isReg() &&
  90                "Expected a register for the first operand");
  91
  92         LLVM_DEBUG(dbgs() << "Scanning after load immediate: "; BBI->dump(););
  93
  94         Register Reg = BBI->getOperand(0).getReg();
  95         int64_t Imm = BBI->getOperand(1).getImm();
  96         MachineOperand *DeadOrKillToUnset = nullptr;
  97         if (BBI->getOperand(0).isDead()) {
  98           DeadOrKillToUnset = &BBI->getOperand(0);
  99           LLVM_DEBUG(dbgs() << " Kill flag of " << *DeadOrKillToUnset
 100                             << " from load immediate " << *BBI
 101                             << " is a unsetting candidate\n");
 102         }
 103         // This loop scans instructions after BBI to see if there is any
 104         // redundant load immediate.
 105         for (auto AfterBBI = std::next(BBI); AfterBBI != MBB.instr_end();
 106              ++AfterBBI) {
 107           // Track the operand that kill Reg. We would unset the kill flag of
 108           // the operand if there is a following redundant load immediate.
 109           int KillIdx = AfterBBI->findRegisterUseOperandIdx(Reg, true, TRI);
 110           if (KillIdx != -1) {
 111             assert(!DeadOrKillToUnset && "Shouldn't kill same register twice");
 112             DeadOrKillToUnset = &AfterBBI->getOperand(KillIdx);
 113             LLVM_DEBUG(dbgs()
 114                        << " Kill flag of " << *DeadOrKillToUnset << " from "
 115                        << *AfterBBI << " is a unsetting candidate\n");
 116           }
 117
 118           if (!AfterBBI->modifiesRegister(Reg, TRI))
 119             continue;
 120           assert(DeadOrKillToUnset &&
 121                  "Shouldn't overwrite a register before it is killed");
 122           // Finish scanning because Reg is overwritten by a non-load
 123           // instruction.
 124           if (AfterBBI->getOpcode() != Opc)
 125             break;
 126           assert(AfterBBI->getOperand(0).isReg() &&
 127                  "Expected a register for the first operand");
 128           // Finish scanning because Reg is overwritten by a relocation or a
 129           // different value.
 130           if (!AfterBBI->getOperand(1).isImm() ||
 131               AfterBBI->getOperand(1).getImm() != Imm)
 132             break;
 133
 134           // It loads same immediate value to the same Reg, which is redundant.
 135           // We would unset kill flag in previous Reg usage to extend live range
 136           // of Reg first, then remove the redundancy.
 137           LLVM_DEBUG(dbgs() << " Unset dead/kill flag of " << *DeadOrKillToUnset
 138                             << " from " << *DeadOrKillToUnset->getParent());
 139           if (DeadOrKillToUnset->isDef())
 140             DeadOrKillToUnset->setIsDead(false);
 141           else
 142             DeadOrKillToUnset->setIsKill(false);
 143           DeadOrKillToUnset =
 144               AfterBBI->findRegisterDefOperand(Reg, true, true, TRI);
 145           if (DeadOrKillToUnset)
 146             LLVM_DEBUG(dbgs()
 147                        << " Dead flag of " << *DeadOrKillToUnset << " from "
 148                        << *AfterBBI << " is a unsetting candidate\n");
 149           InstrsToErase.insert(&*AfterBBI);
 150           LLVM_DEBUG(dbgs() << " Remove redundant load immediate: ";
 151                      AfterBBI->dump());
 152         }
 153       }
 154
 155       for (MachineInstr *MI : InstrsToErase) {
 156         MI->eraseFromParent();
 157       }
 158       NumRemovedInPreEmit += InstrsToErase.size();
 159       return !InstrsToErase.empty();
 160     }
 161
 162     bool runOnMachineFunction(MachineFunction &MF) override {
 163       if (skipFunction(MF.getFunction()) || !RunPreEmitPeephole)
 164         return false;
 165       bool Changed = false;
 166       const PPCInstrInfo *TII = MF.getSubtarget<PPCSubtarget>().getInstrInfo();
 167       const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
 168       SmallVector<MachineInstr *, 4> InstrsToErase;
 169       for (MachineBasicBlock &MBB : MF) {
 170         Changed |= removeRedundantLIs(MBB, TRI);
 171         for (MachineInstr &MI : MBB) {
 172           unsigned Opc = MI.getOpcode();
 173           // Detect self copies - these can result from running AADB.
 174           if (PPCInstrInfo::isSameClassPhysRegCopy(Opc)) {
 175             const MCInstrDesc &MCID = TII->get(Opc);
 176             if (MCID.getNumOperands() == 3 &&
 177                 MI.getOperand(0).getReg() == MI.getOperand(1).getReg() &&
 178                 MI.getOperand(0).getReg() == MI.getOperand(2).getReg()) {
 179               NumberOfSelfCopies++;
 180               LLVM_DEBUG(dbgs() << "Deleting self-copy instruction: ");
 181               LLVM_DEBUG(MI.dump());
 182               InstrsToErase.push_back(&MI);
 183               continue;
 184             }
 185             else if (MCID.getNumOperands() == 2 &&
 186                      MI.getOperand(0).getReg() == MI.getOperand(1).getReg()) {
 187               NumberOfSelfCopies++;
 188               LLVM_DEBUG(dbgs() << "Deleting self-copy instruction: ");
 189               LLVM_DEBUG(MI.dump());
 190               InstrsToErase.push_back(&MI);
 191               continue;
 192             }
 193           }
 194           MachineInstr *DefMIToErase = nullptr;
 195           if (TII->convertToImmediateForm(MI, &DefMIToErase)) {
 196             Changed = true;
 197             NumRRConvertedInPreEmit++;
 198             LLVM_DEBUG(dbgs() << "Converted instruction to imm form: ");
 199             LLVM_DEBUG(MI.dump());
 200             if (DefMIToErase) {
 201               InstrsToErase.push_back(DefMIToErase);
 202             }
 203           }
 204         }
 205
 206         // Eliminate conditional branch based on a constant CR bit by
 207         // CRSET or CRUNSET. We eliminate the conditional branch or
 208         // convert it into an unconditional branch. Also, if the CR bit
 209         // is not used by other instructions, we eliminate CRSET as well.
 210         auto I = MBB.getFirstInstrTerminator();
 211         if (I == MBB.instr_end())
 212           continue;
 213         MachineInstr *Br = &*I;
 214         if (Br->getOpcode() != PPC::BC && Br->getOpcode() != PPC::BCn)
 215           continue;
 216         MachineInstr *CRSetMI = nullptr;
 217         Register CRBit = Br->getOperand(0).getReg();
 218         unsigned CRReg = getCRFromCRBit(CRBit);
 219         bool SeenUse = false;
 220         MachineBasicBlock::reverse_iterator It = Br, Er = MBB.rend();
 221         for (It++; It != Er; It++) {
 222           if (It->modifiesRegister(CRBit, TRI)) {
 223             if ((It->getOpcode() == PPC::CRUNSET ||
 224                  It->getOpcode() == PPC::CRSET) &&
 225                 It->getOperand(0).getReg() == CRBit)
 226               CRSetMI = &*It;
 227             break;
 228           }
 229           if (It->readsRegister(CRBit, TRI))
 230             SeenUse = true;
 231         }
 232         if (!CRSetMI) continue;
 233
 234         unsigned CRSetOp = CRSetMI->getOpcode();
 235         if ((Br->getOpcode() == PPC::BCn && CRSetOp == PPC::CRSET) ||
 236             (Br->getOpcode() == PPC::BC  && CRSetOp == PPC::CRUNSET)) {
 237           // Remove this branch since it cannot be taken.
 238           InstrsToErase.push_back(Br);
 239           MBB.removeSuccessor(Br->getOperand(1).getMBB());
 240         }
 241         else {
 242           // This conditional branch is always taken. So, remove all branches
 243           // and insert an unconditional branch to the destination of this.
 244           MachineBasicBlock::iterator It = Br, Er = MBB.end();
 245           for (; It != Er; It++) {
 246             if (It->isDebugInstr()) continue;
 247             assert(It->isTerminator() && "Non-terminator after a terminator");
 248             InstrsToErase.push_back(&*It);
 249           }
 250           if (!MBB.isLayoutSuccessor(Br->getOperand(1).getMBB())) {
 251             ArrayRef<MachineOperand> NoCond;
 252             TII->insertBranch(MBB, Br->getOperand(1).getMBB(), nullptr,
 253                               NoCond, Br->getDebugLoc());
 254           }
 255           for (auto &Succ : MBB.successors())
 256             if (Succ != Br->getOperand(1).getMBB()) {
 257               MBB.removeSuccessor(Succ);
 258               break;
 259             }
 260         }
 261
 262         // If the CRBit is not used by another instruction, we can eliminate
 263         // CRSET/CRUNSET instruction.
 264         if (!SeenUse) {
 265           // We need to check use of the CRBit in successors.
 266           for (auto &SuccMBB : MBB.successors())
 267             if (SuccMBB->isLiveIn(CRBit) || SuccMBB->isLiveIn(CRReg)) {
 268               SeenUse = true;
 269               break;
 270             }
 271           if (!SeenUse)
 272             InstrsToErase.push_back(CRSetMI);
 273         }
 274       }
 275       for (MachineInstr *MI : InstrsToErase) {
 276         LLVM_DEBUG(dbgs() << "PPC pre-emit peephole: erasing instruction: ");
 277         LLVM_DEBUG(MI->dump());
 278         MI->eraseFromParent();
 279         NumRemovedInPreEmit++;
 280       }
 281       return Changed;
 282     }
 283   };
 284 }
 285
 286 INITIALIZE_PASS(PPCPreEmitPeephole, DEBUG_TYPE, "PowerPC Pre-Emit Peephole",
 287                 false, false)
 288 char PPCPreEmitPeephole::ID = 0;
 289
 290 FunctionPass *llvm::createPPCPreEmitPeepholePass() {
 291   return new PPCPreEmitPeephole();
 292 }