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