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