en Copyright 2015 Java http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#0a2626d0 [DDG] Data Dependence Graph - Graph SimplificationSummary:This is the last functional patch affecting the representation of DDG.Here we try to simplify the DDG to reduce the number of nodes and edges byiteratively merging pairs of nodes that satisfy the following conditions,until no such pair can be identified. A pair of nodes consisting of a and bcan be merged if: 1. the only edge from a is a def-use edge to b and 2. the only edge to b is a def-use edge from a and 3. there is no cyclic edge from b to a and 4. all instructions in a and b belong to the same basic block and 5. both a and b are simple (single or multi instruction) nodes.These criteria allow us to fold many uninteresting def-use edges thatcommonly exist in the graph while avoiding the risk of introducingdependencies that didn't exist before.Authored By: bmahjourReviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfertReviewed By: MeinersburSubscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slackTags: #llvmDifferential Revision: https://reviews.llvm.org/D72350 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Tue, 18 Feb 2020 21:38:10 +0000 Bardia Mahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#86acaa94 [DDG] Data Dependence Graph - OrdinalsSummary:This patch associates ordinal numbers to the DDG Nodes allowingthe builder to order nodes within a pi-block in program order. Thealgorithm works by simply assuming the order in which the BBListis fed into the builder. The builder already relies on the blocks beingin program order so that it can compute the dependencies correctly.Similarly the order of instructions in their parent basic blocksdetermine their program order.Authored By: bmahjourReviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfertReviewed By: MeinersburSubscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slackTags: #llvmDifferential Revision: https://reviews.llvm.org/D70986 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Thu, 19 Dec 2019 15:56:44 +0000 Bardia Mahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#2dd82a1c [DDG] Data Dependence Graph - Topological Sort (Memory Leak Fix)Summary:This fixes the memory leak in bec37c3fc766a7b97f8c52c181c325fd47b75259and re-delivers the reverted patch.In this patch the DDG DAG is sorted topologically to put thenodes in the graph in the order that would satisfy alldependencies. This helps transformations that would like togenerate code based on the DDG. Since the DDG is a DAG areverse-post-order traversal would give us the topologicalordering. This patch also sorts the basic blocks passed tothe builder based on program order to ensure that thedependencies are computed in the correct direction.Authored By: bmahjourReviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfertReviewed By: MeinersburSubscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slackTags: #llvmDifferential Revision: https://reviews.llvm.org/D70609 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Mon, 02 Dec 2019 20:23:26 +0000 Bardia Mahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#67f0685b Revert "[DDG] Data Dependence Graph - Topological Sort"Revert for now to look into the failures on x86This reverts commit bec37c3fc766a7b97f8c52c181c325fd47b75259. List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Mon, 25 Nov 2019 21:17:41 +0000 Bardia Mahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#bec37c3f [DDG] Data Dependence Graph - Topological SortSummary:In this patch the DDG DAG is sorted topologically to put thenodes in the graph in the order that would satisfy alldependencies. This helps transformations that would like togenerate code based on the DDG. Since the DDG is a DAG areverse-post-order traversal would give us the topologicalordering. This patch also sorts the basic blocks passed tothe builder based on program order to ensure that thedependencies are computed in the correct direction.Authored By: bmahjourReviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfertReviewed By: MeinersburSubscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slackTags: #llvmDifferential Revision: https://reviews.llvm.org/D70609 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Mon, 25 Nov 2019 16:12:37 +0000 bmahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#f0af11d8 [DDG] Data Dependence Graph - Pi Block Summary: This patch adds Pi Blocks to the DDG. A pi-block represents a group of DDG nodes that are part of a strongly-connected component of the graph. Replacing all the SCCs with pi-blocks results in an acyclic representation of the DDG. For example if we have: {a -> b}, {b -> c, d}, {c -> a} the cycle a -> b -> c -> a is abstracted into a pi-block "p" as follows: {p -> d} with "p" containing: {a -> b}, {b -> c}, {c -> a} In this implementation the edges between nodes that are part of the pi-block are preserved. The crossing edges (edges where one end of the edge is in the set of nodes belonging to an SCC and the other end is outside that set) are replaced with corresponding edges to/from the pi-block node instead. Authored By: bmahjour Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert Reviewed By: Meinersbur Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slack Tag: #llvm Differential Revision: https://reviews.llvm.org/D68827 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Fri, 08 Nov 2019 20:05:06 +0000 bmahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#db800c26 Data Dependence Graph BasicsSummary:This is the first patch in a series of patches that will implement data dependence graph in LLVM. Many of the ideas used in this implementation are based on the following paper:D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS.This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges.The implementation takes a list of basic-blocks and only considers dependencies among instructions in those basic blocks. Any dependencies coming into or going out of instructions that do not belong to those basic blocks are ignored.The algorithm for building the graph involves the following steps in order: 1. For each instruction in the range of basic blocks to consider, create an atomic node in the resulting graph. 2. For each node in the graph establish def-use edges to/from other nodes in the graph. 3. For each pair of nodes containing memory instruction(s) create memory edges between them. This part of the algorithm goes through the instructions in lexicographical order and creates edges in reverse order if the sink of the dependence occurs before the source of it.Authored By: bmahjourReviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfertReviewed By: Meinersbur, fhahn, myhsuSubscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiottoTag: #llvmDifferential Revision: https://reviews.llvm.org/D65350llvm-svn: 372238 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Wed, 18 Sep 2019 17:43:45 +0000 Bardia Mahjour <bmahjour@ca.ibm.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll#c98ec609 Data Dependence Graph BasicsSummary:This is the first patch in a series of patches that will implement data dependence graph in LLVM. Many of the ideas used in this implementation are based on the following paper:D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS.This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges.The implementation takes a list of basic-blocks and only considers dependencies among instructions in those basic blocks. Any dependencies coming into or going out of instructions that do not belong to those basic blocks are ignored.The algorithm for building the graph involves the following steps in order: 1. For each instruction in the range of basic blocks to consider, create an atomic node in the resulting graph. 2. For each node in the graph establish def-use edges to/from other nodes in the graph. 3. For each pair of nodes containing memory instruction(s) create memory edges between them. This part of the algorithm goes through the instructions in lexicographical order and creates edges in reverse order if the sink of the dependence occurs before the source of it.Authored By: bmahjourReviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfertReviewed By: Meinersbur, fhahn, myhsuSubscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiottoTag: #llvmDifferential Revision: https://reviews.llvm.org/D65350llvm-svn: 372162 List of files: /llvm-project-15.0.7/llvm/test/Analysis/DDG/basic-a.ll Tue, 17 Sep 2019 18:55:44 +0000 Bardia Mahjour <bmahjour@ca.ibm.com>