Use a points-to graph for alias analysis (#16386)
authorMichael Suo <suo@fb.com>
Wed, 30 Jan 2019 19:06:32 +0000 (11:06 -0800)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Wed, 30 Jan 2019 19:28:03 +0000 (11:28 -0800)
commitdc84ff1e5a74164d668fa1afac9e0e0f2315f3b2
treed309fd3dd58ce2477f1d866e53aaf645553ee30a
parentdff8165d04f589dcaca42b76650340e220628f40
Use a points-to graph for alias analysis (#16386)

Summary:
This PR changes the way we store aliasing information from a "set" approach to a "points-to" analysis. Set-based approaches lose information in ways that make it difficult to do "live" updates to the alias DB as one as mutating the graph.

The tradeoff is that simple queries get more expensive, since they require traversing the points-to graph to answer most questions. In practice, this is unlikely to be that costly since we don't have massive aliasing chains, but we could create an approximation/caching layer if this becomes a problem.

My rough plan is:
1. This PR, switching to a points-to graph
2. Make it "live": analyzing a node should record all the edges the node added, so that we can rollback when the node is destroyed.
3. Reduce wildcard scope: we can make the wildcard a special vertex that points to anything that we're not "sure" about; namely, things that have been put inside lists, or graph inputs.
Pull Request resolved: https://github.com/pytorch/pytorch/pull/16386

Differential Revision: D13855117

Pulled By: suo

fbshipit-source-id: f009f58143173c275501624eb105d07ab60fe5e1
13 files changed:
test/cpp/jit/no-gtest.cpp
test/cpp/jit/tests.h
test/test_jit.py
torch/csrc/jit/passes/alias_analysis.cpp
torch/csrc/jit/passes/alias_analysis.h
torch/csrc/jit/passes/batch_mm.cpp
torch/csrc/jit/passes/common_subexpression_elimination.cpp
torch/csrc/jit/passes/constant_propagation.cpp
torch/csrc/jit/passes/create_autodiff_subgraphs.cpp
torch/csrc/jit/passes/dead_code_elimination.cpp
torch/csrc/jit/passes/graph_fuser.cpp
torch/csrc/jit/passes/shape_analysis.cpp
torch/csrc/jit/python_ir.cpp