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