Legalizer.cpp revision 360784 
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/InitializePasses.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Target/TargetMachine.h"
32
33#include <iterator>
34
35#define DEBUG_TYPE "legalizer"
36
37using namespace llvm;
38
39static cl::opt<bool>
40    EnableCSEInLegalizer("enable-cse-in-legalizer",
41                         cl::desc("Should enable CSE in Legalizer"),
42                         cl::Optional, cl::init(false));
43
44char Legalizer::ID = 0;
45INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
46                      "Legalize the Machine IR a function's Machine IR", false,
47                      false)
48INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
49INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
50INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
51                    "Legalize the Machine IR a function's Machine IR", false,
52                    false)
53
54Legalizer::Legalizer() : MachineFunctionPass(ID) { }
55
56void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
57  AU.addRequired<TargetPassConfig>();
58  AU.addRequired<GISelCSEAnalysisWrapperPass>();
59  AU.addPreserved<GISelCSEAnalysisWrapperPass>();
60  getSelectionDAGFallbackAnalysisUsage(AU);
61  MachineFunctionPass::getAnalysisUsage(AU);
62}
63
64void Legalizer::init(MachineFunction &MF) {
65}
66
67static bool isArtifact(const MachineInstr &MI) {
68  switch (MI.getOpcode()) {
69  default:
70    return false;
71  case TargetOpcode::G_TRUNC:
72  case TargetOpcode::G_ZEXT:
73  case TargetOpcode::G_ANYEXT:
74  case TargetOpcode::G_SEXT:
75  case TargetOpcode::G_MERGE_VALUES:
76  case TargetOpcode::G_UNMERGE_VALUES:
77  case TargetOpcode::G_CONCAT_VECTORS:
78  case TargetOpcode::G_BUILD_VECTOR:
79  case TargetOpcode::G_EXTRACT:
80    return true;
81  }
82}
83using InstListTy = GISelWorkList<256>;
84using ArtifactListTy = GISelWorkList<128>;
85
86namespace {
87class LegalizerWorkListManager : public GISelChangeObserver {
88  InstListTy &InstList;
89  ArtifactListTy &ArtifactList;
90#ifndef NDEBUG
91  SmallVector<MachineInstr *, 4> NewMIs;
92#endif
93
94public:
95  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
96      : InstList(Insts), ArtifactList(Arts) {}
97
98  void createdOrChangedInstr(MachineInstr &MI) {
99    // Only legalize pre-isel generic instructions.
100    // Legalization process could generate Target specific pseudo
101    // instructions with generic types. Don't record them
102    if (isPreISelGenericOpcode(MI.getOpcode())) {
103      if (isArtifact(MI))
104        ArtifactList.insert(&MI);
105      else
106        InstList.insert(&MI);
107    }
108  }
109
110  void createdInstr(MachineInstr &MI) override {
111    LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
112    LLVM_DEBUG(NewMIs.push_back(&MI));
113    createdOrChangedInstr(MI);
114  }
115
116  void printNewInstrs() {
117    LLVM_DEBUG({
118      for (const auto *MI : NewMIs)
119        dbgs() << ".. .. New MI: " << *MI;
120      NewMIs.clear();
121    });
122  }
123
124  void erasingInstr(MachineInstr &MI) override {
125    LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
126    InstList.remove(&MI);
127    ArtifactList.remove(&MI);
128  }
129
130  void changingInstr(MachineInstr &MI) override {
131    LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
132  }
133
134  void changedInstr(MachineInstr &MI) override {
135    // When insts change, we want to revisit them to legalize them again.
136    // We'll consider them the same as created.
137    LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
138    createdOrChangedInstr(MI);
139  }
140};
141} // namespace
142
143Legalizer::MFResult
144Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
145                                   ArrayRef<GISelChangeObserver *> AuxObservers,
146                                   MachineIRBuilder &MIRBuilder) {
147  MachineRegisterInfo &MRI = MF.getRegInfo();
148
149  // Populate worklists.
150  InstListTy InstList;
151  ArtifactListTy ArtifactList;
152  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
153  // Perform legalization bottom up so we can DCE as we legalize.
154  // Traverse BB in RPOT and within each basic block, add insts top down,
155  // so when we pop_back_val in the legalization process, we traverse bottom-up.
156  for (auto *MBB : RPOT) {
157    if (MBB->empty())
158      continue;
159    for (MachineInstr &MI : *MBB) {
160      // Only legalize pre-isel generic instructions: others don't have types
161      // and are assumed to be legal.
162      if (!isPreISelGenericOpcode(MI.getOpcode()))
163        continue;
164      if (isArtifact(MI))
165        ArtifactList.deferred_insert(&MI);
166      else
167        InstList.deferred_insert(&MI);
168    }
169  }
170  ArtifactList.finalize();
171  InstList.finalize();
172
173  // This observer keeps the worklists updated.
174  LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
175  // We want both WorkListObserver as well as all the auxiliary observers (e.g.
176  // CSEInfo) to observe all changes. Use the wrapper observer.
177  GISelObserverWrapper WrapperObserver(&WorkListObserver);
178  for (GISelChangeObserver *Observer : AuxObservers)
179    WrapperObserver.addObserver(Observer);
180
181  // Now install the observer as the delegate to MF.
182  // This will keep all the observers notified about new insertions/deletions.
183  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
184  LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder);
185  LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI);
186  auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
187    WrapperObserver.erasingInstr(*DeadMI);
188  };
189  bool Changed = false;
190  SmallVector<MachineInstr *, 128> RetryList;
191  do {
192    LLVM_DEBUG(dbgs() << "=== New Iteration ===\n");
193    assert(RetryList.empty() && "Expected no instructions in RetryList");
194    unsigned NumArtifacts = ArtifactList.size();
195    while (!InstList.empty()) {
196      MachineInstr &MI = *InstList.pop_back_val();
197      assert(isPreISelGenericOpcode(MI.getOpcode()) &&
198             "Expecting generic opcode");
199      if (isTriviallyDead(MI, MRI)) {
200        LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
201        MI.eraseFromParentAndMarkDBGValuesForRemoval();
202        continue;
203      }
204
205      // Do the legalization for this instruction.
206      auto Res = Helper.legalizeInstrStep(MI);
207      // Error out if we couldn't legalize this instruction. We may want to
208      // fall back to DAG ISel instead in the future.
209      if (Res == LegalizerHelper::UnableToLegalize) {
210        // Move illegal artifacts to RetryList instead of aborting because
211        // legalizing InstList may generate artifacts that allow
212        // ArtifactCombiner to combine away them.
213        if (isArtifact(MI)) {
214          LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");
215          assert(NumArtifacts == 0 &&
216                 "Artifacts are only expected in instruction list starting the "
217                 "second iteration, but each iteration starting second must "
218                 "start with an empty artifacts list");
219          (void)NumArtifacts;
220          RetryList.push_back(&MI);
221          continue;
222        }
223        Helper.MIRBuilder.stopObservingChanges();
224        return {Changed, &MI};
225      }
226      WorkListObserver.printNewInstrs();
227      Changed |= Res == LegalizerHelper::Legalized;
228    }
229    // Try to combine the instructions in RetryList again if there
230    // are new artifacts. If not, stop legalizing.
231    if (!RetryList.empty()) {
232      if (!ArtifactList.empty()) {
233        while (!RetryList.empty())
234          ArtifactList.insert(RetryList.pop_back_val());
235      } else {
236        LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
237        Helper.MIRBuilder.stopObservingChanges();
238        return {Changed, RetryList.front()};
239      }
240    }
241    while (!ArtifactList.empty()) {
242      MachineInstr &MI = *ArtifactList.pop_back_val();
243      assert(isPreISelGenericOpcode(MI.getOpcode()) &&
244             "Expecting generic opcode");
245      if (isTriviallyDead(MI, MRI)) {
246        LLVM_DEBUG(dbgs() << MI << "Is dead\n");
247        RemoveDeadInstFromLists(&MI);
248        MI.eraseFromParentAndMarkDBGValuesForRemoval();
249        continue;
250      }
251      SmallVector<MachineInstr *, 4> DeadInstructions;
252      LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
253      if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
254                                            WrapperObserver)) {
255        WorkListObserver.printNewInstrs();
256        for (auto *DeadMI : DeadInstructions) {
257          LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
258          RemoveDeadInstFromLists(DeadMI);
259          DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
260        }
261        Changed = true;
262        continue;
263      }
264      // If this was not an artifact (that could be combined away), this might
265      // need special handling. Add it to InstList, so when it's processed
266      // there, it has to be legal or specially handled.
267      else {
268        LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");
269        InstList.insert(&MI);
270      }
271    }
272  } while (!InstList.empty());
273
274  return {Changed, /*FailedOn*/ nullptr};
275}
276
277bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
278  // If the ISel pipeline failed, do not bother running that pass.
279  if (MF.getProperties().hasProperty(
280          MachineFunctionProperties::Property::FailedISel))
281    return false;
282  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
283  init(MF);
284  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
285  GISelCSEAnalysisWrapper &Wrapper =
286      getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
287  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
288
289  const size_t NumBlocks = MF.size();
290
291  std::unique_ptr<MachineIRBuilder> MIRBuilder;
292  GISelCSEInfo *CSEInfo = nullptr;
293  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
294                       ? EnableCSEInLegalizer
295                       : TPC.isGISelCSEEnabled();
296  if (EnableCSE) {
297    MIRBuilder = std::make_unique<CSEMIRBuilder>();
298    CSEInfo = &Wrapper.get(TPC.getCSEConfig());
299    MIRBuilder->setCSEInfo(CSEInfo);
300  } else
301    MIRBuilder = std::make_unique<MachineIRBuilder>();
302
303  SmallVector<GISelChangeObserver *, 1> AuxObservers;
304  if (EnableCSE && CSEInfo) {
305    // We want CSEInfo in addition to WorkListObserver to observe all changes.
306    AuxObservers.push_back(CSEInfo);
307  }
308
309  const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
310  MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, *MIRBuilder);
311
312  if (Result.FailedOn) {
313    reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
314                       "unable to legalize instruction", *Result.FailedOn);
315    return false;
316  }
317  // For now don't support if new blocks are inserted - we would need to fix the
318  // outer loop for that.
319  if (MF.size() != NumBlocks) {
320    MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
321                                      MF.getFunction().getSubprogram(),
322                                      /*MBB=*/nullptr);
323    R << "inserting blocks is not supported yet";
324    reportGISelFailure(MF, TPC, MORE, R);
325    return false;
326  }
327  return Result.Changed;
328}
329