1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file This file implements the LegalizerHelper class to legalize individual
11 /// instructions and the LegalizePass wrapper pass for the primary
12 /// legalization.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
17 #include "llvm/ADT/PostOrderIterator.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
20 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
21 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
22 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
23 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
24 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
25 #include "llvm/CodeGen/GlobalISel/Utils.h"
26 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/TargetPassConfig.h"
29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
30 #include "llvm/Support/Debug.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     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 IsO0 = TPC.getOptLevel() == CodeGenOpt::Level::None;
166   // Disable CSE for O0.
167   bool EnableCSE = !IsO0 && EnableCSEInLegalizer;
168   if (EnableCSE) {
169     MIRBuilder = make_unique<CSEMIRBuilder>();
170     std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
171     CSEInfo = &Wrapper.get(std::move(Config));
172     MIRBuilder->setCSEInfo(CSEInfo);
173   } else
174     MIRBuilder = make_unique<MachineIRBuilder>();
175   // This observer keeps the worklist updated.
176   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
177   // We want both WorkListObserver as well as CSEInfo to observe all changes.
178   // Use the wrapper observer.
179   GISelObserverWrapper WrapperObserver(&WorkListObserver);
180   if (EnableCSE && CSEInfo)
181     WrapperObserver.addObserver(CSEInfo);
182   // Now install the observer as the delegate to MF.
183   // This will keep all the observers notified about new insertions/deletions.
184   RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
185   LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
186   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
187   LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
188                                            LInfo);
189   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
190     WrapperObserver.erasingInstr(*DeadMI);
191   };
192   bool Changed = false;
193   do {
194     while (!InstList.empty()) {
195       MachineInstr &MI = *InstList.pop_back_val();
196       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
197       if (isTriviallyDead(MI, MRI)) {
198         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
199         MI.eraseFromParentAndMarkDBGValuesForRemoval();
200         continue;
201       }
202 
203       // Do the legalization for this instruction.
204       auto Res = Helper.legalizeInstrStep(MI);
205       // Error out if we couldn't legalize this instruction. We may want to
206       // fall back to DAG ISel instead in the future.
207       if (Res == LegalizerHelper::UnableToLegalize) {
208         Helper.MIRBuilder.stopObservingChanges();
209         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
210                            "unable to legalize instruction", MI);
211         return false;
212       }
213       Changed |= Res == LegalizerHelper::Legalized;
214     }
215     while (!ArtifactList.empty()) {
216       MachineInstr &MI = *ArtifactList.pop_back_val();
217       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
218       if (isTriviallyDead(MI, MRI)) {
219         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
220         RemoveDeadInstFromLists(&MI);
221         MI.eraseFromParentAndMarkDBGValuesForRemoval();
222         continue;
223       }
224       SmallVector<MachineInstr *, 4> DeadInstructions;
225       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
226         for (auto *DeadMI : DeadInstructions) {
227           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
228           RemoveDeadInstFromLists(DeadMI);
229           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
230         }
231         Changed = true;
232         continue;
233       }
234       // If this was not an artifact (that could be combined away), this might
235       // need special handling. Add it to InstList, so when it's processed
236       // there, it has to be legal or specially handled.
237       else
238         InstList.insert(&MI);
239     }
240   } while (!InstList.empty());
241 
242   // For now don't support if new blocks are inserted - we would need to fix the
243   // outerloop for that.
244   if (MF.size() != NumBlocks) {
245     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
246                                       MF.getFunction().getSubprogram(),
247                                       /*MBB=*/nullptr);
248     R << "inserting blocks is not supported yet";
249     reportGISelFailure(MF, TPC, MORE, R);
250     return false;
251   }
252 
253   return Changed;
254 }
255