From 76580abdf6105f34ad4be92517070de8715cf509 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Tue, 12 Jan 2016 17:01:16 +0000 Subject: [PATCH] RDF: Dead code elimination Utility class to perform DFG-based dead code elimination. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257485 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/Hexagon/CMakeLists.txt | 1 + lib/Target/Hexagon/RDFDeadCode.cpp | 204 +++++++++++++++++++++++++++++ lib/Target/Hexagon/RDFDeadCode.h | 65 +++++++++ 3 files changed, 270 insertions(+) create mode 100644 lib/Target/Hexagon/RDFDeadCode.cpp create mode 100644 lib/Target/Hexagon/RDFDeadCode.h diff --git a/lib/Target/Hexagon/CMakeLists.txt b/lib/Target/Hexagon/CMakeLists.txt index 835ca55e349..a9be39880fc 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 + RDFDeadCode.cpp RDFGraph.cpp RDFLiveness.cpp ) diff --git a/lib/Target/Hexagon/RDFDeadCode.cpp b/lib/Target/Hexagon/RDFDeadCode.cpp new file mode 100644 index 00000000000..95668577bd5 --- /dev/null +++ b/lib/Target/Hexagon/RDFDeadCode.cpp @@ -0,0 +1,204 @@ +//===--- RDFDeadCode.cpp --------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// RDF-based generic dead code elimination. + +#include "RDFGraph.h" +#include "RDFLiveness.h" +#include "RDFDeadCode.h" + +#include "llvm/ADT/SetVector.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" + +using namespace llvm; +using namespace rdf; + +// Check if the given instruction has observable side-effects, i.e. if +// it should be considered "live". It is safe for this function to be +// overly conservative (i.e. return "true" for all instructions), but it +// is not safe to return "false" for an instruction that should not be +// considered removable. +bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const { + if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn()) + return true; + if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects()) + return true; + if (MI->isPHI()) + return false; + for (auto &Op : MI->operands()) + if (Op.isReg() && MRI.isReserved(Op.getReg())) + return true; + return false; +} + +void DeadCodeElimination::scanInstr(NodeAddr IA, + SetVector &WorkQ) { + if (!DFG.IsCode(IA)) + return; + if (!isLiveInstr(NodeAddr(IA).Addr->getCode())) + return; + for (NodeAddr RA : IA.Addr->members(DFG)) { + if (!LiveNodes.count(RA.Id)) + WorkQ.insert(RA.Id); + } +} + +void DeadCodeElimination::processDef(NodeAddr DA, + SetVector &WorkQ) { + NodeAddr IA = DA.Addr->getOwner(DFG); + for (NodeAddr UA : IA.Addr->members_if(DFG.IsUse, DFG)) { + if (!LiveNodes.count(UA.Id)) + WorkQ.insert(UA.Id); + } + for (NodeAddr TA : DFG.getRelatedRefs(IA, DA)) + LiveNodes.insert(TA.Id); +} + +void DeadCodeElimination::processUse(NodeAddr UA, + SetVector &WorkQ) { + for (NodeAddr DA : LV.getAllReachingDefs(UA)) { + if (!LiveNodes.count(DA.Id)) + WorkQ.insert(DA.Id); + } +} + +// Traverse the DFG and collect the set dead RefNodes and the set of +// dead instructions. Return "true" if any of these sets is non-empty, +// "false" otherwise. +bool DeadCodeElimination::collect() { + // This function works by first finding all live nodes. The dead nodes + // are then the complement of the set of live nodes. + // + // Assume that all nodes are dead. Identify instructions which must be + // considered live, i.e. instructions with observable side-effects, such + // as calls and stores. All arguments of such instructions are considered + // live. For each live def, all operands used in the corresponding + // instruction are considered live. For each live use, all its reaching + // defs are considered live. + LiveNodes.clear(); + SetVector WorkQ; + for (NodeAddr BA : DFG.getFunc().Addr->members(DFG)) + for (NodeAddr IA : BA.Addr->members(DFG)) + scanInstr(IA, WorkQ); + + while (!WorkQ.empty()) { + NodeId N = *WorkQ.begin(); + WorkQ.remove(N); + LiveNodes.insert(N); + auto RA = DFG.addr(N); + if (DFG.IsDef(RA)) + processDef(RA, WorkQ); + else + processUse(RA, WorkQ); + } + + if (trace()) { + dbgs() << "Live nodes:\n"; + for (NodeId N : LiveNodes) { + auto RA = DFG.addr(N); + dbgs() << PrintNode(RA, DFG) << "\n"; + } + } + + auto IsDead = [this] (NodeAddr IA) -> bool { + for (NodeAddr DA : IA.Addr->members_if(DFG.IsDef, DFG)) + if (LiveNodes.count(DA.Id)) + return false; + return true; + }; + + for (NodeAddr BA : DFG.getFunc().Addr->members(DFG)) { + for (NodeAddr IA : BA.Addr->members(DFG)) { + for (NodeAddr RA : IA.Addr->members(DFG)) + if (!LiveNodes.count(RA.Id)) + DeadNodes.insert(RA.Id); + if (DFG.IsCode(IA)) + if (isLiveInstr(NodeAddr(IA).Addr->getCode())) + continue; + if (IsDead(IA)) { + DeadInstrs.insert(IA.Id); + if (trace()) + dbgs() << "Dead instr: " << PrintNode(IA, DFG) << "\n"; + } + } + } + + return !DeadNodes.empty(); +} + +// Erase the nodes given in the Nodes set from DFG. In addition to removing +// them from the DFG, if a node corresponds to a statement, the corresponding +// machine instruction is erased from the function. +bool DeadCodeElimination::erase(const SetVector &Nodes) { + if (Nodes.empty()) + return false; + + // Prepare the actual set of ref nodes to remove: ref nodes from Nodes + // are included directly, for each InstrNode in Nodes, include the set + // of all RefNodes from it. + NodeList DRNs, DINs; + for (auto I : Nodes) { + auto BA = DFG.addr(I); + uint16_t Type = BA.Addr->getType(); + if (Type == NodeAttrs::Ref) { + DRNs.push_back(DFG.addr(I)); + continue; + } + + // If it's a code node, add all ref nodes from it. + uint16_t Kind = BA.Addr->getKind(); + if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) { + for (auto N : NodeAddr(BA).Addr->members(DFG)) + DRNs.push_back(N); + DINs.push_back(DFG.addr(I)); + } else { + llvm_unreachable("Unexpected code node"); + return false; + } + } + + // Sort the list so that use nodes are removed first. This makes the + // "unlink" functions a bit faster. + auto UsesFirst = [] (NodeAddr A, NodeAddr B) -> bool { + uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind(); + if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def) + return true; + if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use) + return false; + return A.Id < B.Id; + }; + std::sort(DRNs.begin(), DRNs.end(), UsesFirst); + + if (trace()) + dbgs() << "Removing dead ref nodes:\n"; + for (NodeAddr RA : DRNs) { + if (trace()) + dbgs() << " " << PrintNode(RA, DFG) << '\n'; + if (DFG.IsUse(RA)) + DFG.unlinkUse(RA); + else if (DFG.IsDef(RA)) + DFG.unlinkDef(RA); + } + + // Now, remove all dead instruction nodes. + for (NodeAddr IA : DINs) { + NodeAddr BA = IA.Addr->getOwner(DFG); + BA.Addr->removeMember(IA, DFG); + if (!DFG.IsCode(IA)) + continue; + + MachineInstr *MI = NodeAddr(IA).Addr->getCode(); + if (trace()) + dbgs() << "erasing: " << *MI; + MI->eraseFromParent(); + } + return true; +} diff --git a/lib/Target/Hexagon/RDFDeadCode.h b/lib/Target/Hexagon/RDFDeadCode.h new file mode 100644 index 00000000000..f4373fb5007 --- /dev/null +++ b/lib/Target/Hexagon/RDFDeadCode.h @@ -0,0 +1,65 @@ +//===--- RDFDeadCode.h ----------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// RDF-based generic dead code elimination. +// +// The main interface of this class are functions "collect" and "erase". +// This allows custom processing of the function being optimized by a +// particular consumer. The simplest way to use this class would be to +// instantiate an object, and then simply call "collect" and "erase", +// passing the result of "getDeadInstrs()" to it. +// A more complex scenario would be to call "collect" first, then visit +// all post-increment instructions to see if the address update is dead +// or not, and if it is, convert the instruction to a non-updating form. +// After that "erase" can be called with the set of nodes including both, +// dead defs from the updating instructions and the nodes corresponding +// to the dead instructions. + +#ifndef RDF_DEADCODE_H +#define RDF_DEADCODE_H + +#include "RDFGraph.h" +#include "RDFLiveness.h" +#include "llvm/ADT/SetVector.h" + +namespace llvm { + class MachineRegisterInfo; +} + +namespace rdf { + struct DeadCodeElimination { + DeadCodeElimination(DataFlowGraph &dfg, MachineRegisterInfo &mri) + : Trace(false), DFG(dfg), MRI(mri), LV(mri, dfg) {} + + bool collect(); + bool erase(const SetVector &Nodes); + void trace(bool On) { Trace = On; } + bool trace() const { return Trace; } + + SetVector getDeadNodes() { return DeadNodes; } + SetVector getDeadInstrs() { return DeadInstrs; } + DataFlowGraph &getDFG() { return DFG; } + + private: + bool Trace; + SetVector LiveNodes; + SetVector DeadNodes; + SetVector DeadInstrs; + DataFlowGraph &DFG; + MachineRegisterInfo &MRI; + Liveness LV; + + bool isLiveInstr(const MachineInstr *MI) const; + void scanInstr(NodeAddr IA, SetVector &WorkQ); + void processDef(NodeAddr DA, SetVector &WorkQ); + void processUse(NodeAddr UA, SetVector &WorkQ); + }; +} + +#endif -- 2.34.1