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