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/CodeGen/GlobalISel/CSEInfo.h" 16 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h" 17 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h" 18 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 19 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h" 20 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 21 #include "llvm/CodeGen/GlobalISel/Utils.h" 22 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 23 #include "llvm/Support/Debug.h" 24 25 #define DEBUG_TYPE "gi-combiner" 26 27 using namespace llvm; 28 29 namespace llvm { 30 cl::OptionCategory GICombinerOptionCategory( 31 "GlobalISel Combiner", 32 "Control the rules which are enabled. These options all take a comma " 33 "separated list of rules to disable and may be specified by number " 34 "or number range (e.g. 1-10)." 35 #ifndef NDEBUG 36 " They may also be specified by name." 37 #endif 38 ); 39 } // end namespace llvm 40 41 namespace { 42 /// This class acts as the glue the joins the CombinerHelper to the overall 43 /// Combine algorithm. The CombinerHelper is intended to report the 44 /// modifications it makes to the MIR to the GISelChangeObserver and the 45 /// observer subclass will act on these events. In this case, instruction 46 /// erasure will cancel any future visits to the erased instruction and 47 /// instruction creation will schedule that instruction for a future visit. 48 /// Other Combiner implementations may require more complex behaviour from 49 /// their GISelChangeObserver subclass. 50 class WorkListMaintainer : public GISelChangeObserver { 51 using WorkListTy = GISelWorkList<512>; 52 WorkListTy &WorkList; 53 /// The instructions that have been created but we want to report once they 54 /// have their operands. This is only maintained if debug output is requested. 55 SmallPtrSet<const MachineInstr *, 4> CreatedInstrs; 56 57 public: 58 WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {} 59 virtual ~WorkListMaintainer() = default; 60 61 void erasingInstr(MachineInstr &MI) override { 62 LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n"); 63 WorkList.remove(&MI); 64 } 65 void createdInstr(MachineInstr &MI) override { 66 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n"); 67 WorkList.insert(&MI); 68 LLVM_DEBUG(CreatedInstrs.insert(&MI)); 69 } 70 void changingInstr(MachineInstr &MI) override { 71 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n"); 72 WorkList.insert(&MI); 73 } 74 void changedInstr(MachineInstr &MI) override { 75 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n"); 76 WorkList.insert(&MI); 77 } 78 79 void reportFullyCreatedInstrs() { 80 LLVM_DEBUG(for (const auto *MI 81 : CreatedInstrs) { 82 dbgs() << "Created: "; 83 MI->print(dbgs()); 84 }); 85 LLVM_DEBUG(CreatedInstrs.clear()); 86 } 87 }; 88 } 89 90 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC) 91 : CInfo(Info), TPC(TPC) { 92 (void)this->TPC; // FIXME: Remove when used. 93 } 94 95 bool Combiner::combineMachineInstrs(MachineFunction &MF, 96 GISelCSEInfo *CSEInfo) { 97 // If the ISel pipeline failed, do not bother running this pass. 98 // FIXME: Should this be here or in individual combiner passes. 99 if (MF.getProperties().hasProperty( 100 MachineFunctionProperties::Property::FailedISel)) 101 return false; 102 103 Builder = 104 CSEInfo ? std::make_unique<CSEMIRBuilder>() : std::make_unique<MachineIRBuilder>(); 105 MRI = &MF.getRegInfo(); 106 Builder->setMF(MF); 107 if (CSEInfo) 108 Builder->setCSEInfo(CSEInfo); 109 110 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n'); 111 112 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 113 114 bool MFChanged = false; 115 bool Changed; 116 MachineIRBuilder &B = *Builder; 117 118 do { 119 // Collect all instructions. Do a post order traversal for basic blocks and 120 // insert with list bottom up, so while we pop_back_val, we'll traverse top 121 // down RPOT. 122 Changed = false; 123 GISelWorkList<512> WorkList; 124 WorkListMaintainer Observer(WorkList); 125 GISelObserverWrapper WrapperObserver(&Observer); 126 if (CSEInfo) 127 WrapperObserver.addObserver(CSEInfo); 128 RAIIDelegateInstaller DelInstall(MF, &WrapperObserver); 129 for (MachineBasicBlock *MBB : post_order(&MF)) { 130 for (MachineInstr &CurMI : 131 llvm::make_early_inc_range(llvm::reverse(*MBB))) { 132 // Erase dead insts before even adding to the list. 133 if (isTriviallyDead(CurMI, *MRI)) { 134 LLVM_DEBUG(dbgs() << CurMI << "Is dead; erasing.\n"); 135 CurMI.eraseFromParent(); 136 continue; 137 } 138 WorkList.deferred_insert(&CurMI); 139 } 140 } 141 WorkList.finalize(); 142 // Main Loop. Process the instructions here. 143 while (!WorkList.empty()) { 144 MachineInstr *CurrInst = WorkList.pop_back_val(); 145 LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;); 146 Changed |= CInfo.combine(WrapperObserver, *CurrInst, B); 147 Observer.reportFullyCreatedInstrs(); 148 } 149 MFChanged |= Changed; 150 } while (Changed); 151 152 #ifndef NDEBUG 153 if (CSEInfo) { 154 if (auto E = CSEInfo->verify()) { 155 errs() << E << '\n'; 156 assert(false && "CSEInfo is not consistent. Likely missing calls to " 157 "observer on mutations."); 158 } 159 } 160 #endif 161 return MFChanged; 162 } 163