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
29 using namespace llvm;
30
31 STATISTIC(NumOneIteration, "Number of functions with one iteration");
32 STATISTIC(NumTwoIterations, "Number of functions with two iterations");
33 STATISTIC(NumThreeOrMoreIterations,
34 "Number of functions with three or more iterations");
35
36 namespace llvm {
37 cl::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 the 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. In this case, instruction
52 /// erasure will cancel any future visits to the erased instruction and
53 /// instruction creation will schedule that instruction for a future visit.
54 /// Other Combiner implementations may require more complex behaviour from
55 /// their GISelChangeObserver subclass.
56 class Combiner::WorkListMaintainer : public GISelChangeObserver {
57 using WorkListTy = GISelWorkList<512>;
58 WorkListTy &WorkList;
59 /// The instructions that have been created but we want to report once they
60 /// have their operands. This is only maintained if debug output is requested.
61 #ifndef NDEBUG
62 SetVector<const MachineInstr *> CreatedInstrs;
63 #endif
64
65 public:
WorkListMaintainer(WorkListTy & WorkList)66 WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {}
67 virtual ~WorkListMaintainer() = default;
68
erasingInstr(MachineInstr & MI)69 void erasingInstr(MachineInstr &MI) override {
70 LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n");
71 WorkList.remove(&MI);
72 }
createdInstr(MachineInstr & MI)73 void createdInstr(MachineInstr &MI) override {
74 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
75 WorkList.insert(&MI);
76 LLVM_DEBUG(CreatedInstrs.insert(&MI));
77 }
changingInstr(MachineInstr & MI)78 void changingInstr(MachineInstr &MI) override {
79 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
80 WorkList.insert(&MI);
81 }
changedInstr(MachineInstr & MI)82 void changedInstr(MachineInstr &MI) override {
83 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
84 WorkList.insert(&MI);
85 }
86
reportFullyCreatedInstrs()87 void reportFullyCreatedInstrs() {
88 LLVM_DEBUG(for (const auto *MI
89 : CreatedInstrs) {
90 dbgs() << "Created: ";
91 MI->print(dbgs());
92 });
93 LLVM_DEBUG(CreatedInstrs.clear());
94 }
95 };
96
Combiner(MachineFunction & MF,CombinerInfo & CInfo,const TargetPassConfig * TPC,GISelKnownBits * KB,GISelCSEInfo * CSEInfo)97 Combiner::Combiner(MachineFunction &MF, CombinerInfo &CInfo,
98 const TargetPassConfig *TPC, GISelKnownBits *KB,
99 GISelCSEInfo *CSEInfo)
100 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()
101 : std::make_unique<MachineIRBuilder>()),
102 WLObserver(std::make_unique<WorkListMaintainer>(WorkList)),
103 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),
104 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),
105 KB(KB), TPC(TPC), CSEInfo(CSEInfo) {
106 (void)this->TPC; // FIXME: Remove when used.
107
108 // Setup builder.
109 B.setMF(MF);
110 if (CSEInfo)
111 B.setCSEInfo(CSEInfo);
112
113 // Setup observer.
114 ObserverWrapper->addObserver(WLObserver.get());
115 if (CSEInfo)
116 ObserverWrapper->addObserver(CSEInfo);
117
118 B.setChangeObserver(*ObserverWrapper);
119 }
120
121 Combiner::~Combiner() = default;
122
combineMachineInstrs()123 bool Combiner::combineMachineInstrs() {
124 // If the ISel pipeline failed, do not bother running this pass.
125 // FIXME: Should this be here or in individual combiner passes.
126 if (MF.getProperties().hasProperty(
127 MachineFunctionProperties::Property::FailedISel))
128 return false;
129
130 // We can't call this in the constructor because the derived class is
131 // uninitialized at that time.
132 if (!HasSetupMF) {
133 HasSetupMF = true;
134 setupMF(MF, KB);
135 }
136
137 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
138
139 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
140
141 bool MFChanged = false;
142 bool Changed;
143
144 unsigned Iteration = 0;
145 while (true) {
146 ++Iteration;
147 LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n');
148
149 WorkList.clear();
150
151 // Collect all instructions. Do a post order traversal for basic blocks and
152 // insert with list bottom up, so while we pop_back_val, we'll traverse top
153 // down RPOT.
154 Changed = false;
155
156 RAIIDelegateInstaller DelInstall(MF, ObserverWrapper.get());
157 for (MachineBasicBlock *MBB : post_order(&MF)) {
158 for (MachineInstr &CurMI :
159 llvm::make_early_inc_range(llvm::reverse(*MBB))) {
160 // Erase dead insts before even adding to the list.
161 if (isTriviallyDead(CurMI, MRI)) {
162 LLVM_DEBUG(dbgs() << CurMI << "Is dead; erasing.\n");
163 llvm::salvageDebugInfo(MRI, CurMI);
164 CurMI.eraseFromParent();
165 continue;
166 }
167 WorkList.deferred_insert(&CurMI);
168 }
169 }
170 WorkList.finalize();
171 // Main Loop. Process the instructions here.
172 while (!WorkList.empty()) {
173 MachineInstr *CurrInst = WorkList.pop_back_val();
174 LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
175 Changed |= tryCombineAll(*CurrInst);
176 WLObserver->reportFullyCreatedInstrs();
177 }
178 MFChanged |= Changed;
179
180 if (!Changed) {
181 LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #"
182 << Iteration << '\n');
183 break;
184 }
185 // Iterate until a fixed-point is reached if MaxIterations == 0,
186 // otherwise limit the number of iterations.
187 if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) {
188 LLVM_DEBUG(
189 dbgs() << "\nCombiner reached iteration limit after iteration #"
190 << Iteration << '\n');
191 break;
192 }
193 }
194
195 if (Iteration == 1)
196 ++NumOneIteration;
197 else if (Iteration == 2)
198 ++NumTwoIterations;
199 else
200 ++NumThreeOrMoreIterations;
201
202 #ifndef NDEBUG
203 if (CSEInfo) {
204 if (auto E = CSEInfo->verify()) {
205 errs() << E << '\n';
206 assert(false && "CSEInfo is not consistent. Likely missing calls to "
207 "observer on mutations.");
208 }
209 }
210 #endif
211 return MFChanged;
212 }
213