From 04a98e25aac0a853e7667a660518cd7949acd6d5 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Tue, 12 Jan 2016 17:23:48 +0000 Subject: [PATCH] RDF: Copy propagation This is a very limited implementation of DFG-based copy propagation. It only handles actual COPY instructions (does not handle other equivalents such as add-immediate with a 0 operand). The major limitation is that it does not update the DFG: that will be the change required to make it more robust (hopefully coming up soon). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257490 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/Hexagon/CMakeLists.txt | 1 + lib/Target/Hexagon/RDFCopy.cpp | 180 ++++++++++++++++++++++++++++++ lib/Target/Hexagon/RDFCopy.h | 48 ++++++++ 3 files changed, 229 insertions(+) create mode 100644 lib/Target/Hexagon/RDFCopy.cpp create mode 100644 lib/Target/Hexagon/RDFCopy.h diff --git a/lib/Target/Hexagon/CMakeLists.txt b/lib/Target/Hexagon/CMakeLists.txt index a9be39880fc..414aa6963b1 100644 --- a/lib/Target/Hexagon/CMakeLists.txt +++ b/lib/Target/Hexagon/CMakeLists.txt @@ -49,6 +49,7 @@ add_llvm_target(HexagonCodeGen HexagonTargetObjectFile.cpp HexagonTargetTransformInfo.cpp HexagonVLIWPacketizer.cpp + RDFCopy.cpp RDFDeadCode.cpp RDFGraph.cpp RDFLiveness.cpp diff --git a/lib/Target/Hexagon/RDFCopy.cpp b/lib/Target/Hexagon/RDFCopy.cpp new file mode 100644 index 00000000000..c547c719507 --- /dev/null +++ b/lib/Target/Hexagon/RDFCopy.cpp @@ -0,0 +1,180 @@ +//===--- RDFCopy.cpp ------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Simplistic RDF-based copy propagation. + +#include "RDFCopy.h" +#include "RDFGraph.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Support/CommandLine.h" + +#include + +#ifndef NDEBUG +static cl::opt CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden); +static unsigned CpCount = 0; +#endif + +using namespace llvm; +using namespace rdf; + +void CopyPropagation::recordCopy(NodeAddr SA, MachineInstr *MI) { + assert(MI->getOpcode() == TargetOpcode::COPY); + const MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1); + RegisterRef DstR = { Op0.getReg(), Op0.getSubReg() }; + RegisterRef SrcR = { Op1.getReg(), Op1.getSubReg() }; + auto FS = DefM.find(SrcR); + if (FS == DefM.end() || FS->second.empty()) + return; + Copies.push_back(SA.Id); + RDefMap[SrcR][SA.Id] = FS->second.top()->Id; + // Insert DstR into the map. + RDefMap[DstR]; +} + + +void CopyPropagation::updateMap(NodeAddr IA) { + RegisterSet RRs; + for (NodeAddr RA : IA.Addr->members(DFG)) + RRs.insert(RA.Addr->getRegRef()); + bool Common = false; + for (auto &R : RDefMap) { + if (!RRs.count(R.first)) + continue; + Common = true; + break; + } + if (!Common) + return; + + for (auto &R : RDefMap) { + if (!RRs.count(R.first)) + continue; + auto F = DefM.find(R.first); + if (F == DefM.end() || F->second.empty()) + continue; + R.second[IA.Id] = F->second.top()->Id; + } +} + + +bool CopyPropagation::scanBlock(MachineBasicBlock *B) { + bool Changed = false; + auto BA = DFG.getFunc().Addr->findBlock(B, DFG); + DFG.markBlock(BA.Id, DefM); + + for (NodeAddr IA : BA.Addr->members(DFG)) { + if (DFG.IsCode(IA)) { + NodeAddr SA = IA; + MachineInstr *MI = SA.Addr->getCode(); + if (MI->isCopy()) + recordCopy(SA, MI); + } + + updateMap(IA); + DFG.pushDefs(IA, DefM); + } + + MachineDomTreeNode *N = MDT.getNode(B); + for (auto I : *N) + Changed |= scanBlock(I->getBlock()); + + DFG.releaseBlock(BA.Id, DefM); + return Changed; +} + + +bool CopyPropagation::run() { + scanBlock(&DFG.getMF().front()); + + if (trace()) { + dbgs() << "Copies:\n"; + for (auto I : Copies) + dbgs() << *DFG.addr(I).Addr->getCode(); + dbgs() << "\nRDef map:\n"; + for (auto R : RDefMap) { + dbgs() << Print(R.first, DFG) << " -> {"; + for (auto &M : R.second) + dbgs() << ' ' << Print(M.first, DFG) << ':' + << Print(M.second, DFG); + dbgs() << " }\n"; + } + } + + bool Changed = false; + NodeSet Deleted; +#ifndef NDEBUG + bool HasLimit = CpLimit.getNumOccurrences() > 0; +#endif + + for (auto I : Copies) { +#ifndef NDEBUG + if (HasLimit && CpCount >= CpLimit) + break; +#endif + if (Deleted.count(I)) + continue; + auto SA = DFG.addr(I); + NodeList Ds = SA.Addr->members_if(DFG.IsDef, DFG); + if (Ds.size() != 1) + continue; + NodeAddr DA = Ds[0]; + RegisterRef DR0 = DA.Addr->getRegRef(); + NodeList Us = SA.Addr->members_if(DFG.IsUse, DFG); + if (Us.size() != 1) + continue; + NodeAddr UA0 = Us[0]; + RegisterRef UR0 = UA0.Addr->getRegRef(); + NodeId RD0 = UA0.Addr->getReachingDef(); + + for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) { + auto UA = DFG.addr(N); + NextN = UA.Addr->getSibling(); + uint16_t F = UA.Addr->getFlags(); + if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed)) + continue; + if (UA.Addr->getRegRef() != DR0) + continue; + NodeAddr IA = UA.Addr->getOwner(DFG); + assert(DFG.IsCode(IA)); + MachineInstr *MI = NodeAddr(IA).Addr->getCode(); + if (RDefMap[UR0][IA.Id] != RD0) + continue; + MachineOperand &Op = UA.Addr->getOp(); + if (Op.isTied()) + continue; + if (trace()) { + dbgs() << "can replace " << Print(DR0, DFG) + << " with " << Print(UR0, DFG) << " in " + << *NodeAddr(IA).Addr->getCode(); + } + + Op.setReg(UR0.Reg); + Op.setSubReg(UR0.Sub); + Changed = true; +#ifndef NDEBUG + if (HasLimit && CpCount >= CpLimit) + break; + CpCount++; +#endif + + if (MI->isCopy()) { + MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1); + if (Op0.getReg() == Op1.getReg() && Op0.getSubReg() == Op1.getSubReg()) + MI->eraseFromParent(); + Deleted.insert(IA.Id); + } + } + } + + return Changed; +} + diff --git a/lib/Target/Hexagon/RDFCopy.h b/lib/Target/Hexagon/RDFCopy.h new file mode 100644 index 00000000000..02531b94c9b --- /dev/null +++ b/lib/Target/Hexagon/RDFCopy.h @@ -0,0 +1,48 @@ +//===--- RDFCopy.h --------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef RDF_COPY_H +#define RDF_COPY_H + +#include "RDFGraph.h" +#include +#include + +namespace llvm { + class MachineBasicBlock; + class MachineDominatorTree; + class MachineInstr; +} + +namespace rdf { + struct CopyPropagation { + CopyPropagation(DataFlowGraph &dfg) : MDT(dfg.getDT()), DFG(dfg), + Trace(false) {} + + bool run(); + void trace(bool On) { Trace = On; } + bool trace() const { return Trace; } + + private: + const MachineDominatorTree &MDT; + DataFlowGraph &DFG; + DataFlowGraph::DefStackMap DefM; + bool Trace; + + // map: register -> (map: stmt -> reaching def) + std::map> RDefMap; + std::vector Copies; + + void recordCopy(NodeAddr SA, MachineInstr *MI); + void updateMap(NodeAddr IA); + bool scanBlock(MachineBasicBlock *B); + }; +} + +#endif -- 2.34.1