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