better dealing with OP_PHISOURCE insn
PATCH 1/2 better dealing with OP_PHISOURCE insn
When (sure that) we are dealing with OP_PHISOURCE instruction, we should use phi_src' rather then src1', which is dedicated to "binops and sel" (linearize.h) and, by chance/intention, aliases with the former one.
On changed places, I used asserts to ensure the only type of instructions involved in these changes are OP_PHISOURCE and proceeded sparse itself and linux-2.6.35.12 sources with no assertion violation encountered. I'll provide a cumulative patch for this patch series including these asserts, mainly for testing purposes.
--- cse.c | 6 +++--- flow.c | 2 +- linearize.c | 2 +- simplify.c | 6 +++--- 4 files changed, 8 insertions(+), 8 deletions(-)
cse.c +3 -3
@@ -27,8 +27,8 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2)const struct instruction *def1 = phi1->def;const struct instruction *def2 = phi2->def; -if (def1->src1 != def2->src1) -return def1->src1 < def2->src1 ?-1 :1 ; +if (def1->phi_src != def2->phi_src) +return def1->phi_src < def2->phi_src ?-1 :1 ;if (def1->bb != def2->bb)return def1->bb < def2->bb ?-1 :1 ;return 0 ;
@@ -105,7 +105,7 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instructionif (phi ==VOID || !phi->def)continue ; def = phi->def; - hash +=hashval (def->src1); + hash +=hashval (def->phi_src); hash +=hashval (def->bb); }END_FOR_EACH_PTR (phi);break ;
flow.c +1 -1
@@ -105,7 +105,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,if (!def)continue ; source = def->bb; - pseudo = def->src1; + pseudo = def->phi_src;if (!pseudo || !source)continue ; br =last_instruction (source->insns);
linearize.c +1 -1
@@ -1643,7 +1643,7 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct stateif (pseudo_list_size (phi_node->phi_list)==1 ) { pseudo =first_pseudo (phi_node->phi_list);assert (pseudo->type ==PSEUDO_PHI ); -return pseudo->def->src1; +return pseudo->def->phi_src; }return phi_node->target; }
simplify.c +3 -3
@@ -126,10 +126,10 @@ static int clean_up_phi(struct instruction *insn)if (phi ==VOID )continue ; def = phi->def; -if (def->src1 ==VOID || !def->bb) +if (def->phi_src ==VOID || !def->bb)continue ;if (last) { -if (last->src1 != def->src1) +if (last->phi_src != def->phi_src) same =0 ;continue ; }
@@ -137,7 +137,7 @@ static int clean_up_phi(struct instruction *insn) }END_FOR_EACH_PTR (phi);if (same) { -pseudo_t pseudo = last ? last->src1 :VOID ; +pseudo_t pseudo = last ? last->phi_src :VOID ;convert_instruction_target (insn, pseudo);clear_phi (insn);return REPEAT_CSE ;
Signature · 1 line
1.7.1
PATCH 2/2 better dealing with OP_PHISOURCE insn
Remove checking for a case that (most probably) never happens as the only expected instruction is OP_PHISOURCE.
For the sake of assurance, assert added with a comment easing the fix if the assumption of OP_PHISOURCE is wrong (better then masking a problem).
Also, use def' as existing shortcut for phi->def'.
Tested the same way as the previous patch (together).
--- liveness.c | 8 +++----- 1 files changed, 3 insertions(+), 5 deletions(-)
liveness.c +3 -5
@@ -23,11 +23,9 @@ static void phi_defines(struct instruction * phi_node, pseudo_t target, def = phi->def;if (!def || !def->bb)continue ; -if (def->opcode ==OP_PHI ) { -phi_defines (def, target, defines); -continue ; - } -defines (def->bb, phi->def, target); +/* if this ever fails (very unlikely), it's a sign of a regression */ +assert (def->opcode ==OP_PHISOURCE ); +defines (def->bb, def, target); }END_FOR_EACH_PTR (phi); }
Signature · 1 line
1.7.1
This is promised cummulative patch of the two plus added assertions, mainly intended for convenient testing.
--- cse.c | 9 ++++++--- flow.c | 3 ++- linearize.c | 3 ++- liveness.c | 8 +++----- simplify.c | 7 ++++--- 5 files changed, 17 insertions(+), 13 deletions(-)
cse.c +6 -3
@@ -26,9 +26,11 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2) {const struct instruction *def1 = phi1->def;const struct instruction *def2 = phi2->def; +assert (def1->opcode ==OP_PHISOURCE ); +assert (def2->opcode ==OP_PHISOURCE ); -if (def1->src1 != def2->src1) -return def1->src1 < def2->src1 ?-1 :1 ; +if (def1->phi_src != def2->phi_src) +return def1->phi_src < def2->phi_src ?-1 :1 ;if (def1->bb != def2->bb)return def1->bb < def2->bb ?-1 :1 ;return 0 ;
@@ -105,7 +107,8 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instructionif (phi ==VOID || !phi->def)continue ; def = phi->def; - hash +=hashval (def->src1); +assert (def->opcode ==OP_PHISOURCE ); + hash +=hashval (def->phi_src); hash +=hashval (def->bb); }END_FOR_EACH_PTR (phi);break ;
flow.c +2 -1
@@ -104,8 +104,9 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,if (!def)continue ; +assert (def->opcode ==OP_PHISOURCE ); source = def->bb; - pseudo = def->src1; + pseudo = def->phi_src;if (!pseudo || !source)continue ; br =last_instruction (source->insns);
linearize.c +2 -1
@@ -1643,7 +1643,8 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct stateif (pseudo_list_size (phi_node->phi_list)==1 ) { pseudo =first_pseudo (phi_node->phi_list);assert (pseudo->type ==PSEUDO_PHI ); -return pseudo->def->src1; +assert (pseudo->def->opcode ==OP_PHISOURCE ); +return pseudo->def->phi_src; }return phi_node->target; }
liveness.c +3 -5
@@ -23,11 +23,9 @@ static void phi_defines(struct instruction * phi_node, pseudo_t target, def = phi->def;if (!def || !def->bb)continue ; -if (def->opcode ==OP_PHI ) { -phi_defines (def, target, defines); -continue ; - } -defines (def->bb, phi->def, target); +/* if this ever fails (very unlikely), it's a sign of a regression */ +assert (def->opcode ==OP_PHISOURCE ); +defines (def->bb, def, target); }END_FOR_EACH_PTR (phi); }
simplify.c +4 -3
@@ -126,10 +126,11 @@ static int clean_up_phi(struct instruction *insn)if (phi ==VOID )continue ; def = phi->def; -if (def->src1 ==VOID || !def->bb) +assert (def->opcode ==OP_PHISOURCE ); +if (def->phi_src ==VOID || !def->bb)continue ;if (last) { -if (last->src1 != def->src1) +if (last->phi_src != def->phi_src) same =0 ;continue ; }
@@ -137,7 +138,7 @@ static int clean_up_phi(struct instruction *insn) }END_FOR_EACH_PTR (phi);if (same) { -pseudo_t pseudo = last ? last->src1 :VOID ; +pseudo_t pseudo = last ? last->phi_src :VOID ;convert_instruction_target (insn, pseudo);clear_phi (insn);return REPEAT_CSE ;
Signature · 1 line
1.7.1
Christopher Li
maintainerQuoted 9 lines · Jan Pokorný
- if (
def->opcode==OP_PHI) {
-phi_defines(def, target, defines);
- continue;
- }
-defines(def->bb, phi->def, target);
+ /* if this ever fails (very unlikely), it's a sign of a regression */
+assert(def->opcode == OP_PHISOURCE);
+defines(def->bb, def, target);
}END_FOR_EACH_PTR(phi);
That comment usually means there is some thing fishy going on there. I think you are on to some thing. The original code mean to recursively define all the phi source, if the phi source is come from another phi node. But the original code seems wrong. It should lookat def->phi_src->def->opcode instead of def->opcode. I don't think we should remove the phi_defines there. I need to double check this as well.
Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
This is my proposal of how to fix incorrect handling of a recursive "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain in `phi_defines'.
It should be applied instead of my previous 2/2 patch posted on 2011-04-09 which treated this case unwisely as spotted by Chris Li who also outlined respective correction in his reply from 2011-04-14.
The fix required to move `trackable_pseudo' (if we want to avoid a forward declaration).
I also added src_pseudo' in the role of a shortcut and removed def' to reduce the number of levels of such shortcuts (to keep it more readable).
I tried few comparisons (some of them in very carefully) and it seems to do the job (as explained in included comment) right.
--- liveness.c | 39 +++++++++++++++++++++++++-------------- 1 files changed, 25 insertions(+), 14 deletions(-)
liveness.c +25 -13
@@ -12,22 +12,38 @@#include "linearize.h" #include "flow.h" + +static inline int trackable_pseudo (pseudo_t pseudo) +{ +return pseudo && (pseudo->type ==PSEUDO_REG || pseudo->type ==PSEUDO_ARG ); +} +static void phi_defines (struct instruction * phi_node,pseudo_t target, -void (*defines)(struct basic_block *,struct instruction *,pseudo_t )) +void (*defines)(struct basic_block *,struct instruction *,pseudo_t ), +unsigned long generation) {pseudo_t phi; FOR_EACH_PTR(phi_node->phi_list, phi) { -struct instruction *def;if (phi ==VOID )continue ; - def = phi->def; -if (!def || !def->bb) -continue ; -if (def->opcode ==OP_PHI ) { -phi_defines (def, target, defines); +if (!phi->def || !phi->def->bb)continue ; + +/* +* In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move +* "defines" information upstream to the BB of a very first PHISOURCE +* (recursion guarded using "generation" marking of PHI insn BBs). +*/ +pseudo_t src_pseudo = phi->def->phi_src; +if (trackable_pseudo (src_pseudo) && src_pseudo->def->opcode ==OP_PHI ) { + phi_node->bb->generation = generation; +if (src_pseudo->def->bb->generation != generation) { +phi_defines (src_pseudo->def, target, defines, generation); +continue ; + } } -defines (def->bb, phi->def, target); + +defines (phi->def->bb, phi->def, target); }END_FOR_EACH_PTR (phi); }
@@ -103,7 +119,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction */* Other */ case OP_PHI :/* Phi-nodes are "backwards" nodes. Their def doesn't matter */ -phi_defines (insn, insn->target, def); +phi_defines (insn, insn->target, def, ++bb_generation);break ;case OP_PHISOURCE :
@@ -179,11 +195,6 @@ static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo) } } -static inline int trackable_pseudo (pseudo_t pseudo) -{ -return pseudo && (pseudo->type ==PSEUDO_REG || pseudo->type ==PSEUDO_ARG ); -}
Evolution of patch I proposed on 2011-04-15 (to be applied instead of my first 2/2 patch posted on 2011-04-09).
In fact, no need to use `trackable_pseudo' as we are only interested in PSEUDO_REG and we do not expect this pseudo to be NULL (round of testing with additional assert added hadn't proven such test is relevant).
--- liveness.c | 29 ++++++++++++++++++++--------- 1 files changed, 20 insertions(+), 9 deletions(-)
liveness.c +20 -9
@@ -13,21 +13,32 @@#include "flow.h" static void phi_defines (struct instruction * phi_node,pseudo_t target, -void (*defines)(struct basic_block *,struct instruction *,pseudo_t )) +void (*defines)(struct basic_block *,struct instruction *,pseudo_t ), +unsigned long generation) {pseudo_t phi; FOR_EACH_PTR(phi_node->phi_list, phi) { -struct instruction *def;if (phi ==VOID )continue ; - def = phi->def; -if (!def || !def->bb) -continue ; -if (def->opcode ==OP_PHI ) { -phi_defines (def, target, defines); +if (!phi->def || !phi->def->bb)continue ; + +/* +* In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move +* "defines" information upstream to the very first PHISOURCE; +* recursion guarded by generation marking of PHI instructions BBs. +*/ +pseudo_t src_pseudo = phi->def->phi_src; +if (src_pseudo->type ==PSEUDO_REG + && src_pseudo->def->opcode ==OP_PHI ) { + phi_node->bb->generation = generation; +if (src_pseudo->def->bb->generation != generation) { +phi_defines (src_pseudo->def, target, defines, generation); +continue ; + } } -defines (def->bb, phi->def, target); + +defines (phi->def->bb, phi->def, target); }END_FOR_EACH_PTR (phi); }
@@ -103,7 +114,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction */* Other */ case OP_PHI :/* Phi-nodes are "backwards" nodes. Their def doesn't matter */ -phi_defines (insn, insn->target, def); +phi_defines (insn, insn->target, def, ++bb_generation);break ;case OP_PHISOURCE :
Signature · 1 line
1.7.1
(Sorry, I do not use tabs normally so not aware of all these exceptions as with continued "if")
--- liveness.c | 29 ++++++++++++++++++++--------- 1 files changed, 20 insertions(+), 9 deletions(-)
liveness.c +20 -9
@@ -13,21 +13,32 @@#include "flow.h" static void phi_defines (struct instruction * phi_node,pseudo_t target, -void (*defines)(struct basic_block *,struct instruction *,pseudo_t )) +void (*defines)(struct basic_block *,struct instruction *,pseudo_t ), +unsigned long generation) {pseudo_t phi; FOR_EACH_PTR(phi_node->phi_list, phi) { -struct instruction *def;if (phi ==VOID )continue ; - def = phi->def; -if (!def || !def->bb) -continue ; -if (def->opcode ==OP_PHI ) { -phi_defines (def, target, defines); +if (!phi->def || !phi->def->bb)continue ; + +/* +* In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move +* "defines" information upstream to the very first PHISOURCE; +* recursion guarded by generation marking of PHI instructions BBs. +*/ +pseudo_t src_pseudo = phi->def->phi_src; +if (src_pseudo->type ==PSEUDO_REG + && src_pseudo->def->opcode ==OP_PHI ) { + phi_node->bb->generation = generation; +if (src_pseudo->def->bb->generation != generation) { +phi_defines (src_pseudo->def, target, defines, generation); +continue ; + } } -defines (def->bb, phi->def, target); + +defines (phi->def->bb, phi->def, target); }END_FOR_EACH_PTR (phi); }
@@ -103,7 +114,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction */* Other */ case OP_PHI :/* Phi-nodes are "backwards" nodes. Their def doesn't matter */ -phi_defines (insn, insn->target, def); +phi_defines (insn, insn->target, def, ++bb_generation);break ;case OP_PHISOURCE :
Signature · 1 line
1.7.1
Only adding that after applying this patch, the sum of warnings/errors when checking linux-2.6.35.12 sources (defconfig, x86) is not influenced.
Signature · 1 line
Jan
Reformulated comment to better describe what it does.
(Sorry for inconvenience)
--- liveness.c | 29 ++++++++++++++++++++--------- 1 files changed, 20 insertions(+), 9 deletions(-)
liveness.c +20 -9
@@ -13,21 +13,32 @@#include "flow.h" static void phi_defines (struct instruction * phi_node,pseudo_t target, -void (*defines)(struct basic_block *,struct instruction *,pseudo_t )) +void (*defines)(struct basic_block *,struct instruction *,pseudo_t ), +unsigned long generation) {pseudo_t phi; FOR_EACH_PTR(phi_node->phi_list, phi) { -struct instruction *def;if (phi ==VOID )continue ; - def = phi->def; -if (!def || !def->bb) -continue ; -if (def->opcode ==OP_PHI ) { -phi_defines (def, target, defines); +if (!phi->def || !phi->def->bb)continue ; + +/* +* In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move +* "defines" information upstream to BBs of very initial PHISOURCEs; +* recursion guarded by generation marking of PHI instructions BBs. +*/ +pseudo_t src_pseudo = phi->def->phi_src; +if (src_pseudo->type ==PSEUDO_REG + && src_pseudo->def->opcode ==OP_PHI ) { + phi_node->bb->generation = generation; +if (src_pseudo->def->bb->generation != generation) { +phi_defines (src_pseudo->def, target, defines, generation); +continue ; + } } -defines (def->bb, phi->def, target); + +defines (phi->def->bb, phi->def, target); }END_FOR_EACH_PTR (phi); }
@@ -103,7 +114,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction */* Other */ case OP_PHI :/* Phi-nodes are "backwards" nodes. Their def doesn't matter */ -phi_defines (insn, insn->target, def); +phi_defines (insn, insn->target, def, ++bb_generation);break ;case OP_PHISOURCE :
Signature · 1 line
1.7.1