Re: [PATCH] tree-ssa-sink: Improve code sinking pass
On Wed, Mar 13, 2024 at 2:56 PM Ajit Agarwal wrote: > > Hello Richard: > > Currently, code sinking will sink code at the use points with loop having same > nesting depth. The following patch improves code sinking by placing the sunk > code in begining of the block after the labels. > > For example : > > void bar(); > int j; > void foo(int a, int b, int c, int d, int e, int f) > { > int l; > l = a + b + c + d +e + f; > if (a != 5) > { > bar(); > j = l; > } > } > > Code Sinking does the following: > > void bar(); > int j; > void foo(int a, int b, int c, int d, int e, int f) > { > int l; > > if (a != 5) > { > l = a + b + c + d +e + f; > bar(); > j = l; > } > } > > Bootstrapped regtested on powerpc64-linux-gnu. > > Thanks & Regards > > tree-ssa-sink: Improve code sinking pass > > Currently, code sinking will sink code at the use points with loop having same > nesting depth. The following patch improves code sinking by placing the sunk > code in begining of the block after the labels. > > 2024-03-13 Ajit Kumar Agarwal > > gcc/ChangeLog: > > PR tree-optimization/81953 > * tree-ssa-sink.cc (statement_sink_location):Sink statements at > the begining of the basic block after labels. > > gcc/testsuite/ChangeLog: > > PR tree-optimization/81953 > * gcc.dg/tree-ssa/ssa-sink-21.c: New test. > --- > gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 +++ > gcc/tree-ssa-sink.cc| 7 ++- > 2 files changed, 17 insertions(+), 5 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c > b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c > new file mode 100644 > index 000..d3b79ca5803 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c > @@ -0,0 +1,15 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-sink-stats" } */ > +void bar(); > +int j; > +void foo(int a, int b, int c, int d, int e, int f) > +{ > + int l; > + l = a + b + c + d +e + f; > + if (a != 5) > +{ > + bar(); > + j = l; > +} > +} > +/* { dg-final { scan-tree-dump > {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} sink1 } } */ > diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc > index 880d6f70a80..1ec5c048fe7 100644 > --- a/gcc/tree-ssa-sink.cc > +++ b/gcc/tree-ssa-sink.cc > @@ -208,7 +208,6 @@ select_best_block (basic_block early_bb, > loop nest. */ >temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb); > } > - >/* Placing a statement before a setjmp-like function would be invalid > (it cannot be reevaluated when execution follows an abnormal edge). > If we selected a block with abnormal predecessors, just punt. */ > @@ -430,6 +429,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, > continue; > break; > } > + >use = USE_STMT (one_use); > >if (gimple_code (use) != GIMPLE_PHI) OK if you avoid the stray whitespace changes above. Richard. > @@ -439,10 +439,7 @@ statement_sink_location (gimple *stmt, basic_block > frombb, > if (sinkbb == frombb) > return false; > > - if (sinkbb == gimple_bb (use)) > - *togsi = gsi_for_stmt (use); > - else > - *togsi = gsi_after_labels (sinkbb); > + *togsi = gsi_after_labels (sinkbb); > > return true; > } > -- > 2.39.3 >
[PATCH] tree-ssa-sink: Improve code sinking pass
Hello Richard: Currently, code sinking will sink code at the use points with loop having same nesting depth. The following patch improves code sinking by placing the sunk code in begining of the block after the labels. For example : void bar(); int j; void foo(int a, int b, int c, int d, int e, int f) { int l; l = a + b + c + d +e + f; if (a != 5) { bar(); j = l; } } Code Sinking does the following: void bar(); int j; void foo(int a, int b, int c, int d, int e, int f) { int l; if (a != 5) { l = a + b + c + d +e + f; bar(); j = l; } } Bootstrapped regtested on powerpc64-linux-gnu. Thanks & Regards tree-ssa-sink: Improve code sinking pass Currently, code sinking will sink code at the use points with loop having same nesting depth. The following patch improves code sinking by placing the sunk code in begining of the block after the labels. 2024-03-13 Ajit Kumar Agarwal gcc/ChangeLog: PR tree-optimization/81953 * tree-ssa-sink.cc (statement_sink_location):Sink statements at the begining of the basic block after labels. gcc/testsuite/ChangeLog: PR tree-optimization/81953 * gcc.dg/tree-ssa/ssa-sink-21.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 +++ gcc/tree-ssa-sink.cc| 7 ++- 2 files changed, 17 insertions(+), 5 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c new file mode 100644 index 000..d3b79ca5803 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink-stats" } */ +void bar(); +int j; +void foo(int a, int b, int c, int d, int e, int f) +{ + int l; + l = a + b + c + d +e + f; + if (a != 5) +{ + bar(); + j = l; +} +} +/* { dg-final { scan-tree-dump {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} sink1 } } */ diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index 880d6f70a80..1ec5c048fe7 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -208,7 +208,6 @@ select_best_block (basic_block early_bb, loop nest. */ temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb); } - /* Placing a statement before a setjmp-like function would be invalid (it cannot be reevaluated when execution follows an abnormal edge). If we selected a block with abnormal predecessors, just punt. */ @@ -430,6 +429,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, continue; break; } + use = USE_STMT (one_use); if (gimple_code (use) != GIMPLE_PHI) @@ -439,10 +439,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, if (sinkbb == frombb) return false; - if (sinkbb == gimple_bb (use)) - *togsi = gsi_for_stmt (use); - else - *togsi = gsi_after_labels (sinkbb); + *togsi = gsi_after_labels (sinkbb); return true; } -- 2.39.3
Re: [PATCH] tree-ssa-sink: Improve code sinking pass.
On 4/16/23 07:20, Ajit Agarwal wrote: Hello All: This patch improves code sinking pass to sink the blocks before calls in the use blocks or immediate dominator blocks that reduces register pressure. Bootstrapped and regtested on powerpc64-linux-gnu. Thanks & Regards Ajit tree-ssa-sink: Improve code sinking pass. Code Sinking sinks the blocks after call. This increases register pressure for callee-saved registers. Improves code sinking before call in the use blocks or immediate dominator of use blocks. 2023-04-16 Ajit Kumar Agarwal gcc/ChangeLog: * tree-ssa-sink.cc (statement_sink_location): Modifed to move statements before calls. (block_call_p): New function. (def_use_same_block): New function. (select_best_block): Add heuristics to select the best blocks in the immediate post dominator. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. * gcc.dg/tree-ssa/ssa-sink-21.c: New testcase. --- +/* Check def and use stmts are in same block. */ A better function comment would be /* Return TRUE if all the immediate uses of the defs in USE occur in the same block as USE, FALSE otherwise. */ I would also strongly suggest you change "use" to something else. This function is walking over uses and defs, so calling the incoming argument "use" is going to make it excessively hard to write clean comments for this function. Something as simple as "stmt" would be considerably better. + +bool +def_use_same_block (gimple *use) +{ + use_operand_p use_p; + def_operand_p def_p; + imm_use_iterator imm_iter; + ssa_op_iter iter; + + FOR_EACH_SSA_DEF_OPERAND (def_p, use, iter, SSA_OP_DEF) +{ + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p)) + { + if (is_gimple_debug (USE_STMT (use_p))) + continue; + + if (use_p + && (gimple_bb(USE_STMT (use_p)) == gimple_bb (use))) Minor whitespace problems. Make sure to include a space between the function name you are calling and the open parenthesis for the arguments. ie gimple_bb (USE_STMT (use_p)). It also seems like you're not checking all the uses, just one of them? Is that what you intended? If so, then my suggested function comment is wrong and needs further adjustment. This highlights how important it is to have a good function comment. +/* Check if the block has only calls. */ This comment doesn't match the code. It appears that you can have both calls and conditional branches. Please update the function comment appropriately. You should also describe the arguments and return value in the function comment (see my suggestion above as an example for how to describe the function arguments and return value. Based on the code it looks like you're requiring a the block to contain only two real statements. A call followed by a conditional. + +bool +block_call_p (basic_block bb) +{ + int i = 0; + bool is_call = false; + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gimple *last_stmt = gsi_stmt (gsi); ISTM there is likely a function that will give you the last statement in the function. + + if (last_stmt && gimple_code (last_stmt) == GIMPLE_COND) +{ + if (!gsi_end_p (gsi)) + gsi_prev (); + + for (; !gsi_end_p (gsi);) +{ + gimple *stmt = gsi_stmt (gsi); + + if (is_gimple_debug (stmt)) +return false; Definitely incorrect as this can cause the decisions we make for optimization to change based on the existence of debug statements. + + if (is_gimple_call (stmt)) +is_call = true; + else +return false; ISTM that this might be better/clearer. Once you've seen a call, if you see another, you can just return immediately. It also seems like if I ever has a value other than 0/1, then you can return false immediately. if (is_gimple_call (stmt)) { /* We have already seen a call. */ if (is_call) return false; is_call = true; continue; } + + if (!gsi_end_p (gsi)) +gsi_prev (); + + ++i; Isn't this going to cause this routine to return false if it has (for example) one or more labels followed by a CALL, then a conditional? Overall I think the logic in here needs a bit of work. @@ -190,7 +254,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) static basic_block select_best_block (basic_block early_bb, basic_block late_bb, - gimple *stmt) + gimple *stmt, + gimple *use = 0) Rather than use a default value, just fix the callers. There's only 3 and you already fixed one :-) And if you're going to initialize a pointer, use NULL rather than 0. { basic_block best_bb = late_bb; basic_block temp_bb = late_bb; @@ -230,7 +295,28 @@
[PATCH] tree-ssa-sink: Improve code sinking pass.
Hello All: This patch improves code sinking pass to sink the blocks before calls in the use blocks or immediate dominator blocks that reduces register pressure. Bootstrapped and regtested on powerpc64-linux-gnu. Thanks & Regards Ajit tree-ssa-sink: Improve code sinking pass. Code Sinking sinks the blocks after call. This increases register pressure for callee-saved registers. Improves code sinking before call in the use blocks or immediate dominator of use blocks. 2023-04-16 Ajit Kumar Agarwal gcc/ChangeLog: * tree-ssa-sink.cc (statement_sink_location): Modifed to move statements before calls. (block_call_p): New function. (def_use_same_block): New function. (select_best_block): Add heuristics to select the best blocks in the immediate post dominator. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. * gcc.dg/tree-ssa/ssa-sink-21.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 20 +++ gcc/tree-ssa-sink.cc| 134 +++- 3 files changed, 164 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c new file mode 100644 index 000..716bc1f9257 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink -fdump-tree-optimized -fdump-tree-sink-stats" } */ + +void bar(); +int j; +void foo(int a, int b, int c, int d, int e, int f) +{ + int l; + l = a + b + c + d +e + f; + if (a != 5) +{ + bar(); + j = l; +} +} +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c new file mode 100644 index 000..ff41e2ea8ae --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink-stats -fdump-tree-sink-stats" } */ + +void bar(); +int j, x; +void foo(int a, int b, int c, int d, int e, int f) +{ + int l; + l = a + b + c + d +e + f; + if (a != 5) +{ + bar(); + if (b != 3) +x = 3; + else +x = 5; + j = l; +} +} +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */ diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index 87b1d40c174..12babf73321 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -171,6 +171,70 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) return commondom; } +/* Check def and use stmts are in same block. */ + +bool +def_use_same_block (gimple *use) +{ + use_operand_p use_p; + def_operand_p def_p; + imm_use_iterator imm_iter; + ssa_op_iter iter; + + FOR_EACH_SSA_DEF_OPERAND (def_p, use, iter, SSA_OP_DEF) +{ + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p)) + { + if (is_gimple_debug (USE_STMT (use_p))) + continue; + + if (use_p + && (gimple_bb(USE_STMT (use_p)) == gimple_bb (use))) + return true; + } + } + return false; +} + +/* Check if the block has only calls. */ + +bool +block_call_p (basic_block bb) +{ + int i = 0; + bool is_call = false; + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gimple *last_stmt = gsi_stmt (gsi); + + if (last_stmt && gimple_code (last_stmt) == GIMPLE_COND) +{ + if (!gsi_end_p (gsi)) + gsi_prev (); + + for (; !gsi_end_p (gsi);) +{ + gimple *stmt = gsi_stmt (gsi); + + if (is_gimple_debug (stmt)) +return false; + + if (is_gimple_call (stmt)) +is_call = true; + else +return false; + + if (!gsi_end_p (gsi)) +gsi_prev (); + + ++i; + } + } + if (is_call && i == 1) +return true; + + return false; +} + /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator tree, return the best basic block between them (inclusive) to place statements. @@ -190,7 +254,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) static basic_block select_best_block (basic_block early_bb, basic_block late_bb, - gimple *stmt) + gimple *stmt, + gimple *use = 0) { basic_block best_bb = late_bb; basic_block temp_bb = late_bb; @@ -230,7 +295,28 @@ select_best_block (basic_block early_bb, if (threshold > 100) threshold = 100; } + if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb) + && !(best_bb->count * 100 >=