Re: Help in understanding ccp propagator
On Sun, 17 Jun 2007, Revital1 Eres wrote: Hello, I have one more question regarding the comment in tree-ssa-ccp.c file - /* Note that for propagation purposes, we are only interested in visiting statements that load the exact same memory reference stored here. Those statements will have the exact same list of virtual uses, so it is enough to set the output of this statement to be its first virtual definition. */ *output_p = first_vdef (stmt); I wonder if this comment is true also if the vuses are not immediate as in stmt no. 1 in the following example: 1) arr[i].x = tmp1; ... 2) arr[i].y = tmp2; ... 3) reg1 = arr[i].x; ... 4) arr[i].z = tmp2; ... 5) reg2 = arr[i].x; Is it because we are looking for the exact same memory reference (although not immediate) it is enough to look at only first_vdef of every store we encounter in our walk through the virtual def-use chain; or by looking only at the first vdef we could miss vuses that could have been reached by vdefs other than the first one? Well, in the current code we do not walk virtual use-def chains, but make sure all virtual operands are the same. So the above works. If you walk the chains you need to make sure that all virtual operands of the final def you are using are the same - then the above will work again. Richard.
Re: Help in understanding ccp propagator
Hello, I have one more question regarding the comment in tree-ssa-ccp.c file - /* Note that for propagation purposes, we are only interested in visiting statements that load the exact same memory reference stored here. Those statements will have the exact same list of virtual uses, so it is enough to set the output of this statement to be its first virtual definition. */ *output_p = first_vdef (stmt); I wonder if this comment is true also if the vuses are not immediate as in stmt no. 1 in the following example: 1) arr[i].x = tmp1; ... 2) arr[i].y = tmp2; ... 3) reg1 = arr[i].x; ... 4) arr[i].z = tmp2; ... 5) reg2 = arr[i].x; Is it because we are looking for the exact same memory reference (although not immediate) it is enough to look at only first_vdef of every store we encounter in our walk through the virtual def-use chain; or by looking only at the first vdef we could miss vuses that could have been reached by vdefs other than the first one? Thanks again, Revital
Re: Help in understanding ccp propagator
The engine only knew how to propagate cases that always make the same set of vdef/vuses, so it was safe to only tell it to use the first vdef. /* Note that for propagation purposes, we are only interested in visiting statements that load the exact same memory reference stored here. Those statements will have the exact same list of virtual uses, so it is enough to set the output of this statement to be its first virtual definition. */ You are changing this, AFAIK, so you will need to make it handle multiple output values. That's indeed the problem: Consider the following stmt that is been visited - # MPT.1416_722 = VDEF MPT.1416_734 { MPT.1416 } D.61410.first = i0_62; Than output_p will be set to MPT.1416_722 (which is the only vdef of this stmt) - *output_p = first_vdef (stmt); And later on (in add_ssa_edge () function) all the uses of MPT.1416_722 will be added to the working set which in our case is D.61410.second = 97; statement instead of the real uses of D.61410.first. # MPT.1416_723 = VDEF MPT.1416_722 { MPT.1416 } D.61410.second = 97; Is there a way to retrieve the real uses of D.61410.first? Thanks again, Revital
Re: Help in understanding ccp propagator
On 6/12/07, Revital1 Eres [EMAIL PROTECTED] wrote: The engine only knew how to propagate cases that always make the same set of vdef/vuses, so it was safe to only tell it to use the first vdef. /* Note that for propagation purposes, we are only interested in visiting statements that load the exact same memory reference stored here. Those statements will have the exact same list of virtual uses, so it is enough to set the output of this statement to be its first virtual definition. */ You are changing this, AFAIK, so you will need to make it handle multiple output values. That's indeed the problem: Consider the following stmt that is been visited - # MPT.1416_722 = VDEF MPT.1416_734 { MPT.1416 } D.61410.first = i0_62; Than output_p will be set to MPT.1416_722 (which is the only vdef of this stmt) - *output_p = first_vdef (stmt); And later on (in add_ssa_edge () function) all the uses of MPT.1416_722 will be added to the working set which in our case is D.61410.second = 97; statement instead of the real uses of D.61410.first. # MPT.1416_723 = VDEF MPT.1416_722 { MPT.1416 } D.61410.second = 97; Is there a way to retrieve the real uses of D.61410.first? No, you will have to look at each immediate use and determine if it is really a store to the same place. Thanks again, Revital
Re: Help in understanding ccp propagator
I can modify it to catch it pretty easily, just walk back a few vuses if the current set of vuses is defined by something that does not actually touch our offset. This sounds like what I am trying to do in ccp... I am not sure I understand. The new patch uses the infrastructure of the propagator and I do not see an indication in the dumps for vdefs update after the lattice value is changed: 19930 19931 Visiting statement: 19932 D.61410.first = i0_62; 19933 19934 Lattice value changed to CONSTANT 0. Adding SSA edges to worklist. 19935 Thanks again fo your help, Revital So uh, how do you expect the propagator to notice when the used variables have changed if the things the vdefs produced by D.61410.first are not marked as change (so that the immediate uses of it get processed). You will need to add this if it is not there already. Normally, the propagator says oh, the lattice value of D_64 changed, let me mark all it's immediate uses for reprocessing. The only thing that links memory defs to memory uses is the vdef/vuses, so you will have to be able to process and mark those I thought the engine suppose to take care of that. I do not understand why this case is different from other cases where we propagate for vdefs... Thanks again, Revital
Re: Help in understanding ccp propagator
On 6/5/07, Revital1 Eres [EMAIL PROTECTED] wrote: I can modify it to catch it pretty easily, just walk back a few vuses if the current set of vuses is defined by something that does not actually touch our offset. This sounds like what I am trying to do in ccp... I am not sure I understand. The new patch uses the infrastructure of the propagator and I do not see an indication in the dumps for vdefs update after the lattice value is changed: 19930 19931 Visiting statement: 19932 D.61410.first = i0_62; 19933 19934 Lattice value changed to CONSTANT 0. Adding SSA edges to worklist. 19935 Thanks again fo your help, Revital So uh, how do you expect the propagator to notice when the used variables have changed if the things the vdefs produced by D.61410.first are not marked as change (so that the immediate uses of it get processed). You will need to add this if it is not there already. Normally, the propagator says oh, the lattice value of D_64 changed, let me mark all it's immediate uses for reprocessing. The only thing that links memory defs to memory uses is the vdef/vuses, so you will have to be able to process and mark those I thought the engine suppose to take care of that. I do not understand why this case is different from other cases where we propagate for vdefs... The engine only knew how to propagate cases that always make the same set of vdef/vuses, so it was safe to only tell it to use the first vdef. /* Note that for propagation purposes, we are only interested in visiting statements that load the exact same memory reference stored here. Those statements will have the exact same list of virtual uses, so it is enough to set the output of this statement to be its first virtual definition. */ You are changing this, AFAIK, so you will need to make it handle multiple output values. Thanks again, Revital
Re: Help in understanding ccp propagator
I will greatly appreciate any suggestions regarding the following problem I have with the ccp propagator. I am testing the new store ccp patch which propagates constants by walking the virtual use-def chain (http://gcc.gnu.org/ml/gcc-patches/2007-05/msg00055.html) and I encountered the following problem while testing tree_join.cc file which is under libstdc++-v3 testsuite: BTW, a lot of these will be caught with the new VN i posted, whicih should be reviewed and go in soon. Thanks, should it handle cases like the one in the following example - http://gcc.gnu.org/ml/gcc-patches/2007-03/txt00081.txt? I tried it with the VN patch but it seems to not caught it... The final propagator replaces the right operand (D.65705_98) in the following if condition with a constant zero which causes the program to be aborted as i0_62 is not always zero: # i0_62 = PHI i0_5(29), 0(3) L139:; D.61410.first = i0_62; ... D.65705_98 = D.61410.first; - if (D.65704_96 = 0) + if (D.65704_96 = D.65705_98) goto bb 11; else goto bb 14; Tracing the execution of the propagator it seems that the if statement is first been propogated with zero after simulating the execution; but not updated after the lattice value of the variables it depends on changed. Does your store CPP properly say the vdefs have changed when a statement's lattice value changes? I am not sure I understand. The new patch uses the infrastructure of the propagator and I do not see an indication in the dumps for vdefs update after the lattice value is changed: 19930 19931 Visiting statement: 19932 D.61410.first = i0_62; 19933 19934 Lattice value changed to CONSTANT 0. Adding SSA edges to worklist. 19935 Thanks again fo your help, Revital
Re: Help in understanding ccp propagator
On 6/4/07, Revital1 Eres [EMAIL PROTECTED] wrote: I will greatly appreciate any suggestions regarding the following problem I have with the ccp propagator. I am testing the new store ccp patch which propagates constants by walking the virtual use-def chain (http://gcc.gnu.org/ml/gcc-patches/2007-05/msg00055.html) and I encountered the following problem while testing tree_join.cc file which is under libstdc++-v3 testsuite: BTW, a lot of these will be caught with the new VN i posted, whicih should be reviewed and go in soon. Thanks, should it handle cases like the one in the following example - http://gcc.gnu.org/ml/gcc-patches/2007-03/txt00081.txt? I tried it with the VN patch but it seems to not caught it... I can modify it to catch it pretty easily, just walk back a few vuses if the current set of vuses is defined by something that does not actually touch our offset. s? I am not sure I understand. The new patch uses the infrastructure of the propagator and I do not see an indication in the dumps for vdefs update after the lattice value is changed: 19930 19931 Visiting statement: 19932 D.61410.first = i0_62; 19933 19934 Lattice value changed to CONSTANT 0. Adding SSA edges to worklist. 19935 Thanks again fo your help, Revital So uh, how do you expect the propagator to notice when the used variables have changed if the things the vdefs produced by D.61410.first are not marked as change (so that the immediate uses of it get processed). You will need to add this if it is not there already. Normally, the propagator says oh, the lattice value of D_64 changed, let me mark all it's immediate uses for reprocessing. The only thing that links memory defs to memory uses is the vdef/vuses, so you will have to be able to process and mark those