Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/CodeGen/GlobalISel/Legalizer.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
/// \file This file implements the LegalizerHelper class to legalize individual
10
/// instructions and the LegalizePass wrapper pass for the primary
11
/// legalization.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/CodeGen/GlobalISel/Legalizer.h"
16
#include "llvm/ADT/PostOrderIterator.h"
17
#include "llvm/ADT/SetVector.h"
18
#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
19
#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
20
#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
21
#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
22
#include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
23
#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
24
#include "llvm/CodeGen/GlobalISel/Utils.h"
25
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
26
#include "llvm/CodeGen/MachineRegisterInfo.h"
27
#include "llvm/CodeGen/TargetPassConfig.h"
28
#include "llvm/CodeGen/TargetSubtargetInfo.h"
29
#include "llvm/Support/Debug.h"
30
#include "llvm/Target/TargetMachine.h"
31
32
#include <iterator>
33
34
#define DEBUG_TYPE "legalizer"
35
36
using namespace llvm;
37
38
static cl::opt<bool>
39
    EnableCSEInLegalizer("enable-cse-in-legalizer",
40
                         cl::desc("Should enable CSE in Legalizer"),
41
                         cl::Optional, cl::init(false));
42
43
char Legalizer::ID = 0;
44
102k
INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
45
102k
                      "Legalize the Machine IR a function's Machine IR", false,
46
102k
                      false)
47
102k
INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
48
102k
INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
49
102k
INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
50
                    "Legalize the Machine IR a function's Machine IR", false,
51
                    false)
52
53
7.41k
Legalizer::Legalizer() : MachineFunctionPass(ID) { }
54
55
7.34k
void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
56
7.34k
  AU.addRequired<TargetPassConfig>();
57
7.34k
  AU.addRequired<GISelCSEAnalysisWrapperPass>();
58
7.34k
  AU.addPreserved<GISelCSEAnalysisWrapperPass>();
59
7.34k
  getSelectionDAGFallbackAnalysisUsage(AU);
60
7.34k
  MachineFunctionPass::getAnalysisUsage(AU);
61
7.34k
}
62
63
239k
void Legalizer::init(MachineFunction &MF) {
64
239k
}
65
66
17.8M
static bool isArtifact(const MachineInstr &MI) {
67
17.8M
  switch (MI.getOpcode()) {
68
17.8M
  default:
69
13.8M
    return false;
70
17.8M
  case TargetOpcode::G_TRUNC:
71
3.97M
  case TargetOpcode::G_ZEXT:
72
3.97M
  case TargetOpcode::G_ANYEXT:
73
3.97M
  case TargetOpcode::G_SEXT:
74
3.97M
  case TargetOpcode::G_MERGE_VALUES:
75
3.97M
  case TargetOpcode::G_UNMERGE_VALUES:
76
3.97M
  case TargetOpcode::G_CONCAT_VECTORS:
77
3.97M
  case TargetOpcode::G_BUILD_VECTOR:
78
3.97M
  case TargetOpcode::G_EXTRACT:
79
3.97M
    return true;
80
17.8M
  }
81
17.8M
}
82
using InstListTy = GISelWorkList<256>;
83
using ArtifactListTy = GISelWorkList<128>;
84
85
namespace {
86
class LegalizerWorkListManager : public GISelChangeObserver {
87
  InstListTy &InstList;
88
  ArtifactListTy &ArtifactList;
89
#ifndef NDEBUG
90
  SmallVector<MachineInstr *, 4> NewMIs;
91
#endif
92
93
public:
94
  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
95
239k
      : InstList(Insts), ArtifactList(Arts) {}
96
97
6.42M
  void createdOrChangedInstr(MachineInstr &MI) {
98
6.42M
    // Only legalize pre-isel generic instructions.
99
6.42M
    // Legalization process could generate Target specific pseudo
100
6.42M
    // instructions with generic types. Don't record them
101
6.42M
    if (isPreISelGenericOpcode(MI.getOpcode())) {
102
5.60M
      if (isArtifact(MI))
103
3.54M
        ArtifactList.insert(&MI);
104
2.05M
      else
105
2.05M
        InstList.insert(&MI);
106
5.60M
    }
107
6.42M
  }
108
109
5.13M
  void createdInstr(MachineInstr &MI) override {
110
5.13M
    LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
111
5.13M
    LLVM_DEBUG(NewMIs.push_back(&MI));
112
5.13M
    createdOrChangedInstr(MI);
113
5.13M
  }
114
115
14.3M
  void printNewInstrs() {
116
14.3M
    LLVM_DEBUG({
117
14.3M
      for (const auto *MI : NewMIs)
118
14.3M
        dbgs() << ".. .. New MI: " << *MI;
119
14.3M
      NewMIs.clear();
120
14.3M
    });
121
14.3M
  }
122
123
1.61M
  void erasingInstr(MachineInstr &MI) override {
124
1.61M
    LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
125
1.61M
    InstList.remove(&MI);
126
1.61M
    ArtifactList.remove(&MI);
127
1.61M
  }
128
129
1.28M
  void changingInstr(MachineInstr &MI) override {
130
1.28M
    LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
131
1.28M
  }
132
133
1.28M
  void changedInstr(MachineInstr &MI) override {
134
1.28M
    // When insts change, we want to revisit them to legalize them again.
135
1.28M
    // We'll consider them the same as created.
136
1.28M
    LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
137
1.28M
    createdOrChangedInstr(MI);
138
1.28M
  }
139
};
140
} // namespace
141
142
240k
bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
143
240k
  // If the ISel pipeline failed, do not bother running that pass.
144
240k
  if (MF.getProperties().hasProperty(
145
240k
          MachineFunctionProperties::Property::FailedISel))
146
247
    return false;
147
239k
  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
148
239k
  init(MF);
149
239k
  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
150
239k
  GISelCSEAnalysisWrapper &Wrapper =
151
239k
      getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
152
239k
  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
153
239k
154
239k
  const size_t NumBlocks = MF.size();
155
239k
  MachineRegisterInfo &MRI = MF.getRegInfo();
156
239k
157
239k
  // Populate Insts
158
239k
  InstListTy InstList;
159
239k
  ArtifactListTy ArtifactList;
160
239k
  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
161
239k
  // Perform legalization bottom up so we can DCE as we legalize.
162
239k
  // Traverse BB in RPOT and within each basic block, add insts top down,
163
239k
  // so when we pop_back_val in the legalization process, we traverse bottom-up.
164
1.92M
  for (auto *MBB : RPOT) {
165
1.92M
    if (MBB->empty())
166
59.1k
      continue;
167
20.4M
    
for (MachineInstr &MI : *MBB)1.86M
{
168
20.4M
      // Only legalize pre-isel generic instructions: others don't have types
169
20.4M
      // and are assumed to be legal.
170
20.4M
      if (!isPreISelGenericOpcode(MI.getOpcode()))
171
8.26M
        continue;
172
12.2M
      if (isArtifact(MI))
173
436k
        ArtifactList.deferred_insert(&MI);
174
11.7M
      else
175
11.7M
        InstList.deferred_insert(&MI);
176
12.2M
    }
177
1.86M
  }
178
239k
  ArtifactList.finalize();
179
239k
  InstList.finalize();
180
239k
  std::unique_ptr<MachineIRBuilder> MIRBuilder;
181
239k
  GISelCSEInfo *CSEInfo = nullptr;
182
239k
  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
183
239k
                       ? 
EnableCSEInLegalizer37
184
239k
                       : 
TPC.isGISelCSEEnabled()239k
;
185
239k
186
239k
  if (EnableCSE) {
187
239k
    MIRBuilder = make_unique<CSEMIRBuilder>();
188
239k
    CSEInfo = &Wrapper.get(TPC.getCSEConfig());
189
239k
    MIRBuilder->setCSEInfo(CSEInfo);
190
239k
  } else
191
36
    MIRBuilder = make_unique<MachineIRBuilder>();
192
239k
  // This observer keeps the worklist updated.
193
239k
  LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
194
239k
  // We want both WorkListObserver as well as CSEInfo to observe all changes.
195
239k
  // Use the wrapper observer.
196
239k
  GISelObserverWrapper WrapperObserver(&WorkListObserver);
197
239k
  if (EnableCSE && 
CSEInfo239k
)
198
239k
    WrapperObserver.addObserver(CSEInfo);
199
239k
  // Now install the observer as the delegate to MF.
200
239k
  // This will keep all the observers notified about new insertions/deletions.
201
239k
  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
202
239k
  LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
203
239k
  const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
204
239k
  LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
205
239k
                                           LInfo);
206
756k
  auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
207
756k
    WrapperObserver.erasingInstr(*DeadMI);
208
756k
  };
209
239k
  bool Changed = false;
210
386k
  do {
211
14.2M
    while (!InstList.empty()) {
212
13.9M
      MachineInstr &MI = *InstList.pop_back_val();
213
13.9M
      assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
214
13.9M
      if (isTriviallyDead(MI, MRI)) {
215
429
        LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
216
429
        MI.eraseFromParentAndMarkDBGValuesForRemoval();
217
429
        continue;
218
429
      }
219
13.9M
220
13.9M
      // Do the legalization for this instruction.
221
13.9M
      auto Res = Helper.legalizeInstrStep(MI);
222
13.9M
      // Error out if we couldn't legalize this instruction. We may want to
223
13.9M
      // fall back to DAG ISel instead in the future.
224
13.9M
      if (Res == LegalizerHelper::UnableToLegalize) {
225
4.72k
        Helper.MIRBuilder.stopObservingChanges();
226
4.72k
        reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
227
4.72k
                           "unable to legalize instruction", MI);
228
4.72k
        return false;
229
4.72k
      }
230
13.9M
      WorkListObserver.printNewInstrs();
231
13.9M
      Changed |= Res == LegalizerHelper::Legalized;
232
13.9M
    }
233
2.26M
    
while (381k
!ArtifactList.empty()) {
234
1.88M
      MachineInstr &MI = *ArtifactList.pop_back_val();
235
1.88M
      assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
236
1.88M
      if (isTriviallyDead(MI, MRI)) {
237
87
        LLVM_DEBUG(dbgs() << MI << "Is dead\n");
238
87
        RemoveDeadInstFromLists(&MI);
239
87
        MI.eraseFromParentAndMarkDBGValuesForRemoval();
240
87
        continue;
241
87
      }
242
1.88M
      SmallVector<MachineInstr *, 4> DeadInstructions;
243
1.88M
      if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
244
1.88M
                                            WrapperObserver)) {
245
452k
        WorkListObserver.printNewInstrs();
246
756k
        for (auto *DeadMI : DeadInstructions) {
247
756k
          LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
248
756k
          RemoveDeadInstFromLists(DeadMI);
249
756k
          DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
250
756k
        }
251
452k
        Changed = true;
252
452k
        continue;
253
452k
      }
254
1.42M
      // If this was not an artifact (that could be combined away), this might
255
1.42M
      // need special handling. Add it to InstList, so when it's processed
256
1.42M
      // there, it has to be legal or specially handled.
257
1.42M
      else
258
1.42M
        InstList.insert(&MI);
259
1.88M
    }
260
381k
  } while (!InstList.empty());
261
239k
262
239k
  // For now don't support if new blocks are inserted - we would need to fix the
263
239k
  // outerloop for that.
264
239k
  
if (235k
MF.size() != NumBlocks235k
) {
265
0
    MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
266
0
                                      MF.getFunction().getSubprogram(),
267
0
                                      /*MBB=*/nullptr);
268
0
    R << "inserting blocks is not supported yet";
269
0
    reportGISelFailure(MF, TPC, MORE, R);
270
0
    return false;
271
0
  }
272
235k
273
235k
  return Changed;
274
235k
}