1//===-- lib/CodeGen/GlobalISel/Combiner.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// This file constains common code to combine machine functions at generic
10// level.
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/GlobalISel/Combiner.h"
14#include "llvm/ADT/PostOrderIterator.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
18#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
19#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
20#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
21#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
22#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
23#include "llvm/CodeGen/GlobalISel/Utils.h"
24#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
25#include "llvm/Support/Debug.h"
26
27#define DEBUG_TYPE "gi-combiner"
28
29using namespace llvm;
30
31STATISTIC(NumOneIteration, "Number of functions with one iteration");
32STATISTIC(NumTwoIterations, "Number of functions with two iterations");
33STATISTIC(NumThreeOrMoreIterations,
34 "Number of functions with three or more iterations");
35
36namespace llvm {
37cl::OptionCategory GICombinerOptionCategory(
38 "GlobalISel Combiner",
39 "Control the rules which are enabled. These options all take a comma "
40 "separated list of rules to disable and may be specified by number "
41 "or number range (e.g. 1-10)."
42#ifndef NDEBUG
43 " They may also be specified by name."
44#endif
45);
46} // end namespace llvm
47
48/// This class acts as the glue that joins the CombinerHelper to the overall
49/// Combine algorithm. The CombinerHelper is intended to report the
50/// modifications it makes to the MIR to the GISelChangeObserver and the
51/// observer subclass will act on these events.
52class Combiner::WorkListMaintainer : public GISelChangeObserver {
53protected:
54#ifndef NDEBUG
55 /// The instructions that have been created but we want to report once they
56 /// have their operands. This is only maintained if debug output is requested.
57 SmallSetVector<const MachineInstr *, 32> CreatedInstrs;
58#endif
59 using Level = CombinerInfo::ObserverLevel;
60
61public:
62 static std::unique_ptr<WorkListMaintainer>
63 create(Level Lvl, WorkListTy &WorkList, MachineRegisterInfo &MRI);
64
65 virtual ~WorkListMaintainer() = default;
66
67 void reportFullyCreatedInstrs() {
68 LLVM_DEBUG({
69 for (auto *MI : CreatedInstrs) {
70 dbgs() << "Created: " << *MI;
71 }
72 CreatedInstrs.clear();
73 });
74 }
75
76 virtual void reset() = 0;
77 virtual void appliedCombine() = 0;
78};
79
80/// A configurable WorkListMaintainer implementation.
81/// The ObserverLevel determines how the WorkListMaintainer reacts to MIR
82/// changes.
83template <CombinerInfo::ObserverLevel Lvl>
84class Combiner::WorkListMaintainerImpl : public Combiner::WorkListMaintainer {
85 WorkListTy &WorkList;
86 MachineRegisterInfo &MRI;
87
88 // Defer handling these instructions until the combine finishes.
89 SmallSetVector<MachineInstr *, 32> DeferList;
90
91 // Track VRegs that (might) have lost a use.
92 SmallSetVector<Register, 32> LostUses;
93
94public:
95 WorkListMaintainerImpl(WorkListTy &WorkList, MachineRegisterInfo &MRI)
96 : WorkList(WorkList), MRI(MRI) {}
97
98 virtual ~WorkListMaintainerImpl() = default;
99
100 void reset() override {
101 DeferList.clear();
102 LostUses.clear();
103 }
104
105 void erasingInstr(MachineInstr &MI) override {
106 // MI will become dangling, remove it from all lists.
107 LLVM_DEBUG(dbgs() << "Erasing: " << MI; CreatedInstrs.remove(&MI));
108 WorkList.remove(I: &MI);
109 if constexpr (Lvl != Level::Basic) {
110 DeferList.remove(X: &MI);
111 noteLostUses(MI);
112 }
113 }
114
115 void createdInstr(MachineInstr &MI) override {
116 LLVM_DEBUG(dbgs() << "Creating: " << MI; CreatedInstrs.insert(&MI));
117 if constexpr (Lvl == Level::Basic)
118 WorkList.insert(I: &MI);
119 else
120 // Defer handling newly created instructions, because they don't have
121 // operands yet. We also insert them into the WorkList in reverse
122 // order so that they will be combined top down.
123 DeferList.insert(X: &MI);
124 }
125
126 void changingInstr(MachineInstr &MI) override {
127 LLVM_DEBUG(dbgs() << "Changing: " << MI);
128 // Some uses might get dropped when MI is changed.
129 // For now, overapproximate by assuming all uses will be dropped.
130 // TODO: Is a more precise heuristic or manual tracking of use count
131 // decrements worth it?
132 if constexpr (Lvl != Level::Basic)
133 noteLostUses(MI);
134 }
135
136 void changedInstr(MachineInstr &MI) override {
137 LLVM_DEBUG(dbgs() << "Changed: " << MI);
138 if constexpr (Lvl == Level::Basic)
139 WorkList.insert(I: &MI);
140 else
141 // Defer this for DCE
142 DeferList.insert(X: &MI);
143 }
144
145 // Only track changes during the combine and then walk the def/use-chains once
146 // the combine is finished, because:
147 // - instructions might have multiple defs during the combine.
148 // - use counts aren't accurate during the combine.
149 void appliedCombine() override {
150 if constexpr (Lvl == Level::Basic)
151 return;
152
153 // DCE deferred instructions and add them to the WorkList bottom up.
154 while (!DeferList.empty()) {
155 MachineInstr &MI = *DeferList.pop_back_val();
156 if (tryDCE(MI, MRI))
157 continue;
158
159 if constexpr (Lvl >= Level::SinglePass)
160 addUsersToWorkList(MI);
161
162 WorkList.insert(I: &MI);
163 }
164
165 // Handle instructions that have lost a user.
166 while (!LostUses.empty()) {
167 Register Use = LostUses.pop_back_val();
168 MachineInstr *UseMI = MRI.getVRegDef(Reg: Use);
169 if (!UseMI)
170 continue;
171
172 // If DCE succeeds, UseMI's uses are added back to LostUses by
173 // erasingInstr.
174 if (tryDCE(MI&: *UseMI, MRI))
175 continue;
176
177 if constexpr (Lvl >= Level::SinglePass) {
178 // OneUse checks are relatively common, so we might be able to combine
179 // the single remaining user of this Reg.
180 if (MRI.hasOneNonDBGUser(RegNo: Use))
181 WorkList.insert(I: &*MRI.use_instr_nodbg_begin(RegNo: Use));
182
183 WorkList.insert(I: UseMI);
184 }
185 }
186 }
187
188 void noteLostUses(MachineInstr &MI) {
189 for (auto &Use : MI.explicit_uses()) {
190 if (!Use.isReg() || !Use.getReg().isVirtual())
191 continue;
192 LostUses.insert(X: Use.getReg());
193 }
194 }
195
196 void addUsersToWorkList(MachineInstr &MI) {
197 for (auto &Def : MI.defs()) {
198 Register DefReg = Def.getReg();
199 if (!DefReg.isVirtual())
200 continue;
201 for (auto &UseMI : MRI.use_nodbg_instructions(Reg: DefReg)) {
202 WorkList.insert(I: &UseMI);
203 }
204 }
205 }
206};
207
208std::unique_ptr<Combiner::WorkListMaintainer>
209Combiner::WorkListMaintainer::create(Level Lvl, WorkListTy &WorkList,
210 MachineRegisterInfo &MRI) {
211 switch (Lvl) {
212 case Level::Basic:
213 return std::make_unique<WorkListMaintainerImpl<Level::Basic>>(args&: WorkList,
214 args&: MRI);
215 case Level::DCE:
216 return std::make_unique<WorkListMaintainerImpl<Level::DCE>>(args&: WorkList, args&: MRI);
217 case Level::SinglePass:
218 return std::make_unique<WorkListMaintainerImpl<Level::SinglePass>>(args&: WorkList,
219 args&: MRI);
220 }
221 llvm_unreachable("Illegal ObserverLevel");
222}
223
224Combiner::Combiner(MachineFunction &MF, CombinerInfo &CInfo,
225 const TargetPassConfig *TPC, GISelValueTracking *VT,
226 GISelCSEInfo *CSEInfo)
227 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()
228 : std::make_unique<MachineIRBuilder>()),
229 WLObserver(WorkListMaintainer::create(Lvl: CInfo.ObserverLvl, WorkList,
230 MRI&: MF.getRegInfo())),
231 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),
232 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),
233 VT(VT), TPC(TPC), CSEInfo(CSEInfo) {
234 (void)this->TPC; // FIXME: Remove when used.
235
236 // Setup builder.
237 B.setMF(MF);
238 if (CSEInfo)
239 B.setCSEInfo(CSEInfo);
240
241 B.setChangeObserver(*ObserverWrapper);
242}
243
244Combiner::~Combiner() = default;
245
246bool Combiner::tryDCE(MachineInstr &MI, MachineRegisterInfo &MRI) {
247 if (!isTriviallyDead(MI, MRI))
248 return false;
249 LLVM_DEBUG(dbgs() << "Dead: " << MI);
250 llvm::salvageDebugInfo(MRI, MI);
251 MI.eraseFromParent();
252 return true;
253}
254
255bool Combiner::combineMachineInstrs() {
256 // If the ISel pipeline failed, do not bother running this pass.
257 // FIXME: Should this be here or in individual combiner passes.
258 if (MF.getProperties().hasFailedISel())
259 return false;
260
261 // We can't call this in the constructor because the derived class is
262 // uninitialized at that time.
263 if (!HasSetupMF) {
264 HasSetupMF = true;
265 setupMF(mf&: MF, vt: VT);
266 }
267
268 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
269
270 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
271
272 bool MFChanged = false;
273 bool Changed;
274
275 unsigned Iteration = 0;
276 while (true) {
277 ++Iteration;
278 LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n');
279
280 Changed = false;
281 WorkList.clear();
282 WLObserver->reset();
283 ObserverWrapper->clearObservers();
284 if (CSEInfo)
285 ObserverWrapper->addObserver(O: CSEInfo);
286
287 // If Observer-based DCE is enabled, perform full DCE only before the first
288 // iteration.
289 bool EnableDCE = CInfo.ObserverLvl >= CombinerInfo::ObserverLevel::DCE
290 ? CInfo.EnableFullDCE && Iteration == 1
291 : CInfo.EnableFullDCE;
292
293 // Collect all instructions. Do a post order traversal for basic blocks and
294 // insert with list bottom up, so while we pop_back_val, we'll traverse top
295 // down RPOT.
296 RAIIMFObsDelInstaller DelInstall(MF, *ObserverWrapper);
297 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
298 for (MachineInstr &CurMI :
299 llvm::make_early_inc_range(Range: llvm::reverse(C&: *MBB))) {
300 // Erase dead insts before even adding to the list.
301 if (EnableDCE && tryDCE(MI&: CurMI, MRI))
302 continue;
303 WorkList.deferred_insert(I: &CurMI);
304 }
305 }
306 WorkList.finalize();
307
308 // Only notify WLObserver during actual combines
309 ObserverWrapper->addObserver(O: WLObserver.get());
310 // Main Loop. Process the instructions here.
311 while (!WorkList.empty()) {
312 MachineInstr &CurrInst = *WorkList.pop_back_val();
313 LLVM_DEBUG(dbgs() << "\nTry combining " << CurrInst);
314 bool AppliedCombine = tryCombineAll(I&: CurrInst);
315 LLVM_DEBUG(WLObserver->reportFullyCreatedInstrs());
316 Changed |= AppliedCombine;
317 if (AppliedCombine)
318 WLObserver->appliedCombine();
319 }
320 MFChanged |= Changed;
321
322 if (!Changed) {
323 LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #"
324 << Iteration << '\n');
325 break;
326 }
327 // Iterate until a fixed-point is reached if MaxIterations == 0,
328 // otherwise limit the number of iterations.
329 if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) {
330 LLVM_DEBUG(
331 dbgs() << "\nCombiner reached iteration limit after iteration #"
332 << Iteration << '\n');
333 break;
334 }
335 }
336
337 if (Iteration == 1)
338 ++NumOneIteration;
339 else if (Iteration == 2)
340 ++NumTwoIterations;
341 else
342 ++NumThreeOrMoreIterations;
343
344#ifndef NDEBUG
345 if (CSEInfo) {
346 if (auto E = CSEInfo->verify()) {
347 errs() << E << '\n';
348 assert(false && "CSEInfo is not consistent. Likely missing calls to "
349 "observer on mutations.");
350 }
351 }
352#endif
353 return MFChanged;
354}
355