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/Analysis/OptimizationRemarkEmitter.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/LostDebugLocObserver.h"
25 #include "llvm/CodeGen/GlobalISel/Utils.h"
26 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.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/Support/Error.h"
32 
33 #define DEBUG_TYPE "legalizer"
34 
35 using namespace llvm;
36 
37 static cl::opt<bool>
38     EnableCSEInLegalizer("enable-cse-in-legalizer",
39                          cl::desc("Should enable CSE in Legalizer"),
40                          cl::Optional, cl::init(false));
41 
42 // This is a temporary hack, should be removed soon.
43 static cl::opt<bool> AllowGInsertAsArtifact(
44     "allow-ginsert-as-artifact",
45     cl::desc("Allow G_INSERT to be considered an artifact. Hack around AMDGPU "
46              "test infinite loops."),
47     cl::Optional, cl::init(true));
48 
49 enum class DebugLocVerifyLevel {
50   None,
51   Legalizations,
52   LegalizationsAndArtifactCombiners,
53 };
54 #ifndef NDEBUG
55 static cl::opt<DebugLocVerifyLevel> VerifyDebugLocs(
56     "verify-legalizer-debug-locs",
57     cl::desc("Verify that debug locations are handled"),
58     cl::values(
59         clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"),
60         clEnumValN(DebugLocVerifyLevel::Legalizations, "legalizations",
61                    "Verify legalizations"),
62         clEnumValN(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners,
63                    "legalizations+artifactcombiners",
64                    "Verify legalizations and artifact combines")),
65     cl::init(DebugLocVerifyLevel::Legalizations));
66 #else
67 // Always disable it for release builds by preventing the observer from being
68 // installed.
69 static const DebugLocVerifyLevel VerifyDebugLocs = DebugLocVerifyLevel::None;
70 #endif
71 
72 char Legalizer::ID = 0;
73 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
74                       "Legalize the Machine IR a function's Machine IR", false,
75                       false)
76 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
77 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
78 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
79                     "Legalize the Machine IR a function's Machine IR", false,
80                     false)
81 
82 Legalizer::Legalizer() : MachineFunctionPass(ID) { }
83 
84 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
85   AU.addRequired<TargetPassConfig>();
86   AU.addRequired<GISelCSEAnalysisWrapperPass>();
87   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
88   getSelectionDAGFallbackAnalysisUsage(AU);
89   MachineFunctionPass::getAnalysisUsage(AU);
90 }
91 
92 void Legalizer::init(MachineFunction &MF) {
93 }
94 
95 static bool isArtifact(const MachineInstr &MI) {
96   switch (MI.getOpcode()) {
97   default:
98     return false;
99   case TargetOpcode::G_TRUNC:
100   case TargetOpcode::G_ZEXT:
101   case TargetOpcode::G_ANYEXT:
102   case TargetOpcode::G_SEXT:
103   case TargetOpcode::G_MERGE_VALUES:
104   case TargetOpcode::G_UNMERGE_VALUES:
105   case TargetOpcode::G_CONCAT_VECTORS:
106   case TargetOpcode::G_BUILD_VECTOR:
107   case TargetOpcode::G_EXTRACT:
108     return true;
109   case TargetOpcode::G_INSERT:
110     return AllowGInsertAsArtifact;
111   }
112 }
113 using InstListTy = GISelWorkList<256>;
114 using ArtifactListTy = GISelWorkList<128>;
115 
116 namespace {
117 class LegalizerWorkListManager : public GISelChangeObserver {
118   InstListTy &InstList;
119   ArtifactListTy &ArtifactList;
120 #ifndef NDEBUG
121   SmallVector<MachineInstr *, 4> NewMIs;
122 #endif
123 
124 public:
125   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
126       : InstList(Insts), ArtifactList(Arts) {}
127 
128   void createdOrChangedInstr(MachineInstr &MI) {
129     // Only legalize pre-isel generic instructions.
130     // Legalization process could generate Target specific pseudo
131     // instructions with generic types. Don't record them
132     if (isPreISelGenericOpcode(MI.getOpcode())) {
133       if (isArtifact(MI))
134         ArtifactList.insert(&MI);
135       else
136         InstList.insert(&MI);
137     }
138   }
139 
140   void createdInstr(MachineInstr &MI) override {
141     LLVM_DEBUG(NewMIs.push_back(&MI));
142     createdOrChangedInstr(MI);
143   }
144 
145   void printNewInstrs() {
146     LLVM_DEBUG({
147       for (const auto *MI : NewMIs)
148         dbgs() << ".. .. New MI: " << *MI;
149       NewMIs.clear();
150     });
151   }
152 
153   void erasingInstr(MachineInstr &MI) override {
154     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
155     InstList.remove(&MI);
156     ArtifactList.remove(&MI);
157   }
158 
159   void changingInstr(MachineInstr &MI) override {
160     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
161   }
162 
163   void changedInstr(MachineInstr &MI) override {
164     // When insts change, we want to revisit them to legalize them again.
165     // We'll consider them the same as created.
166     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
167     createdOrChangedInstr(MI);
168   }
169 };
170 } // namespace
171 
172 Legalizer::MFResult
173 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
174                                    ArrayRef<GISelChangeObserver *> AuxObservers,
175                                    LostDebugLocObserver &LocObserver,
176                                    MachineIRBuilder &MIRBuilder) {
177   MIRBuilder.setMF(MF);
178   MachineRegisterInfo &MRI = MF.getRegInfo();
179 
180   // Populate worklists.
181   InstListTy InstList;
182   ArtifactListTy ArtifactList;
183   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
184   // Perform legalization bottom up so we can DCE as we legalize.
185   // Traverse BB in RPOT and within each basic block, add insts top down,
186   // so when we pop_back_val in the legalization process, we traverse bottom-up.
187   for (auto *MBB : RPOT) {
188     if (MBB->empty())
189       continue;
190     for (MachineInstr &MI : *MBB) {
191       // Only legalize pre-isel generic instructions: others don't have types
192       // and are assumed to be legal.
193       if (!isPreISelGenericOpcode(MI.getOpcode()))
194         continue;
195       if (isArtifact(MI))
196         ArtifactList.deferred_insert(&MI);
197       else
198         InstList.deferred_insert(&MI);
199     }
200   }
201   ArtifactList.finalize();
202   InstList.finalize();
203 
204   // This observer keeps the worklists updated.
205   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
206   // We want both WorkListObserver as well as all the auxiliary observers (e.g.
207   // CSEInfo) to observe all changes. Use the wrapper observer.
208   GISelObserverWrapper WrapperObserver(&WorkListObserver);
209   for (GISelChangeObserver *Observer : AuxObservers)
210     WrapperObserver.addObserver(Observer);
211 
212   // Now install the observer as the delegate to MF.
213   // This will keep all the observers notified about new insertions/deletions.
214   RAIIMFObsDelInstaller Installer(MF, WrapperObserver);
215   LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder);
216   LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI);
217   bool Changed = false;
218   SmallVector<MachineInstr *, 128> RetryList;
219   do {
220     LLVM_DEBUG(dbgs() << "=== New Iteration ===\n");
221     assert(RetryList.empty() && "Expected no instructions in RetryList");
222     unsigned NumArtifacts = ArtifactList.size();
223     while (!InstList.empty()) {
224       MachineInstr &MI = *InstList.pop_back_val();
225       assert(isPreISelGenericOpcode(MI.getOpcode()) &&
226              "Expecting generic opcode");
227       if (isTriviallyDead(MI, MRI)) {
228         salvageDebugInfo(MRI, MI);
229         eraseInstr(MI, MRI, &LocObserver);
230         continue;
231       }
232 
233       // Do the legalization for this instruction.
234       auto Res = Helper.legalizeInstrStep(MI, LocObserver);
235       // Error out if we couldn't legalize this instruction. We may want to
236       // fall back to DAG ISel instead in the future.
237       if (Res == LegalizerHelper::UnableToLegalize) {
238         // Move illegal artifacts to RetryList instead of aborting because
239         // legalizing InstList may generate artifacts that allow
240         // ArtifactCombiner to combine away them.
241         if (isArtifact(MI)) {
242           LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");
243           assert(NumArtifacts == 0 &&
244                  "Artifacts are only expected in instruction list starting the "
245                  "second iteration, but each iteration starting second must "
246                  "start with an empty artifacts list");
247           (void)NumArtifacts;
248           RetryList.push_back(&MI);
249           continue;
250         }
251         Helper.MIRBuilder.stopObservingChanges();
252         return {Changed, &MI};
253       }
254       WorkListObserver.printNewInstrs();
255       LocObserver.checkpoint();
256       Changed |= Res == LegalizerHelper::Legalized;
257     }
258     // Try to combine the instructions in RetryList again if there
259     // are new artifacts. If not, stop legalizing.
260     if (!RetryList.empty()) {
261       if (!ArtifactList.empty()) {
262         while (!RetryList.empty())
263           ArtifactList.insert(RetryList.pop_back_val());
264       } else {
265         LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
266         Helper.MIRBuilder.stopObservingChanges();
267         return {Changed, RetryList.front()};
268       }
269     }
270     LocObserver.checkpoint();
271     while (!ArtifactList.empty()) {
272       MachineInstr &MI = *ArtifactList.pop_back_val();
273       assert(isPreISelGenericOpcode(MI.getOpcode()) &&
274              "Expecting generic opcode");
275       if (isTriviallyDead(MI, MRI)) {
276         salvageDebugInfo(MRI, MI);
277         eraseInstr(MI, MRI, &LocObserver);
278         continue;
279       }
280       SmallVector<MachineInstr *, 4> DeadInstructions;
281       LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
282       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
283                                             WrapperObserver)) {
284         WorkListObserver.printNewInstrs();
285         eraseInstrs(DeadInstructions, MRI, &LocObserver);
286         LocObserver.checkpoint(
287             VerifyDebugLocs ==
288             DebugLocVerifyLevel::LegalizationsAndArtifactCombiners);
289         Changed = true;
290         continue;
291       }
292       // If this was not an artifact (that could be combined away), this might
293       // need special handling. Add it to InstList, so when it's processed
294       // there, it has to be legal or specially handled.
295       else {
296         LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");
297         InstList.insert(&MI);
298       }
299     }
300   } while (!InstList.empty());
301 
302   return {Changed, /*FailedOn*/ nullptr};
303 }
304 
305 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
306   // If the ISel pipeline failed, do not bother running that pass.
307   if (MF.getProperties().hasProperty(
308           MachineFunctionProperties::Property::FailedISel))
309     return false;
310   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
311   init(MF);
312   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
313   GISelCSEAnalysisWrapper &Wrapper =
314       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
315   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
316 
317   const size_t NumBlocks = MF.size();
318 
319   std::unique_ptr<MachineIRBuilder> MIRBuilder;
320   GISelCSEInfo *CSEInfo = nullptr;
321   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
322                        ? EnableCSEInLegalizer
323                        : TPC.isGISelCSEEnabled();
324   if (EnableCSE) {
325     MIRBuilder = std::make_unique<CSEMIRBuilder>();
326     CSEInfo = &Wrapper.get(TPC.getCSEConfig());
327     MIRBuilder->setCSEInfo(CSEInfo);
328   } else
329     MIRBuilder = std::make_unique<MachineIRBuilder>();
330 
331   SmallVector<GISelChangeObserver *, 1> AuxObservers;
332   if (EnableCSE && CSEInfo) {
333     // We want CSEInfo in addition to WorkListObserver to observe all changes.
334     AuxObservers.push_back(CSEInfo);
335   }
336   assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
337   LostDebugLocObserver LocObserver(DEBUG_TYPE);
338   if (VerifyDebugLocs > DebugLocVerifyLevel::None)
339     AuxObservers.push_back(&LocObserver);
340 
341   const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
342   MFResult Result =
343       legalizeMachineFunction(MF, LI, AuxObservers, LocObserver, *MIRBuilder);
344 
345   if (Result.FailedOn) {
346     reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
347                        "unable to legalize instruction", *Result.FailedOn);
348     return false;
349   }
350   // For now don't support if new blocks are inserted - we would need to fix the
351   // outer loop for that.
352   if (MF.size() != NumBlocks) {
353     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
354                                       MF.getFunction().getSubprogram(),
355                                       /*MBB=*/nullptr);
356     R << "inserting blocks is not supported yet";
357     reportGISelFailure(MF, TPC, MORE, R);
358     return false;
359   }
360 
361   if (LocObserver.getNumLostDebugLocs()) {
362     MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",
363                                       MF.getFunction().getSubprogram(),
364                                       /*MBB=*/&*MF.begin());
365     R << "lost "
366       << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())
367       << " debug locations during pass";
368     reportGISelWarning(MF, TPC, MORE, R);
369     // Example remark:
370     // --- !Missed
371     // Pass:            gisel-legalize
372     // Name:            GISelFailure
373     // DebugLoc:        { File: '.../legalize-urem.mir', Line: 1, Column: 0 }
374     // Function:        test_urem_s32
375     // Args:
376     //   - String:          'lost '
377     //   - NumLostDebugLocs: '1'
378     //   - String:          ' debug locations during pass'
379     // ...
380   }
381 
382   // If for some reason CSE was not enabled, make sure that we invalidate the
383   // CSEInfo object (as we currently declare that the analysis is preserved).
384   // The next time get on the wrapper is called, it will force it to recompute
385   // the analysis.
386   if (!EnableCSE)
387     Wrapper.setComputed(false);
388   return Result.Changed;
389 }
390