Coverage Report

Created: 2019-07-24 05:18

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