Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - MIBuilder--*- 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 CSEMIRBuilder class which CSEs as it builds
10
/// instructions.
11
//===----------------------------------------------------------------------===//
12
//
13
14
#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
15
#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
16
17
using namespace llvm;
18
19
bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
20
303k
                              MachineBasicBlock::const_iterator B) const {
21
303k
  auto MBBEnd = getMBB().end();
22
303k
  if (B == MBBEnd)
23
268k
    return true;
24
35.1k
  assert(A->getParent() == B->getParent() &&
25
35.1k
         "Iterators should be in same block");
26
35.1k
  const MachineBasicBlock *BBA = A->getParent();
27
35.1k
  MachineBasicBlock::const_iterator I = BBA->begin();
28
1.80M
  for (; &*I != A && 
&*I != B1.78M
;
++I1.76M
)
29
1.76M
    ;
30
35.1k
  return &*I == A;
31
35.1k
}
32
33
MachineInstrBuilder
34
CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
35
6.40M
                                       void *&NodeInsertPos) {
36
6.40M
  GISelCSEInfo *CSEInfo = getCSEInfo();
37
6.40M
  assert(CSEInfo && "Can't get here without setting CSEInfo");
38
6.40M
  MachineBasicBlock *CurMBB = &getMBB();
39
6.40M
  MachineInstr *MI =
40
6.40M
      CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
41
6.40M
  if (MI) {
42
303k
    CSEInfo->countOpcodeHit(MI->getOpcode());
43
303k
    auto CurrPos = getInsertPt();
44
303k
    if (!dominates(MI, CurrPos))
45
17.0k
      CurMBB->splice(CurrPos, CurMBB, MI);
46
303k
    return MachineInstrBuilder(getMF(), MI);
47
303k
  }
48
6.10M
  return MachineInstrBuilder();
49
6.10M
}
50
51
14.0M
bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
52
14.0M
  const GISelCSEInfo *CSEInfo = getCSEInfo();
53
14.0M
  if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
54
7.66M
    return false;
55
6.41M
  return true;
56
6.41M
}
57
58
void CSEMIRBuilder::profileDstOp(const DstOp &Op,
59
6.40M
                                 GISelInstProfileBuilder &B) const {
60
6.40M
  switch (Op.getDstOpKind()) {
61
6.40M
  case DstOp::DstType::Ty_RC:
62
0
    B.addNodeIDRegType(Op.getRegClass());
63
0
    break;
64
6.40M
  default:
65
6.40M
    B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
66
6.40M
    break;
67
6.40M
  }
68
6.40M
}
69
70
void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
71
4.46M
                                 GISelInstProfileBuilder &B) const {
72
4.46M
  switch (Op.getSrcOpKind()) {
73
4.46M
  case SrcOp::SrcType::Ty_Predicate:
74
0
    B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
75
0
    break;
76
4.46M
  default:
77
4.46M
    B.addNodeIDRegType(Op.getReg());
78
4.46M
    break;
79
4.46M
  }
80
4.46M
}
81
82
void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
83
6.40M
                                     unsigned Opc) const {
84
6.40M
  // First add the MBB (Local CSE).
85
6.40M
  B.addNodeIDMBB(&getMBB());
86
6.40M
  // Then add the opcode.
87
6.40M
  B.addNodeIDOpcode(Opc);
88
6.40M
}
89
90
void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
91
                                      ArrayRef<SrcOp> SrcOps,
92
                                      Optional<unsigned> Flags,
93
3.37M
                                      GISelInstProfileBuilder &B) const {
94
3.37M
95
3.37M
  profileMBBOpcode(B, Opc);
96
3.37M
  // Then add the DstOps.
97
3.37M
  profileDstOps(DstOps, B);
98
3.37M
  // Then add the SrcOps.
99
3.37M
  profileSrcOps(SrcOps, B);
100
3.37M
  // Add Flags if passed in.
101
3.37M
  if (Flags)
102
843k
    B.addNodeIDFlag(*Flags);
103
3.37M
}
104
105
MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
106
6.10M
                                             void *NodeInsertPos) {
107
6.10M
  assert(canPerformCSEForOpc(MIB->getOpcode()) &&
108
6.10M
         "Attempting to CSE illegal op");
109
6.10M
  MachineInstr *MIBInstr = MIB;
110
6.10M
  getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
111
6.10M
  return MIB;
112
6.10M
}
113
114
11.0M
bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
115
11.0M
  if (DstOps.size() == 1)
116
11.0M
    return true; // always possible to emit copy to just 1 vreg.
117
4.52k
118
4.55k
  
return std::all_of(DstOps.begin(), DstOps.end(), [](const DstOp &Op) 4.52k
{
119
4.55k
    DstOp::DstType DT = Op.getDstOpKind();
120
4.55k
    return DT == DstOp::DstType::Ty_LLT || 
DT == DstOp::DstType::Ty_RC4.49k
;
121
4.55k
  });
122
4.52k
}
123
124
MachineInstrBuilder
125
CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
126
303k
                                        MachineInstrBuilder &MIB) {
127
303k
  assert(checkCopyToDefsPossible(DstOps) &&
128
303k
         "Impossible return a single MIB with copies to multiple defs");
129
303k
  if (DstOps.size() == 1) {
130
303k
    const DstOp &Op = DstOps[0];
131
303k
    if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
132
84.8k
      return buildCopy(Op.getReg(), MIB->getOperand(0).getReg());
133
219k
  }
134
219k
  return MIB;
135
219k
}
136
137
MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
138
                                              ArrayRef<DstOp> DstOps,
139
                                              ArrayRef<SrcOp> SrcOps,
140
11.0M
                                              Optional<unsigned> Flag) {
141
11.0M
  switch (Opc) {
142
11.0M
  default:
143
9.94M
    break;
144
11.0M
  case TargetOpcode::G_ADD:
145
1.09M
  case TargetOpcode::G_AND:
146
1.09M
  case TargetOpcode::G_ASHR:
147
1.09M
  case TargetOpcode::G_LSHR:
148
1.09M
  case TargetOpcode::G_MUL:
149
1.09M
  case TargetOpcode::G_OR:
150
1.09M
  case TargetOpcode::G_SHL:
151
1.09M
  case TargetOpcode::G_SUB:
152
1.09M
  case TargetOpcode::G_XOR:
153
1.09M
  case TargetOpcode::G_UDIV:
154
1.09M
  case TargetOpcode::G_SDIV:
155
1.09M
  case TargetOpcode::G_UREM:
156
1.09M
  case TargetOpcode::G_SREM: {
157
1.09M
    // Try to constant fold these.
158
1.09M
    assert(SrcOps.size() == 2 && "Invalid sources");
159
1.09M
    assert(DstOps.size() == 1 && "Invalid dsts");
160
1.09M
    if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(),
161
282
                                                SrcOps[1].getReg(), *getMRI()))
162
282
      return buildConstant(DstOps[0], Cst->getSExtValue());
163
1.09M
    break;
164
1.09M
  }
165
11.0M
  }
166
11.0M
  bool CanCopy = checkCopyToDefsPossible(DstOps);
167
11.0M
  if (!canPerformCSEForOpc(Opc))
168
7.66M
    return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
169
3.37M
  // If we can CSE this instruction, but involves generating copies to multiple
170
3.37M
  // regs, give up. This frequently happens to UNMERGEs.
171
3.37M
  if (!CanCopy) {
172
3.31k
    auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
173
3.31k
    // CSEInfo would have tracked this instruction. Remove it from the temporary
174
3.31k
    // insts.
175
3.31k
    getCSEInfo()->handleRemoveInst(&*MIB);
176
3.31k
    return MIB;
177
3.31k
  }
178
3.37M
  FoldingSetNodeID ID;
179
3.37M
  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
180
3.37M
  void *InsertPos = nullptr;
181
3.37M
  profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
182
3.37M
  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
183
3.37M
  if (MIB) {
184
75.5k
    // Handle generating copies here.
185
75.5k
    return generateCopiesIfRequired(DstOps, MIB);
186
75.5k
  }
187
3.29M
  // This instruction does not exist in the CSEInfo. Build it and CSE it.
188
3.29M
  MachineInstrBuilder NewMIB =
189
3.29M
      MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
190
3.29M
  return memoizeMI(NewMIB, InsertPos);
191
3.29M
}
192
193
MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
194
3.00M
                                                 const ConstantInt &Val) {
195
3.00M
  constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
196
3.00M
  if (!canPerformCSEForOpc(Opc))
197
0
    return MachineIRBuilder::buildConstant(Res, Val);
198
3.00M
199
3.00M
  // For vectors, CSE the element only for now.
200
3.00M
  LLT Ty = Res.getLLTTy(*getMRI());
201
3.00M
  if (Ty.isVector())
202
123
    return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
203
3.00M
204
3.00M
  FoldingSetNodeID ID;
205
3.00M
  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
206
3.00M
  void *InsertPos = nullptr;
207
3.00M
  profileMBBOpcode(ProfBuilder, Opc);
208
3.00M
  profileDstOp(Res, ProfBuilder);
209
3.00M
  ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
210
3.00M
  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
211
3.00M
  if (MIB) {
212
228k
    // Handle generating copies here.
213
228k
    return generateCopiesIfRequired({Res}, MIB);
214
228k
  }
215
2.78M
216
2.78M
  MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
217
2.78M
  return memoizeMI(NewMIB, InsertPos);
218
2.78M
}
219
220
MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
221
28.5k
                                                  const ConstantFP &Val) {
222
28.5k
  constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
223
28.5k
  if (!canPerformCSEForOpc(Opc))
224
63
    return MachineIRBuilder::buildFConstant(Res, Val);
225
28.4k
226
28.4k
  // For vectors, CSE the element only for now.
227
28.4k
  LLT Ty = Res.getLLTTy(*getMRI());
228
28.4k
  if (Ty.isVector())
229
1
    return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
230
28.4k
231
28.4k
  FoldingSetNodeID ID;
232
28.4k
  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
233
28.4k
  void *InsertPos = nullptr;
234
28.4k
  profileMBBOpcode(ProfBuilder, Opc);
235
28.4k
  profileDstOp(Res, ProfBuilder);
236
28.4k
  ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
237
28.4k
  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
238
28.4k
  if (MIB) {
239
28
    // Handle generating copies here.
240
28
    return generateCopiesIfRequired({Res}, MIB);
241
28
  }
242
28.4k
  MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
243
28.4k
  return memoizeMI(NewMIB, InsertPos);
244
28.4k
}