* backwards threader cleanups @ 2017-09-01 20:18 Aldy Hernandez 2017-09-01 22:11 ` Jeff Law 2017-09-02 2:16 ` Trevor Saunders 0 siblings, 2 replies; 7+ messages in thread From: Aldy Hernandez @ 2017-09-01 20:18 UTC (permalink / raw) To: gcc-patches; +Cc: Jeff Law [-- Attachment #1: Type: text/plain, Size: 434 bytes --] Hi. Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. The main gist of the patch is making the path vectors live in the heap, not GC. But I also cleaned up some comments to reflect reality, and renamed VAR_BB which could use a more meaningful name. Finally, I abstracted some common code to register_jump_thread_path_if_profitable() in preparation for some upcoming work by me :). Tested on x86-64 Linux. OK? [-- Attachment #2: curr --] [-- Type: application/octet-stream, Size: 22666 bytes --] gcc/ * tree-ssa-threadbackward.c (fsm_find_thread_path): Make GC vectors heap vectors. Clean up comments. (profitable_jump_thread_path): Same. Misc cleanups. (convert_and_register_jump_thread_path): Make GC vectors heap vectors. (check_subpath_and_update_thread_path): Same. Clean up comments. (handle_phi): Abstract common code to to register_jump_thread_path_if_profitable. Rename VAR_BB to DEF_BB. Update comments. Make GC vectors heap vectors. (handle_assignment): Same. (register_jump_thread_path_if_profitable): New. (fsm_find_control_statement_thread_paths): Rename VAR_BB to DEF_BB. Make GC vectors heap vectors. Clean up comments. * tree-ssa-threadupdate.c (delete_jump_thread_path): Fix typo in comment. diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 24def1deed9..73105c9c387 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -59,14 +59,15 @@ get_gimple_control_stmt (basic_block bb) return NULL; } -/* Return true if the CFG contains at least one path from START_BB to END_BB. - When a path is found, record in PATH the blocks from END_BB to START_BB. - VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound - the recursion to basic blocks belonging to LOOP. */ +/* Return true if the CFG contains at least one path from START_BB to + END_BB. When a path is found, record in PATH the blocks from + END_BB to START_BB. VISITED_BBS is used to make sure we don't fall + into an infinite loop. Bound the recursion to basic blocks + belonging to LOOP. */ static bool fsm_find_thread_path (basic_block start_bb, basic_block end_bb, - vec<basic_block, va_gc> *&path, + vec<basic_block> &path, hash_set<basic_block> *visited_bbs, loop_p loop) { if (loop != start_bb->loop_father) @@ -74,7 +75,7 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, if (start_bb == end_bb) { - vec_safe_push (path, start_bb); + path.safe_push (start_bb); return true; } @@ -85,7 +86,7 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, FOR_EACH_EDGE (e, ei, start_bb->succs) if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) { - vec_safe_push (path, start_bb); + path.safe_push (start_bb); return true; } } @@ -99,21 +100,21 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, final taken edge from the path, NULL otherwise. NAME is the SSA_NAME of the variable we found to have a constant - value on PATH. ARG is the value of that SSA_NAME. + value on PATH. ARG is the constant value of NAME on that path. BBI will be appended to PATH when we have a profitable jump threading path. Callers are responsible for removing BBI from PATH in that case. - SPEED_P indicate that we could increase code size to improve the code path */ + SPEED_P indicate that we could increase code size to improve the + code path. */ static edge -profitable_jump_thread_path (vec<basic_block, va_gc> *&path, - basic_block bbi, tree name, tree arg, bool speed_p, - bool *creates_irreducible_loop) +profitable_jump_thread_path (vec<basic_block> &path, + basic_block bbi, tree name, tree arg, + bool speed_p, bool *creates_irreducible_loop) { /* Note BBI is not in the path yet, hence the +1 in the test below to make sure BBI is accounted for in the path length test. */ - int path_length = path->length (); /* We can get a length of 0 here when the statement that makes a conditional generate a compile-time constant @@ -124,10 +125,10 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, wanted by wiring up all the incoming edges. If we run this early in IPA, that might be worth doing. For now we just reject that case. */ - if (path_length == 0) + if (path.is_empty ()) return NULL; - if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) + if (path.length () + 1 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "FSM jump-thread path not considered: " @@ -148,13 +149,11 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, /* Add BBI to the path. From this point onward, if we decide we the path is not profitable to thread, we must remove BBI from the path. */ - vec_safe_push (path, bbi); - ++path_length; + path.safe_push (bbi); int n_insns = 0; gimple_stmt_iterator gsi; - int j; - loop_p loop = (*path)[0]->loop_father; + loop_p loop = path[0]->loop_father; bool path_crosses_loops = false; bool threaded_through_latch = false; bool multiway_branch_in_path = false; @@ -168,9 +167,9 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, will have to be duplicated, we will not record the path if there are too many instructions on the path. Also check that all the blocks in the path belong to a single loop. */ - for (j = 0; j < path_length; j++) + for (unsigned j = 0; j < path.length (); j++) { - basic_block bb = (*path)[j]; + basic_block bb = path[j]; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " bb:%i", bb->index); @@ -181,7 +180,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, loop father, nor how many statements are in that block because it will not be copied or whether or not it ends in a multiway branch. */ - if (j < path_length - 1) + if (j < path.length () - 1) { int orig_n_insns = n_insns; if (bb->loop_father != loop) @@ -268,7 +267,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, threaded_through_latch = true; } - gimple *stmt = get_gimple_control_stmt ((*path)[0]); + gimple *stmt = get_gimple_control_stmt (path[0]); gcc_assert (stmt); /* We are going to remove the control statement at the end of the @@ -301,14 +300,14 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, latch, then this thread would create an irreducible loop. We have to know the outgoing edge to figure this out. */ - edge taken_edge = find_taken_edge ((*path)[0], arg); + edge taken_edge = find_taken_edge (path[0], arg); /* There are cases where we may not be able to extract the taken edge. For example, a computed goto to an absolute address. Handle those cases gracefully. */ if (taken_edge == NULL) { - path->pop (); + path.pop (); return NULL; } @@ -324,7 +323,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "FSM jump-thread path not considered: " "the path crosses loops.\n"); - path->pop (); + path.pop (); return NULL; } @@ -340,7 +339,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM jump-thread path not considered: " "the number of instructions on the path " "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n"); - path->pop (); + path.pop (); return NULL; } } @@ -350,7 +349,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM jump-thread path not considered: " "duplication of %i insns is needed and optimizing for size.\n", n_insns); - path->pop (); + path.pop (); return NULL; } @@ -364,15 +363,16 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, optimizer would have done anyway, so an irreducible loop is not so bad. */ if (!threaded_multiway_branch && *creates_irreducible_loop - && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) - > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))) + && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) + > (path.length () * + (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS)))) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "FSM would create irreducible loop without threading " "multiway branch.\n"); - path->pop (); + path.pop (); return NULL; } @@ -392,7 +392,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM did not thread around loop and would copy too " "many statements.\n"); - path->pop (); + path.pop (); return NULL; } @@ -406,7 +406,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM Thread through multiway branch without threading " "a multiway branch.\n"); - path->pop (); + path.pop (); return NULL; } return taken_edge; @@ -419,16 +419,15 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, register the path. */ static void -convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path, - edge taken_edge) +convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge) { vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> (); /* Record the edges between the blocks in PATH. */ - for (unsigned int j = 0; j < path->length () - 1; j++) + for (unsigned int j = 0; j + 1 < path.length (); j++) { - basic_block bb1 = (*path)[path->length () - j - 1]; - basic_block bb2 = (*path)[path->length () - j - 2]; + basic_block bb1 = path[path.length () - j - 1]; + basic_block bb2 = path[path.length () - j - 2]; edge e = find_edge (bb1, bb2); gcc_assert (e); @@ -445,26 +444,27 @@ convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path, --max_threaded_paths; } -/* While following a chain of SSA_NAME definitions, we jumped from a definition - in LAST_BB to a definition in VAR_BB (walking backwards). +/* While following a chain of SSA_NAME definitions, we jumped from a + definition in LAST_BB to a definition in NEW_BB (walking + backwards). - Verify there is a single path between the blocks and none of the blocks - in the path is already in VISITED_BBS. If so, then update VISISTED_BBS, - add the new blocks to PATH and return TRUE. Otherwise return FALSE. + Verify there is a single path between the blocks and none of the + blocks in the path is already in VISITED_BBS. If so, then update + VISISTED_BBS, add the new blocks to PATH and return TRUE. + Otherwise return FALSE. Store the length of the subpath in NEXT_PATH_LENGTH. */ static bool check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + vec<basic_block> &path, int *next_path_length) { edge e; int e_count = 0; edge_iterator ei; - vec<basic_block, va_gc> *next_path; - vec_alloc (next_path, 10); + vec<basic_block> next_path = vNULL; FOR_EACH_EDGE (e, ei, last_bb->preds) { @@ -479,7 +479,7 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, /* If there is more than one path, stop. */ if (e_count > 1) { - vec_free (next_path); + next_path.release (); return false; } } @@ -488,39 +488,72 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, is stopped by one of the bounds. */ if (e_count == 0) { - vec_free (next_path); + next_path.release (); return false; } /* Make sure we haven't already visited any of the nodes in NEXT_PATH. Don't add them here to avoid pollution. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) + for (unsigned int i = 0; i + 1 < next_path.length (); i++) { - if (visited_bbs->contains ((*next_path)[i])) + if (visited_bbs->contains (next_path[i])) { - vec_free (next_path); + next_path.release (); return false; } } /* Now add the nodes to VISISTED_BBS. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) - visited_bbs->add ((*next_path)[i]); + for (unsigned int i = 0; i + 1 < next_path.length (); i++) + visited_bbs->add (next_path[i]); /* Append all the nodes from NEXT_PATH to PATH. */ - vec_safe_splice (path, next_path); - *next_path_length = next_path->length (); - vec_free (next_path); + path.safe_splice (next_path); + *next_path_length = next_path.length (); + next_path.release (); return true; } +/* If this is a profitable jump thread path, register it. + + NAME is an SSA NAME with a possible constant value of ARG on PATH. + + DEF_BB is the basic block that ultimately defines the constant. + + SPEED_P indicate that we could increase code size to improve the + code path. +*/ + +static void +register_jump_thread_path_if_profitable (vec<basic_block> &path, + tree name, + tree arg, + basic_block def_bb, + bool speed_p) +{ + if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) + return; + + bool irreducible = false; + edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg, + speed_p, &irreducible); + if (taken_edge) + { + convert_and_register_jump_thread_path (path, taken_edge); + path.pop (); + + if (irreducible) + vect_free_loop_info_assumptions (path[0]->loop_father); + } +} + static void fsm_find_control_statement_thread_paths (tree, hash_set<basic_block> *, - vec<basic_block, va_gc> *&, + vec<basic_block> &, bool, bool); -/* Given PHI which defines NAME in block VAR_BB, recurse through the +/* Given PHI which defines NAME in block DEF_BB, recurse through the PHI's arguments searching for paths where NAME will ultimately have a constant value. @@ -534,9 +567,9 @@ static void fsm_find_control_statement_thread_paths (tree, SPEED_P indicates if we are optimizing for speed over space. */ static void -handle_phi (gphi *phi, tree name, basic_block var_bb, +handle_phi (gphi *phi, tree name, basic_block def_bb, hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + vec<basic_block> &path, bool seen_loop_phi, bool speed_p) { /* Iterate over the arguments of PHI. */ @@ -546,37 +579,22 @@ handle_phi (gphi *phi, tree name, basic_block var_bb, basic_block bbi = gimple_phi_arg_edge (phi, i)->src; /* Skip edges pointing outside the current loop. */ - if (!arg || var_bb->loop_father != bbi->loop_father) + if (!arg || def_bb->loop_father != bbi->loop_father) continue; if (TREE_CODE (arg) == SSA_NAME) { - vec_safe_push (path, bbi); + path.safe_push (bbi); /* Recursively follow SSA_NAMEs looking for a constant definition. */ fsm_find_control_statement_thread_paths (arg, visited_bbs, path, seen_loop_phi, speed_p); - path->pop (); + path.pop (); continue; } - if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) - continue; - - /* If this is a profitable jump thread path, then convert it - into the canonical form and register it. */ - bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg, - speed_p, &irreducible); - if (taken_edge) - { - convert_and_register_jump_thread_path (path, taken_edge); - path->pop (); - - if (irreducible) - vect_free_loop_info_assumptions ((*path)[0]->loop_father); - } + register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p); } } @@ -610,7 +628,7 @@ handle_assignment_p (gimple *stmt) return false; } -/* Given STMT which defines NAME in block VAR_BB, recurse through the +/* Given STMT which defines NAME in block DEF_BB, recurse through the PHI's arguments searching for paths where NAME will ultimately have a constant value. @@ -624,9 +642,9 @@ handle_assignment_p (gimple *stmt) SPEED_P indicates if we are optimizing for speed over space. */ static void -handle_assignment (gimple *stmt, tree name, basic_block var_bb, +handle_assignment (gimple *stmt, tree name, basic_block def_bb, hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + vec<basic_block> &path, bool seen_loop_phi, bool speed_p) { tree arg = gimple_assign_rhs1 (stmt); @@ -637,40 +655,31 @@ handle_assignment (gimple *stmt, tree name, basic_block var_bb, else { - /* profitable_jump_thread_path is going to push the current + /* register_jump_thread_path_if_profitable will push the current block onto the path. But the path will always have the current block at this point. So we can just pop it. */ - path->pop (); + path.pop (); - bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, var_bb, - name, arg, speed_p, - &irreducible); - if (taken_edge) - { - convert_and_register_jump_thread_path (path, taken_edge); - path->pop (); - - if (irreducible) - vect_free_loop_info_assumptions ((*path)[0]->loop_father); - } + register_jump_thread_path_if_profitable (path, name, arg, def_bb, + speed_p); /* And put the current block back onto the path so that the state of the stack is unchanged when we leave. */ - vec_safe_push (path, var_bb); + path.safe_push (def_bb); } } -/* We trace the value of the SSA_NAME NAME back through any phi nodes looking - for places where it gets a constant value and save the path. Stop after - having recorded MAX_PATHS jump threading paths. +/* We trace the value of the SSA_NAME NAME back through any phi nodes + looking for places where it gets a constant value and save the + path. - SPEED_P indicate that we could increase code size to improve the code path */ + SPEED_P indicate that we could increase code size to improve the + code path. */ static void fsm_find_control_statement_thread_paths (tree name, hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + vec<basic_block> &path, bool seen_loop_phi, bool speed_p) { /* If NAME appears in an abnormal PHI, then don't try to trace its @@ -679,9 +688,9 @@ fsm_find_control_statement_thread_paths (tree name, return; gimple *def_stmt = SSA_NAME_DEF_STMT (name); - basic_block var_bb = gimple_bb (def_stmt); + basic_block def_bb = gimple_bb (def_stmt); - if (var_bb == NULL) + if (def_bb == NULL) return; /* We allow the SSA chain to contains PHIs and simple copies and constant @@ -700,11 +709,11 @@ fsm_find_control_statement_thread_paths (tree name, return; /* Avoid infinite recursion. */ - if (visited_bbs->add (var_bb)) + if (visited_bbs->add (def_bb)) return; int next_path_length = 0; - basic_block last_bb_in_path = path->last (); + basic_block last_bb_in_path = path.last (); if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt)) { @@ -715,33 +724,33 @@ fsm_find_control_statement_thread_paths (tree name, } /* Following the chain of SSA_NAME definitions, we jumped from a definition in - LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are - different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ - if (var_bb != last_bb_in_path) + LAST_BB_IN_PATH to a definition in DEF_BB. When these basic blocks are + different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB. */ + if (def_bb != last_bb_in_path) { - /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path + /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path will already be in VISITED_BBS. When they are not equal, then we must ensure that first block is accounted for to ensure we do not create bogus jump threading paths. */ - visited_bbs->add ((*path)[0]); - if (!check_subpath_and_update_thread_path (last_bb_in_path, var_bb, + visited_bbs->add (path[0]); + if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb, visited_bbs, path, &next_path_length)) return; } - gcc_assert (path->last () == var_bb); + gcc_assert (path.last () == def_bb); if (gimple_code (def_stmt) == GIMPLE_PHI) - handle_phi (as_a <gphi *> (def_stmt), name, var_bb, + handle_phi (as_a <gphi *> (def_stmt), name, def_bb, visited_bbs, path, seen_loop_phi, speed_p); else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) - handle_assignment (def_stmt, name, var_bb, + handle_assignment (def_stmt, name, def_bb, visited_bbs, path, seen_loop_phi, speed_p); /* Remove all the nodes that we added from NEXT_PATH. */ if (next_path_length) - vec_safe_truncate (path, (path->length () - next_path_length)); + path.truncate (path.length () - next_path_length); } /* Search backwards from BB looking for paths where NAME (an SSA_NAME) @@ -749,7 +758,8 @@ fsm_find_control_statement_thread_paths (tree name, It is assumed that BB ends with a control statement and that by finding a path where NAME is a constant, we can thread the path. - SPEED_P indicate that we could increase code size to improve the code path */ + SPEED_P indicate that we could increase code size to improve the + code path. */ void find_jump_threads_backwards (basic_block bb, bool speed_p) @@ -776,9 +786,8 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) if (!name || TREE_CODE (name) != SSA_NAME) return; - vec<basic_block, va_gc> *bb_path; - vec_alloc (bb_path, 10); - vec_safe_push (bb_path, bb); + vec<basic_block> bb_path = vNULL; + bb_path.safe_push (bb); hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); @@ -786,7 +795,7 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) speed_p); delete visited_bbs; - vec_free (bb_path); + bb_path.release (); } namespace { diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 9da74675eef..d5d534fde04 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2588,7 +2588,7 @@ thread_through_all_blocks (bool may_peel_loop_headers) return retval; } -/* Delete the jump threading path PATH. We have to explcitly delete +/* Delete the jump threading path PATH. We have to explicitly delete each entry in the vector, then the container. */ void ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: backwards threader cleanups 2017-09-01 20:18 backwards threader cleanups Aldy Hernandez @ 2017-09-01 22:11 ` Jeff Law 2017-09-02 17:43 ` Aldy Hernandez 2017-09-02 2:16 ` Trevor Saunders 1 sibling, 1 reply; 7+ messages in thread From: Jeff Law @ 2017-09-01 22:11 UTC (permalink / raw) To: Aldy Hernandez, gcc-patches On 09/01/2017 02:18 PM, Aldy Hernandez wrote: > Hi. > > Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. > The main gist of the patch is making the path vectors live in the > heap, not GC. But I also cleaned up some comments to reflect reality, > and renamed VAR_BB which could use a more meaningful name. Finally, I > abstracted some common code to > register_jump_thread_path_if_profitable() in preparation for some > upcoming work by me :). > > Tested on x86-64 Linux. It looks like you dropped a level of indirection for path in profitable_jump_thread_path and perhaps others that push blocks onto the path? Does your change from having the vectors in the GC space to the heap also change them from embeddable vectors to a space efficient vector? It has to for this change to be safe. See the discussion in vec.h I don't recall any inherent reason we use the embedded vector layout. It's the default which is probably why it's used here more than anything. Otherwise the change looks good. I think you just to make sure you're not using the embedded layout. Which I think is just a different type when you declare the vec. Jeff ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: backwards threader cleanups 2017-09-01 22:11 ` Jeff Law @ 2017-09-02 17:43 ` Aldy Hernandez 2017-09-11 9:01 ` Aldy Hernandez 2017-09-11 22:38 ` Jeff Law 0 siblings, 2 replies; 7+ messages in thread From: Aldy Hernandez @ 2017-09-02 17:43 UTC (permalink / raw) To: Jeff Law; +Cc: gcc-patches On Fri, Sep 1, 2017 at 6:11 PM, Jeff Law <law@redhat.com> wrote: > On 09/01/2017 02:18 PM, Aldy Hernandez wrote: >> Hi. >> >> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. >> The main gist of the patch is making the path vectors live in the >> heap, not GC. But I also cleaned up some comments to reflect reality, >> and renamed VAR_BB which could use a more meaningful name. Finally, I >> abstracted some common code to >> register_jump_thread_path_if_profitable() in preparation for some >> upcoming work by me :). >> >> Tested on x86-64 Linux. > It looks like you dropped a level of indirection for path in > profitable_jump_thread_path and perhaps others that push blocks onto the > path? Does your change from having the vectors in the GC space to the > heap also change them from embeddable vectors to a space efficient > vector? It has to for this change to be safe. Part of my initial motivation was eliminating the double indirection as well as removing the out-of-line calls to vec_alloc() and vec_whatever_push(). And yes, the default plain vector<> uses the heap: template<typename T, typename A = va_heap, typename L = typename A::default_layout> struct GTY((user)) vec { }; ...and va_heap defaults to the space efficient vector: struct va_heap { typedef vl_ptr default_layout; ... } > > See the discussion in vec.h > > I don't recall any inherent reason we use the embedded vector layout. > It's the default which is probably why it's used here more than anything. Just a wild guess, but this may be why: FIXME - Ideally, they would all be vl_ptr to encourage using regular instances for vectors, but the existing GTY machinery is limited in that it can only deal with GC objects that are pointers themselves. and: /* Use vl_embed as the default layout for GC vectors. Due to GTY limitations, GC vectors must always be pointers, so it is more efficient to use a pointer to the vl_embed layout, rather than using a pointer to a pointer as would be the case with vl_ptr. */ > > Otherwise the change looks good. I think you just to make sure you're > not using the embedded layout. Which I think is just a different type > when you declare the vec. I have made the vectors auto_vec as Trevor suggested. As auto_vec is just an inherited plain vec<> with some magic allocation sauce, they can be passed around interchangeably. I also changed the hash sets so they live on the stack as opposed to allocating memory dynamically, at Trevor's request as well. Bootstraps. OK pending another round of tests? Aldy ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: backwards threader cleanups 2017-09-02 17:43 ` Aldy Hernandez @ 2017-09-11 9:01 ` Aldy Hernandez 2017-09-11 22:38 ` Jeff Law 1 sibling, 0 replies; 7+ messages in thread From: Aldy Hernandez @ 2017-09-11 9:01 UTC (permalink / raw) To: Jeff Law; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 2875 bytes --] PING. An this time with an actual patch ;-). Aldy On Sat, Sep 2, 2017 at 1:43 PM, Aldy Hernandez <aldyh@redhat.com> wrote: > On Fri, Sep 1, 2017 at 6:11 PM, Jeff Law <law@redhat.com> wrote: >> On 09/01/2017 02:18 PM, Aldy Hernandez wrote: >>> Hi. >>> >>> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. >>> The main gist of the patch is making the path vectors live in the >>> heap, not GC. But I also cleaned up some comments to reflect reality, >>> and renamed VAR_BB which could use a more meaningful name. Finally, I >>> abstracted some common code to >>> register_jump_thread_path_if_profitable() in preparation for some >>> upcoming work by me :). >>> >>> Tested on x86-64 Linux. >> It looks like you dropped a level of indirection for path in >> profitable_jump_thread_path and perhaps others that push blocks onto the >> path? Does your change from having the vectors in the GC space to the >> heap also change them from embeddable vectors to a space efficient >> vector? It has to for this change to be safe. > > Part of my initial motivation was eliminating the double indirection > as well as removing the out-of-line calls to vec_alloc() and > vec_whatever_push(). > > And yes, the default plain vector<> uses the heap: > > template<typename T, > typename A = va_heap, > typename L = typename A::default_layout> > struct GTY((user)) vec > { > }; > > ...and va_heap defaults to the space efficient vector: > > struct va_heap > { > typedef vl_ptr default_layout; > ... > } > >> >> See the discussion in vec.h >> >> I don't recall any inherent reason we use the embedded vector layout. >> It's the default which is probably why it's used here more than anything. > > Just a wild guess, but this may be why: > > FIXME - Ideally, they would all be vl_ptr to encourage using regular > instances for vectors, but the existing GTY machinery is limited > in that it can only deal with GC objects that are pointers > themselves. > > and: > > /* Use vl_embed as the default layout for GC vectors. Due to GTY > limitations, GC vectors must always be pointers, so it is more > efficient to use a pointer to the vl_embed layout, rather than > using a pointer to a pointer as would be the case with vl_ptr. */ > >> >> Otherwise the change looks good. I think you just to make sure you're >> not using the embedded layout. Which I think is just a different type >> when you declare the vec. > > I have made the vectors auto_vec as Trevor suggested. As auto_vec is > just an inherited plain vec<> with some magic allocation sauce, they > can be passed around interchangeably. > > I also changed the hash sets so they live on the stack as opposed to > allocating memory dynamically, at Trevor's request as well. > > Bootstraps. OK pending another round of tests? > > Aldy [-- Attachment #2: curr --] [-- Type: application/octet-stream, Size: 23635 bytes --] commit feacae1edb2f70d2f7b6f1bf5730acc1671041d6 Author: Aldy Hernandez <aldyh@redhat.com> Date: Thu Aug 31 06:32:37 2017 -0400 * tree-ssa-threadbackward.c (fsm_find_thread_path): Make GC vectors heap vectors. Clean up comments. Make visited_bbs a reference. (profitable_jump_thread_path): Make GC vectors heap vectors. Clean up comments. Misc cleanups. (convert_and_register_jump_thread_path): Make GC vectors heap vectors. (check_subpath_and_update_thread_path): Same. Clean up comments. Make visited_bbs a reference. (handle_phi): Abstract common code to to register_jump_thread_path_if_profitable. Rename VAR_BB to DEF_BB. Update comments. Make GC vectors heap vectors. Make visited_bbs a reference. (handle_assignment): Same. (register_jump_thread_path_if_profitable): New. (fsm_find_control_statement_thread_paths): Rename VAR_BB to DEF_BB. Make GC vectors heap vectors. Clean up comments. Make visited_bbs a reference. (find_jump_threads_backwards): Make visited_bbs live in the stack. * tree-ssa-threadupdate.c (delete_jump_thread_path): Fix typo in comment. diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 24def1deed9..12bc80350f5 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -59,33 +59,34 @@ get_gimple_control_stmt (basic_block bb) return NULL; } -/* Return true if the CFG contains at least one path from START_BB to END_BB. - When a path is found, record in PATH the blocks from END_BB to START_BB. - VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound - the recursion to basic blocks belonging to LOOP. */ +/* Return true if the CFG contains at least one path from START_BB to + END_BB. When a path is found, record in PATH the blocks from + END_BB to START_BB. VISITED_BBS is used to make sure we don't fall + into an infinite loop. Bound the recursion to basic blocks + belonging to LOOP. */ static bool fsm_find_thread_path (basic_block start_bb, basic_block end_bb, - vec<basic_block, va_gc> *&path, - hash_set<basic_block> *visited_bbs, loop_p loop) + vec<basic_block> &path, + hash_set<basic_block> &visited_bbs, loop_p loop) { if (loop != start_bb->loop_father) return false; if (start_bb == end_bb) { - vec_safe_push (path, start_bb); + path.safe_push (start_bb); return true; } - if (!visited_bbs->add (start_bb)) + if (!visited_bbs.add (start_bb)) { edge e; edge_iterator ei; FOR_EACH_EDGE (e, ei, start_bb->succs) if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) { - vec_safe_push (path, start_bb); + path.safe_push (start_bb); return true; } } @@ -99,21 +100,21 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, final taken edge from the path, NULL otherwise. NAME is the SSA_NAME of the variable we found to have a constant - value on PATH. ARG is the value of that SSA_NAME. + value on PATH. ARG is the constant value of NAME on that path. BBI will be appended to PATH when we have a profitable jump threading path. Callers are responsible for removing BBI from PATH in that case. - SPEED_P indicate that we could increase code size to improve the code path */ + SPEED_P indicate that we could increase code size to improve the + code path. */ static edge -profitable_jump_thread_path (vec<basic_block, va_gc> *&path, - basic_block bbi, tree name, tree arg, bool speed_p, - bool *creates_irreducible_loop) +profitable_jump_thread_path (vec<basic_block> &path, + basic_block bbi, tree name, tree arg, + bool speed_p, bool *creates_irreducible_loop) { /* Note BBI is not in the path yet, hence the +1 in the test below to make sure BBI is accounted for in the path length test. */ - int path_length = path->length (); /* We can get a length of 0 here when the statement that makes a conditional generate a compile-time constant @@ -124,10 +125,10 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, wanted by wiring up all the incoming edges. If we run this early in IPA, that might be worth doing. For now we just reject that case. */ - if (path_length == 0) + if (path.is_empty ()) return NULL; - if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) + if (path.length () + 1 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "FSM jump-thread path not considered: " @@ -148,13 +149,11 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, /* Add BBI to the path. From this point onward, if we decide we the path is not profitable to thread, we must remove BBI from the path. */ - vec_safe_push (path, bbi); - ++path_length; + path.safe_push (bbi); int n_insns = 0; gimple_stmt_iterator gsi; - int j; - loop_p loop = (*path)[0]->loop_father; + loop_p loop = path[0]->loop_father; bool path_crosses_loops = false; bool threaded_through_latch = false; bool multiway_branch_in_path = false; @@ -168,9 +167,9 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, will have to be duplicated, we will not record the path if there are too many instructions on the path. Also check that all the blocks in the path belong to a single loop. */ - for (j = 0; j < path_length; j++) + for (unsigned j = 0; j < path.length (); j++) { - basic_block bb = (*path)[j]; + basic_block bb = path[j]; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " bb:%i", bb->index); @@ -181,7 +180,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, loop father, nor how many statements are in that block because it will not be copied or whether or not it ends in a multiway branch. */ - if (j < path_length - 1) + if (j < path.length () - 1) { int orig_n_insns = n_insns; if (bb->loop_father != loop) @@ -268,7 +267,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, threaded_through_latch = true; } - gimple *stmt = get_gimple_control_stmt ((*path)[0]); + gimple *stmt = get_gimple_control_stmt (path[0]); gcc_assert (stmt); /* We are going to remove the control statement at the end of the @@ -301,14 +300,14 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, latch, then this thread would create an irreducible loop. We have to know the outgoing edge to figure this out. */ - edge taken_edge = find_taken_edge ((*path)[0], arg); + edge taken_edge = find_taken_edge (path[0], arg); /* There are cases where we may not be able to extract the taken edge. For example, a computed goto to an absolute address. Handle those cases gracefully. */ if (taken_edge == NULL) { - path->pop (); + path.pop (); return NULL; } @@ -324,7 +323,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "FSM jump-thread path not considered: " "the path crosses loops.\n"); - path->pop (); + path.pop (); return NULL; } @@ -340,7 +339,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM jump-thread path not considered: " "the number of instructions on the path " "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n"); - path->pop (); + path.pop (); return NULL; } } @@ -350,7 +349,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM jump-thread path not considered: " "duplication of %i insns is needed and optimizing for size.\n", n_insns); - path->pop (); + path.pop (); return NULL; } @@ -364,15 +363,16 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, optimizer would have done anyway, so an irreducible loop is not so bad. */ if (!threaded_multiway_branch && *creates_irreducible_loop - && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) - > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))) + && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) + > (path.length () * + (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS)))) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "FSM would create irreducible loop without threading " "multiway branch.\n"); - path->pop (); + path.pop (); return NULL; } @@ -392,7 +392,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM did not thread around loop and would copy too " "many statements.\n"); - path->pop (); + path.pop (); return NULL; } @@ -406,7 +406,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, fprintf (dump_file, "FSM Thread through multiway branch without threading " "a multiway branch.\n"); - path->pop (); + path.pop (); return NULL; } return taken_edge; @@ -419,16 +419,15 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path, register the path. */ static void -convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path, - edge taken_edge) +convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge) { vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> (); /* Record the edges between the blocks in PATH. */ - for (unsigned int j = 0; j < path->length () - 1; j++) + for (unsigned int j = 0; j + 1 < path.length (); j++) { - basic_block bb1 = (*path)[path->length () - j - 1]; - basic_block bb2 = (*path)[path->length () - j - 2]; + basic_block bb1 = path[path.length () - j - 1]; + basic_block bb2 = path[path.length () - j - 2]; edge e = find_edge (bb1, bb2); gcc_assert (e); @@ -445,82 +444,104 @@ convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path, --max_threaded_paths; } -/* While following a chain of SSA_NAME definitions, we jumped from a definition - in LAST_BB to a definition in VAR_BB (walking backwards). +/* While following a chain of SSA_NAME definitions, we jumped from a + definition in LAST_BB to a definition in NEW_BB (walking + backwards). - Verify there is a single path between the blocks and none of the blocks - in the path is already in VISITED_BBS. If so, then update VISISTED_BBS, - add the new blocks to PATH and return TRUE. Otherwise return FALSE. + Verify there is a single path between the blocks and none of the + blocks in the path is already in VISITED_BBS. If so, then update + VISISTED_BBS, add the new blocks to PATH and return TRUE. + Otherwise return FALSE. Store the length of the subpath in NEXT_PATH_LENGTH. */ static bool check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, - hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + hash_set<basic_block> &visited_bbs, + vec<basic_block> &path, int *next_path_length) { edge e; int e_count = 0; edge_iterator ei; - vec<basic_block, va_gc> *next_path; - vec_alloc (next_path, 10); + auto_vec<basic_block> next_path; FOR_EACH_EDGE (e, ei, last_bb->preds) { - hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; + hash_set<basic_block> visited_bbs; if (fsm_find_thread_path (new_bb, e->src, next_path, visited_bbs, e->src->loop_father)) ++e_count; - delete visited_bbs; - /* If there is more than one path, stop. */ if (e_count > 1) - { - vec_free (next_path); - return false; - } + return false; } /* Stop if we have not found a path: this could occur when the recursion is stopped by one of the bounds. */ if (e_count == 0) - { - vec_free (next_path); - return false; - } + return false; /* Make sure we haven't already visited any of the nodes in NEXT_PATH. Don't add them here to avoid pollution. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) + for (unsigned int i = 0; i + 1 < next_path.length (); i++) { - if (visited_bbs->contains ((*next_path)[i])) - { - vec_free (next_path); - return false; - } + if (visited_bbs.contains (next_path[i])) + return false; } /* Now add the nodes to VISISTED_BBS. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) - visited_bbs->add ((*next_path)[i]); + for (unsigned int i = 0; i + 1 < next_path.length (); i++) + visited_bbs.add (next_path[i]); /* Append all the nodes from NEXT_PATH to PATH. */ - vec_safe_splice (path, next_path); - *next_path_length = next_path->length (); - vec_free (next_path); + path.safe_splice (next_path); + *next_path_length = next_path.length (); return true; } +/* If this is a profitable jump thread path, register it. + + NAME is an SSA NAME with a possible constant value of ARG on PATH. + + DEF_BB is the basic block that ultimately defines the constant. + + SPEED_P indicate that we could increase code size to improve the + code path. +*/ + +static void +register_jump_thread_path_if_profitable (vec<basic_block> &path, + tree name, + tree arg, + basic_block def_bb, + bool speed_p) +{ + if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) + return; + + bool irreducible = false; + edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg, + speed_p, &irreducible); + if (taken_edge) + { + convert_and_register_jump_thread_path (path, taken_edge); + path.pop (); + + if (irreducible) + vect_free_loop_info_assumptions (path[0]->loop_father); + } +} + static void fsm_find_control_statement_thread_paths (tree, - hash_set<basic_block> *, - vec<basic_block, va_gc> *&, + hash_set<basic_block> &, + vec<basic_block> &, bool, bool); -/* Given PHI which defines NAME in block VAR_BB, recurse through the +/* Given PHI which defines NAME in block DEF_BB, recurse through the PHI's arguments searching for paths where NAME will ultimately have a constant value. @@ -534,9 +555,9 @@ static void fsm_find_control_statement_thread_paths (tree, SPEED_P indicates if we are optimizing for speed over space. */ static void -handle_phi (gphi *phi, tree name, basic_block var_bb, - hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, +handle_phi (gphi *phi, tree name, basic_block def_bb, + hash_set<basic_block> &visited_bbs, + vec<basic_block> &path, bool seen_loop_phi, bool speed_p) { /* Iterate over the arguments of PHI. */ @@ -546,37 +567,22 @@ handle_phi (gphi *phi, tree name, basic_block var_bb, basic_block bbi = gimple_phi_arg_edge (phi, i)->src; /* Skip edges pointing outside the current loop. */ - if (!arg || var_bb->loop_father != bbi->loop_father) + if (!arg || def_bb->loop_father != bbi->loop_father) continue; if (TREE_CODE (arg) == SSA_NAME) { - vec_safe_push (path, bbi); + path.safe_push (bbi); /* Recursively follow SSA_NAMEs looking for a constant definition. */ fsm_find_control_statement_thread_paths (arg, visited_bbs, path, seen_loop_phi, speed_p); - path->pop (); + path.pop (); continue; } - if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) - continue; - - /* If this is a profitable jump thread path, then convert it - into the canonical form and register it. */ - bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg, - speed_p, &irreducible); - if (taken_edge) - { - convert_and_register_jump_thread_path (path, taken_edge); - path->pop (); - - if (irreducible) - vect_free_loop_info_assumptions ((*path)[0]->loop_father); - } + register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p); } } @@ -610,7 +616,7 @@ handle_assignment_p (gimple *stmt) return false; } -/* Given STMT which defines NAME in block VAR_BB, recurse through the +/* Given STMT which defines NAME in block DEF_BB, recurse through the PHI's arguments searching for paths where NAME will ultimately have a constant value. @@ -624,9 +630,9 @@ handle_assignment_p (gimple *stmt) SPEED_P indicates if we are optimizing for speed over space. */ static void -handle_assignment (gimple *stmt, tree name, basic_block var_bb, - hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, +handle_assignment (gimple *stmt, tree name, basic_block def_bb, + hash_set<basic_block> &visited_bbs, + vec<basic_block> &path, bool seen_loop_phi, bool speed_p) { tree arg = gimple_assign_rhs1 (stmt); @@ -637,40 +643,31 @@ handle_assignment (gimple *stmt, tree name, basic_block var_bb, else { - /* profitable_jump_thread_path is going to push the current + /* register_jump_thread_path_if_profitable will push the current block onto the path. But the path will always have the current block at this point. So we can just pop it. */ - path->pop (); + path.pop (); - bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, var_bb, - name, arg, speed_p, - &irreducible); - if (taken_edge) - { - convert_and_register_jump_thread_path (path, taken_edge); - path->pop (); - - if (irreducible) - vect_free_loop_info_assumptions ((*path)[0]->loop_father); - } + register_jump_thread_path_if_profitable (path, name, arg, def_bb, + speed_p); /* And put the current block back onto the path so that the state of the stack is unchanged when we leave. */ - vec_safe_push (path, var_bb); + path.safe_push (def_bb); } } -/* We trace the value of the SSA_NAME NAME back through any phi nodes looking - for places where it gets a constant value and save the path. Stop after - having recorded MAX_PATHS jump threading paths. +/* We trace the value of the SSA_NAME NAME back through any phi nodes + looking for places where it gets a constant value and save the + path. - SPEED_P indicate that we could increase code size to improve the code path */ + SPEED_P indicate that we could increase code size to improve the + code path. */ static void fsm_find_control_statement_thread_paths (tree name, - hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + hash_set<basic_block> &visited_bbs, + vec<basic_block> &path, bool seen_loop_phi, bool speed_p) { /* If NAME appears in an abnormal PHI, then don't try to trace its @@ -679,9 +676,9 @@ fsm_find_control_statement_thread_paths (tree name, return; gimple *def_stmt = SSA_NAME_DEF_STMT (name); - basic_block var_bb = gimple_bb (def_stmt); + basic_block def_bb = gimple_bb (def_stmt); - if (var_bb == NULL) + if (def_bb == NULL) return; /* We allow the SSA chain to contains PHIs and simple copies and constant @@ -700,11 +697,11 @@ fsm_find_control_statement_thread_paths (tree name, return; /* Avoid infinite recursion. */ - if (visited_bbs->add (var_bb)) + if (visited_bbs.add (def_bb)) return; int next_path_length = 0; - basic_block last_bb_in_path = path->last (); + basic_block last_bb_in_path = path.last (); if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt)) { @@ -715,33 +712,33 @@ fsm_find_control_statement_thread_paths (tree name, } /* Following the chain of SSA_NAME definitions, we jumped from a definition in - LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are - different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ - if (var_bb != last_bb_in_path) + LAST_BB_IN_PATH to a definition in DEF_BB. When these basic blocks are + different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB. */ + if (def_bb != last_bb_in_path) { - /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path + /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path will already be in VISITED_BBS. When they are not equal, then we must ensure that first block is accounted for to ensure we do not create bogus jump threading paths. */ - visited_bbs->add ((*path)[0]); - if (!check_subpath_and_update_thread_path (last_bb_in_path, var_bb, + visited_bbs.add (path[0]); + if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb, visited_bbs, path, &next_path_length)) return; } - gcc_assert (path->last () == var_bb); + gcc_assert (path.last () == def_bb); if (gimple_code (def_stmt) == GIMPLE_PHI) - handle_phi (as_a <gphi *> (def_stmt), name, var_bb, + handle_phi (as_a <gphi *> (def_stmt), name, def_bb, visited_bbs, path, seen_loop_phi, speed_p); else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) - handle_assignment (def_stmt, name, var_bb, + handle_assignment (def_stmt, name, def_bb, visited_bbs, path, seen_loop_phi, speed_p); /* Remove all the nodes that we added from NEXT_PATH. */ if (next_path_length) - vec_safe_truncate (path, (path->length () - next_path_length)); + path.truncate (path.length () - next_path_length); } /* Search backwards from BB looking for paths where NAME (an SSA_NAME) @@ -749,7 +746,8 @@ fsm_find_control_statement_thread_paths (tree name, It is assumed that BB ends with a control statement and that by finding a path where NAME is a constant, we can thread the path. - SPEED_P indicate that we could increase code size to improve the code path */ + SPEED_P indicate that we could increase code size to improve the + code path. */ void find_jump_threads_backwards (basic_block bb, bool speed_p) @@ -776,17 +774,13 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) if (!name || TREE_CODE (name) != SSA_NAME) return; - vec<basic_block, va_gc> *bb_path; - vec_alloc (bb_path, 10); - vec_safe_push (bb_path, bb); - hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; + auto_vec<basic_block> bb_path; + bb_path.safe_push (bb); + hash_set<basic_block> visited_bbs; max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false, speed_p); - - delete visited_bbs; - vec_free (bb_path); } namespace { diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 9da74675eef..d5d534fde04 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2588,7 +2588,7 @@ thread_through_all_blocks (bool may_peel_loop_headers) return retval; } -/* Delete the jump threading path PATH. We have to explcitly delete +/* Delete the jump threading path PATH. We have to explicitly delete each entry in the vector, then the container. */ void ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: backwards threader cleanups 2017-09-02 17:43 ` Aldy Hernandez 2017-09-11 9:01 ` Aldy Hernandez @ 2017-09-11 22:38 ` Jeff Law 1 sibling, 0 replies; 7+ messages in thread From: Jeff Law @ 2017-09-11 22:38 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches On 09/02/2017 11:43 AM, Aldy Hernandez wrote: > On Fri, Sep 1, 2017 at 6:11 PM, Jeff Law <law@redhat.com> wrote: >> On 09/01/2017 02:18 PM, Aldy Hernandez wrote: >>> Hi. >>> >>> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. >>> The main gist of the patch is making the path vectors live in the >>> heap, not GC. But I also cleaned up some comments to reflect reality, >>> and renamed VAR_BB which could use a more meaningful name. Finally, I >>> abstracted some common code to >>> register_jump_thread_path_if_profitable() in preparation for some >>> upcoming work by me :). >>> >>> Tested on x86-64 Linux. >> It looks like you dropped a level of indirection for path in >> profitable_jump_thread_path and perhaps others that push blocks onto the >> path? Does your change from having the vectors in the GC space to the >> heap also change them from embeddable vectors to a space efficient >> vector? It has to for this change to be safe. > > Part of my initial motivation was eliminating the double indirection > as well as removing the out-of-line calls to vec_alloc() and > vec_whatever_push(). > > And yes, the default plain vector<> uses the heap: > > template<typename T, > typename A = va_heap, > typename L = typename A::default_layout> > struct GTY((user)) vec > { > }; > > ...and va_heap defaults to the space efficient vector: > > struct va_heap > { > typedef vl_ptr default_layout; > ... > } > >> >> See the discussion in vec.h >> >> I don't recall any inherent reason we use the embedded vector layout. >> It's the default which is probably why it's used here more than anything. > > Just a wild guess, but this may be why: > > FIXME - Ideally, they would all be vl_ptr to encourage using regular > instances for vectors, but the existing GTY machinery is limited > in that it can only deal with GC objects that are pointers > themselves. > > and: > > /* Use vl_embed as the default layout for GC vectors. Due to GTY > limitations, GC vectors must always be pointers, so it is more > efficient to use a pointer to the vl_embed layout, rather than > using a pointer to a pointer as would be the case with vl_ptr. */ > >> >> Otherwise the change looks good. I think you just to make sure you're >> not using the embedded layout. Which I think is just a different type >> when you declare the vec. > > I have made the vectors auto_vec as Trevor suggested. As auto_vec is > just an inherited plain vec<> with some magic allocation sauce, they > can be passed around interchangeably. > > I also changed the hash sets so they live on the stack as opposed to > allocating memory dynamically, at Trevor's request as well. > > Bootstraps. OK pending another round of tests? Yes. Thanks for double-checking on the embedded vs space efficient stuff. jeff ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: backwards threader cleanups 2017-09-01 20:18 backwards threader cleanups Aldy Hernandez 2017-09-01 22:11 ` Jeff Law @ 2017-09-02 2:16 ` Trevor Saunders 2017-09-02 17:30 ` Aldy Hernandez 1 sibling, 1 reply; 7+ messages in thread From: Trevor Saunders @ 2017-09-02 2:16 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches, Jeff Law On Fri, Sep 01, 2017 at 04:18:20PM -0400, Aldy Hernandez wrote: > Hi. > > Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. > The main gist of the patch is making the path vectors live in the > heap, not GC. But I also cleaned up some comments to reflect reality, > and renamed VAR_BB which could use a more meaningful name. Finally, I > abstracted some common code to > register_jump_thread_path_if_profitable() in preparation for some > upcoming work by me :). > > Tested on x86-64 Linux. > > OK? check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, hash_set<basic_block> *visited_bbs, - vec<basic_block, va_gc> *&path, + vec<basic_block> &path, int *next_path_length) { edge e; int e_count = 0; edge_iterator ei; - vec<basic_block, va_gc> *next_path; - vec_alloc (next_path, 10); + vec<basic_block> next_path = vNULL; I believe all paths out of this scope release next_path, so it can be said the scope owns this vector and you could use auto_vec here. @@ -776,9 +786,8 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) if (!name || TREE_CODE (name) != SSA_NAME) return; - vec<basic_block, va_gc> *bb_path; - vec_alloc (bb_path, 10); - vec_safe_push (bb_path, bb); + vec<basic_block> bb_path = vNULL; same holds here I think. + bb_path.safe_push (bb); hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; btw I don't see why this hash table can't be just a hash_table<> and live on the stack. thanks Trev ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: backwards threader cleanups 2017-09-02 2:16 ` Trevor Saunders @ 2017-09-02 17:30 ` Aldy Hernandez 0 siblings, 0 replies; 7+ messages in thread From: Aldy Hernandez @ 2017-09-02 17:30 UTC (permalink / raw) To: Trevor Saunders; +Cc: gcc-patches, Jeff Law On Fri, Sep 1, 2017 at 10:16 PM, Trevor Saunders <tbsaunde@tbsaunde.org> wrote: > On Fri, Sep 01, 2017 at 04:18:20PM -0400, Aldy Hernandez wrote: >> Hi. >> >> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends. >> The main gist of the patch is making the path vectors live in the >> heap, not GC. But I also cleaned up some comments to reflect reality, >> and renamed VAR_BB which could use a more meaningful name. Finally, I >> abstracted some common code to >> register_jump_thread_path_if_profitable() in preparation for some >> upcoming work by me :). >> >> Tested on x86-64 Linux. >> >> OK? > > check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, > hash_set<basic_block> *visited_bbs, > - vec<basic_block, va_gc> *&path, > + vec<basic_block> &path, > int *next_path_length) > { > edge e; > int e_count = 0; > edge_iterator ei; > - vec<basic_block, va_gc> *next_path; > - vec_alloc (next_path, 10); > + vec<basic_block> next_path = vNULL; > > I believe all paths out of this scope release next_path, so it can be > said the scope owns this vector and you could use auto_vec here. I originally wanted plain vec<> so it could be passed around to other work I'm doing on the threader, but I see that auto_vec<> inherits from vec<T, va_heap>, and the default vec<> is just vec<T, va_heap, va_heap::default_layout>. So...it's all the same, and will work seamlessly. Thanks. Will do. > > @@ -776,9 +786,8 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) > if (!name || TREE_CODE (name) != SSA_NAME) > return; > > - vec<basic_block, va_gc> *bb_path; > - vec_alloc (bb_path, 10); > - vec_safe_push (bb_path, bb); > + vec<basic_block> bb_path = vNULL; > > same holds here I think. Will do. > > + bb_path.safe_push (bb); > hash_set<basic_block> *visited_bbs = new hash_set<basic_block>; > > btw I don't see why this hash table can't be just a hash_table<> and > live on the stack. Very good point. Thanks. ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2017-09-11 22:38 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-09-01 20:18 backwards threader cleanups Aldy Hernandez 2017-09-01 22:11 ` Jeff Law 2017-09-02 17:43 ` Aldy Hernandez 2017-09-11 9:01 ` Aldy Hernandez 2017-09-11 22:38 ` Jeff Law 2017-09-02 2:16 ` Trevor Saunders 2017-09-02 17:30 ` Aldy Hernandez
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).