355 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file constains common code to combine machine functions at generic10// 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 29using namespace llvm;30 31STATISTIC(NumOneIteration, "Number of functions with one iteration");32STATISTIC(NumTwoIterations, "Number of functions with two iterations");33STATISTIC(NumThreeOrMoreIterations,34 "Number of functions with three or more iterations");35 36namespace llvm {37cl::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 NDEBUG43 " They may also be specified by name."44#endif45);46} // end namespace llvm47 48/// This class acts as the glue that joins the CombinerHelper to the overall49/// Combine algorithm. The CombinerHelper is intended to report the50/// modifications it makes to the MIR to the GISelChangeObserver and the51/// observer subclass will act on these events.52class Combiner::WorkListMaintainer : public GISelChangeObserver {53protected:54#ifndef NDEBUG55 /// The instructions that have been created but we want to report once they56 /// have their operands. This is only maintained if debug output is requested.57 SmallSetVector<const MachineInstr *, 32> CreatedInstrs;58#endif59 using Level = CombinerInfo::ObserverLevel;60 61public:62 static std::unique_ptr<WorkListMaintainer>63 create(Level Lvl, WorkListTy &WorkList, MachineRegisterInfo &MRI);64 65 ~WorkListMaintainer() override = default;66 67 void reportFullyCreatedInstrs() {68 LLVM_DEBUG({69 for (auto *MI : CreatedInstrs) {70 dbgs() << "Created: " << *MI;71 }72 CreatedInstrs.clear();73 });74 }75 76 virtual void reset() = 0;77 virtual void appliedCombine() = 0;78};79 80/// A configurable WorkListMaintainer implementation.81/// The ObserverLevel determines how the WorkListMaintainer reacts to MIR82/// changes.83template <CombinerInfo::ObserverLevel Lvl>84class Combiner::WorkListMaintainerImpl : public Combiner::WorkListMaintainer {85 WorkListTy &WorkList;86 MachineRegisterInfo &MRI;87 88 // Defer handling these instructions until the combine finishes.89 SmallSetVector<MachineInstr *, 32> DeferList;90 91 // Track VRegs that (might) have lost a use.92 SmallSetVector<Register, 32> LostUses;93 94public:95 WorkListMaintainerImpl(WorkListTy &WorkList, MachineRegisterInfo &MRI)96 : WorkList(WorkList), MRI(MRI) {}97 98 ~WorkListMaintainerImpl() override = default;99 100 void reset() override {101 DeferList.clear();102 LostUses.clear();103 }104 105 void erasingInstr(MachineInstr &MI) override {106 // MI will become dangling, remove it from all lists.107 LLVM_DEBUG(dbgs() << "Erasing: " << MI; CreatedInstrs.remove(&MI));108 WorkList.remove(&MI);109 if constexpr (Lvl != Level::Basic) {110 DeferList.remove(&MI);111 noteLostUses(MI);112 }113 }114 115 void createdInstr(MachineInstr &MI) override {116 LLVM_DEBUG(dbgs() << "Creating: " << MI; CreatedInstrs.insert(&MI));117 if constexpr (Lvl == Level::Basic)118 WorkList.insert(&MI);119 else120 // Defer handling newly created instructions, because they don't have121 // operands yet. We also insert them into the WorkList in reverse122 // order so that they will be combined top down.123 DeferList.insert(&MI);124 }125 126 void changingInstr(MachineInstr &MI) override {127 LLVM_DEBUG(dbgs() << "Changing: " << MI);128 // Some uses might get dropped when MI is changed.129 // For now, overapproximate by assuming all uses will be dropped.130 // TODO: Is a more precise heuristic or manual tracking of use count131 // decrements worth it?132 if constexpr (Lvl != Level::Basic)133 noteLostUses(MI);134 }135 136 void changedInstr(MachineInstr &MI) override {137 LLVM_DEBUG(dbgs() << "Changed: " << MI);138 if constexpr (Lvl == Level::Basic)139 WorkList.insert(&MI);140 else141 // Defer this for DCE142 DeferList.insert(&MI);143 }144 145 // Only track changes during the combine and then walk the def/use-chains once146 // the combine is finished, because:147 // - instructions might have multiple defs during the combine.148 // - use counts aren't accurate during the combine.149 void appliedCombine() override {150 if constexpr (Lvl == Level::Basic)151 return;152 153 // DCE deferred instructions and add them to the WorkList bottom up.154 while (!DeferList.empty()) {155 MachineInstr &MI = *DeferList.pop_back_val();156 if (tryDCE(MI, MRI))157 continue;158 159 if constexpr (Lvl >= Level::SinglePass)160 addUsersToWorkList(MI);161 162 WorkList.insert(&MI);163 }164 165 // Handle instructions that have lost a user.166 while (!LostUses.empty()) {167 Register Use = LostUses.pop_back_val();168 MachineInstr *UseMI = MRI.getVRegDef(Use);169 if (!UseMI)170 continue;171 172 // If DCE succeeds, UseMI's uses are added back to LostUses by173 // erasingInstr.174 if (tryDCE(*UseMI, MRI))175 continue;176 177 if constexpr (Lvl >= Level::SinglePass) {178 // OneUse checks are relatively common, so we might be able to combine179 // the single remaining user of this Reg.180 if (MRI.hasOneNonDBGUser(Use))181 WorkList.insert(&*MRI.use_instr_nodbg_begin(Use));182 183 WorkList.insert(UseMI);184 }185 }186 }187 188 void noteLostUses(MachineInstr &MI) {189 for (auto &Use : MI.explicit_uses()) {190 if (!Use.isReg() || !Use.getReg().isVirtual())191 continue;192 LostUses.insert(Use.getReg());193 }194 }195 196 void addUsersToWorkList(MachineInstr &MI) {197 for (auto &Def : MI.defs()) {198 Register DefReg = Def.getReg();199 if (!DefReg.isVirtual())200 continue;201 for (auto &UseMI : MRI.use_nodbg_instructions(DefReg)) {202 WorkList.insert(&UseMI);203 }204 }205 }206};207 208std::unique_ptr<Combiner::WorkListMaintainer>209Combiner::WorkListMaintainer::create(Level Lvl, WorkListTy &WorkList,210 MachineRegisterInfo &MRI) {211 switch (Lvl) {212 case Level::Basic:213 return std::make_unique<WorkListMaintainerImpl<Level::Basic>>(WorkList,214 MRI);215 case Level::DCE:216 return std::make_unique<WorkListMaintainerImpl<Level::DCE>>(WorkList, MRI);217 case Level::SinglePass:218 return std::make_unique<WorkListMaintainerImpl<Level::SinglePass>>(WorkList,219 MRI);220 }221 llvm_unreachable("Illegal ObserverLevel");222}223 224Combiner::Combiner(MachineFunction &MF, CombinerInfo &CInfo,225 const TargetPassConfig *TPC, GISelValueTracking *VT,226 GISelCSEInfo *CSEInfo)227 : Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()228 : std::make_unique<MachineIRBuilder>()),229 WLObserver(WorkListMaintainer::create(CInfo.ObserverLvl, WorkList,230 MF.getRegInfo())),231 ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),232 Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),233 VT(VT), TPC(TPC), CSEInfo(CSEInfo) {234 (void)this->TPC; // FIXME: Remove when used.235 236 // Setup builder.237 B.setMF(MF);238 if (CSEInfo)239 B.setCSEInfo(CSEInfo);240 241 B.setChangeObserver(*ObserverWrapper);242}243 244Combiner::~Combiner() = default;245 246bool Combiner::tryDCE(MachineInstr &MI, MachineRegisterInfo &MRI) {247 if (!isTriviallyDead(MI, MRI))248 return false;249 LLVM_DEBUG(dbgs() << "Dead: " << MI);250 llvm::salvageDebugInfo(MRI, MI);251 MI.eraseFromParent();252 return true;253}254 255bool Combiner::combineMachineInstrs() {256 // If the ISel pipeline failed, do not bother running this pass.257 // FIXME: Should this be here or in individual combiner passes.258 if (MF.getProperties().hasFailedISel())259 return false;260 261 // We can't call this in the constructor because the derived class is262 // uninitialized at that time.263 if (!HasSetupMF) {264 HasSetupMF = true;265 setupMF(MF, VT);266 }267 268 LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');269 270 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);271 272 bool MFChanged = false;273 bool Changed;274 275 unsigned Iteration = 0;276 while (true) {277 ++Iteration;278 LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n');279 280 Changed = false;281 WorkList.clear();282 WLObserver->reset();283 ObserverWrapper->clearObservers();284 if (CSEInfo)285 ObserverWrapper->addObserver(CSEInfo);286 287 // If Observer-based DCE is enabled, perform full DCE only before the first288 // iteration.289 bool EnableDCE = CInfo.ObserverLvl >= CombinerInfo::ObserverLevel::DCE290 ? CInfo.EnableFullDCE && Iteration == 1291 : CInfo.EnableFullDCE;292 293 // Collect all instructions. Do a post order traversal for basic blocks and294 // insert with list bottom up, so while we pop_back_val, we'll traverse top295 // down RPOT.296 RAIIMFObsDelInstaller DelInstall(MF, *ObserverWrapper);297 for (MachineBasicBlock *MBB : post_order(&MF)) {298 for (MachineInstr &CurMI :299 llvm::make_early_inc_range(llvm::reverse(*MBB))) {300 // Erase dead insts before even adding to the list.301 if (EnableDCE && tryDCE(CurMI, MRI))302 continue;303 WorkList.deferred_insert(&CurMI);304 }305 }306 WorkList.finalize();307 308 // Only notify WLObserver during actual combines309 ObserverWrapper->addObserver(WLObserver.get());310 // Main Loop. Process the instructions here.311 while (!WorkList.empty()) {312 MachineInstr &CurrInst = *WorkList.pop_back_val();313 LLVM_DEBUG(dbgs() << "\nTry combining " << CurrInst);314 bool AppliedCombine = tryCombineAll(CurrInst);315 LLVM_DEBUG(WLObserver->reportFullyCreatedInstrs());316 Changed |= AppliedCombine;317 if (AppliedCombine)318 WLObserver->appliedCombine();319 }320 MFChanged |= Changed;321 322 if (!Changed) {323 LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #"324 << Iteration << '\n');325 break;326 }327 // Iterate until a fixed-point is reached if MaxIterations == 0,328 // otherwise limit the number of iterations.329 if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) {330 LLVM_DEBUG(331 dbgs() << "\nCombiner reached iteration limit after iteration #"332 << Iteration << '\n');333 break;334 }335 }336 337 if (Iteration == 1)338 ++NumOneIteration;339 else if (Iteration == 2)340 ++NumTwoIterations;341 else342 ++NumThreeOrMoreIterations;343 344#ifndef NDEBUG345 if (CSEInfo) {346 if (auto E = CSEInfo->verify()) {347 errs() << E << '\n';348 assert(false && "CSEInfo is not consistent. Likely missing calls to "349 "observer on mutations.");350 }351 }352#endif353 return MFChanged;354}355