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) 60 : GISelChangeObserver(), WorkList(WorkList) {} 61 virtual ~WorkListMaintainer() { 62 } 63 64 void erasingInstr(MachineInstr &MI) override { 65 LLVM_DEBUG(dbgs() << "Erasing: " << MI << "\n"); 66 WorkList.remove(&MI); 67 } 68 void createdInstr(MachineInstr &MI) override { 69 LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n"); 70 WorkList.insert(&MI); 71 LLVM_DEBUG(CreatedInstrs.insert(&MI)); 72 } 73 void changingInstr(MachineInstr &MI) override { 74 LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n"); 75 WorkList.insert(&MI); 76 } 77 void changedInstr(MachineInstr &MI) override { 78 LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n"); 79 WorkList.insert(&MI); 80 } 81 82 void reportFullyCreatedInstrs() { 83 LLVM_DEBUG(for (const auto *MI 84 : CreatedInstrs) { 85 dbgs() << "Created: "; 86 MI->print(dbgs()); 87 }); 88 LLVM_DEBUG(CreatedInstrs.clear()); 89 } 90 }; 91 } 92 93 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC) 94 : CInfo(Info), TPC(TPC) { 95 (void)this->TPC; // FIXME: Remove when used. 96 } 97 98 bool Combiner::combineMachineInstrs(MachineFunction &MF, 99 GISelCSEInfo *CSEInfo) { 100 // If the ISel pipeline failed, do not bother running this pass. 101 // FIXME: Should this be here or in individual combiner passes. 102 if (MF.getProperties().hasProperty( 103 MachineFunctionProperties::Property::FailedISel)) 104 return false; 105 106 Builder = 107 CSEInfo ? std::make_unique<CSEMIRBuilder>() : std::make_unique<MachineIRBuilder>(); 108 MRI = &MF.getRegInfo(); 109 Builder->setMF(MF); 110 if (CSEInfo) 111 Builder->setCSEInfo(CSEInfo); 112 113 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n'); 114 115 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 116 117 bool MFChanged = false; 118 bool Changed; 119 MachineIRBuilder &B = *Builder.get(); 120 121 do { 122 // Collect all instructions. Do a post order traversal for basic blocks and 123 // insert with list bottom up, so while we pop_back_val, we'll traverse top 124 // down RPOT. 125 Changed = false; 126 GISelWorkList<512> WorkList; 127 WorkListMaintainer Observer(WorkList); 128 GISelObserverWrapper WrapperObserver(&Observer); 129 if (CSEInfo) 130 WrapperObserver.addObserver(CSEInfo); 131 RAIIDelegateInstaller DelInstall(MF, &WrapperObserver); 132 for (MachineBasicBlock *MBB : post_order(&MF)) { 133 for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) { 134 MachineInstr *CurMI = &*MII; 135 ++MII; 136 // Erase dead insts before even adding to the list. 137 if (isTriviallyDead(*CurMI, *MRI)) { 138 LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n"); 139 CurMI->eraseFromParentAndMarkDBGValuesForRemoval(); 140 continue; 141 } 142 WorkList.deferred_insert(CurMI); 143 } 144 } 145 WorkList.finalize(); 146 // Main Loop. Process the instructions here. 147 while (!WorkList.empty()) { 148 MachineInstr *CurrInst = WorkList.pop_back_val(); 149 LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;); 150 Changed |= CInfo.combine(WrapperObserver, *CurrInst, B); 151 Observer.reportFullyCreatedInstrs(); 152 } 153 MFChanged |= Changed; 154 } while (Changed); 155 156 #ifndef NDEBUG 157 if (CSEInfo) { 158 if (auto E = CSEInfo->verify()) { 159 errs() << E << '\n'; 160 assert(false && "CSEInfo is not consistent. Likely missing calls to " 161 "observer on mutations."); 162 } 163 } 164 #endif 165 return MFChanged; 166 } 167