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
25using namespace llvm;
26
27char Localizer::ID = 0;
28INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
29                      "Move/duplicate certain instructions close to their use",
30                      false, false)
31INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
32INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
33                    "Move/duplicate certain instructions close to their use",
34                    false, false)
35
36Localizer::Localizer(std::function<bool(const MachineFunction &)> F)
37    : MachineFunctionPass(ID), DoNotRunPass(F) {}
38
39Localizer::Localizer()
40    : Localizer([](const MachineFunction &) { return false; }) {}
41
42void Localizer::init(MachineFunction &MF) {
43  MRI = &MF.getRegInfo();
44  TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());
45}
46
47void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {
48  AU.addRequired<TargetTransformInfoWrapperPass>();
49  getSelectionDAGFallbackAnalysisUsage(AU);
50  MachineFunctionPass::getAnalysisUsage(AU);
51}
52
53bool 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
62unsigned 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
76bool 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
151bool 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
204bool 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}
226