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: 66 WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {} 67 virtual ~WorkListMaintainer() = default; 68 69 void erasingInstr(MachineInstr &MI) override { 70 LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n"); 71 WorkList.remove(&MI); 72 } 73 void createdInstr(MachineInstr &MI) override { 74 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n"); 75 WorkList.insert(&MI); 76 LLVM_DEBUG(CreatedInstrs.insert(&MI)); 77 } 78 void changingInstr(MachineInstr &MI) override { 79 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n"); 80 WorkList.insert(&MI); 81 } 82 void changedInstr(MachineInstr &MI) override { 83 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n"); 84 WorkList.insert(&MI); 85 } 86 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 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 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