Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveRangeShrink.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===//
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
///
9
/// \file
10
/// This pass moves instructions close to the definition of its operands to
11
/// shrink live range of the def instruction. The code motion is limited within
12
/// the basic block. The moved instruction should have 1 def, and more than one
13
/// uses, all of which are the only use of the def.
14
///
15
///===---------------------------------------------------------------------===//
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/ADT/iterator_range.h"
20
#include "llvm/CodeGen/MachineBasicBlock.h"
21
#include "llvm/CodeGen/MachineFunction.h"
22
#include "llvm/CodeGen/MachineFunctionPass.h"
23
#include "llvm/CodeGen/MachineInstr.h"
24
#include "llvm/CodeGen/MachineOperand.h"
25
#include "llvm/CodeGen/MachineRegisterInfo.h"
26
#include "llvm/CodeGen/TargetRegisterInfo.h"
27
#include "llvm/Pass.h"
28
#include "llvm/Support/Debug.h"
29
#include "llvm/Support/raw_ostream.h"
30
#include <iterator>
31
#include <utility>
32
33
using namespace llvm;
34
35
#define DEBUG_TYPE "lrshrink"
36
37
STATISTIC(NumInstrsHoistedToShrinkLiveRange,
38
          "Number of insructions hoisted to shrink live range.");
39
40
namespace {
41
42
class LiveRangeShrink : public MachineFunctionPass {
43
public:
44
  static char ID;
45
46
11.3k
  LiveRangeShrink() : MachineFunctionPass(ID) {
47
11.3k
    initializeLiveRangeShrinkPass(*PassRegistry::getPassRegistry());
48
11.3k
  }
49
50
11.3k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
51
11.3k
    AU.setPreservesCFG();
52
11.3k
    MachineFunctionPass::getAnalysisUsage(AU);
53
11.3k
  }
54
55
146k
  StringRef getPassName() const override { return "Live Range Shrink"; }
56
57
  bool runOnMachineFunction(MachineFunction &MF) override;
58
};
59
60
} // end anonymous namespace
61
62
char LiveRangeShrink::ID = 0;
63
64
char &llvm::LiveRangeShrinkID = LiveRangeShrink::ID;
65
66
INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false,
67
                false)
68
69
using InstOrderMap = DenseMap<MachineInstr *, unsigned>;
70
71
/// Returns \p New if it's dominated by \p Old, otherwise return \p Old.
72
/// \p M maintains a map from instruction to its dominating order that satisfies
73
/// M[A] > M[B] guarantees that A is dominated by B.
74
/// If \p New is not in \p M, return \p Old. Otherwise if \p Old is null, return
75
/// \p New.
76
static MachineInstr *FindDominatedInstruction(MachineInstr &New,
77
                                              MachineInstr *Old,
78
386k
                                              const InstOrderMap &M) {
79
386k
  auto NewIter = M.find(&New);
80
386k
  if (NewIter == M.end())
81
13.0k
    return Old;
82
373k
  if (Old == nullptr)
83
283k
    return &New;
84
90.1k
  unsigned OrderOld = M.find(Old)->second;
85
90.1k
  unsigned OrderNew = NewIter->second;
86
90.1k
  if (OrderOld != OrderNew)
87
89.8k
    return OrderOld < OrderNew ? 
&New36.3k
:
Old53.5k
;
88
341
  // OrderOld == OrderNew, we need to iterate down from Old to see if it
89
341
  // can reach New, if yes, New is dominated by Old.
90
341
  for (MachineInstr *I = Old->getNextNode(); M.find(I)->second == OrderNew;
91
341
       
I = I->getNextNode()0
)
92
75
    if (I == &New)
93
75
      return &New;
94
341
  
return Old266
;
95
341
}
96
97
/// Builds Instruction to its dominating order number map \p M by traversing
98
/// from instruction \p Start.
99
static void BuildInstOrderMap(MachineBasicBlock::iterator Start,
100
408k
                              InstOrderMap &M) {
101
408k
  M.clear();
102
408k
  unsigned i = 0;
103
408k
  for (MachineInstr &I : make_range(Start, Start->getParent()->end()))
104
3.33M
    M[&I] = i++;
105
408k
}
106
107
135k
bool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) {
108
135k
  if (skipFunction(MF.getFunction()))
109
196
    return false;
110
135k
111
135k
  MachineRegisterInfo &MRI = MF.getRegInfo();
112
135k
113
135k
  LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
114
135k
115
135k
  InstOrderMap IOM;
116
135k
  // Map from register to instruction order (value of IOM) where the
117
135k
  // register is used last. When moving instructions up, we need to
118
135k
  // make sure all its defs (including dead def) will not cross its
119
135k
  // last use when moving up.
120
135k
  DenseMap<unsigned, std::pair<unsigned, MachineInstr *>> UseMap;
121
135k
122
397k
  for (MachineBasicBlock &MBB : MF) {
123
397k
    if (MBB.empty())
124
4.02k
      continue;
125
393k
    bool SawStore = false;
126
393k
    BuildInstOrderMap(MBB.begin(), IOM);
127
393k
    UseMap.clear();
128
393k
129
3.56M
    for (MachineBasicBlock::iterator Next = MBB.begin(); Next != MBB.end();) {
130
3.16M
      MachineInstr &MI = *Next;
131
3.16M
      ++Next;
132
3.16M
      if (MI.isPHI() || 
MI.isDebugInstr()3.10M
)
133
65.1k
        continue;
134
3.10M
      if (MI.mayStore())
135
215k
        SawStore = true;
136
3.10M
137
3.10M
      unsigned CurrentOrder = IOM[&MI];
138
3.10M
      unsigned Barrier = 0;
139
3.10M
      MachineInstr *BarrierMI = nullptr;
140
11.9M
      for (const MachineOperand &MO : MI.operands()) {
141
11.9M
        if (!MO.isReg() || 
MO.isDebug()8.55M
)
142
3.44M
          continue;
143
8.55M
        if (MO.isUse())
144
5.06M
          UseMap[MO.getReg()] = std::make_pair(CurrentOrder, &MI);
145
3.49M
        else if (MO.isDead() && 
UseMap.count(MO.getReg())1.04M
)
146
385k
          // Barrier is the last instruction where MO get used. MI should not
147
385k
          // be moved above Barrier.
148
385k
          if (Barrier < UseMap[MO.getReg()].first) {
149
197k
            Barrier = UseMap[MO.getReg()].first;
150
197k
            BarrierMI = UseMap[MO.getReg()].second;
151
197k
          }
152
8.55M
      }
153
3.10M
154
3.10M
      if (!MI.isSafeToMove(nullptr, SawStore)) {
155
890k
        // If MI has side effects, it should become a barrier for code motion.
156
890k
        // IOM is rebuild from the next instruction to prevent later
157
890k
        // instructions from being moved before this MI.
158
890k
        if (MI.hasUnmodeledSideEffects() && 
Next != MBB.end()23.3k
) {
159
15.5k
          BuildInstOrderMap(Next, IOM);
160
15.5k
          SawStore = false;
161
15.5k
        }
162
890k
        continue;
163
890k
      }
164
2.21M
165
2.21M
      const MachineOperand *DefMO = nullptr;
166
2.21M
      MachineInstr *Insert = nullptr;
167
2.21M
168
2.21M
      // Number of live-ranges that will be shortened. We do not count
169
2.21M
      // live-ranges that are defined by a COPY as it could be coalesced later.
170
2.21M
      unsigned NumEligibleUse = 0;
171
2.21M
172
6.13M
      for (const MachineOperand &MO : MI.operands()) {
173
6.13M
        if (!MO.isReg() || 
MO.isDead()4.86M
||
MO.isDebug()3.95M
)
174
2.18M
          continue;
175
3.95M
        unsigned Reg = MO.getReg();
176
3.95M
        // Do not move the instruction if it def/uses a physical register,
177
3.95M
        // unless it is a constant physical register or a noreg.
178
3.95M
        if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
179
1.42M
          if (!Reg || 
MRI.isConstantPhysReg(Reg)1.08M
)
180
430k
            continue;
181
996k
          Insert = nullptr;
182
996k
          break;
183
996k
        }
184
2.52M
        if (MO.isDef()) {
185
1.40M
          // Do not move if there is more than one def.
186
1.40M
          if (DefMO) {
187
579
            Insert = nullptr;
188
579
            break;
189
579
          }
190
1.40M
          DefMO = &MO;
191
1.40M
        } else 
if (1.12M
MRI.hasOneNonDBGUse(Reg)1.12M
&&
MRI.hasOneDef(Reg)626k
&&
DefMO626k
&&
192
1.12M
                   MRI.getRegClass(DefMO->getReg()) ==
193
598k
                       MRI.getRegClass(MO.getReg())) {
194
386k
          // The heuristic does not handle different register classes yet
195
386k
          // (registers of different sizes, looser/tighter constraints). This
196
386k
          // is because it needs more accurate model to handle register
197
386k
          // pressure correctly.
198
386k
          MachineInstr &DefInstr = *MRI.def_instr_begin(Reg);
199
386k
          if (!DefInstr.isCopy())
200
263k
            NumEligibleUse++;
201
386k
          Insert = FindDominatedInstruction(DefInstr, Insert, IOM);
202
737k
        } else {
203
737k
          Insert = nullptr;
204
737k
          break;
205
737k
        }
206
2.52M
      }
207
2.21M
208
2.21M
      // If Barrier equals IOM[I], traverse forward to find if BarrierMI is
209
2.21M
      // after Insert, if yes, then we should not hoist.
210
2.24M
      for (MachineInstr *I = Insert; I && 
IOM[I] == Barrier213k
;
211
2.21M
           
I = I->getNextNode()28.0k
)
212
29.2k
        if (I == BarrierMI) {
213
1.20k
          Insert = nullptr;
214
1.20k
          break;
215
1.20k
        }
216
2.21M
      // Move the instruction when # of shrunk live range > 1.
217
2.21M
      if (DefMO && 
Insert1.40M
&&
NumEligibleUse > 1184k
&&
Barrier <= IOM[Insert]49.8k
) {
218
49.7k
        MachineBasicBlock::iterator I = std::next(Insert->getIterator());
219
49.7k
        // Skip all the PHI and debug instructions.
220
49.8k
        while (I != MBB.end() && (I->isPHI() || 
I->isDebugInstr()49.7k
))
221
96
          I = std::next(I);
222
49.7k
        if (I == MI.getIterator())
223
47.4k
          continue;
224
2.38k
225
2.38k
        // Update the dominator order to be the same as the insertion point.
226
2.38k
        // We do this to maintain a non-decreasing order without need to update
227
2.38k
        // all instruction orders after the insertion point.
228
2.38k
        unsigned NewOrder = IOM[&*I];
229
2.38k
        IOM[&MI] = NewOrder;
230
2.38k
        NumInstrsHoistedToShrinkLiveRange++;
231
2.38k
232
2.38k
        // Find MI's debug value following MI.
233
2.38k
        MachineBasicBlock::iterator EndIter = std::next(MI.getIterator());
234
2.38k
        if (MI.getOperand(0).isReg())
235
2.38k
          
for (; 2.38k
EndIter != MBB.end() &&
EndIter->isDebugValue()2.38k
&&
236
2.38k
                 
EndIter->getOperand(0).isReg()2
&&
237
2.38k
                 
EndIter->getOperand(0).getReg() == MI.getOperand(0).getReg()2
;
238
2.38k
               
++EndIter, ++Next2
)
239
2
            IOM[&*EndIter] = NewOrder;
240
2.38k
        MBB.splice(I, &MBB, MI.getIterator(), EndIter);
241
2.38k
      }
242
2.21M
    }
243
393k
  }
244
135k
  return false;
245
135k
}