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/SetVector.h"
18 #include "llvm/CodeGen/GlobalISel/LegalizerCombiner.h"
19 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
20 #include "llvm/CodeGen/GlobalISel/Utils.h"
21 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/TargetPassConfig.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Target/TargetSubtargetInfo.h"
27 
28 #include <iterator>
29 
30 #define DEBUG_TYPE "legalizer"
31 
32 using namespace llvm;
33 
34 char Legalizer::ID = 0;
35 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
36                       "Legalize the Machine IR a function's Machine IR", false,
37                       false)
38 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
39 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
40                     "Legalize the Machine IR a function's Machine IR", false,
41                     false)
42 
43 Legalizer::Legalizer() : MachineFunctionPass(ID) {
44   initializeLegalizerPass(*PassRegistry::getPassRegistry());
45 }
46 
47 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
48   AU.addRequired<TargetPassConfig>();
49   MachineFunctionPass::getAnalysisUsage(AU);
50 }
51 
52 void Legalizer::init(MachineFunction &MF) {
53 }
54 
55 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
56   // If the ISel pipeline failed, do not bother running that pass.
57   if (MF.getProperties().hasProperty(
58           MachineFunctionProperties::Property::FailedISel))
59     return false;
60   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
61   init(MF);
62   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
63   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
64   LegalizerHelper Helper(MF);
65 
66   // FIXME: an instruction may need more than one pass before it is legal. For
67   // example on most architectures <3 x i3> is doubly-illegal. It would
68   // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
69   // probably want a worklist of instructions rather than naive iterate until
70   // convergence for performance reasons.
71   bool Changed = false;
72   MachineBasicBlock::iterator NextMI;
73   using VecType = SmallSetVector<MachineInstr *, 8>;
74   VecType WorkList;
75   VecType CombineList;
76   for (auto &MBB : MF) {
77     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
78       // Get the next Instruction before we try to legalize, because there's a
79       // good chance MI will be deleted.
80       NextMI = std::next(MI);
81 
82       // Only legalize pre-isel generic instructions: others don't have types
83       // and are assumed to be legal.
84       if (!isPreISelGenericOpcode(MI->getOpcode()))
85         continue;
86       unsigned NumNewInsns = 0;
87       WorkList.clear();
88       CombineList.clear();
89       Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
90         // Only legalize pre-isel generic instructions.
91         // Legalization process could generate Target specific pseudo
92         // instructions with generic types. Don't record them
93         if (isPreISelGenericOpcode(MI->getOpcode())) {
94           ++NumNewInsns;
95           WorkList.insert(MI);
96           CombineList.insert(MI);
97         }
98       });
99       WorkList.insert(&*MI);
100       LegalizerCombiner C(Helper.MIRBuilder, MF.getRegInfo());
101       bool Changed = false;
102       LegalizerHelper::LegalizeResult Res;
103       do {
104         assert(!WorkList.empty() && "Expecting illegal ops");
105         while (!WorkList.empty()) {
106           NumNewInsns = 0;
107           MachineInstr *CurrInst = WorkList.pop_back_val();
108           Res = Helper.legalizeInstrStep(*CurrInst);
109           // Error out if we couldn't legalize this instruction. We may want to
110           // fall back to DAG ISel instead in the future.
111           if (Res == LegalizerHelper::UnableToLegalize) {
112             Helper.MIRBuilder.stopRecordingInsertions();
113             if (Res == LegalizerHelper::UnableToLegalize) {
114               reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
115                                  "unable to legalize instruction", *CurrInst);
116               return false;
117             }
118           }
119           Changed |= Res == LegalizerHelper::Legalized;
120           // If CurrInst was legalized, there's a good chance that it might have
121           // been erased. So remove it from the Combine List.
122           if (Res == LegalizerHelper::Legalized)
123             CombineList.remove(CurrInst);
124 
125 #ifndef NDEBUG
126           if (NumNewInsns)
127             for (unsigned I = WorkList.size() - NumNewInsns,
128                           E = WorkList.size();
129                  I != E; ++I)
130               DEBUG(dbgs() << ".. .. New MI: " << *WorkList[I];);
131 #endif
132         }
133         // Do the combines.
134         while (!CombineList.empty()) {
135           NumNewInsns = 0;
136           MachineInstr *CurrInst = CombineList.pop_back_val();
137           SmallVector<MachineInstr *, 4> DeadInstructions;
138           Changed |= C.tryCombineInstruction(*CurrInst, DeadInstructions);
139           for (auto *DeadMI : DeadInstructions) {
140             DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
141             CombineList.remove(DeadMI);
142             WorkList.remove(DeadMI);
143             DeadMI->eraseFromParent();
144           }
145 #ifndef NDEBUG
146           if (NumNewInsns)
147             for (unsigned I = CombineList.size() - NumNewInsns,
148                           E = CombineList.size();
149                  I != E; ++I)
150               DEBUG(dbgs() << ".. .. Combine New MI: " << *CombineList[I];);
151 #endif
152         }
153       } while (!WorkList.empty());
154 
155       Helper.MIRBuilder.stopRecordingInsertions();
156     }
157   }
158 
159   MachineRegisterInfo &MRI = MF.getRegInfo();
160   MachineIRBuilder MIRBuilder(MF);
161   LegalizerCombiner C(MIRBuilder, MRI);
162   for (auto &MBB : MF) {
163     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
164       // Get the next Instruction before we try to legalize, because there's a
165       // good chance MI will be deleted.
166       // TOOD: Perhaps move this to a combiner pass later?.
167       NextMI = std::next(MI);
168       SmallVector<MachineInstr *, 4> DeadInsts;
169       Changed |= C.tryCombineMerges(*MI, DeadInsts);
170       for (auto *DeadMI : DeadInsts)
171         DeadMI->eraseFromParent();
172     }
173   }
174 
175   return Changed;
176 }
177