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/GISelWorkList.h"
20 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
21 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
22 #include "llvm/CodeGen/GlobalISel/Utils.h"
23 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/TargetInstrInfo.h"
26 #include "llvm/CodeGen/TargetPassConfig.h"
27 #include "llvm/CodeGen/TargetSubtargetInfo.h"
28 #include "llvm/Support/Debug.h"
29 
30 #include <iterator>
31 
32 #define DEBUG_TYPE "legalizer"
33 
34 using namespace llvm;
35 
36 char Legalizer::ID = 0;
37 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
38                       "Legalize the Machine IR a function's Machine IR", false,
39                       false)
40 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
41 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
42                     "Legalize the Machine IR a function's Machine IR", false,
43                     false)
44 
45 Legalizer::Legalizer() : MachineFunctionPass(ID) {
46   initializeLegalizerPass(*PassRegistry::getPassRegistry());
47 }
48 
49 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
50   AU.addRequired<TargetPassConfig>();
51   MachineFunctionPass::getAnalysisUsage(AU);
52 }
53 
54 void Legalizer::init(MachineFunction &MF) {
55 }
56 
57 static bool isArtifact(const MachineInstr &MI) {
58   switch (MI.getOpcode()) {
59   default:
60     return false;
61   case TargetOpcode::G_TRUNC:
62   case TargetOpcode::G_ZEXT:
63   case TargetOpcode::G_ANYEXT:
64   case TargetOpcode::G_SEXT:
65   case TargetOpcode::G_MERGE_VALUES:
66   case TargetOpcode::G_UNMERGE_VALUES:
67     return true;
68   }
69 }
70 
71 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
72   // If the ISel pipeline failed, do not bother running that pass.
73   if (MF.getProperties().hasProperty(
74           MachineFunctionProperties::Property::FailedISel))
75     return false;
76   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
77   init(MF);
78   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
79   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
80   LegalizerHelper Helper(MF);
81 
82   const size_t NumBlocks = MF.size();
83   MachineRegisterInfo &MRI = MF.getRegInfo();
84 
85   // Populate Insts
86   GISelWorkList<256> InstList;
87   GISelWorkList<128> ArtifactList;
88   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
89   // Perform legalization bottom up so we can DCE as we legalize.
90   // Traverse BB in RPOT and within each basic block, add insts top down,
91   // so when we pop_back_val in the legalization process, we traverse bottom-up.
92   for (auto *MBB : RPOT) {
93     if (MBB->empty())
94       continue;
95     for (MachineInstr &MI : *MBB) {
96       // Only legalize pre-isel generic instructions: others don't have types
97       // and are assumed to be legal.
98       if (!isPreISelGenericOpcode(MI.getOpcode()))
99         continue;
100       if (isArtifact(MI))
101         ArtifactList.insert(&MI);
102       else
103         InstList.insert(&MI);
104     }
105   }
106   Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
107     // Only legalize pre-isel generic instructions.
108     // Legalization process could generate Target specific pseudo
109     // instructions with generic types. Don't record them
110     if (isPreISelGenericOpcode(MI->getOpcode())) {
111       if (isArtifact(*MI))
112         ArtifactList.insert(MI);
113       else
114         InstList.insert(MI);
115     }
116     DEBUG(dbgs() << ".. .. New MI: " << *MI;);
117   });
118   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
119   LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
120   auto RemoveDeadInstFromLists = [&InstList,
121                                   &ArtifactList](MachineInstr *DeadMI) {
122     InstList.remove(DeadMI);
123     ArtifactList.remove(DeadMI);
124   };
125   bool Changed = false;
126   do {
127     while (!InstList.empty()) {
128       MachineInstr &MI = *InstList.pop_back_val();
129       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
130       if (isTriviallyDead(MI, MRI)) {
131         DEBUG(dbgs() << MI << "Is dead; erasing.\n");
132         MI.eraseFromParentAndMarkDBGValuesForRemoval();
133         continue;
134       }
135 
136       // Do the legalization for this instruction.
137       auto Res = Helper.legalizeInstrStep(MI);
138       // Error out if we couldn't legalize this instruction. We may want to
139       // fall back to DAG ISel instead in the future.
140       if (Res == LegalizerHelper::UnableToLegalize) {
141         Helper.MIRBuilder.stopRecordingInsertions();
142         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
143                            "unable to legalize instruction", MI);
144         return false;
145       }
146       Changed |= Res == LegalizerHelper::Legalized;
147     }
148     while (!ArtifactList.empty()) {
149       MachineInstr &MI = *ArtifactList.pop_back_val();
150       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
151       if (isTriviallyDead(MI, MRI)) {
152         DEBUG(dbgs() << MI << "Is dead; erasing.\n");
153         RemoveDeadInstFromLists(&MI);
154         MI.eraseFromParentAndMarkDBGValuesForRemoval();
155         continue;
156       }
157       SmallVector<MachineInstr *, 4> DeadInstructions;
158       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
159         for (auto *DeadMI : DeadInstructions) {
160           DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
161           RemoveDeadInstFromLists(DeadMI);
162           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
163         }
164         Changed = true;
165         continue;
166       }
167       // If this was not an artifact (that could be combined away), this might
168       // need special handling. Add it to InstList, so when it's processed
169       // there, it has to be legal or specially handled.
170       else
171         InstList.insert(&MI);
172     }
173   } while (!InstList.empty());
174 
175   // For now don't support if new blocks are inserted - we would need to fix the
176   // outerloop for that.
177   if (MF.size() != NumBlocks) {
178     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
179                                       MF.getFunction()->getSubprogram(),
180                                       /*MBB=*/nullptr);
181     R << "inserting blocks is not supported yet";
182     reportGISelFailure(MF, TPC, MORE, R);
183     return false;
184   }
185 
186   return Changed;
187 }
188