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.insert(&MI);
159       else
160         InstList.insert(&MI);
161     }
162   }
163   std::unique_ptr<MachineIRBuilder> MIRBuilder;
164   GISelCSEInfo *CSEInfo = nullptr;
165   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
166                        ? EnableCSEInLegalizer
167                        : TPC.isGISelCSEEnabled();
168 
169   if (EnableCSE) {
170     MIRBuilder = make_unique<CSEMIRBuilder>();
171     std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
172     CSEInfo = &Wrapper.get(std::move(Config));
173     MIRBuilder->setCSEInfo(CSEInfo);
174   } else
175     MIRBuilder = make_unique<MachineIRBuilder>();
176   // This observer keeps the worklist updated.
177   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
178   // We want both WorkListObserver as well as CSEInfo to observe all changes.
179   // Use the wrapper observer.
180   GISelObserverWrapper WrapperObserver(&WorkListObserver);
181   if (EnableCSE && CSEInfo)
182     WrapperObserver.addObserver(CSEInfo);
183   // Now install the observer as the delegate to MF.
184   // This will keep all the observers notified about new insertions/deletions.
185   RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
186   LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
187   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
188   LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
189                                            LInfo);
190   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
191     WrapperObserver.erasingInstr(*DeadMI);
192   };
193   bool Changed = false;
194   do {
195     while (!InstList.empty()) {
196       MachineInstr &MI = *InstList.pop_back_val();
197       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
198       if (isTriviallyDead(MI, MRI)) {
199         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
200         MI.eraseFromParentAndMarkDBGValuesForRemoval();
201         continue;
202       }
203 
204       // Do the legalization for this instruction.
205       auto Res = Helper.legalizeInstrStep(MI);
206       // Error out if we couldn't legalize this instruction. We may want to
207       // fall back to DAG ISel instead in the future.
208       if (Res == LegalizerHelper::UnableToLegalize) {
209         Helper.MIRBuilder.stopObservingChanges();
210         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
211                            "unable to legalize instruction", MI);
212         return false;
213       }
214       Changed |= Res == LegalizerHelper::Legalized;
215     }
216     while (!ArtifactList.empty()) {
217       MachineInstr &MI = *ArtifactList.pop_back_val();
218       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
219       if (isTriviallyDead(MI, MRI)) {
220         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
221         RemoveDeadInstFromLists(&MI);
222         MI.eraseFromParentAndMarkDBGValuesForRemoval();
223         continue;
224       }
225       SmallVector<MachineInstr *, 4> DeadInstructions;
226       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
227         for (auto *DeadMI : DeadInstructions) {
228           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
229           RemoveDeadInstFromLists(DeadMI);
230           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
231         }
232         Changed = true;
233         continue;
234       }
235       // If this was not an artifact (that could be combined away), this might
236       // need special handling. Add it to InstList, so when it's processed
237       // there, it has to be legal or specially handled.
238       else
239         InstList.insert(&MI);
240     }
241   } while (!InstList.empty());
242 
243   // For now don't support if new blocks are inserted - we would need to fix the
244   // outerloop for that.
245   if (MF.size() != NumBlocks) {
246     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
247                                       MF.getFunction().getSubprogram(),
248                                       /*MBB=*/nullptr);
249     R << "inserting blocks is not supported yet";
250     reportGISelFailure(MF, TPC, MORE, R);
251     return false;
252   }
253 
254   return Changed;
255 }
256