[llvm-branch-commits] [llvm] ebfe4de - [DDG] Fix duplicate edge removal during pi-block formation
Author: Bardia Mahjour Date: 2021-01-07T10:31:11-05:00 New Revision: ebfe4de2c04b09d3ae935325e6c02c68f2965b00 URL: https://github.com/llvm/llvm-project/commit/ebfe4de2c04b09d3ae935325e6c02c68f2965b00 DIFF: https://github.com/llvm/llvm-project/commit/ebfe4de2c04b09d3ae935325e6c02c68f2965b00.diff LOG: [DDG] Fix duplicate edge removal during pi-block formation When creating pi-blocks we try to avoid creating duplicate edges between outside nodes and the pi-block when an edge is of the same kind and direction as another one that has already been created. We do this by keeping track of the edges in an enumerated array called EdgeAlreadyCreated. The problem is that this array is declared local to the loop that iterates over the nodes in the pi-block, so the information gets lost every time a new inside-node is iterated over. The fix is to move the declaration to the outer loop. Reviewed By: Meinersbur Differential Revision: https://reviews.llvm.org/D94094 Added: Modified: llvm/lib/Analysis/DependenceGraphBuilder.cpp llvm/unittests/Analysis/DDGTest.cpp Removed: diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp index fbf0f6651599..04a34472659c 100644 --- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp +++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp @@ -140,75 +140,74 @@ template void AbstractDependenceGraphBuilder::createPiBlocks() { if (*N == PiNode || NodesInSCC.count(N)) continue; - for (NodeType *SCCNode : NL) { - -enum Direction { - Incoming, // Incoming edges to the SCC - Outgoing, // Edges going ot of the SCC - DirectionCount // To make the enum usable as an array index. -}; - -// Use these flags to help us avoid creating redundant edges. If there -// are more than one edges from an outside node to inside nodes, we only -// keep one edge from that node to the pi-block node. Similarly, if -// there are more than one edges from inside nodes to an outside node, -// we only keep one edge from the pi-block node to the outside node. -// There is a flag defined for each direction (incoming vs outgoing) and -// for each type of edge supported, using a two-dimensional boolean -// array. -using EdgeKind = typename EdgeType::EdgeKind; -EnumeratedArray EdgeAlreadyCreated[DirectionCount]{ -false, false}; - -auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst, - const EdgeKind K) { - switch (K) { - case EdgeKind::RegisterDefUse: -createDefUseEdge(Src, Dst); -break; - case EdgeKind::MemoryDependence: -createMemoryEdge(Src, Dst); -break; - case EdgeKind::Rooted: -createRootedEdge(Src, Dst); -break; - default: -llvm_unreachable("Unsupported type of edge."); - } -}; - -auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New, - const Direction Dir) { - if (!Src->hasEdgeTo(*Dst)) -return; - LLVM_DEBUG(dbgs() - << "reconnecting(" - << (Dir == Direction::Incoming ? "incoming)" : "outgoing)") - << ":\nSrc:" << *Src << "\nDst:" << *Dst - << "\nNew:" << *New << "\n"); - assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) && - "Invalid direction."); - - SmallVector EL; - Src->findEdgesTo(*Dst, EL); - for (EdgeType *OldEdge : EL) { -EdgeKind Kind = OldEdge->getKind(); -if (!EdgeAlreadyCreated[Dir][Kind]) { - if (Dir == Direction::Incoming) { -createEdgeOfKind(*Src, *New, Kind); -LLVM_DEBUG(dbgs() << "created edge from Src to New.\n"); - } else if (Dir == Direction::Outgoing) { -createEdgeOfKind(*New, *Dst, Kind); -LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n"); - } - EdgeAlreadyCreated[Dir][Kind] = true; + enum Direction { +Incoming, // Incoming edges to the SCC +Outgoing, // Edges going ot of the SCC +DirectionCount // To make the enum usable as an array index. + }; + + // Use these flags to help us avoid creating redundant edges. If there + // are more than one edges from an outside node to inside nodes, we only + // keep one edge from that node to the pi-block node. Similarly, if + // there are more than one edges from inside nodes to an outside node, + // we only keep one edge from the pi-block node to the outside node. + // There is a flag defined
[llvm-branch-commits] [llvm] 573d578 - [DDG] Data Dependence Graph - DOT printer tests
Author: Bardia Mahjour Date: 2021-01-07T10:51:14-05:00 New Revision: 573d5782482841e16588e81be687ea6bcf3624fa URL: https://github.com/llvm/llvm-project/commit/573d5782482841e16588e81be687ea6bcf3624fa DIFF: https://github.com/llvm/llvm-project/commit/573d5782482841e16588e81be687ea6bcf3624fa.diff LOG: [DDG] Data Dependence Graph - DOT printer tests Adds some tests to check the formatting of the dot file produced when using -dot-ddg. Reviewed By: Meinersbur Differential Revision: https://reviews.llvm.org/D93949 Added: llvm/test/Analysis/DDG/print-dot-ddg.ll Modified: Removed: diff --git a/llvm/test/Analysis/DDG/print-dot-ddg.ll b/llvm/test/Analysis/DDG/print-dot-ddg.ll new file mode 100644 index ..8a4d55bc2e8b --- /dev/null +++ b/llvm/test/Analysis/DDG/print-dot-ddg.ll @@ -0,0 +1,74 @@ +; RUN: opt -aa-pipeline=basic-aa -passes=dot-ddg -dot-ddg-filename-prefix=out.full < %s 2>&1 > /dev/null +; RUN: FileCheck %s -input-file=out.full.foo.for.body.dot +; RUN: opt -aa-pipeline=basic-aa -passes=dot-ddg -dot-ddg-filename-prefix=out.only -dot-ddg-only < %s 2>&1 > /dev/null +; RUN: FileCheck %s -input-file=out.only.foo.for.body.dot -check-prefix=CHECK-ONLY + +target datalayout = "e-m:e-i64:64-n32:64-v256:256:256-v512:512:512" + +; Test the dot graph printer for a non-trivial DDG graph generated from +; the following test case. In particular it tests that pi-blocks are +; printed properly and that multiple memory dependencies on a single edge +; are shown in the full dot graph. +; +; void foo(float * restrict A, float * restrict B, int n) { +; for (int i = 0; i < n; i++) { +; A[i] = A[i] + B[i]; +; B[i+1] = A[i] + 1; +; } +; } + + +; CHECK: digraph "DDG for 'foo.for.body'" +; CHECK-NEXT: label="DDG for 'foo.for.body'"; +; CHECK: {{Node0x.*}} [shape=record,label="{\\nroot\n}"] +; CHECK: {{Node0x.*}} -> {{Node0x.*}}[label="[rooted]"] +; CHECK-COUNT-6: {{Node0x.*}} -> {{Node0x.*}}[label="[def-use]"] +; CHECK-NOT: {{Node0x.*}} -> {{Node0x.*}}[label="[def-use]"] +; CHECK: [shape=record,label="{\\n %arrayidx10 = getelementptr inbounds float, float* %B, i64 %indvars.iv.next\n}"]; +; CHECK: [shape=record,label="{\\n %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv\n %0 = load float, float* %arrayidx, align 4\n}"]; +; CHECK: {{Node0x.*}} -> {{Node0x.*}}[label="[consistent anti [0|<]!, consistent input [0|<]!]"] +; CHECK: [shape=record,label="{\\n--- start of nodes in pi-block ---\n\\n %1 = load float, float* %arrayidx2, align 4\n\n\\n %add = fadd fast float %0, %1\n\n\\n store float %add, float* %arrayidx4, align 4\n\n\\n %2 = load float, float* %arrayidx6, align 4\n %add7 = fadd fast float %2, 1.00e+00\n\n\\n store float %add7, float* %arrayidx10, align 4\n--- end of nodes in pi-block ---\n}"]; + +; CHECK-ONLY: digraph "DDG for 'foo.for.body'" +; CHECK-ONLY-NEXT: label="DDG for 'foo.for.body'"; +; CHECK-ONLY: [shape=record,label="{pi-block\nwith\n2 nodes\n}"]; +; CHECK-ONLY-COUNT-6: {{Node0x.*}} -> {{Node0x.*}}[label="[def-use]"]; +; CHECK-NOT: {{Node0x.*}} -> {{Node0x.*}}[label="[def-use]"]; +; CHECK-ONLY: [shape=record,label="{ %arrayidx10 = getelementptr inbounds float, float* %B, i64 %indvars.iv.next\n}"]; +; CHECK-ONLY: [shape=record,label="{ %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv\n %0 = load float, float* %arrayidx, align 4\n}"]; +; CHECK-ONLY: {{Node0x.*}} -> {{Node0x.*}}[label="[memory]"] +; CHECK-ONLY: [shape=record,label="{pi-block\nwith\n5 nodes\n}"]; + +define void @foo(float* noalias %A, float* noalias %B, i32 signext %n) { +entry: + %cmp1 = icmp sgt i32 %n, 0 + br i1 %cmp1, label %for.body.preheader, label %for.end + +for.body.preheader: ; preds = %entry + %wide.trip.count = zext i32 %n to i64 + br label %for.body + +for.body: ; preds = %for.body.preheader, %for.body + %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv + %0 = load float, float* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds float, float* %B, i64 %indvars.iv + %1 = load float, float* %arrayidx2, align 4 + %add = fadd fast float %0, %1 + %arrayidx4 = getelementptr inbounds float, float* %A, i64 %indvars.iv + store float %add, float* %arrayidx4, align 4 + %arrayidx6 = getelementptr inbounds float, float* %A, i64 %indvars.iv + %2 = load float, float* %arrayidx6, align 4 + %add7 = fadd fast float %2, 1.00e+00 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %arrayidx10 = getelementptr inbounds float, float* %B, i64 %indvars.iv.next + store float %add7, float* %arrayidx10, align 4 + %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count + br i1 %exitcond, label %for.body, label %for.end.loopexit + +for.end.loopexit:
[llvm-branch-commits] [clang] fd4a107 - [DDG] Data Dependence Graph - DOT printer
Author: Bardia Mahjour Date: 2020-12-14T16:41:14-05:00 New Revision: fd4a10732c8bd646ccc621c0a9af512be252f33a URL: https://github.com/llvm/llvm-project/commit/fd4a10732c8bd646ccc621c0a9af512be252f33a DIFF: https://github.com/llvm/llvm-project/commit/fd4a10732c8bd646ccc621c0a9af512be252f33a.diff LOG: [DDG] Data Dependence Graph - DOT printer This patch implements a DDG printer pass that generates a graph in the DOT description language, providing a more visually appealing representation of the DDG. Similar to the CFG DOT printer, this functionality is provided under an option called -dot-ddg and can be generated in a less verbose mode under -dot-ddg-only option. Differential Revision: https://reviews.llvm.org/D90159 Added: llvm/include/llvm/Analysis/DDGPrinter.h llvm/lib/Analysis/DDGPrinter.cpp Modified: clang/lib/StaticAnalyzer/Core/ExprEngine.cpp llvm/include/llvm/Analysis/CFGPrinter.h llvm/include/llvm/Analysis/DDG.h llvm/include/llvm/Support/DOTGraphTraits.h llvm/include/llvm/Support/GraphWriter.h llvm/lib/Analysis/CFGPrinter.cpp llvm/lib/Analysis/CMakeLists.txt llvm/lib/Analysis/CallPrinter.cpp llvm/lib/CodeGen/MachineScheduler.cpp llvm/lib/CodeGen/ScheduleDAGPrinter.cpp llvm/lib/Passes/PassBuilder.cpp llvm/lib/Passes/PassRegistry.def Removed: diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 409741cdb6e4..f285b652c175 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -3149,7 +3149,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { if (Stop(N)) return true; - if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc())) + if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr)) break; PostCallback(N); @@ -3158,7 +3158,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { return false; } - static bool isNodeHidden(const ExplodedNode *N) { + static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) { return N->isTrivial(); } diff --git a/llvm/include/llvm/Analysis/CFGPrinter.h b/llvm/include/llvm/Analysis/CFGPrinter.h index bc6a19f2e2b9..53700798b6b3 100644 --- a/llvm/include/llvm/Analysis/CFGPrinter.h +++ b/llvm/include/llvm/Analysis/CFGPrinter.h @@ -295,7 +295,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { " fillcolor=\"" + Color + "70\""; return Attrs; } - bool isNodeHidden(const BasicBlock *Node); + bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo); void computeHiddenNodes(const Function *F); }; } // End llvm namespace diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h index 9e2b7907eaec..8d225c155cd4 100644 --- a/llvm/include/llvm/Analysis/DDG.h +++ b/llvm/include/llvm/Analysis/DDG.h @@ -290,6 +290,12 @@ template class DependenceGraphInfo { bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const; + /// Return a string representing the type of dependence that the dependence + /// analysis identified between the two given nodes. This function assumes + /// that there is a memory dependence between the given two nodes. + const std::string getDependenceString(const NodeType &Src, +const NodeType &Dst) const; + protected: // Name of the graph. std::string Name; @@ -463,6 +469,26 @@ bool DependenceGraphInfo::getDependencies( return !Deps.empty(); } +template +const std::string +DependenceGraphInfo::getDependenceString(const NodeType &Src, + const NodeType &Dst) const { + std::string Str; + raw_string_ostream OS(Str); + DependenceList Deps; + if (!getDependencies(Src, Dst, Deps)) +return OS.str(); + interleaveComma(Deps, OS, [&](const std::unique_ptr &D) { +D->dump(OS); +// Remove the extra new-line character printed by the dump +// method +if (OS.str().back() == '\n') + OS.str().pop_back(); + }); + + return OS.str(); +} + //======// // GraphTraits specializations for the DDG //======// diff --git a/llvm/include/llvm/Analysis/DDGPrinter.h b/llvm/include/llvm/Analysis/DDGPrinter.h new file mode 100644 index ..5cfe2ce33c99 --- /dev/null +++ b/llvm/include/llvm/Analysis/DDGPrinter.h @@ -0,0 +1,91 @@ +//===- llvm/Analysis/DDGPrinter.h ---*- C++ -*-===// +// +// 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
[llvm-branch-commits] [clang] a29ecca - Revert "[DDG] Data Dependence Graph - DOT printer"
Author: Bardia Mahjour Date: 2020-12-14T16:54:20-05:00 New Revision: a29ecca7819a6ed4250d3689b12b1f664bb790d7 URL: https://github.com/llvm/llvm-project/commit/a29ecca7819a6ed4250d3689b12b1f664bb790d7 DIFF: https://github.com/llvm/llvm-project/commit/a29ecca7819a6ed4250d3689b12b1f664bb790d7.diff LOG: Revert "[DDG] Data Dependence Graph - DOT printer" This reverts commit fd4a10732c8bd646ccc621c0a9af512be252f33a, to investigate the failure on windows: http://lab.llvm.org:8011/#/builders/127/builds/3274 Added: Modified: clang/lib/StaticAnalyzer/Core/ExprEngine.cpp llvm/include/llvm/Analysis/CFGPrinter.h llvm/include/llvm/Analysis/DDG.h llvm/include/llvm/Support/DOTGraphTraits.h llvm/include/llvm/Support/GraphWriter.h llvm/lib/Analysis/CFGPrinter.cpp llvm/lib/Analysis/CMakeLists.txt llvm/lib/Analysis/CallPrinter.cpp llvm/lib/CodeGen/MachineScheduler.cpp llvm/lib/CodeGen/ScheduleDAGPrinter.cpp llvm/lib/Passes/PassBuilder.cpp llvm/lib/Passes/PassRegistry.def Removed: llvm/include/llvm/Analysis/DDGPrinter.h llvm/lib/Analysis/DDGPrinter.cpp diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index f285b652c175..409741cdb6e4 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -3149,7 +3149,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { if (Stop(N)) return true; - if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr)) + if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc())) break; PostCallback(N); @@ -3158,7 +3158,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { return false; } - static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) { + static bool isNodeHidden(const ExplodedNode *N) { return N->isTrivial(); } diff --git a/llvm/include/llvm/Analysis/CFGPrinter.h b/llvm/include/llvm/Analysis/CFGPrinter.h index 53700798b6b3..bc6a19f2e2b9 100644 --- a/llvm/include/llvm/Analysis/CFGPrinter.h +++ b/llvm/include/llvm/Analysis/CFGPrinter.h @@ -295,7 +295,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { " fillcolor=\"" + Color + "70\""; return Attrs; } - bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo); + bool isNodeHidden(const BasicBlock *Node); void computeHiddenNodes(const Function *F); }; } // End llvm namespace diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h index 8d225c155cd4..9e2b7907eaec 100644 --- a/llvm/include/llvm/Analysis/DDG.h +++ b/llvm/include/llvm/Analysis/DDG.h @@ -290,12 +290,6 @@ template class DependenceGraphInfo { bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const; - /// Return a string representing the type of dependence that the dependence - /// analysis identified between the two given nodes. This function assumes - /// that there is a memory dependence between the given two nodes. - const std::string getDependenceString(const NodeType &Src, -const NodeType &Dst) const; - protected: // Name of the graph. std::string Name; @@ -469,26 +463,6 @@ bool DependenceGraphInfo::getDependencies( return !Deps.empty(); } -template -const std::string -DependenceGraphInfo::getDependenceString(const NodeType &Src, - const NodeType &Dst) const { - std::string Str; - raw_string_ostream OS(Str); - DependenceList Deps; - if (!getDependencies(Src, Dst, Deps)) -return OS.str(); - interleaveComma(Deps, OS, [&](const std::unique_ptr &D) { -D->dump(OS); -// Remove the extra new-line character printed by the dump -// method -if (OS.str().back() == '\n') - OS.str().pop_back(); - }); - - return OS.str(); -} - //======// // GraphTraits specializations for the DDG //======// diff --git a/llvm/include/llvm/Analysis/DDGPrinter.h b/llvm/include/llvm/Analysis/DDGPrinter.h deleted file mode 100644 index 5cfe2ce33c99.. --- a/llvm/include/llvm/Analysis/DDGPrinter.h +++ /dev/null @@ -1,91 +0,0 @@ -//===- llvm/Analysis/DDGPrinter.h ---*- C++ -*-===// -// -// 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 -// -//===--===// - -//===--===// -// -// This file defin
[llvm-branch-commits] [llvm] 6eff127 - [DDG] Data Dependence Graph - DOT printer - recommit
Author: Bardia Mahjour Date: 2020-12-16T12:37:36-05:00 New Revision: 6eff12788ee8d3f85f6e57809e757ca3250813d8 URL: https://github.com/llvm/llvm-project/commit/6eff12788ee8d3f85f6e57809e757ca3250813d8 DIFF: https://github.com/llvm/llvm-project/commit/6eff12788ee8d3f85f6e57809e757ca3250813d8.diff LOG: [DDG] Data Dependence Graph - DOT printer - recommit This is being recommitted to try and address the MSVC complaint. This patch implements a DDG printer pass that generates a graph in the DOT description language, providing a more visually appealing representation of the DDG. Similar to the CFG DOT printer, this functionality is provided under an option called -dot-ddg and can be generated in a less verbose mode under -dot-ddg-only option. Reviewed By: Meinersbur Differential Revision: https://reviews.llvm.org/D90159 Added: llvm/include/llvm/Analysis/DDGPrinter.h llvm/lib/Analysis/DDGPrinter.cpp Modified: clang/lib/StaticAnalyzer/Core/ExprEngine.cpp llvm/include/llvm/Analysis/CFGPrinter.h llvm/include/llvm/Analysis/DDG.h llvm/include/llvm/Support/DOTGraphTraits.h llvm/include/llvm/Support/GraphWriter.h llvm/lib/Analysis/CFGPrinter.cpp llvm/lib/Analysis/CMakeLists.txt llvm/lib/Analysis/CallPrinter.cpp llvm/lib/CodeGen/MachineScheduler.cpp llvm/lib/CodeGen/ScheduleDAGPrinter.cpp llvm/lib/Passes/PassBuilder.cpp llvm/lib/Passes/PassRegistry.def Removed: diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 409741cdb6e4..f285b652c175 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -3149,7 +3149,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { if (Stop(N)) return true; - if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc())) + if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr)) break; PostCallback(N); @@ -3158,7 +3158,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { return false; } - static bool isNodeHidden(const ExplodedNode *N) { + static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) { return N->isTrivial(); } diff --git a/llvm/include/llvm/Analysis/CFGPrinter.h b/llvm/include/llvm/Analysis/CFGPrinter.h index bc6a19f2e2b9..53700798b6b3 100644 --- a/llvm/include/llvm/Analysis/CFGPrinter.h +++ b/llvm/include/llvm/Analysis/CFGPrinter.h @@ -295,7 +295,7 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { " fillcolor=\"" + Color + "70\""; return Attrs; } - bool isNodeHidden(const BasicBlock *Node); + bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo); void computeHiddenNodes(const Function *F); }; } // End llvm namespace diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h index 9e2b7907eaec..8d225c155cd4 100644 --- a/llvm/include/llvm/Analysis/DDG.h +++ b/llvm/include/llvm/Analysis/DDG.h @@ -290,6 +290,12 @@ template class DependenceGraphInfo { bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const; + /// Return a string representing the type of dependence that the dependence + /// analysis identified between the two given nodes. This function assumes + /// that there is a memory dependence between the given two nodes. + const std::string getDependenceString(const NodeType &Src, +const NodeType &Dst) const; + protected: // Name of the graph. std::string Name; @@ -463,6 +469,26 @@ bool DependenceGraphInfo::getDependencies( return !Deps.empty(); } +template +const std::string +DependenceGraphInfo::getDependenceString(const NodeType &Src, + const NodeType &Dst) const { + std::string Str; + raw_string_ostream OS(Str); + DependenceList Deps; + if (!getDependencies(Src, Dst, Deps)) +return OS.str(); + interleaveComma(Deps, OS, [&](const std::unique_ptr &D) { +D->dump(OS); +// Remove the extra new-line character printed by the dump +// method +if (OS.str().back() == '\n') + OS.str().pop_back(); + }); + + return OS.str(); +} + //======// // GraphTraits specializations for the DDG //======// diff --git a/llvm/include/llvm/Analysis/DDGPrinter.h b/llvm/include/llvm/Analysis/DDGPrinter.h new file mode 100644 index ..4477b387fe50 --- /dev/null +++ b/llvm/include/llvm/Analysis/DDGPrinter.h @@ -0,0 +1,91 @@ +//===- llvm/Analysis/DDGPrinter.h ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exception
[llvm-branch-commits] [llvm] 4db9b78 - [LV] Epilogue Vectorization with Optimal Control Flow - Default Enablement
Author: Bardia Mahjour Date: 2020-12-07T14:29:36-05:00 New Revision: 4db9b78c8146bb8f13cfb21939778de4e90ea32f URL: https://github.com/llvm/llvm-project/commit/4db9b78c8146bb8f13cfb21939778de4e90ea32f DIFF: https://github.com/llvm/llvm-project/commit/4db9b78c8146bb8f13cfb21939778de4e90ea32f.diff LOG: [LV] Epilogue Vectorization with Optimal Control Flow - Default Enablement This patch enables epilogue vectorization by default per reviewer requests. Differential Revision: https://reviews.llvm.org/D89566 Added: Modified: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp llvm/test/Transforms/LoopVectorize/X86/gather_scatter.ll llvm/test/Transforms/LoopVectorize/X86/invariant-load-gather.ll llvm/test/Transforms/LoopVectorize/X86/invariant-store-vectorization.ll llvm/test/Transforms/LoopVectorize/X86/masked_load_store.ll Removed: diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index 8c02be8530be..6ba14e942ff8 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -175,7 +175,7 @@ STATISTIC(LoopsAnalyzed, "Number of loops analyzed for vectorization"); STATISTIC(LoopsEpilogueVectorized, "Number of epilogues vectorized"); static cl::opt EnableEpilogueVectorization( -"enable-epilogue-vectorization", cl::init(false), cl::Hidden, +"enable-epilogue-vectorization", cl::init(true), cl::Hidden, cl::desc("Enable vectorization of epilogue loops.")); static cl::opt EpilogueVectorizationForceVF( diff --git a/llvm/test/Transforms/LoopVectorize/X86/gather_scatter.ll b/llvm/test/Transforms/LoopVectorize/X86/gather_scatter.ll index f2dd89ea7d9f..8816303ebafd 100644 --- a/llvm/test/Transforms/LoopVectorize/X86/gather_scatter.ll +++ b/llvm/test/Transforms/LoopVectorize/X86/gather_scatter.ll @@ -22,10 +22,10 @@ target triple = "x86_64-pc_linux" ; Function Attrs: nounwind uwtable define void @foo1(float* noalias %in, float* noalias %out, i32* noalias %trigger, i32* noalias %index) { ; AVX512-LABEL: @foo1( -; AVX512-NEXT: entry: +; AVX512-NEXT: iter.check: ; AVX512-NEXT:br label [[VECTOR_BODY:%.*]] ; AVX512: vector.body: -; AVX512-NEXT:[[INDEX6:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_3:%.*]], [[VECTOR_BODY]] ] +; AVX512-NEXT:[[INDEX6:%.*]] = phi i64 [ 0, [[ITER_CHECK:%.*]] ], [ [[INDEX_NEXT_3:%.*]], [[VECTOR_BODY]] ] ; AVX512-NEXT:[[TMP0:%.*]] = getelementptr inbounds i32, i32* [[TRIGGER:%.*]], i64 [[INDEX6]] ; AVX512-NEXT:[[TMP1:%.*]] = bitcast i32* [[TMP0]] to <16 x i32>* ; AVX512-NEXT:[[WIDE_LOAD:%.*]] = load <16 x i32>, <16 x i32>* [[TMP1]], align 4 diff --git a/llvm/test/Transforms/LoopVectorize/X86/invariant-load-gather.ll b/llvm/test/Transforms/LoopVectorize/X86/invariant-load-gather.ll index ed352559b5bf..f106f05730b4 100644 --- a/llvm/test/Transforms/LoopVectorize/X86/invariant-load-gather.ll +++ b/llvm/test/Transforms/LoopVectorize/X86/invariant-load-gather.ll @@ -6,12 +6,12 @@ target triple = "x86_64-unknown-linux-gnu" define i32 @inv_load_conditional(i32* %a, i64 %n, i32* %b, i32 %k) { ; CHECK-LABEL: @inv_load_conditional( -; CHECK-NEXT: entry: +; CHECK-NEXT: iter.check: ; CHECK-NEXT:[[NTRUNC:%.*]] = trunc i64 [[N:%.*]] to i32 ; CHECK-NEXT:[[TMP0:%.*]] = icmp sgt i64 [[N]], 1 ; CHECK-NEXT:[[SMAX:%.*]] = select i1 [[TMP0]], i64 [[N]], i64 1 -; CHECK-NEXT:[[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX]], 16 -; CHECK-NEXT:br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] +; CHECK-NEXT:[[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX]], 8 +; CHECK-NEXT:br i1 [[MIN_ITERS_CHECK]], label [[VEC_EPILOG_SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: ; CHECK-NEXT:[[A4:%.*]] = bitcast i32* [[A:%.*]] to i8* ; CHECK-NEXT:[[B1:%.*]] = bitcast i32* [[B:%.*]] to i8* @@ -22,20 +22,23 @@ define i32 @inv_load_conditional(i32* %a, i64 %n, i32* %b, i32 %k) { ; CHECK-NEXT:[[BOUND0:%.*]] = icmp ugt i8* [[UGLYGEP]], [[B1]] ; CHECK-NEXT:[[BOUND1:%.*]] = icmp ugt i32* [[SCEVGEP]], [[A]] ; CHECK-NEXT:[[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] -; CHECK-NEXT:br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] +; CHECK-NEXT:br i1 [[FOUND_CONFLICT]], label [[VEC_EPILOG_SCALAR_PH]], label [[VECTOR_MAIN_LOOP_ITER_CHECK:%.*]] +; CHECK: vector.main.loop.iter.check: +; CHECK-NEXT:[[MIN_ITERS_CHECK5:%.*]] = icmp ult i64 [[SMAX]], 16 +; CHECK-NEXT:br i1 [[MIN_ITERS_CHECK5]], label [[VEC_EPILOG_PH:%.*]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: ; CHECK-NEXT:[[N_VEC:%.*]] = and i64 [[SMAX]], 9223372036854775792 ; CHECK-NEXT:[[BROADCAST_SPLATINSERT:%.*]] = insertelement <16 x i32*> undef, i32* [[A]], i32 0 ; CHECK-NEXT:[[BROADCAS
[llvm-branch-commits] [llvm] 4c70b6e - [LV] Make optimal-epilog-vectorization-profitability.ll more robust
Author: Bardia Mahjour Date: 2020-12-08T12:35:08-05:00 New Revision: 4c70b6ee45e89268598d1bd0811778244f136025 URL: https://github.com/llvm/llvm-project/commit/4c70b6ee45e89268598d1bd0811778244f136025 DIFF: https://github.com/llvm/llvm-project/commit/4c70b6ee45e89268598d1bd0811778244f136025.diff LOG: [LV] Make optimal-epilog-vectorization-profitability.ll more robust Add a CHECK to properly limit the scope of CHECK-NOTs Added: Modified: llvm/test/Transforms/LoopVectorize/PowerPC/optimal-epilog-vectorization-profitability.ll Removed: diff --git a/llvm/test/Transforms/LoopVectorize/PowerPC/optimal-epilog-vectorization-profitability.ll b/llvm/test/Transforms/LoopVectorize/PowerPC/optimal-epilog-vectorization-profitability.ll index 7cb5f34fa57c..88cfa5bd40c5 100644 --- a/llvm/test/Transforms/LoopVectorize/PowerPC/optimal-epilog-vectorization-profitability.ll +++ b/llvm/test/Transforms/LoopVectorize/PowerPC/optimal-epilog-vectorization-profitability.ll @@ -16,6 +16,7 @@ target triple = "powerpc64le-unknown-linux-gnu" ; CHECK-NOT: vec.epilog.ph ; CHECK-NOT: vec.epilog.vector.body ; CHECK-NOT: vec.epilog.middle.block +; CHECK: ret void define dso_local void @f1(float* noalias %aa, float* noalias %bb, float* noalias %cc, i32 signext %N) #0 { entry: @@ -53,6 +54,7 @@ for.end: ; preds = %for.end.loopexit, % ; CHECK-NOT: vec.epilog.ph ; CHECK-NOT: vec.epilog.vector.body ; CHECK-NOT: vec.epilog.middle.block +; CHECK: ret void define dso_local void @f2(float* noalias %aa, float* noalias %bb, float* noalias %cc, i32 signext %N) #1 { entry: @@ -90,6 +92,7 @@ for.end: ; preds = %for.end.loopexit, % ; CHECK-MIN-D-NOT: vec.epilog.ph ; CHECK-MIN-D-NOT: vec.epilog.vector.body ; CHECK-MIN-D-NOT: vec.epilog.middle.block +; CHECK-MIN-D: ret void ; Specify a smaller minimum VF (via `-epilogue-vectorization-minimum-VF=4`) and ; make sure the epilogue gets vectorized in that case. @@ -99,6 +102,7 @@ for.end: ; preds = %for.end.loopexit, % ; CHECK-MIN-4: vec.epilog.ph ; CHECK-MIN-4: vec.epilog.vector.body ; CHECK-MIN-4: vec.epilog.middle.block +; CHECK-MIN-4: ret void define dso_local void @f3(float* noalias %aa, float* noalias %bb, float* noalias %cc, i32 signext %N) { entry: ___ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits