pascal-lab/Tai-e

CHA seems slower than context-insensitive pointer analysis

Closed this issue · 4 comments

enochii commented

Description

Hello, I ran Tai-e to construct call graph for benchmark antlr with both CHA and context-insentive (CI) pointer analysis. The results seems a bit surprising: CHA is slower than CI. I wonder if this is reasonable, or I was doing something wrong here.

Here is the command line options and the corresponding outputs:

CHA:

-cp java-benchmarks\dacapo-2006\antlr.jar;java-benchmarks\dacapo-2006\antlr-deps.jar -m dacapo.antlr.Main -java 6 -a cg=algorithm:cha;dump-methods:true;dump-call-edges:true

5645 classes with 53961 methods in the world
WorldBuilder finishes, elapsed time: 5.40s
cg starts ...
Call graph has 30583 reachable methods and 537515 edges
Dumping reachable methods to output\reachable-methods.txt
Dumping call edges to output\call-edges.txt
cg finishes, elapsed time: 105.09s
Tai-e finishes, elapsed time: 110.83s

CI:

-cp java-benchmarks\dacapo-2006\antlr.jar;java-benchmarks\dacapo-2006\antlr-deps.jar -m dacapo.antlr.Main -java 6 -a pta=cs:ci -a cg=dump-methods:true;dump-call-edges:true

5645 classes with 53961 methods in the world
WorldBuilder finishes, elapsed time: 5.73s
pta starts ...
[Pointer analysis] elapsed time: 12.09s
...
pta finishes, elapsed time: 14.04s
cg starts ...
Call graph has 8040 reachable methods and 46189 edges
Dumping reachable methods to output\reachable-methods.txt
Dumping call edges to \output\call-edges.txt
cg finishes, elapsed time: 0.52s
Tai-e finishes, elapsed time: 20.63s
zhangt2333 commented 
cg starts ...
Call graph has 30583 reachable methods and 537515 edges
Dumping reachable methods to output\reachable-methods.txt
Dumping call edges to output\call-edges.txt
cg finishes, elapsed time: 105.09s
cg starts ...
Call graph has 8040 reachable methods and 46189 edges
Dumping reachable methods to output\reachable-methods.txt
Dumping call edges to \output\call-edges.txt
cg finishes, elapsed time: 0.52s

It's important to note that CHA introduced a larger call graph, which will make dumping (dump-methods:true; dump-call-edges:true) more time-consuming.

enochii commented

I don't think this dumping option is the main reason here. I re-ran CHA without dumping (cg=algorithm:cha;dump-methods:false;dump-call-edges:false). Here is the results:

-cp java-benchmarks\dacapo-2006\antlr.jar;java-benchmarks\dacapo-2006\antlr-deps.jar -m dacapo.antlr.Main -java 6 -a cg=algorithm:cha;dump-methods:false;dump-call-edges:false

WorldBuilder starts ...
5645 classes with 53961 methods in the world
WorldBuilder finishes, elapsed time: 5.16s
cg starts ...
Call graph has 30583 reachable methods and 537515 edges
cg finishes, elapsed time: 80.00s
Tai-e finishes, elapsed time: 85.56s
zhangt2333 commented

The implementation of CHA in Tai-e is not well optimized like Pointer Analysis (CI) in Tai-e.

CHA suffers from poor precision, as it introduces more call graph edges, especially with methods like hashCode, equals, and toString from java.lang.Object.

zhangt2333 commented

Option --pre-build-ir is suggested to enabled (to exclude the impact of frontend) for a fairer comparison.

I have done some optimization in the CHABuilder (Commit 083f0cc). Here are the results after optimization:

  • CHA:
-cp java-benchmarks\dacapo-2006\antlr.jar;java-benchmarks\dacapo-2006\antlr-deps.jar -m dacapo.antlr.Main -java 6 -a cg=algorithm:cha --pre-build-ir

WorldBuilder starts ...
[Build IR for all methods] elapsed time: 8.96s
5645 classes with 53961 methods in the world
WorldBuilder finishes, elapsed time: 13.63s
cg starts ...
Call graph has 30583 reachable methods and 537515 edges
cg finishes, elapsed time: 0.62s
Tai-e finishes, elapsed time: 14.51s
  • PTA(CI):
-cp java-benchmarks\dacapo-2006\antlr.jar;java-benchmarks\dacapo-2006\antlr-deps.jar -m dacapo.antlr.Main -java 6 -a cg=algorithm:pta --pre-build-ir

WorldBuilder starts ...
[Build IR for all methods] elapsed time: 8.39s
5645 classes with 53961 methods in the world
WorldBuilder finishes, elapsed time: 12.38s
pta starts ...
[Pointer analysis] elapsed time: 2.26s
...
pta finishes, elapsed time: 2.78s
cg starts ...
Call graph has 8040 reachable methods and 46189 edges
cg finishes, elapsed time: 0.00s
Tai-e finishes, elapsed time: 15.38s
  • 👍1