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 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. 52 class Combiner::WorkListMaintainer : public GISelChangeObserver { 53 protected: 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 61 public: 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. 83 template <CombinerInfo::ObserverLevel Lvl> 84 class 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 94 public: 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(&MI); 109 if constexpr (Lvl != Level::Basic) { 110 DeferList.remove(&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(&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(&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(&MI); 140 else 141 // Defer this for DCE 142 DeferList.insert(&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(&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(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(*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(Use)) 181 WorkList.insert(&*MRI.use_instr_nodbg_begin(Use)); 182 183 WorkList.insert(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(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(DefReg)) { 202 WorkList.insert(&UseMI); 203 } 204 } 205 } 206 }; 207 208 std::unique_ptr<Combiner::WorkListMaintainer> 209 Combiner::WorkListMaintainer::create(Level Lvl, WorkListTy &WorkList, 210 MachineRegisterInfo &MRI) { 211 switch (Lvl) { 212 case Level::Basic: 213 return std::make_unique<WorkListMaintainerImpl<Level::Basic>>(WorkList, 214 MRI); 215 case Level::DCE: 216 return std::make_unique<WorkListMaintainerImpl<Level::DCE>>(WorkList, MRI); 217 case Level::SinglePass: 218 return std::make_unique<WorkListMaintainerImpl<Level::SinglePass>>(WorkList, 219 MRI); 220 default: 221 llvm_unreachable("Illegal ObserverLevel"); 222 } 223 } 224 225 Combiner::Combiner(MachineFunction &MF, CombinerInfo &CInfo, 226 const TargetPassConfig *TPC, GISelKnownBits *KB, 227 GISelCSEInfo *CSEInfo) 228 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>() 229 : std::make_unique<MachineIRBuilder>()), 230 WLObserver(WorkListMaintainer::create(CInfo.ObserverLvl, WorkList, 231 MF.getRegInfo())), 232 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo), 233 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()), 234 KB(KB), TPC(TPC), CSEInfo(CSEInfo) { 235 (void)this->TPC; // FIXME: Remove when used. 236 237 // Setup builder. 238 B.setMF(MF); 239 if (CSEInfo) 240 B.setCSEInfo(CSEInfo); 241 242 B.setChangeObserver(*ObserverWrapper); 243 } 244 245 Combiner::~Combiner() = default; 246 247 bool Combiner::tryDCE(MachineInstr &MI, MachineRegisterInfo &MRI) { 248 if (!isTriviallyDead(MI, MRI)) 249 return false; 250 LLVM_DEBUG(dbgs() << "Dead: " << MI); 251 llvm::salvageDebugInfo(MRI, MI); 252 MI.eraseFromParent(); 253 return true; 254 } 255 256 bool Combiner::combineMachineInstrs() { 257 // If the ISel pipeline failed, do not bother running this pass. 258 // FIXME: Should this be here or in individual combiner passes. 259 if (MF.getProperties().hasProperty( 260 MachineFunctionProperties::Property::FailedISel)) 261 return false; 262 263 // We can't call this in the constructor because the derived class is 264 // uninitialized at that time. 265 if (!HasSetupMF) { 266 HasSetupMF = true; 267 setupMF(MF, KB); 268 } 269 270 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n'); 271 272 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 273 274 bool MFChanged = false; 275 bool Changed; 276 277 unsigned Iteration = 0; 278 while (true) { 279 ++Iteration; 280 LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n'); 281 282 Changed = false; 283 WorkList.clear(); 284 WLObserver->reset(); 285 ObserverWrapper->clearObservers(); 286 if (CSEInfo) 287 ObserverWrapper->addObserver(CSEInfo); 288 289 // If Observer-based DCE is enabled, perform full DCE only before the first 290 // iteration. 291 bool EnableDCE = CInfo.ObserverLvl >= CombinerInfo::ObserverLevel::DCE 292 ? CInfo.EnableFullDCE && Iteration == 1 293 : CInfo.EnableFullDCE; 294 295 // Collect all instructions. Do a post order traversal for basic blocks and 296 // insert with list bottom up, so while we pop_back_val, we'll traverse top 297 // down RPOT. 298 RAIIMFObsDelInstaller DelInstall(MF, *ObserverWrapper); 299 for (MachineBasicBlock *MBB : post_order(&MF)) { 300 for (MachineInstr &CurMI : 301 llvm::make_early_inc_range(llvm::reverse(*MBB))) { 302 // Erase dead insts before even adding to the list. 303 if (EnableDCE && tryDCE(CurMI, MRI)) 304 continue; 305 WorkList.deferred_insert(&CurMI); 306 } 307 } 308 WorkList.finalize(); 309 310 // Only notify WLObserver during actual combines 311 ObserverWrapper->addObserver(WLObserver.get()); 312 // Main Loop. Process the instructions here. 313 while (!WorkList.empty()) { 314 MachineInstr &CurrInst = *WorkList.pop_back_val(); 315 LLVM_DEBUG(dbgs() << "\nTry combining " << CurrInst); 316 bool AppliedCombine = tryCombineAll(CurrInst); 317 LLVM_DEBUG(WLObserver->reportFullyCreatedInstrs()); 318 Changed |= AppliedCombine; 319 if (AppliedCombine) 320 WLObserver->appliedCombine(); 321 } 322 MFChanged |= Changed; 323 324 if (!Changed) { 325 LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #" 326 << Iteration << '\n'); 327 break; 328 } 329 // Iterate until a fixed-point is reached if MaxIterations == 0, 330 // otherwise limit the number of iterations. 331 if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) { 332 LLVM_DEBUG( 333 dbgs() << "\nCombiner reached iteration limit after iteration #" 334 << Iteration << '\n'); 335 break; 336 } 337 } 338 339 if (Iteration == 1) 340 ++NumOneIteration; 341 else if (Iteration == 2) 342 ++NumTwoIterations; 343 else 344 ++NumThreeOrMoreIterations; 345 346 #ifndef NDEBUG 347 if (CSEInfo) { 348 if (auto E = CSEInfo->verify()) { 349 errs() << E << '\n'; 350 assert(false && "CSEInfo is not consistent. Likely missing calls to " 351 "observer on mutations."); 352 } 353 } 354 #endif 355 return MFChanged; 356 } 357