diff options
| author | Richard Biener <rguenther@suse.de> | 2021-04-29 08:32:00 +0200 |
|---|---|---|
| committer | Richard Biener <rguenther@suse.de> | 2021-04-29 10:02:59 +0200 |
| commit | c57a8aea0c3ab8394f7dbfa417ee27b4613f63b7 (patch) | |
| tree | 4d498411bb34de7ba9c037734e507cabab92b093 /gcc/tree-ssa-structalias.c | |
| parent | 2e8ee0a364ac7dc9959b1caac7d7145afedd1eaa (diff) | |
| download | gcc-c57a8aea0c3ab8394f7dbfa417ee27b4613f63b7.zip gcc-c57a8aea0c3ab8394f7dbfa417ee27b4613f63b7.tar.gz gcc-c57a8aea0c3ab8394f7dbfa417ee27b4613f63b7.tar.bz2 | |
middle-end/38474 - speedup PTA constraint solving
In testcases like PR38474 and PR99912 we're seeing very slow
PTA solving. One can observe an excessive amount of forwarding,
mostly during sd constraint solving. The way we solve the graph
does not avoid forwarding the same bits through multiple paths,
and especially when such alternate path involves ESCAPED as
intermediate this causes the ESCAPED solution to be expanded
in receivers.
The following adds heuristic to add_graph_edge which adds
forwarding edges but also guards the initial solution forwarding
(which is the expensive part) to detect the case of ESCAPED
receiving the same set and the destination already containing
ESCAPED.
This speeds up the PTA solving process by more than 50%.
2021-04-29 Richard Biener <rguenther@suse.de>
PR middle-end/38474
* tree-ssa-structalias.c (add_graph_edge): Avoid direct
forwarding when indirect forwarding through ESCAPED
alread happens.
Diffstat (limited to 'gcc/tree-ssa-structalias.c')
| -rw-r--r-- | gcc/tree-ssa-structalias.c | 16 |
1 files changed, 16 insertions, 0 deletions
diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c index 529ec3a..a023871 100644 --- a/gcc/tree-ssa-structalias.c +++ b/gcc/tree-ssa-structalias.c @@ -1195,6 +1195,22 @@ add_graph_edge (constraint_graph_t graph, unsigned int to, if (!graph->succs[from]) graph->succs[from] = BITMAP_ALLOC (&pta_obstack); + + /* The graph solving process does not avoid "triangles", thus + there can be multiple paths from a node to another involving + intermediate other nodes. That causes extra copying which is + most difficult to avoid when the intermediate node is ESCAPED + because there are no edges added from ESCAPED. Avoid + adding the direct edge FROM -> TO when we have FROM -> ESCAPED + and TO contains ESCAPED. + ??? Note this is only a heuristic, it does not prevent the + situation from occuring. The heuristic helps PR38474 and + PR99912 significantly. */ + if (to < FIRST_REF_NODE + && bitmap_bit_p (graph->succs[from], find (escaped_id)) + && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id)) + return false; + if (bitmap_set_bit (graph->succs[from], to)) { r = true; |