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