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