From: Krzysztof Parzyszek Date: Tue, 12 Jan 2016 19:09:01 +0000 (+0000) Subject: [Hexagon] Implement RDF-based post-RA optimizations X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=5c562302c20d5ba1aadf47c92980bb0feab9bf01 [Hexagon] Implement RDF-based post-RA optimizations - Handle simple cases of register copies (what current RDF CP allows). - Hexagon-specific dead code elimination: handles dead address updates in post-increment instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257504 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Target/Hexagon/CMakeLists.txt b/lib/Target/Hexagon/CMakeLists.txt index 414aa6963b1..333ca6a757a 100644 --- a/lib/Target/Hexagon/CMakeLists.txt +++ b/lib/Target/Hexagon/CMakeLists.txt @@ -39,6 +39,8 @@ add_llvm_target(HexagonCodeGen HexagonNewValueJump.cpp HexagonOptimizeSZextends.cpp HexagonPeephole.cpp + HexagonRDF.cpp + HexagonRDFOpt.cpp HexagonRegisterInfo.cpp HexagonSelectionDAGInfo.cpp HexagonSplitConst32AndConst64.cpp diff --git a/lib/Target/Hexagon/HexagonRDF.cpp b/lib/Target/Hexagon/HexagonRDF.cpp new file mode 100644 index 00000000000..06719cddf4b --- /dev/null +++ b/lib/Target/Hexagon/HexagonRDF.cpp @@ -0,0 +1,60 @@ +//===--- HexagonRDF.cpp ---------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "HexagonRDF.h" +#include "HexagonInstrInfo.h" +#include "HexagonRegisterInfo.h" + +#include "llvm/CodeGen/MachineInstr.h" + +using namespace llvm; +using namespace rdf; + +bool HexagonRegisterAliasInfo::covers(RegisterRef RA, RegisterRef RB) const { + if (RA == RB) + return true; + + if (TargetRegisterInfo::isVirtualRegister(RA.Reg) && + TargetRegisterInfo::isVirtualRegister(RB.Reg)) { + // Hexagon-specific cases. + if (RA.Reg == RB.Reg) { + if (RA.Sub == 0) + return true; + if (RB.Sub == 0) + return false; + } + } + + return RegisterAliasInfo::covers(RA, RB); +} + +bool HexagonRegisterAliasInfo::covers(const RegisterSet &RRs, RegisterRef RR) + const { + if (RRs.count(RR)) + return true; + + if (!TargetRegisterInfo::isPhysicalRegister(RR.Reg)) { + assert(TargetRegisterInfo::isVirtualRegister(RR.Reg)); + // Check if both covering subregisters are present. + bool HasLo = RRs.count({RR.Reg, Hexagon::subreg_loreg}); + bool HasHi = RRs.count({RR.Reg, Hexagon::subreg_hireg}); + if (HasLo && HasHi) + return true; + } + + if (RR.Sub == 0) { + // Check if both covering subregisters are present. + unsigned Lo = TRI.getSubReg(RR.Reg, Hexagon::subreg_loreg); + unsigned Hi = TRI.getSubReg(RR.Reg, Hexagon::subreg_hireg); + if (RRs.count({Lo, 0}) && RRs.count({Hi, 0})) + return true; + } + + return RegisterAliasInfo::covers(RRs, RR); +} diff --git a/lib/Target/Hexagon/HexagonRDF.h b/lib/Target/Hexagon/HexagonRDF.h new file mode 100644 index 00000000000..00c1889e8eb --- /dev/null +++ b/lib/Target/Hexagon/HexagonRDF.h @@ -0,0 +1,28 @@ +//===--- HexagonRDF.h -----------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef HEXAGON_RDF_H +#define HEXAGON_RDF_H +#include "RDFGraph.h" + +namespace llvm { + class TargetRegisterInfo; +} + +namespace rdf { + struct HexagonRegisterAliasInfo : public RegisterAliasInfo { + HexagonRegisterAliasInfo(const TargetRegisterInfo &TRI) + : RegisterAliasInfo(TRI) {} + bool covers(RegisterRef RA, RegisterRef RR) const override; + bool covers(const RegisterSet &RRs, RegisterRef RR) const override; + }; +} + +#endif + diff --git a/lib/Target/Hexagon/HexagonRDFOpt.cpp b/lib/Target/Hexagon/HexagonRDFOpt.cpp new file mode 100644 index 00000000000..e820b49e047 --- /dev/null +++ b/lib/Target/Hexagon/HexagonRDFOpt.cpp @@ -0,0 +1,272 @@ +//===--- HexagonRDFOpt.cpp ------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "HexagonInstrInfo.h" +#include "HexagonRDF.h" +#include "HexagonSubtarget.h" +#include "RDFCopy.h" +#include "RDFDeadCode.h" +#include "RDFGraph.h" +#include "RDFLiveness.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominanceFrontier.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Format.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" + +using namespace llvm; +using namespace rdf; + +namespace llvm { + void initializeHexagonRDFOptPass(PassRegistry&); + FunctionPass *createHexagonRDFOpt(); +} + +namespace { + cl::opt RDFLimit("rdf-limit", cl::init(UINT_MAX)); + unsigned RDFCount = 0; + cl::opt RDFDump("rdf-dump", cl::init(false)); + + class HexagonRDFOpt : public MachineFunctionPass { + public: + HexagonRDFOpt() : MachineFunctionPass(ID) { + initializeHexagonRDFOptPass(*PassRegistry::getPassRegistry()); + } + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(AU); + } + const char *getPassName() const override { + return "Hexagon RDF optimizations"; + } + bool runOnMachineFunction(MachineFunction &MF) override; + + static char ID; + + private: + MachineDominatorTree *MDT; + MachineRegisterInfo *MRI; + }; + + char HexagonRDFOpt::ID = 0; +} + +INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier) +INITIALIZE_PASS_END(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false) + + +struct HexagonDCE : public DeadCodeElimination { + using DeadCodeElimination::DeadCodeElimination; + + bool rewrite(NodeAddr IA, SetVector &Remove); + void removeOperand(NodeAddr IA, unsigned OpNum); + + bool run(); +}; + + +bool HexagonDCE::run() { + bool Collected = collect(); + if (!Collected) + return false; + + const SetVector &DeadNodes = getDeadNodes(); + const SetVector &DeadInstrs = getDeadInstrs(); + + typedef DenseMap RefToInstrMap; + RefToInstrMap R2I; + SetVector PartlyDead; + DataFlowGraph &DFG = getDFG(); + + for (NodeAddr BA : DFG.getFunc().Addr->members(DFG)) { + for (auto TA : BA.Addr->members_if(DFG.IsCode, DFG)) { + NodeAddr SA = TA; + for (NodeAddr RA : SA.Addr->members(DFG)) { + R2I.insert(std::make_pair(RA.Id, SA.Id)); + if (DFG.IsDef(RA) && DeadNodes.count(RA.Id)) + if (!DeadInstrs.count(SA.Id)) + PartlyDead.insert(SA.Id); + } + } + } + + // Nodes to remove. + SetVector Remove = DeadInstrs; + + bool Changed = false; + for (NodeId N : PartlyDead) { + auto SA = DFG.addr(N); + if (trace()) + dbgs() << "Partly dead: " << *SA.Addr->getCode(); + Changed |= rewrite(SA, Remove); + } + + return erase(Remove) || Changed; +} + + +void HexagonDCE::removeOperand(NodeAddr IA, unsigned OpNum) { + MachineInstr *MI = NodeAddr(IA).Addr->getCode(); + + auto getOpNum = [MI] (MachineOperand &Op) -> unsigned { + for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i) + if (&MI->getOperand(i) == &Op) + return i; + llvm_unreachable("Invalid operand"); + }; + DenseMap OpMap; + NodeList Refs = IA.Addr->members(getDFG()); + for (NodeAddr RA : Refs) + OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp()))); + + MI->RemoveOperand(OpNum); + + for (NodeAddr RA : Refs) { + unsigned N = OpMap[RA.Id]; + if (N < OpNum) + RA.Addr->setRegRef(&MI->getOperand(N)); + else if (N > OpNum) + RA.Addr->setRegRef(&MI->getOperand(N-1)); + } +} + + +bool HexagonDCE::rewrite(NodeAddr IA, SetVector &Remove) { + if (!getDFG().IsCode(IA)) + return false; + DataFlowGraph &DFG = getDFG(); + MachineInstr *MI = NodeAddr(IA).Addr->getCode(); + auto &HII = static_cast(DFG.getTII()); + if (HII.getAddrMode(MI) != HexagonII::PostInc) + return false; + unsigned Opc = MI->getOpcode(); + unsigned OpNum, NewOpc; + switch (Opc) { + case Hexagon::L2_loadri_pi: + NewOpc = Hexagon::L2_loadri_io; + OpNum = 1; + break; + case Hexagon::L2_loadrd_pi: + NewOpc = Hexagon::L2_loadrd_io; + OpNum = 1; + break; + case Hexagon::V6_vL32b_pi: + NewOpc = Hexagon::V6_vL32b_ai; + OpNum = 1; + break; + case Hexagon::S2_storeri_pi: + NewOpc = Hexagon::S2_storeri_io; + OpNum = 0; + break; + case Hexagon::S2_storerd_pi: + NewOpc = Hexagon::S2_storerd_io; + OpNum = 0; + break; + case Hexagon::V6_vS32b_pi: + NewOpc = Hexagon::V6_vS32b_ai; + OpNum = 0; + break; + default: + return false; + } + auto IsDead = [this] (NodeAddr DA) -> bool { + return getDeadNodes().count(DA.Id); + }; + NodeList Defs; + MachineOperand &Op = MI->getOperand(OpNum); + for (NodeAddr DA : IA.Addr->members_if(DFG.IsDef, DFG)) { + if (&DA.Addr->getOp() != &Op) + continue; + Defs = DFG.getRelatedRefs(IA, DA); + if (!std::all_of(Defs.begin(), Defs.end(), IsDead)) + return false; + break; + } + + // Mark all nodes in Defs for removal. + for (auto D : Defs) + Remove.insert(D.Id); + + if (trace()) + dbgs() << "Rewriting: " << *MI; + MI->setDesc(HII.get(NewOpc)); + MI->getOperand(OpNum+2).setImm(0); + removeOperand(IA, OpNum); + if (trace()) + dbgs() << " to: " << *MI; + + return true; +} + + +bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) { + if (RDFLimit.getPosition()) { + if (RDFCount >= RDFLimit) + return false; + RDFCount++; + } + + MDT = &getAnalysis(); + const auto &MDF = getAnalysis(); + const auto &HII = *MF.getSubtarget().getInstrInfo(); + const auto &HRI = *MF.getSubtarget().getRegisterInfo(); + MRI = &MF.getRegInfo(); + + HexagonRegisterAliasInfo HAI(HRI); + TargetOperandInfo TOI(HII); + + if (RDFDump) + MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr); + DataFlowGraph G(MF, HII, HRI, *MDT, MDF, HAI, TOI); + G.build(); + if (RDFDump) { + dbgs() << PrintNode(G.getFunc(), G) << '\n'; + dbgs() << MF.getName() << '\n'; + } + + bool Changed; + CopyPropagation CP(G); + CP.trace(RDFDump); + Changed = CP.run(); + if (Changed) + G.build(); + + HexagonDCE DCE(G, *MRI); + DCE.trace(RDFDump); + Changed |= DCE.run(); + + if (Changed) { + Liveness LV(*MRI, G); + LV.trace(RDFDump); + LV.computeLiveIns(); + LV.resetLiveIns(); + LV.resetKills(); + } + + if (RDFDump) + MF.print(dbgs() << "After " << getPassName() << "\n", nullptr); + return false; +} + + +FunctionPass *llvm::createHexagonRDFOpt() { + return new HexagonRDFOpt(); +} + + diff --git a/lib/Target/Hexagon/HexagonTargetMachine.cpp b/lib/Target/Hexagon/HexagonTargetMachine.cpp index 9dccd696c98..34b03fb74ce 100644 --- a/lib/Target/Hexagon/HexagonTargetMachine.cpp +++ b/lib/Target/Hexagon/HexagonTargetMachine.cpp @@ -26,7 +26,11 @@ using namespace llvm; -static cl:: opt DisableHardwareLoops("disable-hexagon-hwloops", + +static cl::opt EnableRDFOpt("rdf-opt", cl::Hidden, cl::ZeroOrMore, + cl::init(true), cl::desc("Enable RDF-based optimizations")); + +static cl::opt DisableHardwareLoops("disable-hexagon-hwloops", cl::Hidden, cl::desc("Disable Hardware Loops for Hexagon target")); static cl::opt DisableHexagonCFGOpt("disable-hexagon-cfgopt", @@ -111,6 +115,7 @@ namespace llvm { FunctionPass *createHexagonOptimizeSZextends(); FunctionPass *createHexagonPacketizer(); FunctionPass *createHexagonPeephole(); + FunctionPass *createHexagonRDFOpt(); FunctionPass *createHexagonSplitConst32AndConst64(); FunctionPass *createHexagonSplitDoubleRegs(); FunctionPass *createHexagonStoreWidening(); @@ -262,9 +267,12 @@ void HexagonPassConfig::addPreRegAlloc() { } void HexagonPassConfig::addPostRegAlloc() { - if (getOptLevel() != CodeGenOpt::None) + if (getOptLevel() != CodeGenOpt::None) { + if (EnableRDFOpt) + addPass(createHexagonRDFOpt()); if (!DisableHexagonCFGOpt) addPass(createHexagonCFGOptimizer(), false); + } } void HexagonPassConfig::addPreSched2() { diff --git a/test/CodeGen/Hexagon/postinc-offset.ll b/test/CodeGen/Hexagon/postinc-offset.ll index 5e0f4751f30..cf8c4e5f71d 100644 --- a/test/CodeGen/Hexagon/postinc-offset.ll +++ b/test/CodeGen/Hexagon/postinc-offset.ll @@ -1,4 +1,5 @@ -; RUN: llc -enable-aa-sched-mi -march=hexagon -mcpu=hexagonv5 < %s | FileCheck %s +; RUN: llc -enable-aa-sched-mi -march=hexagon -mcpu=hexagonv5 -rdf-opt=0 \ +; RUN: < %s | FileCheck %s ; CHECK: { ; CHECK: ={{ *}}memd([[REG0:(r[0-9]+)]]{{ *}}++{{ *}}#8) diff --git a/test/CodeGen/Hexagon/rdf-copy.ll b/test/CodeGen/Hexagon/rdf-copy.ll new file mode 100644 index 00000000000..96153ca31fa --- /dev/null +++ b/test/CodeGen/Hexagon/rdf-copy.ll @@ -0,0 +1,54 @@ +; RUN: llc -march=hexagon < %s | FileCheck %s +; +; Check that +; { +; r1 = r0 +; } +; { +; r0 = memw(r1 + #0) +; } +; was copy-propagated to +; { +; r1 = r0 +; r0 = memw(r0 + #0) +; } +; +; CHECK-LABEL: LBB0_1 +; CHECK: [[DST:r[0-9]+]] = [[SRC:r[0-9]+]] +; CHECK-DAG: memw([[SRC]] +; CHECK-DAG-NOT: memw([[DST]] +; CHECK-LABEL: LBB0_2 + +target datalayout = "e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:32:32-f64:64:64-f32:32:32-v64:64:64-v32:32:32-a0:0-n16:32" +target triple = "hexagon" + +%union.t = type { %struct.t, [64 x i8] } +%struct.t = type { [12 x i8], %struct.r*, double } +%struct.r = type opaque + +define %union.t* @foo(%union.t* %chain) nounwind readonly { +entry: + %tobool = icmp eq %union.t* %chain, null + br i1 %tobool, label %if.end, label %while.cond.preheader + +while.cond.preheader: ; preds = %entry + br label %while.cond + +while.cond: ; preds = %while.cond.preheader, %while.cond + %chain.addr.0 = phi %union.t* [ %0, %while.cond ], [ %chain, %while.cond.preheader ] + %chain1 = bitcast %union.t* %chain.addr.0 to %union.t** + %0 = load %union.t*, %union.t** %chain1, align 4, !tbaa !0 + %tobool2 = icmp eq %union.t* %0, null + br i1 %tobool2, label %if.end.loopexit, label %while.cond + +if.end.loopexit: ; preds = %while.cond + br label %if.end + +if.end: ; preds = %if.end.loopexit, %entry + %chain.addr.1 = phi %union.t* [ null, %entry ], [ %chain.addr.0, %if.end.loopexit ] + ret %union.t* %chain.addr.1 +} + +!0 = !{!"any pointer", !1} +!1 = !{!"omnipotent char", !2} +!2 = !{!"Simple C/C++ TBAA"} diff --git a/test/CodeGen/Hexagon/rdf-dead-loop.ll b/test/CodeGen/Hexagon/rdf-dead-loop.ll new file mode 100644 index 00000000000..3762c79d4f5 --- /dev/null +++ b/test/CodeGen/Hexagon/rdf-dead-loop.ll @@ -0,0 +1,31 @@ +; RUN: llc -march=hexagon < %s | FileCheck %s +; CHECK-NOT: ={{.*}}add +; CHECK-NOT: mem{{[bdhwu]}} + +define void @main() #0 { +entry: + br label %body + +body: + %ip_vec30 = phi <2 x i32> [ %ip_vec, %body ], [ zeroinitializer, %entry ] + %scevgep.phi = phi i32* [ %scevgep.inc, %body ], [ undef, %entry ] + %polly.indvar = phi i32 [ %polly.indvar_next, %body ], [ 0, %entry ] + %vector_ptr = bitcast i32* %scevgep.phi to <2 x i32>* + %_p_vec_full = load <2 x i32>, <2 x i32>* %vector_ptr, align 8 + %ip_vec = add <2 x i32> %_p_vec_full, %ip_vec30 + %polly.indvar_next = add nsw i32 %polly.indvar, 2 + %polly.loop_cond = icmp slt i32 %polly.indvar, 4 + %scevgep.inc = getelementptr i32, i32* %scevgep.phi, i32 2 + br i1 %polly.loop_cond, label %body, label %exit + +exit: + %0 = extractelement <2 x i32> %ip_vec, i32 1 + ret void + +} + +attributes #0 = { "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"="true" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!0 = !{!"int", !1} +!1 = !{!"omnipotent char", !2} +!2 = !{!"Simple C/C++ TBAA"}