[llvm-branch-commits] [llvm] ebfe4de - [DDG] Fix duplicate edge removal during pi-block formation

2021-01-07 Thread Bardia Mahjour via llvm-branch-commits

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

2021-01-07 Thread Bardia Mahjour via llvm-branch-commits

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

2020-12-14 Thread Bardia Mahjour via llvm-branch-commits

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"

2020-12-14 Thread Bardia Mahjour via llvm-branch-commits

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

2020-12-16 Thread Bardia Mahjour via llvm-branch-commits

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

2020-12-07 Thread Bardia Mahjour via llvm-branch-commits

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

2020-12-08 Thread Bardia Mahjour via llvm-branch-commits

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