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 } 221 llvm_unreachable("Illegal ObserverLevel"); 222 } 223 224 Combiner::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(CInfo.ObserverLvl, WorkList, 230 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 244 Combiner::~Combiner() = default; 245 246 bool 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 255 bool 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, 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(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(&MF)) { 298 for (MachineInstr &CurMI : 299 llvm::make_early_inc_range(llvm::reverse(*MBB))) { 300 // Erase dead insts before even adding to the list. 301 if (EnableDCE && tryDCE(CurMI, MRI)) 302 continue; 303 WorkList.deferred_insert(&CurMI); 304 } 305 } 306 WorkList.finalize(); 307 308 // Only notify WLObserver during actual combines 309 ObserverWrapper->addObserver(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(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