Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/GlobalISel/CSEInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CSEInfo.cpp ------------------------------===//
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
//
10
//===----------------------------------------------------------------------===//
11
#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
12
#include "llvm/CodeGen/MachineRegisterInfo.h"
13
14
#define DEBUG_TYPE "cseinfo"
15
16
using namespace llvm;
17
char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
18
102k
INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
19
102k
                      "Analysis containing CSE Info", false, true)
20
102k
INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
21
                    "Analysis containing CSE Info", false, true)
22
23
/// -------- UniqueMachineInstr -------------//
24
25
12.2M
void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
26
12.2M
  GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
27
12.2M
}
28
/// -----------------------------------------
29
30
/// --------- CSEConfigFull ---------- ///
31
40.3M
bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
32
40.3M
  switch (Opc) {
33
40.3M
  default:
34
21.6M
    break;
35
40.3M
  case TargetOpcode::G_ADD:
36
18.7M
  case TargetOpcode::G_AND:
37
18.7M
  case TargetOpcode::G_ASHR:
38
18.7M
  case TargetOpcode::G_LSHR:
39
18.7M
  case TargetOpcode::G_MUL:
40
18.7M
  case TargetOpcode::G_OR:
41
18.7M
  case TargetOpcode::G_SHL:
42
18.7M
  case TargetOpcode::G_SUB:
43
18.7M
  case TargetOpcode::G_XOR:
44
18.7M
  case TargetOpcode::G_UDIV:
45
18.7M
  case TargetOpcode::G_SDIV:
46
18.7M
  case TargetOpcode::G_UREM:
47
18.7M
  case TargetOpcode::G_SREM:
48
18.7M
  case TargetOpcode::G_CONSTANT:
49
18.7M
  case TargetOpcode::G_FCONSTANT:
50
18.7M
  case TargetOpcode::G_ZEXT:
51
18.7M
  case TargetOpcode::G_SEXT:
52
18.7M
  case TargetOpcode::G_ANYEXT:
53
18.7M
  case TargetOpcode::G_UNMERGE_VALUES:
54
18.7M
  case TargetOpcode::G_TRUNC:
55
18.7M
    return true;
56
21.6M
  }
57
21.6M
  return false;
58
21.6M
}
59
60
46.9k
bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
61
46.9k
  return Opc == TargetOpcode::G_CONSTANT;
62
46.9k
}
63
64
std::unique_ptr<CSEConfigBase>
65
477k
llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) {
66
477k
  std::unique_ptr<CSEConfigBase> Config;
67
477k
  if (Level == CodeGenOpt::None)
68
3.38k
    Config = make_unique<CSEConfigConstantOnly>();
69
474k
  else
70
474k
    Config = make_unique<CSEConfigFull>();
71
477k
  return Config;
72
477k
}
73
74
/// -----------------------------------------
75
76
/// -------- GISelCSEInfo -------------//
77
477k
void GISelCSEInfo::setMF(MachineFunction &MF) {
78
477k
  this->MF = &MF;
79
477k
  this->MRI = &MF.getRegInfo();
80
477k
}
81
82
14.3k
GISelCSEInfo::~GISelCSEInfo() {}
83
84
bool GISelCSEInfo::isUniqueMachineInstValid(
85
303k
    const UniqueMachineInstr &UMI) const {
86
303k
  // Should we check here and assert that the instruction has been fully
87
303k
  // constructed?
88
303k
  // FIXME: Any other checks required to be done here? Remove this method if
89
303k
  // none.
90
303k
  return true;
91
303k
}
92
93
1.02M
void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
94
1.02M
  bool Removed = CSEMap.RemoveNode(UMI);
95
1.02M
  (void)Removed;
96
1.02M
  assert(Removed && "Invalidation called on invalid UMI");
97
1.02M
  // FIXME: Should UMI be deallocated/destroyed?
98
1.02M
}
99
100
UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
101
                                                  MachineBasicBlock *MBB,
102
6.40M
                                                  void *&InsertPos) {
103
6.40M
  auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
104
6.40M
  if (Node) {
105
303k
    if (!isUniqueMachineInstValid(*Node)) {
106
0
      invalidateUniqueMachineInstr(Node);
107
0
      return nullptr;
108
0
    }
109
303k
110
303k
    if (Node->MI->getParent() != MBB)
111
0
      return nullptr;
112
6.40M
  }
113
6.40M
  return Node;
114
6.40M
}
115
116
10.2M
void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
117
10.2M
  handleRecordedInsts();
118
10.2M
  assert(UMI);
119
10.2M
  UniqueMachineInstr *MaybeNewNode = UMI;
120
10.2M
  if (InsertPos)
121
6.10M
    CSEMap.InsertNode(UMI, InsertPos);
122
4.15M
  else
123
4.15M
    MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
124
10.2M
  if (MaybeNewNode != UMI) {
125
14.7k
    // A similar node exists in the folding set. Let's ignore this one.
126
14.7k
    return;
127
14.7k
  }
128
10.2M
  assert(InstrMapping.count(UMI->MI) == 0 &&
129
10.2M
         "This instruction should not be in the map");
130
10.2M
  InstrMapping[UMI->MI] = MaybeNewNode;
131
10.2M
}
132
133
10.2M
UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
134
10.2M
  assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
135
10.2M
  auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
136
10.2M
  return Node;
137
10.2M
}
138
139
10.2M
void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
140
10.2M
  assert(MI);
141
10.2M
  // If it exists in temporary insts, remove it.
142
10.2M
  TemporaryInsts.remove(MI);
143
10.2M
  auto *Node = getUniqueInstrForMI(MI);
144
10.2M
  insertNode(Node, InsertPos);
145
10.2M
}
146
147
MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
148
                                                    MachineBasicBlock *MBB,
149
6.40M
                                                    void *&InsertPos) {
150
6.40M
  handleRecordedInsts();
151
6.40M
  if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
152
303k
    LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
153
303k
    return const_cast<MachineInstr *>(Inst->MI);
154
303k
  }
155
6.10M
  return nullptr;
156
6.10M
}
157
158
303k
void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
159
#ifndef NDEBUG
160
  if (OpcodeHitTable.count(Opc))
161
    OpcodeHitTable[Opc] += 1;
162
  else
163
    OpcodeHitTable[Opc] = 1;
164
#endif
165
  // Else do nothing.
166
303k
}
167
168
29.0M
void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
169
29.0M
  if (shouldCSE(MI->getOpcode())) {
170
8.40M
    TemporaryInsts.insert(MI);
171
8.40M
    LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
172
8.40M
  }
173
29.0M
}
174
175
265k
void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
176
265k
  assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
177
265k
  auto *UMI = InstrMapping.lookup(MI);
178
265k
  LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
179
265k
  if (UMI) {
180
0
    // Invalidate this MI.
181
0
    invalidateUniqueMachineInstr(UMI);
182
0
    InstrMapping.erase(MI);
183
0
  }
184
265k
  /// Now insert the new instruction.
185
265k
  if (UMI) {
186
0
    /// We'll reuse the same UniqueMachineInstr to avoid the new
187
0
    /// allocation.
188
0
    *UMI = UniqueMachineInstr(MI);
189
0
    insertNode(UMI, nullptr);
190
265k
  } else {
191
265k
    /// This is a new instruction. Allocate a new UniqueMachineInstr and
192
265k
    /// Insert.
193
265k
    insertInstr(MI);
194
265k
  }
195
265k
}
196
197
4.19M
void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
198
4.19M
  if (auto *UMI = InstrMapping.lookup(MI)) {
199
1.02M
    invalidateUniqueMachineInstr(UMI);
200
1.02M
    InstrMapping.erase(MI);
201
1.02M
  }
202
4.19M
  TemporaryInsts.remove(MI);
203
4.19M
}
204
205
16.6M
void GISelCSEInfo::handleRecordedInsts() {
206
16.9M
  while (!TemporaryInsts.empty()) {
207
265k
    auto *MI = TemporaryInsts.pop_back_val();
208
265k
    handleRecordedInst(MI);
209
265k
  }
210
16.6M
}
211
212
63.6M
bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
213
63.6M
  // Only GISel opcodes are CSEable
214
63.6M
  if (!isPreISelGenericOpcode(Opc))
215
23.2M
    return false;
216
40.3M
  assert(CSEOpt.get() && "CSEConfig not set");
217
40.3M
  return CSEOpt->shouldCSEOpc(Opc);
218
40.3M
}
219
220
4.19M
void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
221
29.0M
void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
222
2.57M
void GISelCSEInfo::changingInstr(MachineInstr &MI) {
223
2.57M
  // For now, perform erase, followed by insert.
224
2.57M
  erasingInstr(MI);
225
2.57M
  createdInstr(MI);
226
2.57M
}
227
1.28M
void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
228
229
477k
void GISelCSEInfo::analyze(MachineFunction &MF) {
230
477k
  setMF(MF);
231
1.92M
  for (auto &MBB : MF) {
232
1.92M
    if (MBB.empty())
233
59.1k
      continue;
234
20.4M
    
for (MachineInstr &MI : MBB)1.86M
{
235
20.4M
      if (!shouldCSE(MI.getOpcode()))
236
16.5M
        continue;
237
3.89M
      LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
238
3.89M
      insertInstr(&MI);
239
3.89M
    }
240
1.86M
  }
241
477k
}
242
243
955k
void GISelCSEInfo::releaseMemory() {
244
955k
  print();
245
955k
  CSEMap.clear();
246
955k
  InstrMapping.clear();
247
955k
  UniqueInstrAllocator.Reset();
248
955k
  TemporaryInsts.clear();
249
955k
  CSEOpt.reset();
250
955k
  MRI = nullptr;
251
955k
  MF = nullptr;
252
#ifndef NDEBUG
253
  OpcodeHitTable.clear();
254
#endif
255
}
256
257
955k
void GISelCSEInfo::print() {
258
955k
  LLVM_DEBUG(for (auto &It
259
955k
                  : OpcodeHitTable) {
260
955k
    dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
261
955k
           << "\n";
262
955k
  };);
263
955k
}
264
/// -----------------------------------------
265
// ---- Profiling methods for FoldingSetNode --- //
266
const GISelInstProfileBuilder &
267
12.2M
GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
268
12.2M
  addNodeIDMBB(MI->getParent());
269
12.2M
  addNodeIDOpcode(MI->getOpcode());
270
12.2M
  for (auto &Op : MI->operands())
271
27.6M
    addNodeIDMachineOperand(Op);
272
12.2M
  addNodeIDFlag(MI->getFlags());
273
12.2M
  return *this;
274
12.2M
}
275
276
const GISelInstProfileBuilder &
277
18.6M
GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
278
18.6M
  ID.AddInteger(Opc);
279
18.6M
  return *this;
280
18.6M
}
281
282
const GISelInstProfileBuilder &
283
31.0M
GISelInstProfileBuilder::addNodeIDRegType(const LLT &Ty) const {
284
31.0M
  uint64_t Val = Ty.getUniqueRAWLLTData();
285
31.0M
  ID.AddInteger(Val);
286
31.0M
  return *this;
287
31.0M
}
288
289
const GISelInstProfileBuilder &
290
0
GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
291
0
  ID.AddPointer(RC);
292
0
  return *this;
293
0
}
294
295
const GISelInstProfileBuilder &
296
0
GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
297
0
  ID.AddPointer(RB);
298
0
  return *this;
299
0
}
300
301
const GISelInstProfileBuilder &
302
0
GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
303
0
  ID.AddInteger(Imm);
304
0
  return *this;
305
0
}
306
307
const GISelInstProfileBuilder &
308
12.3M
GISelInstProfileBuilder::addNodeIDRegNum(unsigned Reg) const {
309
12.3M
  ID.AddInteger(Reg);
310
12.3M
  return *this;
311
12.3M
}
312
313
const GISelInstProfileBuilder &
314
4.46M
GISelInstProfileBuilder::addNodeIDRegType(const unsigned Reg) const {
315
4.46M
  addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
316
4.46M
  return *this;
317
4.46M
}
318
319
const GISelInstProfileBuilder &
320
18.6M
GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
321
18.6M
  ID.AddPointer(MBB);
322
18.6M
  return *this;
323
18.6M
}
324
325
const GISelInstProfileBuilder &
326
13.1M
GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
327
13.1M
  if (Flag)
328
1.33M
    ID.AddInteger(Flag);
329
13.1M
  return *this;
330
13.1M
}
331
332
const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
333
35.1M
    const MachineOperand &MO) const {
334
35.1M
  if (MO.isReg()) {
335
24.6M
    unsigned Reg = MO.getReg();
336
24.6M
    if (!MO.isDef())
337
12.3M
      addNodeIDRegNum(Reg);
338
24.6M
    LLT Ty = MRI.getType(Reg);
339
24.6M
    if (Ty.isValid())
340
24.6M
      addNodeIDRegType(Ty);
341
24.6M
    auto *RB = MRI.getRegBankOrNull(Reg);
342
24.6M
    if (RB)
343
0
      addNodeIDRegType(RB);
344
24.6M
    auto *RC = MRI.getRegClassOrNull(Reg);
345
24.6M
    if (RC)
346
0
      addNodeIDRegType(RC);
347
24.6M
    assert(!MO.isImplicit() && "Unhandled case");
348
24.6M
  } else 
if (10.4M
MO.isImm()10.4M
)
349
0
    ID.AddInteger(MO.getImm());
350
10.4M
  else if (MO.isCImm())
351
10.3M
    ID.AddPointer(MO.getCImm());
352
131k
  else if (MO.isFPImm())
353
131k
    ID.AddPointer(MO.getFPImm());
354
0
  else if (MO.isPredicate())
355
0
    ID.AddInteger(MO.getPredicate());
356
0
  else
357
0
    llvm_unreachable("Unhandled operand type");
358
35.1M
  // Handle other types
359
35.1M
  return *this;
360
35.1M
}
361
362
GISelCSEInfo &
363
GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
364
477k
                             bool Recompute) {
365
477k
  if (!AlreadyComputed || 
Recompute0
) {
366
477k
    Info.setCSEConfig(std::move(CSEOpt));
367
477k
    Info.analyze(*MF);
368
477k
    AlreadyComputed = true;
369
477k
  }
370
477k
  return Info;
371
477k
}
372
14.3k
void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
373
14.3k
  AU.setPreservesAll();
374
14.3k
  MachineFunctionPass::getAnalysisUsage(AU);
375
14.3k
}
376
377
477k
bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
378
477k
  releaseMemory();
379
477k
  Wrapper.setMF(MF);
380
477k
  return false;
381
477k
}