From 4d6b8d4213376e8a2405782c7e360b03d4a2b04a Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 13 Nov 2020 13:17:01 +0100 Subject: [PATCH] improve VN PHI hashing This reduces the number of collisions for PHIs in the VN hashtable by always hashing the number of predecessors and separately hashing the block number when we never merge PHIs from different blocks. This improves collisions seen for the PR69609 testcase dramatically. 2020-11-13 Richard Biener * tree-ssa-sccvn.c (vn_phi_compute_hash): Always hash the number of predecessors. Hash the block number also for loop header PHIs. (expressions_equal_p): Short-cut SSA name compares, remove test for NULL operands. (vn_phi_eq): Cache number of predecessors, change inlined test from expressions_equal_p. --- gcc/tree-ssa-sccvn.c | 27 +++++++++++++++++++++------ 1 file changed, 21 insertions(+), 6 deletions(-) diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 8c93e515b6c..4d78054b1e0 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -4126,13 +4126,27 @@ vn_nary_op_insert_stmt (gimple *stmt, tree result) static inline hashval_t vn_phi_compute_hash (vn_phi_t vp1) { - inchash::hash hstate (EDGE_COUNT (vp1->block->preds) > 2 - ? vp1->block->index : EDGE_COUNT (vp1->block->preds)); + inchash::hash hstate; tree phi1op; tree type; edge e; edge_iterator ei; + hstate.add_int (EDGE_COUNT (vp1->block->preds)); + switch (EDGE_COUNT (vp1->block->preds)) + { + case 1: + break; + case 2: + if (vp1->block->loop_father->header == vp1->block) + ; + else + break; + /* Fallthru. */ + default: + hstate.add_int (vp1->block->index); + } + /* If all PHI arguments are constants we need to distinguish the PHI node via its type. */ type = vp1->type; @@ -4277,11 +4291,12 @@ vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2) /* Any phi in the same block will have it's arguments in the same edge order, because of how we store phi nodes. */ - for (unsigned i = 0; i < EDGE_COUNT (vp1->block->preds); ++i) + unsigned nargs = EDGE_COUNT (vp1->block->preds); + for (unsigned i = 0; i < nargs; ++i) { tree phi1op = vp1->phiargs[i]; tree phi2op = vp2->phiargs[i]; - if (phi1op == VN_TOP || phi2op == VN_TOP) + if (phi1op == phi2op) continue; if (!expressions_equal_p (phi1op, phi2op)) return false; @@ -5612,8 +5627,8 @@ expressions_equal_p (tree e1, tree e2) if (e1 == VN_TOP || e2 == VN_TOP) return true; - /* If only one of them is null, they cannot be equal. */ - if (!e1 || !e2) + /* SSA_NAME compare pointer equal. */ + if (TREE_CODE (e1) == SSA_NAME || TREE_CODE (e2) == SSA_NAME) return false; /* Now perform the actual comparison. */ -- 2.30.2