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