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 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
144   // If the ISel pipeline failed, do not bother running that pass.
145   if (MF.getProperties().hasProperty(
146           MachineFunctionProperties::Property::FailedISel))
147     return false;
148   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
149   init(MF);
150   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
151   GISelCSEAnalysisWrapper &Wrapper =
152       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
153   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
154 
155   const size_t NumBlocks = MF.size();
156   MachineRegisterInfo &MRI = MF.getRegInfo();
157 
158   // Populate Insts
159   InstListTy InstList;
160   ArtifactListTy ArtifactList;
161   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
162   // Perform legalization bottom up so we can DCE as we legalize.
163   // Traverse BB in RPOT and within each basic block, add insts top down,
164   // so when we pop_back_val in the legalization process, we traverse bottom-up.
165   for (auto *MBB : RPOT) {
166     if (MBB->empty())
167       continue;
168     for (MachineInstr &MI : *MBB) {
169       // Only legalize pre-isel generic instructions: others don't have types
170       // and are assumed to be legal.
171       if (!isPreISelGenericOpcode(MI.getOpcode()))
172         continue;
173       if (isArtifact(MI))
174         ArtifactList.deferred_insert(&MI);
175       else
176         InstList.deferred_insert(&MI);
177     }
178   }
179   ArtifactList.finalize();
180   InstList.finalize();
181   std::unique_ptr<MachineIRBuilder> MIRBuilder;
182   GISelCSEInfo *CSEInfo = nullptr;
183   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
184                        ? EnableCSEInLegalizer
185                        : TPC.isGISelCSEEnabled();
186 
187   if (EnableCSE) {
188     MIRBuilder = std::make_unique<CSEMIRBuilder>();
189     CSEInfo = &Wrapper.get(TPC.getCSEConfig());
190     MIRBuilder->setCSEInfo(CSEInfo);
191   } else
192     MIRBuilder = std::make_unique<MachineIRBuilder>();
193   // This observer keeps the worklist updated.
194   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
195   // We want both WorkListObserver as well as CSEInfo to observe all changes.
196   // Use the wrapper observer.
197   GISelObserverWrapper WrapperObserver(&WorkListObserver);
198   if (EnableCSE && CSEInfo)
199     WrapperObserver.addObserver(CSEInfo);
200   // Now install the observer as the delegate to MF.
201   // This will keep all the observers notified about new insertions/deletions.
202   RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
203   LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
204   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
205   LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
206                                            LInfo);
207   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
208     WrapperObserver.erasingInstr(*DeadMI);
209   };
210   auto stopLegalizing = [&](MachineInstr &MI) {
211     Helper.MIRBuilder.stopObservingChanges();
212     reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
213                        "unable to legalize instruction", MI);
214   };
215   bool Changed = false;
216   SmallVector<MachineInstr *, 128> RetryList;
217   do {
218     assert(RetryList.empty() && "Expected no instructions in RetryList");
219     unsigned NumArtifacts = ArtifactList.size();
220     while (!InstList.empty()) {
221       MachineInstr &MI = *InstList.pop_back_val();
222       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
223       if (isTriviallyDead(MI, MRI)) {
224         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
225         MI.eraseFromParentAndMarkDBGValuesForRemoval();
226         continue;
227       }
228 
229       // Do the legalization for this instruction.
230       auto Res = Helper.legalizeInstrStep(MI);
231       // Error out if we couldn't legalize this instruction. We may want to
232       // fall back to DAG ISel instead in the future.
233       if (Res == LegalizerHelper::UnableToLegalize) {
234         // Move illegal artifacts to RetryList instead of aborting because
235         // legalizing InstList may generate artifacts that allow
236         // ArtifactCombiner to combine away them.
237         if (isArtifact(MI)) {
238           RetryList.push_back(&MI);
239           continue;
240         }
241         stopLegalizing(MI);
242         return false;
243       }
244       WorkListObserver.printNewInstrs();
245       Changed |= Res == LegalizerHelper::Legalized;
246     }
247     // Try to combine the instructions in RetryList again if there
248     // are new artifacts. If not, stop legalizing.
249     if (!RetryList.empty()) {
250       if (ArtifactList.size() > NumArtifacts) {
251         while (!RetryList.empty())
252           ArtifactList.insert(RetryList.pop_back_val());
253       } else {
254         MachineInstr *MI = *RetryList.begin();
255         stopLegalizing(*MI);
256         return false;
257       }
258     }
259     while (!ArtifactList.empty()) {
260       MachineInstr &MI = *ArtifactList.pop_back_val();
261       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
262       if (isTriviallyDead(MI, MRI)) {
263         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
264         RemoveDeadInstFromLists(&MI);
265         MI.eraseFromParentAndMarkDBGValuesForRemoval();
266         continue;
267       }
268       SmallVector<MachineInstr *, 4> DeadInstructions;
269       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
270                                             WrapperObserver)) {
271         WorkListObserver.printNewInstrs();
272         for (auto *DeadMI : DeadInstructions) {
273           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
274           RemoveDeadInstFromLists(DeadMI);
275           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
276         }
277         Changed = true;
278         continue;
279       }
280       // If this was not an artifact (that could be combined away), this might
281       // need special handling. Add it to InstList, so when it's processed
282       // there, it has to be legal or specially handled.
283       else
284         InstList.insert(&MI);
285     }
286   } while (!InstList.empty());
287 
288   // For now don't support if new blocks are inserted - we would need to fix the
289   // outerloop for that.
290   if (MF.size() != NumBlocks) {
291     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
292                                       MF.getFunction().getSubprogram(),
293                                       /*MBB=*/nullptr);
294     R << "inserting blocks is not supported yet";
295     reportGISelFailure(MF, TPC, MORE, R);
296     return false;
297   }
298 
299   return Changed;
300 }
301