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