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/Analysis/TargetTransformInfo.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/CodeGen/MachineRegisterInfo.h"
  16 #include "llvm/Support/Debug.h"
  17
  18 #define DEBUG_TYPE "localizer"
  19
  20 using namespace llvm;
  21
  22 char Localizer::ID = 0;
  23 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
  24                       "Move/duplicate certain instructions close to their use",
  25                       false, false)
  26 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
  27 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
  28                     "Move/duplicate certain instructions close to their use",
  29                     false, false)
  30
  31 Localizer::Localizer() : MachineFunctionPass(ID) { }
  32
  33 void Localizer::init(MachineFunction &MF) {
  34   MRI = &MF.getRegInfo();
  35   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
  36 }
  37
  38 bool Localizer::shouldLocalize(const MachineInstr &MI) {
  39   // Assuming a spill and reload of a value has a cost of 1 instruction each,
  40   // this helper function computes the maximum number of uses we should consider
  41   // for remat. E.g. on arm64 global addresses take 2 insts to materialize. We
  42   // break even in terms of code size when the original MI has 2 users vs
  43   // choosing to potentially spill. Any more than 2 users we we have a net code
  44   // size increase. This doesn't take into account register pressure though.
  45   auto maxUses = [](unsigned RematCost) {
  46     // A cost of 1 means remats are basically free.
  47     if (RematCost == 1)
  48       return UINT_MAX;
  49     if (RematCost == 2)
  50       return 2U;
  51
  52     // Remat is too expensive, only sink if there's one user.
  53     if (RematCost > 2)
  54       return 1U;
  55     llvm_unreachable("Unexpected remat cost");
  56   };
  57
  58   // Helper to walk through uses and terminate if we've reached a limit. Saves
  59   // us spending time traversing uses if all we want to know is if it's >= min.
  60   auto isUsesAtMost = [&](unsigned Reg, unsigned MaxUses) {
  61     unsigned NumUses = 0;
  62     auto UI = MRI->use_instr_nodbg_begin(Reg), UE = MRI->use_instr_nodbg_end();
  63     for (; UI != UE && NumUses < MaxUses; ++UI) {
  64       NumUses++;
  65     }
  66     // If we haven't reached the end yet then there are more than MaxUses users.
  67     return UI == UE;
  68   };
  69
  70   switch (MI.getOpcode()) {
  71   default:
  72     return false;
  73   // Constants-like instructions should be close to their users.
  74   // We don't want long live-ranges for them.
  75   case TargetOpcode::G_CONSTANT:
  76   case TargetOpcode::G_FCONSTANT:
  77   case TargetOpcode::G_FRAME_INDEX:
  78   case TargetOpcode::G_INTTOPTR:
  79     return true;
  80   case TargetOpcode::G_GLOBAL_VALUE: {
  81     unsigned RematCost = TTI->getGISelRematGlobalCost();
  82     Register Reg = MI.getOperand(0).getReg();
  83     unsigned MaxUses = maxUses(RematCost);
  84     if (MaxUses == UINT_MAX)
  85       return true; // Remats are "free" so always localize.
  86     bool B = isUsesAtMost(Reg, MaxUses);
  87     return B;
  88   }
  89   }
  90 }
  91
  92 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
  93   AU.addRequired<TargetTransformInfoWrapperPass>();
  94   getSelectionDAGFallbackAnalysisUsage(AU);
  95   MachineFunctionPass::getAnalysisUsage(AU);
  96 }
  97
  98 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
  99                            MachineBasicBlock *&InsertMBB) {
 100   MachineInstr &MIUse = *MOUse.getParent();
 101   InsertMBB = MIUse.getParent();
 102   if (MIUse.isPHI())
 103     InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB();
 104   return InsertMBB == Def.getParent();
 105 }
 106
 107 bool Localizer::localizeInterBlock(MachineFunction &MF,
 108                                    LocalizedSetVecT &LocalizedInstrs) {
 109   bool Changed = false;
 110   DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
 111
 112   // Since the IRTranslator only emits constants into the entry block, and the
 113   // rest of the GISel pipeline generally emits constants close to their users,
 114   // we only localize instructions in the entry block here. This might change if
 115   // we start doing CSE across blocks.
 116   auto &MBB = MF.front();
 117   for (auto RI = MBB.rbegin(), RE = MBB.rend(); RI != RE; ++RI) {
 118     MachineInstr &MI = *RI;
 119     if (!shouldLocalize(MI))
 120       continue;
 121     LLVM_DEBUG(dbgs() << "Should localize: " << MI);
 122     assert(MI.getDesc().getNumDefs() == 1 &&
 123            "More than one definition not supported yet");
 124     Register Reg = MI.getOperand(0).getReg();
 125     // Check if all the users of MI are local.
 126     // We are going to invalidation the list of use operands, so we
 127     // can't use range iterator.
 128     for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
 129          MOIt != MOItEnd;) {
 130       MachineOperand &MOUse = *MOIt++;
 131       // Check if the use is already local.
 132       MachineBasicBlock *InsertMBB;
 133       LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();
 134                  dbgs() << "Checking use: " << MIUse
 135                         << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
 136       if (isLocalUse(MOUse, MI, InsertMBB))
 137         continue;
 138       LLVM_DEBUG(dbgs() << "Fixing non-local use\n");
 139       Changed = true;
 140       auto MBBAndReg = std::make_pair(InsertMBB, Reg);
 141       auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
 142       if (NewVRegIt == MBBWithLocalDef.end()) {
 143         // Create the localized instruction.
 144         MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
 145         LocalizedInstrs.insert(LocalizedMI);
 146         MachineInstr &UseMI = *MOUse.getParent();
 147         if (MRI->hasOneUse(Reg) && !UseMI.isPHI())
 148           InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI);
 149         else
 150           InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),
 151                             LocalizedMI);
 152
 153         // Set a new register for the definition.
 154         Register NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg));
 155         MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg));
 156         LocalizedMI->getOperand(0).setReg(NewReg);
 157         NewVRegIt =
 158             MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
 159         LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
 160       }
 161       LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)
 162                         << '\n');
 163       // Update the user reg.
 164       MOUse.setReg(NewVRegIt->second);
 165     }
 166   }
 167   return Changed;
 168 }
 169
 170 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {
 171   bool Changed = false;
 172
 173   // For each already-localized instruction which has multiple users, then we
 174   // scan the block top down from the current position until we hit one of them.
 175
 176   // FIXME: Consider doing inst duplication if live ranges are very long due to
 177   // many users, but this case may be better served by regalloc improvements.
 178
 179   for (MachineInstr *MI : LocalizedInstrs) {
 180     Register Reg = MI->getOperand(0).getReg();
 181     MachineBasicBlock &MBB = *MI->getParent();
 182     // All of the user MIs of this reg.
 183     SmallPtrSet<MachineInstr *, 32> Users;
 184     for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
 185       if (!UseMI.isPHI())
 186         Users.insert(&UseMI);
 187     }
 188     // If all the users were PHIs then they're not going to be in our block,
 189     // don't try to move this instruction.
 190     if (Users.empty())
 191       continue;
 192
 193     MachineBasicBlock::iterator II(MI);
 194     ++II;
 195     while (II != MBB.end() && !Users.count(&*II))
 196       ++II;
 197
 198     LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
 199                       << "\n");
 200     assert(II != MBB.end() && "Didn't find the user in the MBB");
 201     MI->removeFromParent();
 202     MBB.insert(II, MI);
 203     Changed = true;
 204   }
 205   return Changed;
 206 }
 207
 208 bool Localizer::runOnMachineFunction(MachineFunction &MF) {
 209   // If the ISel pipeline failed, do not bother running that pass.
 210   if (MF.getProperties().hasProperty(
 211           MachineFunctionProperties::Property::FailedISel))
 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 }