llvm/lib/CodeGen/GlobalISel/Localizer.cpp

   1 //===- Localizer.cpp ---------------------- Localize some instrs -*- C++ -*-==//
   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 /// \file
   9 /// This file implements the Localizer class.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/CodeGen/GlobalISel/Localizer.h"
  13 #include "llvm/ADT/DenseMap.h"
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "llvm/Analysis/TargetTransformInfo.h"
  16 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
  17 #include "llvm/CodeGen/GlobalISel/Utils.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/TargetLowering.h"
  20 #include "llvm/InitializePasses.h"
  21 #include "llvm/Support/Debug.h"
  22
  23 #define DEBUG_TYPE "localizer"
  24
  25 using namespace llvm;
  26
  27 char Localizer::ID = 0;
  28 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
  29                       "Move/duplicate certain instructions close to their use",
  30                       false, false)
  31 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
  32 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
  33                     "Move/duplicate certain instructions close to their use",
  34                     false, false)
  35
  36 Localizer::Localizer(std::function<bool(const MachineFunction &)> F)
  37     : MachineFunctionPass(ID), DoNotRunPass(F) {}
  38
  39 Localizer::Localizer()
  40     : Localizer([](const MachineFunction &) { return false; }) {}
  41
  42 void Localizer::init(MachineFunction &MF) {
  43   MRI = &MF.getRegInfo();
  44   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
  45 }
  46
  47 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
  48   AU.addRequired<TargetTransformInfoWrapperPass>();
  49   getSelectionDAGFallbackAnalysisUsage(AU);
  50   MachineFunctionPass::getAnalysisUsage(AU);
  51 }
  52
  53 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
  54                            MachineBasicBlock *&InsertMBB) {
  55   MachineInstr &MIUse = *MOUse.getParent();
  56   InsertMBB = MIUse.getParent();
  57   if (MIUse.isPHI())
  58     InsertMBB = MIUse.getOperand(MOUse.getOperandNo() + 1).getMBB();
  59   return InsertMBB == Def.getParent();
  60 }
  61
  62 unsigned Localizer::getNumPhiUses(MachineOperand &Op) const {
  63   auto *MI = dyn_cast<GPhi>(&*Op.getParent());
  64   if (!MI)
  65     return 0;
  66
  67   Register SrcReg = Op.getReg();
  68   unsigned NumUses = 0;
  69   for (unsigned I = 0, NumVals = MI->getNumIncomingValues(); I < NumVals; ++I) {
  70     if (MI->getIncomingValue(I) == SrcReg)
  71       ++NumUses;
  72   }
  73   return NumUses;
  74 }
  75
  76 bool Localizer::localizeInterBlock(MachineFunction &MF,
  77                                    LocalizedSetVecT &LocalizedInstrs) {
  78   bool Changed = false;
  79   DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
  80
  81   // Since the IRTranslator only emits constants into the entry block, and the
  82   // rest of the GISel pipeline generally emits constants close to their users,
  83   // we only localize instructions in the entry block here. This might change if
  84   // we start doing CSE across blocks.
  85   auto &MBB = MF.front();
  86   auto &TL = *MF.getSubtarget().getTargetLowering();
  87   for (MachineInstr &MI : llvm::reverse(MBB)) {
  88     if (!TL.shouldLocalize(MI, TTI))
  89       continue;
  90     LLVM_DEBUG(dbgs() << "Should localize: " << MI);
  91     assert(MI.getDesc().getNumDefs() == 1 &&
  92            "More than one definition not supported yet");
  93     Register Reg = MI.getOperand(0).getReg();
  94     // Check if all the users of MI are local.
  95     // We are going to invalidation the list of use operands, so we
  96     // can't use range iterator.
  97     for (MachineOperand &MOUse :
  98          llvm::make_early_inc_range(MRI->use_operands(Reg))) {
  99       // Check if the use is already local.
 100       MachineBasicBlock *InsertMBB;
 101       LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
 102                  dbgs() << "Checking use: " << MIUse
 103                         << " #Opd: " << MOUse.getOperandNo() << '\n');
 104       if (isLocalUse(MOUse, MI, InsertMBB)) {
 105         // Even if we're in the same block, if the block is very large we could
 106         // still have many long live ranges. Try to do intra-block localization
 107         // too.
 108         LocalizedInstrs.insert(&MI);
 109         continue;
 110       }
 111
 112       // PHIs look like a single user but can use the same register in multiple
 113       // edges, causing remat into each predecessor. Allow this to a certain
 114       // extent.
 115       unsigned NumPhiUses = getNumPhiUses(MOUse);
 116       const unsigned PhiThreshold = 2; // FIXME: Tune this more.
 117       if (NumPhiUses > PhiThreshold)
 118         continue;
 119
 120       LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
 121       Changed = true;
 122       auto MBBAndReg = std::make_pair(InsertMBB, Reg);
 123       auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
 124       if (NewVRegIt == MBBWithLocalDef.end()) {
 125         // Create the localized instruction.
 126         MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
 127         LocalizedInstrs.insert(LocalizedMI);
 128         MachineInstr &UseMI = *MOUse.getParent();
 129         if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
 130           InsertMBB->insert(UseMI, LocalizedMI);
 131         else
 132           InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
 133                             LocalizedMI);
 134
 135         // Set a new register for the definition.
 136         Register NewReg = MRI->cloneVirtualRegister(Reg);
 137         LocalizedMI->getOperand(0).setReg(NewReg);
 138         NewVRegIt =
 139             MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
 140         LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
 141       }
 142       LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
 143                         << '\n');
 144       // Update the user reg.
 145       MOUse.setReg(NewVRegIt->second);
 146     }
 147   }
 148   return Changed;
 149 }
 150
 151 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
 152   bool Changed = false;
 153
 154   // For each already-localized instruction which has multiple users, then we
 155   // scan the block top down from the current position until we hit one of them.
 156
 157   // FIXME: Consider doing inst duplication if live ranges are very long due to
 158   // many users, but this case may be better served by regalloc improvements.
 159
 160   for (MachineInstr *MI : LocalizedInstrs) {
 161     Register Reg = MI->getOperand(0).getReg();
 162     MachineBasicBlock &MBB = *MI->getParent();
 163     // All of the user MIs of this reg.
 164     SmallPtrSet<MachineInstr *, 32> Users;
 165     for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
 166       if (!UseMI.isPHI())
 167         Users.insert(&UseMI);
 168     }
 169     MachineBasicBlock::iterator II(MI);
 170     // If all the users were PHIs then they're not going to be in our block, we
 171     // may still benefit from sinking, especially since the value might be live
 172     // across a call.
 173     if (Users.empty()) {
 174       // Make sure we don't sink in between two terminator sequences by scanning
 175       // forward, not backward.
 176       II = MBB.getFirstTerminatorForward();
 177       LLVM_DEBUG(dbgs() << "Only phi users: moving inst to end: " << *MI);
 178     } else {
 179       ++II;
 180       while (II != MBB.end() && !Users.count(&*II))
 181         ++II;
 182       assert(II != MBB.end() && "Didn't find the user in the MBB");
 183       LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *II);
 184     }
 185
 186     MI->removeFromParent();
 187     MBB.insert(II, MI);
 188     Changed = true;
 189
 190     // If the instruction (constant) being localized has single user, we can
 191     // propagate debug location from user.
 192     if (Users.size() == 1) {
 193       const auto &DefDL = MI->getDebugLoc();
 194       const auto &UserDL = (*Users.begin())->getDebugLoc();
 195
 196       if ((!DefDL || DefDL.getLine() == 0) && UserDL && UserDL.getLine() != 0) {
 197         MI->setDebugLoc(UserDL);
 198       }
 199     }
 200   }
 201   return Changed;
 202 }
 203
 204 bool Localizer::runOnMachineFunction(MachineFunction &MF) {
 205   // If the ISel pipeline failed, do not bother running that pass.
 206   if (MF.getProperties().hasProperty(
 207           MachineFunctionProperties::Property::FailedISel))
 208     return false;
 209
 210   // Don't run the pass if the target asked so.
 211   if (DoNotRunPass(MF))
 212     return false;
 213
 214   LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
 215
 216   init(MF);
 217
 218   // Keep track of the instructions we localized. We'll do a second pass of
 219   // intra-block localization to further reduce live ranges.
 220   LocalizedSetVecT LocalizedInstrs;
 221
 222   bool Changed = localizeInterBlock(MF, LocalizedInstrs);
 223   Changed |= localizeIntraBlock(LocalizedInstrs);
 224   return Changed;
 225 }