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/Support/Debug.h"
30 #include "llvm/Target/TargetMachine.h"
31 
32 #include <iterator>
33 
34 #define DEBUG_TYPE "legalizer"
35 
36 using namespace llvm;
37 
38 static cl::opt<bool>
39     EnableCSEInLegalizer("enable-cse-in-legalizer",
40                          cl::desc("Should enable CSE in Legalizer"),
41                          cl::Optional, cl::init(false));
42 
43 char Legalizer::ID = 0;
44 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
45                       "Legalize the Machine IR a function's Machine IR", false,
46                       false)
47 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
48 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
49 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
50                     "Legalize the Machine IR a function's Machine IR", false,
51                     false)
52 
53 Legalizer::Legalizer() : MachineFunctionPass(ID) {
54   initializeLegalizerPass(*PassRegistry::getPassRegistry());
55 }
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 
92 public:
93   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
94       : InstList(Insts), ArtifactList(Arts) {}
95 
96   void createdInstr(MachineInstr &MI) override {
97     // Only legalize pre-isel generic instructions.
98     // Legalization process could generate Target specific pseudo
99     // instructions with generic types. Don't record them
100     if (isPreISelGenericOpcode(MI.getOpcode())) {
101       if (isArtifact(MI))
102         ArtifactList.insert(&MI);
103       else
104         InstList.insert(&MI);
105     }
106     LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
107   }
108 
109   void erasingInstr(MachineInstr &MI) override {
110     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
111     InstList.remove(&MI);
112     ArtifactList.remove(&MI);
113   }
114 
115   void changingInstr(MachineInstr &MI) override {
116     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
117   }
118 
119   void changedInstr(MachineInstr &MI) override {
120     // When insts change, we want to revisit them to legalize them again.
121     // We'll consider them the same as created.
122     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
123     createdInstr(MI);
124   }
125 };
126 } // namespace
127 
128 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
129   // If the ISel pipeline failed, do not bother running that pass.
130   if (MF.getProperties().hasProperty(
131           MachineFunctionProperties::Property::FailedISel))
132     return false;
133   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
134   init(MF);
135   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
136   GISelCSEAnalysisWrapper &Wrapper =
137       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
138   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
139 
140   const size_t NumBlocks = MF.size();
141   MachineRegisterInfo &MRI = MF.getRegInfo();
142 
143   // Populate Insts
144   InstListTy InstList;
145   ArtifactListTy ArtifactList;
146   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
147   // Perform legalization bottom up so we can DCE as we legalize.
148   // Traverse BB in RPOT and within each basic block, add insts top down,
149   // so when we pop_back_val in the legalization process, we traverse bottom-up.
150   for (auto *MBB : RPOT) {
151     if (MBB->empty())
152       continue;
153     for (MachineInstr &MI : *MBB) {
154       // Only legalize pre-isel generic instructions: others don't have types
155       // and are assumed to be legal.
156       if (!isPreISelGenericOpcode(MI.getOpcode()))
157         continue;
158       if (isArtifact(MI))
159         ArtifactList.deferred_insert(&MI);
160       else
161         InstList.deferred_insert(&MI);
162     }
163   }
164   ArtifactList.finalize();
165   InstList.finalize();
166   std::unique_ptr<MachineIRBuilder> MIRBuilder;
167   GISelCSEInfo *CSEInfo = nullptr;
168   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
169                        ? EnableCSEInLegalizer
170                        : TPC.isGISelCSEEnabled();
171 
172   if (EnableCSE) {
173     MIRBuilder = make_unique<CSEMIRBuilder>();
174     CSEInfo = &Wrapper.get(TPC.getCSEConfig());
175     MIRBuilder->setCSEInfo(CSEInfo);
176   } else
177     MIRBuilder = make_unique<MachineIRBuilder>();
178   // This observer keeps the worklist updated.
179   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
180   // We want both WorkListObserver as well as CSEInfo to observe all changes.
181   // Use the wrapper observer.
182   GISelObserverWrapper WrapperObserver(&WorkListObserver);
183   if (EnableCSE && CSEInfo)
184     WrapperObserver.addObserver(CSEInfo);
185   // Now install the observer as the delegate to MF.
186   // This will keep all the observers notified about new insertions/deletions.
187   RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
188   LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
189   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
190   LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
191                                            LInfo);
192   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
193     WrapperObserver.erasingInstr(*DeadMI);
194   };
195   bool Changed = false;
196   do {
197     while (!InstList.empty()) {
198       MachineInstr &MI = *InstList.pop_back_val();
199       assert(isPreISelGenericOpcode(MI.getOpcode()) && "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         Helper.MIRBuilder.stopObservingChanges();
212         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
213                            "unable to legalize instruction", MI);
214         return false;
215       }
216       Changed |= Res == LegalizerHelper::Legalized;
217     }
218     while (!ArtifactList.empty()) {
219       MachineInstr &MI = *ArtifactList.pop_back_val();
220       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
221       if (isTriviallyDead(MI, MRI)) {
222         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
223         RemoveDeadInstFromLists(&MI);
224         MI.eraseFromParentAndMarkDBGValuesForRemoval();
225         continue;
226       }
227       SmallVector<MachineInstr *, 4> DeadInstructions;
228       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
229                                             WrapperObserver)) {
230         for (auto *DeadMI : DeadInstructions) {
231           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
232           RemoveDeadInstFromLists(DeadMI);
233           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
234         }
235         Changed = true;
236         continue;
237       }
238       // If this was not an artifact (that could be combined away), this might
239       // need special handling. Add it to InstList, so when it's processed
240       // there, it has to be legal or specially handled.
241       else
242         InstList.insert(&MI);
243     }
244   } while (!InstList.empty());
245 
246   // For now don't support if new blocks are inserted - we would need to fix the
247   // outerloop for that.
248   if (MF.size() != NumBlocks) {
249     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
250                                       MF.getFunction().getSubprogram(),
251                                       /*MBB=*/nullptr);
252     R << "inserting blocks is not supported yet";
253     reportGISelFailure(MF, TPC, MORE, R);
254     return false;
255   }
256 
257   return Changed;
258 }
259