llvm/lib/Target/Hexagon/HexagonAggressiveRDFCopy.cpp - llvm-project - Git at Google


            
            //===--- HexagonAggressiveRDFCopy.cpp -------------------------------------===//

            
            //

            
            // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

            
            // See https://llvm.org/LICENSE.txt for license information.

            
            // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

            
            //

            
            //===----------------------------------------------------------------------===//

            
            //

            
            // RDF-based aggressive copy propagation.

            
            //

            
            // This optimization extends the standard RDF copy propagation with support for

            
            // super-register and sub-register copy propagation. It determines candidates

            
            // for copy propagation by verifying that both the copy instruction and all

            
            // reached uses have the same reaching definitions for the source register(s).

            
            //

            
            // Key differences:

            
            // 1. Super-register handling: Can propagate copies involving super-registers

            
            //    and their sub-registers (e.g., double-register pairs on Hexagon).

            
            // 2. Sub-register coverage: Verifies that all sub-registers of the source

            
            //    register have consistent reaching definitions before propagating.

            
            // 3. Combine instruction support: Handles A2_combinew instructions that

            
            //    combine two 32-bit registers into a 64-bit register pair.

            
            //

            
            // Algorithm:

            
            // 1. Scan all basic blocks in dominator tree order, maintaining a stack of

            
            //    reaching definitions for each register.

            
            // 2. For each copy instruction:

            
            //    a. Record the copy and its source/destination register mapping.

            
            //    b. Find the reaching definition for the source register at the copy.

            
            //    c. For each use reached by the copy's destination register:

            
            //       - Check if all sub-registers of the source have the same reaching

            
            //         definition at both the copy and the use.

            
            //       - If yes, mark the use as replaceable.

            
            // 3. Replace all marked uses with the source register of the copy.

            
            //

            
            // Example:

            
            //   BB1:

            
            //     R1 = ...                    // Def1

            
            //     D0 = A2_combinew R1, R0     // Copy: D0 = {R1, R0}

            
            //     ... = D0                    // Use of D0

            
            //

            
            // If R1 and R0 have the same reaching definitions at both the copy and the

            
            // use, the use of D0 can be replaced with the original source registers.

            
            // D0 is super-register corresponding to R1:0.

            
            //

            
            //===----------------------------------------------------------------------===//


            #include "HexagonAggressiveRDFCopy.h"

            
            #include "llvm/CodeGen/MachineDominators.h"

            
            #include "llvm/CodeGen/MachineInstr.h"

            
            #include "llvm/CodeGen/MachineOperand.h"

            
            #include "llvm/CodeGen/RDFGraph.h"

            
            #include "llvm/CodeGen/RDFLiveness.h"

            
            #include "llvm/CodeGen/RDFRegisters.h"

            
            #include "llvm/CodeGen/TargetInstrInfo.h"

            
            #include "llvm/CodeGen/TargetOpcodes.h"

            
            #include "llvm/CodeGen/TargetRegisterInfo.h"

            
            #include "llvm/MC/MCRegisterInfo.h"

            
            #include "llvm/Support/CommandLine.h"

            
            #include "llvm/Support/Debug.h"

            
            #include "llvm/Support/ErrorHandling.h"

            
            #include "llvm/Support/raw_ostream.h"


            #include <cassert>

            
            #include <cstdint>

            
            #include <utility>


            using namespace llvm;

            
            using namespace rdf;


            #ifndef NDEBUG

            
            extern cl::opt<unsigned> RDFCpLimit;

            
            static unsigned RDFCpCount = 0;

            
            #endif


            // Record destination and source registers in EqualityMap

            
            // if this is a copy instruction

            
            bool AggressiveCopyPropagation::interpretAsCopy(const MachineInstr *MI,

            
                                                            EqualityMap &EM) {

            
              unsigned Opc = MI->getOpcode();

            
              switch (Opc) {

            
              case TargetOpcode::COPY: {

            
                const MachineOperand &Dst = MI->getOperand(0);

            
                const MachineOperand &Src = MI->getOperand(1);

            
                RegisterRef DstR = DFG.makeRegRef(Dst.getReg(), Dst.getSubReg());

            
                RegisterRef SrcR = DFG.makeRegRef(Src.getReg(), Src.getSubReg());

            
                assert(Register::isPhysicalRegister(DstR.Id));

            
                assert(Register::isPhysicalRegister(SrcR.Id));

            
                if (HRI.isFakeReg(DstR.Id) || HRI.isFakeReg(SrcR.Id))

            
                  return false;

            
                if (TRI.getMinimalPhysRegClass(DstR.Id) !=

            
                    TRI.getMinimalPhysRegClass(SrcR.Id))

            
                  return false;

            
                if (!DFG.isTracked(SrcR) || !DFG.isTracked(DstR))

            
                  return false;

            
                EM.insert(std::make_pair(DstR, SrcR));

            
                return true;

            
              }

            
              case TargetOpcode::REG_SEQUENCE:

            
                llvm_unreachable("Unexpected REG_SEQUENCE");

            
              }

            
              return false;

            
            }


            // Track instructions determined to be copies along with their uses.

            
            // The register, sub-register copy pairs are given by EqualityMap

            
            // Find the reaching def from DefM stack for source (LHS) registers in each

            
            // copy. ReachedUseToCopyMap stores each reached use (UseNode) of a copy along

            
            // with the copy DefNode and source register

            
            void AggressiveCopyPropagation::recordCopy(NodeAddr<StmtNode *> SA,

            
                                                       EqualityMap &EM) {

            
              if (trace())

            
                CopyMap.insert(std::make_pair(SA.Id, EM));


              // Find and store reaching def for each source register

            
              // EqualityMap should also contain subregs

            
              for (auto I : EM) {

            
                if (PRI.equal_to(I.first, I.second))

            
                  continue;

            
                NodeId RDefId = 0;

            
                auto FS = DefM.find(I.second.Id);

            
                if (FS != DefM.end() && !FS->second.empty()) {

            
                  auto Def = FS->second.top()->Addr->getRegRef(DFG);

            
                  // Avoid adding subreg as reaching def for superreg

            
                  if (Register::isPhysicalRegister(Def.Id) &&

            
                      TRI.isSuperRegister(Def.Id, I.second.Id))

            
                    continue;

            
                  RDefId = FS->second.top()->Id;

            
                }

            
                RDefMap[I.second][SA.Id] = RDefId;

            
              }

            
              for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {

            
                RegisterRef DR = DA.Addr->getRegRef(DFG);

            
                auto FR = EM.find(DR);

            
                if (FR == EM.end())

            
                  continue;

            
                // Iterate over DR and its subregisters

            
                // if present in EqualityMap, find its reached uses

            
                for (MCPhysReg SubDReg : TRI.subregs_inclusive(DR.Id)) {

            
                  auto SubDR = DFG.makeRegRef(SubDReg, 0);

            
                  auto FR = EM.find(SubDR);

            
                  if (FR == EM.end())

            
                    continue;

            
                  RegisterRef SR = FR->second;

            
                  // Redundant copy

            
                  if (PRI.equal_to(SubDR, SR))

            
                    continue;

            
                  for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {

            
                    auto UA = DFG.addr<UseNode *>(N);

            
                    NextN = UA.Addr->getSibling();

            
                    uint16_t F = UA.Addr->getFlags();

            
                    // Skip phi node uses

            
                    // Skip shadow uses. When shadow nodes are present, the register has

            
                    // multiple reaching defs.

            
                    if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed) ||

            
                        (F & NodeAttrs::Shadow))

            
                      continue;

            
                    if (!PRI.equal_to(UA.Addr->getRegRef(DFG), SubDR))

            
                      continue;

            
                    MachineOperand &Op = UA.Addr->getOp();

            
                    // Skip operand if def and use of a register happens in same instruction

            
                    if (Op.isTied())

            
                      continue;

            
                    if (ReachedUseToCopyMap.find(UA.Id) != ReachedUseToCopyMap.end())

            
                      llvm_unreachable("Multiple copy instructions reach this use");

            
                    ReachedUseToCopyMap.insert(

            
                        std::make_pair(UA.Id, std::make_pair(DA, SR)));

            
                  }

            
                }

            
              }

            
            }


            // Now that we can obtain reaching def for uses from DefM,

            
            // check that reaching defs for source register and subregisters at the use

            
            // instruction, are the same as reaching defs for the copy. Uses that satisfy

            
            // this check can be replaced with the source registers of the copy.

            
            void AggressiveCopyPropagation::recordReplacableUses(NodeAddr<InstrNode *> IA) {

            
              for (NodeAddr<UseNode *> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {

            
                // Check if any uses of the instruction are reached by a copy

            
                auto CopyUseIt = ReachedUseToCopyMap.find(UA.Id);

            
                if (CopyUseIt == ReachedUseToCopyMap.end())

            
                  continue;

            
                [[maybe_unused]] auto UseReg = UA.Addr->getRegRef(DFG);

            
                auto DA = CopyUseIt->second.first;

            
                auto SR = CopyUseIt->second.second;

            
                [[maybe_unused]] auto DefReg = DA.Addr->getRegRef(DFG);

            
                assert(PRI.equal_to(DefReg, UseReg));

            
                NodeAddr<InstrNode *> DefI = DA.Addr->getOwner(DFG);

            
                // Aggr of subregs that have same reaching def (at IA) as DefI

            
                RegisterAggr RRs(PRI);

            
                // Registers that need to be added as use nodes in updated IA

            
                SmallVector<RegisterRef, 4> UseRefs;

            
                for (MCPhysReg S : TRI.subregs_inclusive(SR.Id)) {

            
                  auto SRef = DFG.makeRegRef(S, 0);

            
                  NodeId RDefId = 0;

            
                  // If there is no reaching def for SRef at DefI,

            
                  // do not check if SRef can be propagated

            
                  auto RDefIt = RDefMap.find(SRef);

            
                  if (RDefIt == RDefMap.end())

            
                    continue;

            
                  auto DefIIt = RDefIt->second.find(DefI.Id);

            
                  if (DefIIt == RDefIt->second.end())

            
                    continue;

            
                  // If we already have reaching def for SRef at IA,

            
                  // use it instead of searching DefM.

            
                  auto IAIt = RDefIt->second.find(IA.Id);

            
                  if (IAIt != RDefIt->second.end()) {

            
                    RDefId = IAIt->second;

            
                  } else {

            
                    auto F = DefM.find(S);

            
                    if (F != DefM.end() && !F->second.empty()) {

            
                      auto Def = F->second.top()->Addr->getRegRef(DFG);

            
                      // Avoid adding subreg as reaching def for superreg

            
                      if (Register::isPhysicalRegister(Def.Id) &&

            
                          TRI.isSuperRegister(Def.Id, S))

            
                        continue;

            
                      RDefId = F->second.top()->Id;

            
                    }

            
                  }

            
                  // If reaching def for SRef at DefI is not same as IA,

            
                  // SRef can not propagated to IA.

            
                  if (DefIIt->second != RDefId)

            
                    continue;

            
                  RRs.insert(SRef);

            
                  UseRefs.push_back(SRef);

            
                  RDefIt->second[IA.Id] = RDefId;

            
                  // If registers or sub-registers that can be propagated cover SR,

            
                  // the use node is a candidate for copy propagation

            
                  if (RRs.hasCoverOf(SR))

            
                    break;

            
                }

            
                // Use node can be replaced with new use nodes created from UseRefs

            
                if (RRs.hasCoverOf(SR))

            
                  ReplacableUses.push_back(std::make_pair(UA, UseRefs));

            
              }

            
            }


            // Recursively process all children in the dominator tree.

            
            // Find copy instructions and reached uses that are candidates for propagation

            
            void AggressiveCopyPropagation::scanBlock(MachineBasicBlock *B) {

            
              NodeAddr<BlockNode *> BA = DFG.findBlock(B);

            
              DFG.markBlock(BA.Id, DefM);


              for (NodeAddr<InstrNode *> IA : BA.Addr->members(DFG)) {

            
                if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {

            
                  NodeAddr<StmtNode *> SA = IA;

            
                  EqualityMap EM(RegisterRefLess(DFG.getPRI()));

            
                  if (interpretAsCopy(SA.Addr->getCode(), EM))

            
                    recordCopy(SA, EM);

            
                  recordReplacableUses(IA);

            
                }

            
                DFG.pushAllDefs(IA, DefM);

            
              }


              MachineDomTreeNode *N = MDT.getNode(B);

            
              for (auto *I : *N)

            
                scanBlock(I->getBlock());


              DFG.releaseBlock(BA.Id, DefM);

            
              return;

            
            }


            bool AggressiveCopyPropagation::run() {

            
              scanBlock(MDT.getRootNode()->getBlock());


              if (trace()) {

            
                dbgs() << "Copies:\n";

            
                for (auto &C : CopyMap) {

            
                  dbgs() << "Instr: " << *DFG.addr<StmtNode *>(C.first).Addr->getCode();

            
                  dbgs() << "   eq: {";

            
                  for (auto J : C.second)

            
                    dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='

            
                           << Print<RegisterRef>(J.second, DFG);

            
                  dbgs() << " }\n";

            
                }

            
                dbgs() << "\nCopy def-use:\n";

            
                for (auto &U : ReachedUseToCopyMap) {

            
                  auto DA = U.second.first;

            
                  auto DefI = DA.Addr->getOwner(DFG);

            
                  auto UseI = DFG.addr<UseNode *>(U.first).Addr->getOwner(DFG);

            
                  dbgs() << "Copy def: " << *DFG.addr<StmtNode *>(DefI.Id).Addr->getCode();

            
                  dbgs() << "Copy use: " << *DFG.addr<StmtNode *>(UseI.Id).Addr->getCode();

            
                }

            
                dbgs() << "\nRDef map:\n";

            
                for (auto R : RDefMap) {

            
                  dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";

            
                  for (auto &M : R.second)

            
                    dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'

            
                           << Print<NodeId>(M.second, DFG);

            
                  dbgs() << " }\n";

            
                }

            
              }


              bool Changed = false;

            
            #ifndef NDEBUG

            
              bool HasLimit = RDFCpLimit.getNumOccurrences() > 0;

            
            #endif


              auto MinPhysReg = [this](RegisterRef RR) -> unsigned {

            
                const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Id);

            
                if ((RC.LaneMask & RR.Mask) == RC.LaneMask)

            
                  return RR.Id;

            
                for (MCSubRegIndexIterator S(RR.Id, &TRI); S.isValid(); ++S)

            
                  if (RR.Mask == TRI.getSubRegIndexLaneMask(S.getSubRegIndex()))

            
                    return S.getSubReg();

            
                llvm_unreachable("Should have found a register");

            
                return 0;

            
              };


              // Iterate over all candidate uses found and replace with source register of

            
              // copy

            
              for (auto P : ReplacableUses) {

            
            #ifndef NDEBUG

            
                if (HasLimit && RDFCpCount >= RDFCpLimit)

            
                  break;

            
            #endif

            
                NodeAddr<UseNode *> UA = P.first;

            
                SmallVector<RegisterRef, 4> UseRefs = P.second;


                // UseRefs should never be empty if RRs.hasCoverOf(SR) was true

            
                assert(!UseRefs.empty() &&

            
                       "UseRefs should not be empty for replaceable use");


                auto IA = UA.Addr->getOwner(DFG);

            
                auto DR = UA.Addr->getRegRef(DFG);

            
                auto SR = ReachedUseToCopyMap[UA.Id].second;

            
                if (HRI.isFakeReg(SR.Id))

            
                  continue;


                if (trace()) {

            
                  dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG) << " with "

            
                         << Print<RegisterRef>(SR, DFG) << " in "

            
                         << *NodeAddr<StmtNode *>(IA).Addr->getCode();

            
                }


                // Update existing use node to use the source register

            
                MachineOperand &Op = UA.Addr->getOp();

            
                unsigned NewReg = MinPhysReg(SR);

            
                Op.setReg(NewReg);

            
                Op.setSubReg(0);

            
                DFG.unlinkUse(UA, false);

            
                bool firstUseNode = true;


                for (auto UR : UseRefs) {

            
                  // If we have more than one use (such as multiple subregs),

            
                  // add a new shadow use node

            
                  if (!firstUseNode) {

            
                    UA.Addr->setFlags(UA.Addr->getFlags() | NodeAttrs::Shadow);

            
                    UA = DFG.getNextShadow(IA, UA, true);

            
                  }

            
                  if (RDefMap[UR][IA.Id] != 0) {

            
                    UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode *>(RDefMap[UR][IA.Id]));

            
                  } else {

            
                    // No reaching def present

            
                    UA.Addr->setReachingDef(0);

            
                    UA.Addr->setSibling(0);

            
                  }

            
                  firstUseNode = false;

            
                }


                Changed = true;

            
            #ifndef NDEBUG

            
                if (HasLimit && RDFCpCount >= RDFCpLimit)

            
                  break;

            
                RDFCpCount++;

            
            #endif


              } // for (UA in replacable uses)


              return Changed;

            
            }
	//===--- HexagonAggressiveRDFCopy.cpp -------------------------------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// RDF-based aggressive copy propagation.
	//
	// This optimization extends the standard RDF copy propagation with support for
	// super-register and sub-register copy propagation. It determines candidates
	// for copy propagation by verifying that both the copy instruction and all
	// reached uses have the same reaching definitions for the source register(s).
	//
	// Key differences:
	// 1. Super-register handling: Can propagate copies involving super-registers
	// and their sub-registers (e.g., double-register pairs on Hexagon).
	// 2. Sub-register coverage: Verifies that all sub-registers of the source
	// register have consistent reaching definitions before propagating.
	// 3. Combine instruction support: Handles A2_combinew instructions that
	// combine two 32-bit registers into a 64-bit register pair.
	//
	// Algorithm:
	// 1. Scan all basic blocks in dominator tree order, maintaining a stack of
	// reaching definitions for each register.
	// 2. For each copy instruction:
	// a. Record the copy and its source/destination register mapping.
	// b. Find the reaching definition for the source register at the copy.
	// c. For each use reached by the copy's destination register:
	// - Check if all sub-registers of the source have the same reaching
	// definition at both the copy and the use.
	// - If yes, mark the use as replaceable.
	// 3. Replace all marked uses with the source register of the copy.
	//
	// Example:
	// BB1:
	// R1 = ... // Def1
	// D0 = A2_combinew R1, R0 // Copy: D0 = {R1, R0}
	// ... = D0 // Use of D0
	//
	// If R1 and R0 have the same reaching definitions at both the copy and the
	// use, the use of D0 can be replaced with the original source registers.
	// D0 is super-register corresponding to R1:0.
	//
	//===----------------------------------------------------------------------===//

	#include "HexagonAggressiveRDFCopy.h"
	#include "llvm/CodeGen/MachineDominators.h"
	#include "llvm/CodeGen/MachineInstr.h"
	#include "llvm/CodeGen/MachineOperand.h"
	#include "llvm/CodeGen/RDFGraph.h"
	#include "llvm/CodeGen/RDFLiveness.h"
	#include "llvm/CodeGen/RDFRegisters.h"
	#include "llvm/CodeGen/TargetInstrInfo.h"
	#include "llvm/CodeGen/TargetOpcodes.h"
	#include "llvm/CodeGen/TargetRegisterInfo.h"
	#include "llvm/MC/MCRegisterInfo.h"
	#include "llvm/Support/CommandLine.h"
	#include "llvm/Support/Debug.h"
	#include "llvm/Support/ErrorHandling.h"
	#include "llvm/Support/raw_ostream.h"

	#include <cassert>
	#include <cstdint>
	#include <utility>

	using namespace llvm;
	using namespace rdf;

	#ifndef NDEBUG
	extern cl::opt<unsigned> RDFCpLimit;
	static unsigned RDFCpCount = 0;
	#endif

	// Record destination and source registers in EqualityMap
	// if this is a copy instruction
	bool AggressiveCopyPropagation::interpretAsCopy(const MachineInstr *MI,
	EqualityMap &EM) {
	unsigned Opc = MI->getOpcode();
	switch (Opc) {
	case TargetOpcode::COPY: {
	const MachineOperand &Dst = MI->getOperand(0);
	const MachineOperand &Src = MI->getOperand(1);
	RegisterRef DstR = DFG.makeRegRef(Dst.getReg(), Dst.getSubReg());
	RegisterRef SrcR = DFG.makeRegRef(Src.getReg(), Src.getSubReg());
	assert(Register::isPhysicalRegister(DstR.Id));
	assert(Register::isPhysicalRegister(SrcR.Id));
	if (HRI.isFakeReg(DstR.Id) \|\| HRI.isFakeReg(SrcR.Id))
	return false;
	if (TRI.getMinimalPhysRegClass(DstR.Id) !=
	TRI.getMinimalPhysRegClass(SrcR.Id))
	return false;
	if (!DFG.isTracked(SrcR) \|\| !DFG.isTracked(DstR))
	return false;
	EM.insert(std::make_pair(DstR, SrcR));
	return true;
	}
	case TargetOpcode::REG_SEQUENCE:
	llvm_unreachable("Unexpected REG_SEQUENCE");
	}
	return false;
	}

	// Track instructions determined to be copies along with their uses.
	// The register, sub-register copy pairs are given by EqualityMap
	// Find the reaching def from DefM stack for source (LHS) registers in each
	// copy. ReachedUseToCopyMap stores each reached use (UseNode) of a copy along
	// with the copy DefNode and source register
	void AggressiveCopyPropagation::recordCopy(NodeAddr<StmtNode *> SA,
	EqualityMap &EM) {
	if (trace())
	CopyMap.insert(std::make_pair(SA.Id, EM));

	// Find and store reaching def for each source register
	// EqualityMap should also contain subregs
	for (auto I : EM) {
	if (PRI.equal_to(I.first, I.second))
	continue;
	NodeId RDefId = 0;
	auto FS = DefM.find(I.second.Id);
	if (FS != DefM.end() && !FS->second.empty()) {
	auto Def = FS->second.top()->Addr->getRegRef(DFG);
	// Avoid adding subreg as reaching def for superreg
	if (Register::isPhysicalRegister(Def.Id) &&
	TRI.isSuperRegister(Def.Id, I.second.Id))
	continue;
	RDefId = FS->second.top()->Id;
	}
	RDefMap[I.second][SA.Id] = RDefId;
	}
	for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {
	RegisterRef DR = DA.Addr->getRegRef(DFG);
	auto FR = EM.find(DR);
	if (FR == EM.end())
	continue;
	// Iterate over DR and its subregisters
	// if present in EqualityMap, find its reached uses
	for (MCPhysReg SubDReg : TRI.subregs_inclusive(DR.Id)) {
	auto SubDR = DFG.makeRegRef(SubDReg, 0);
	auto FR = EM.find(SubDR);
	if (FR == EM.end())
	continue;
	RegisterRef SR = FR->second;
	// Redundant copy
	if (PRI.equal_to(SubDR, SR))
	continue;
	for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
	auto UA = DFG.addr<UseNode *>(N);
	NextN = UA.Addr->getSibling();
	uint16_t F = UA.Addr->getFlags();
	// Skip phi node uses
	// Skip shadow uses. When shadow nodes are present, the register has
	// multiple reaching defs.
	if ((F & NodeAttrs::PhiRef) \|\| (F & NodeAttrs::Fixed) \|\|
	(F & NodeAttrs::Shadow))
	continue;
	if (!PRI.equal_to(UA.Addr->getRegRef(DFG), SubDR))
	continue;
	MachineOperand &Op = UA.Addr->getOp();
	// Skip operand if def and use of a register happens in same instruction
	if (Op.isTied())
	continue;
	if (ReachedUseToCopyMap.find(UA.Id) != ReachedUseToCopyMap.end())
	llvm_unreachable("Multiple copy instructions reach this use");
	ReachedUseToCopyMap.insert(
	std::make_pair(UA.Id, std::make_pair(DA, SR)));
	}
	}
	}
	}

	// Now that we can obtain reaching def for uses from DefM,
	// check that reaching defs for source register and subregisters at the use
	// instruction, are the same as reaching defs for the copy. Uses that satisfy
	// this check can be replaced with the source registers of the copy.
	void AggressiveCopyPropagation::recordReplacableUses(NodeAddr<InstrNode *> IA) {
	for (NodeAddr<UseNode *> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
	// Check if any uses of the instruction are reached by a copy
	auto CopyUseIt = ReachedUseToCopyMap.find(UA.Id);
	if (CopyUseIt == ReachedUseToCopyMap.end())
	continue;
	[[maybe_unused]] auto UseReg = UA.Addr->getRegRef(DFG);
	auto DA = CopyUseIt->second.first;
	auto SR = CopyUseIt->second.second;
	[[maybe_unused]] auto DefReg = DA.Addr->getRegRef(DFG);
	assert(PRI.equal_to(DefReg, UseReg));
	NodeAddr<InstrNode *> DefI = DA.Addr->getOwner(DFG);
	// Aggr of subregs that have same reaching def (at IA) as DefI
	RegisterAggr RRs(PRI);
	// Registers that need to be added as use nodes in updated IA
	SmallVector<RegisterRef, 4> UseRefs;
	for (MCPhysReg S : TRI.subregs_inclusive(SR.Id)) {
	auto SRef = DFG.makeRegRef(S, 0);
	NodeId RDefId = 0;
	// If there is no reaching def for SRef at DefI,
	// do not check if SRef can be propagated
	auto RDefIt = RDefMap.find(SRef);
	if (RDefIt == RDefMap.end())
	continue;
	auto DefIIt = RDefIt->second.find(DefI.Id);
	if (DefIIt == RDefIt->second.end())
	continue;
	// If we already have reaching def for SRef at IA,
	// use it instead of searching DefM.
	auto IAIt = RDefIt->second.find(IA.Id);
	if (IAIt != RDefIt->second.end()) {
	RDefId = IAIt->second;
	} else {
	auto F = DefM.find(S);
	if (F != DefM.end() && !F->second.empty()) {
	auto Def = F->second.top()->Addr->getRegRef(DFG);
	// Avoid adding subreg as reaching def for superreg
	if (Register::isPhysicalRegister(Def.Id) &&
	TRI.isSuperRegister(Def.Id, S))
	continue;
	RDefId = F->second.top()->Id;
	}
	}
	// If reaching def for SRef at DefI is not same as IA,
	// SRef can not propagated to IA.
	if (DefIIt->second != RDefId)
	continue;
	RRs.insert(SRef);
	UseRefs.push_back(SRef);
	RDefIt->second[IA.Id] = RDefId;
	// If registers or sub-registers that can be propagated cover SR,
	// the use node is a candidate for copy propagation
	if (RRs.hasCoverOf(SR))
	break;
	}
	// Use node can be replaced with new use nodes created from UseRefs
	if (RRs.hasCoverOf(SR))
	ReplacableUses.push_back(std::make_pair(UA, UseRefs));
	}
	}

	// Recursively process all children in the dominator tree.
	// Find copy instructions and reached uses that are candidates for propagation
	void AggressiveCopyPropagation::scanBlock(MachineBasicBlock *B) {
	NodeAddr<BlockNode *> BA = DFG.findBlock(B);
	DFG.markBlock(BA.Id, DefM);

	for (NodeAddr<InstrNode *> IA : BA.Addr->members(DFG)) {
	if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
	NodeAddr<StmtNode *> SA = IA;
	EqualityMap EM(RegisterRefLess(DFG.getPRI()));
	if (interpretAsCopy(SA.Addr->getCode(), EM))
	recordCopy(SA, EM);
	recordReplacableUses(IA);
	}
	DFG.pushAllDefs(IA, DefM);
	}

	MachineDomTreeNode *N = MDT.getNode(B);
	for (auto I : N)
	scanBlock(I->getBlock());

	DFG.releaseBlock(BA.Id, DefM);
	return;
	}

	bool AggressiveCopyPropagation::run() {
	scanBlock(MDT.getRootNode()->getBlock());

	if (trace()) {
	dbgs() << "Copies:\n";
	for (auto &C : CopyMap) {
	dbgs() << "Instr: " << DFG.addr<StmtNode >(C.first).Addr->getCode();
	dbgs() << " eq: {";
	for (auto J : C.second)
	dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='
	<< Print<RegisterRef>(J.second, DFG);
	dbgs() << " }\n";
	}
	dbgs() << "\nCopy def-use:\n";
	for (auto &U : ReachedUseToCopyMap) {
	auto DA = U.second.first;
	auto DefI = DA.Addr->getOwner(DFG);
	auto UseI = DFG.addr<UseNode *>(U.first).Addr->getOwner(DFG);
	dbgs() << "Copy def: " << DFG.addr<StmtNode >(DefI.Id).Addr->getCode();
	dbgs() << "Copy use: " << DFG.addr<StmtNode >(UseI.Id).Addr->getCode();
	}
	dbgs() << "\nRDef map:\n";
	for (auto R : RDefMap) {
	dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
	for (auto &M : R.second)
	dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
	<< Print<NodeId>(M.second, DFG);
	dbgs() << " }\n";
	}
	}

	bool Changed = false;
	#ifndef NDEBUG
	bool HasLimit = RDFCpLimit.getNumOccurrences() > 0;
	#endif

	auto MinPhysReg = [this](RegisterRef RR) -> unsigned {
	const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Id);
	if ((RC.LaneMask & RR.Mask) == RC.LaneMask)
	return RR.Id;
	for (MCSubRegIndexIterator S(RR.Id, &TRI); S.isValid(); ++S)
	if (RR.Mask == TRI.getSubRegIndexLaneMask(S.getSubRegIndex()))
	return S.getSubReg();
	llvm_unreachable("Should have found a register");
	return 0;
	};

	// Iterate over all candidate uses found and replace with source register of
	// copy
	for (auto P : ReplacableUses) {
	#ifndef NDEBUG
	if (HasLimit && RDFCpCount >= RDFCpLimit)
	break;
	#endif
	NodeAddr<UseNode *> UA = P.first;
	SmallVector<RegisterRef, 4> UseRefs = P.second;

	// UseRefs should never be empty if RRs.hasCoverOf(SR) was true
	assert(!UseRefs.empty() &&
	"UseRefs should not be empty for replaceable use");

	auto IA = UA.Addr->getOwner(DFG);
	auto DR = UA.Addr->getRegRef(DFG);
	auto SR = ReachedUseToCopyMap[UA.Id].second;
	if (HRI.isFakeReg(SR.Id))
	continue;

	if (trace()) {
	dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG) << " with "
	<< Print<RegisterRef>(SR, DFG) << " in "
	<< NodeAddr<StmtNode >(IA).Addr->getCode();
	}

	// Update existing use node to use the source register
	MachineOperand &Op = UA.Addr->getOp();
	unsigned NewReg = MinPhysReg(SR);
	Op.setReg(NewReg);
	Op.setSubReg(0);
	DFG.unlinkUse(UA, false);
	bool firstUseNode = true;

	for (auto UR : UseRefs) {
	// If we have more than one use (such as multiple subregs),
	// add a new shadow use node
	if (!firstUseNode) {
	UA.Addr->setFlags(UA.Addr->getFlags() \| NodeAttrs::Shadow);
	UA = DFG.getNextShadow(IA, UA, true);
	}
	if (RDefMap[UR][IA.Id] != 0) {
	UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode *>(RDefMap[UR][IA.Id]));
	} else {
	// No reaching def present
	UA.Addr->setReachingDef(0);
	UA.Addr->setSibling(0);
	}
	firstUseNode = false;
	}

	Changed = true;
	#ifndef NDEBUG
	if (HasLimit && RDFCpCount >= RDFCpLimit)
	break;
	RDFCpCount++;
	#endif

	} // for (UA in replacable uses)

	return Changed;
	}