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 
31 #include <iterator>
32 
33 #define DEBUG_TYPE "legalizer"
34 
35 using namespace llvm;
36 
37 static cl::opt<bool>
38     EnableCSEInLegalizer("enable-cse-in-legalizer",
39                          cl::desc("Should enable CSE in Legalizer"),
40                          cl::Optional, cl::init(false));
41 
42 char Legalizer::ID = 0;
43 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
44                       "Legalize the Machine IR a function's Machine IR", false,
45                       false)
46 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
47 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
48 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
49                     "Legalize the Machine IR a function's Machine IR", false,
50                     false)
51 
52 Legalizer::Legalizer() : MachineFunctionPass(ID) {
53   initializeLegalizerPass(*PassRegistry::getPassRegistry());
54 }
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 
91 public:
92   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
93       : InstList(Insts), ArtifactList(Arts) {}
94 
95   void createdInstr(MachineInstr &MI) override {
96     // Only legalize pre-isel generic instructions.
97     // Legalization process could generate Target specific pseudo
98     // instructions with generic types. Don't record them
99     if (isPreISelGenericOpcode(MI.getOpcode())) {
100       if (isArtifact(MI))
101         ArtifactList.insert(&MI);
102       else
103         InstList.insert(&MI);
104     }
105     LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
106   }
107 
108   void erasingInstr(MachineInstr &MI) override {
109     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
110     InstList.remove(&MI);
111     ArtifactList.remove(&MI);
112   }
113 
114   void changingInstr(MachineInstr &MI) override {
115     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
116   }
117 
118   void changedInstr(MachineInstr &MI) override {
119     // When insts change, we want to revisit them to legalize them again.
120     // We'll consider them the same as created.
121     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
122     createdInstr(MI);
123   }
124 };
125 } // namespace
126 
127 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
128   // If the ISel pipeline failed, do not bother running that pass.
129   if (MF.getProperties().hasProperty(
130           MachineFunctionProperties::Property::FailedISel))
131     return false;
132   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
133   init(MF);
134   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
135   GISelCSEAnalysisWrapper &Wrapper =
136       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
137   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
138 
139   const size_t NumBlocks = MF.size();
140   MachineRegisterInfo &MRI = MF.getRegInfo();
141 
142   // Populate Insts
143   InstListTy InstList;
144   ArtifactListTy ArtifactList;
145   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
146   // Perform legalization bottom up so we can DCE as we legalize.
147   // Traverse BB in RPOT and within each basic block, add insts top down,
148   // so when we pop_back_val in the legalization process, we traverse bottom-up.
149   for (auto *MBB : RPOT) {
150     if (MBB->empty())
151       continue;
152     for (MachineInstr &MI : *MBB) {
153       // Only legalize pre-isel generic instructions: others don't have types
154       // and are assumed to be legal.
155       if (!isPreISelGenericOpcode(MI.getOpcode()))
156         continue;
157       if (isArtifact(MI))
158         ArtifactList.deferred_insert(&MI);
159       else
160         InstList.deferred_insert(&MI);
161     }
162   }
163   ArtifactList.finalize();
164   InstList.finalize();
165   std::unique_ptr<MachineIRBuilder> MIRBuilder;
166   GISelCSEInfo *CSEInfo = nullptr;
167   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
168                        ? EnableCSEInLegalizer
169                        : TPC.isGISelCSEEnabled();
170 
171   if (EnableCSE) {
172     MIRBuilder = make_unique<CSEMIRBuilder>();
173     std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
174     CSEInfo = &Wrapper.get(std::move(Config));
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         for (auto *DeadMI : DeadInstructions) {
230           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
231           RemoveDeadInstFromLists(DeadMI);
232           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
233         }
234         Changed = true;
235         continue;
236       }
237       // If this was not an artifact (that could be combined away), this might
238       // need special handling. Add it to InstList, so when it's processed
239       // there, it has to be legal or specially handled.
240       else
241         InstList.insert(&MI);
242     }
243   } while (!InstList.empty());
244 
245   // For now don't support if new blocks are inserted - we would need to fix the
246   // outerloop for that.
247   if (MF.size() != NumBlocks) {
248     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
249                                       MF.getFunction().getSubprogram(),
250                                       /*MBB=*/nullptr);
251     R << "inserting blocks is not supported yet";
252     reportGISelFailure(MF, TPC, MORE, R);
253     return false;
254   }
255 
256   return Changed;
257 }
258