This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [ping][PATCH][1 of 2] Add value range info to SSA_NAME for zero sign extension elimination in RTL


On Tue, 10 Sep 2013, Kugan wrote:

> On 09/09/13 19:01, Richard Biener wrote:
> > On Mon, Sep 9, 2013 at 1:09 AM, Kugan <kugan.vivekanandarajah@linaro.org>
> > wrote:
> > > 
> > > On 06/09/13 16:16, Richard Biener wrote:
> > > > 
> > > > On 9/3/13 2:15 PM, Kugan wrote:
> > > > > 
> > > > > Thanks Richard for reviewing.
> > > > > 
> > > > > On 02/09/13 22:15, Richard Biener wrote:
> > > > > > 
> > > > > > On Wed, Jul 3, 2013 at 2:25 PM, Kugan
> > > > > > <kugan.vivekanandarajah@linaro.org> wrote:
> > > > > > > 
> > > > > > > On 17/06/13 18:33, Richard Biener wrote:
> > > > > > > > 
> > > > > > > > 
> > > > > > > > On Mon, 17 Jun 2013, Kugan wrote:
> > > > > > > > +/* Extract the value range of assigned exprassion for
> > > > > > > > GIMPLE_ASSIGN
> > > > > > > > stmt.
> > > > > > > > +   If the extracted value range is valid, return true else
> > > > > > > > return
> > > > > > > > +   false.  */
> > > > > > > > +static bool
> > > 
> > > 
> > > [snip]
> > > 
> > > 
> > > > > > > > 
> > > > > > > >       for (i = 0; i < num_vr_values; i++)
> > > > > > > >         if (vr_value[i])
> > > > > > > >           {
> > > > > > > >             tree name = ssa_name (i);
> > > > > > > >             if (POINTER_TYPE_P (name))
> > > > > > > >               continue;
> > > > > > > >             if (vr_value[i].type == VR_RANGE
> > > > > > > >                 || vr_value[i].type == VR_ANTI_RANGE)
> > > > > > > >               tree_ssa_set_value_range (name, tree_to_double_int
> > > > > > > > (vr_value[i].min), tree_to_double_int (vr_value[i].max),
> > > > > > > > vr_value[i].type
> > > > > > > > == VR_RANGE);
> > > > > > > >           }
> > > > > > > > 
> > > > > > > 
> > > > > > > Thanks Richard for taking time to review it.
> > > > > > > 
> > > > > > > I was doing something like what you are suggesting earlier but
> > > > > > > noticed some
> > > > > > > problems and that?s the reason why I changed.
> > > > > > > 
> > > > > > > For example, for the following testcase from the test suite,
> > > > > > > 
> > > > > > > unsigned long l = (unsigned long)-2;
> > > > > > > unsigned short s;
> > > > > > > 
> > > > > > > int main () {
> > > > > > >      long t = l + 1;
> > > > > > >      s = l;
> > > > > > >      if (s != (unsigned short) -2)
> > > > > > >        abort ();
> > > > > > >      exit (0);
> > > > > > > }
> > > > > > > 
> > > > > > > with the following gimple stmts
> > > > > > > 
> > > > > > > main ()
> > > > > > > {
> > > > > > >      short unsigned int s.1;
> > > > > > >      long unsigned int l.0;
> > > > > > > 
> > > > > > > ;;   basic block 2, loop depth 0
> > > > > > > ;;    pred:       ENTRY
> > > > > > >      l.0_2 = l;
> > > > > > >      s.1_3 = (short unsigned int) l.0_2;
> > > > > > >      s = s.1_3;
> > > > > > >      if (s.1_3 != 65534)
> > > > > > >        goto <bb 3>;
> > > > > > >      else
> > > > > > >        goto <bb 4>;
> > > > > > > ;;    succ:       3
> > > > > > > ;;                4
> > > > > > > 
> > > > > > > ;;   basic block 3, loop depth 0
> > > > > > > ;;    pred:       2
> > > > > > >      abort ();
> > > > > > > ;;    succ:
> > > > > > > 
> > > > > > > ;;   basic block 4, loop depth 0
> > > > > > > ;;    pred:       2
> > > > > > >      exit (0);
> > > > > > > ;;    succ:
> > > > > > > 
> > > > > > > }
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > has the following value range.
> > > > > > > 
> > > > > > > l.0_2: VARYING
> > > > > > > s.1_3: [0, +INF]
> > > > > > > 
> > > > > > > 
> > > > > > >    From zero/sign extension point of view, the variable s.1_3 is
> > > > > > > expected to
> > > > > > > have a value that will overflow (or varying) as this is what is
> > > > > > > assigned to
> > > > > > > a smaller variable. extract_range_from_assignment initially
> > > > > > > calculates the
> > > > > > > value range as VARYING but later changed to [0, +INF] by
> > > > > > > extract_range_basic. What I need here is the value that will be
> > > > > > > assigned
> > > > > > > from the rhs expression and not the value that we will have with
> > > > > > > proper
> > > > > > > assignment.
> > > > > > 
> > > > > > 
> > > > > > I don't understand this.  The relevant statement is
> > > > > > 
> > > > > >      s.1_3 = (short unsigned int) l.0_2;
> > > > > > 
> > > > > > right?  You have value-ranges for both s.1_3 and l.0_2 as above.
> > > > > > And
> > > > > > you clearly cannot optimize the truncation away (and if you could,
> > > > > > you wond't need value-range information for that fact).
> > > > > > 
> > > > > This is true. But just by looking at the value range of s.1.3 we will
> > > > > only see [0 +INF], as we are transferring directly from the lattice to
> > > > > lhs its value range.
> > > > > 
> > > > > [0, +INF] here tells us  vrp_val_is_max and it is not
> > > > > is_positive_overflow_infinity (or varying). Thats why we need to get
> > > > > the
> > > > > value range of RHS expression which will tell us the actual range. We
> > > > > can then use this range and see of we can fit it to lhs type without
> > > > > truncation.
> > > > 
> > > > 
> > > > Well, my point is you want to look at the l.0_2 value-range for this.
> > > > Storing the l.0_2 value-range for s.1_3 is wrong.
> > > > 
> > > 
> > > Yes, tree SSA_NAME should have it's correct value range. But, assigning
> > > rhs
> > > expression's value range is not totally wrong , it is just that it can be
> > > conservative value range (please correct me if I am wrong here) in few
> > > cases, as it can have wider range.
> > 
> > If it's a sign-changing conversion it can be surely wrong.
> > 
> 
> It is not sign-changing conversion. Rather, when we have rhs expression  value
> which is VR_VARYING it is set to [0, +INF]
> 
> 
> i.e, in extract_range_from_assignment, if the value range is VR_VARYING,
> follwing is done
>  if (vr->type == VR_VARYING)
>      extract_range_basic (vr, stmt);
> 
> In extract_range_basic (when the value range is varying), when the following
> code executes, it changes VR_VARYING to [0, +INF],
> 
>  if (INTEGRAL_TYPE_P (type)
>        && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
>      set_value_range_to_nonnegative (vr, type,
>                                      sop || stmt_overflow_infinity (stmt));
> 
> This will happen only when we have VR_VARYING for the rhs expression. This is
> wrong from zero/sign extension elimination point of view as we cant rely on
> this converted value range.
> 
> 
> Currently I am leaving this as varying so that we can decide whether to
> eliminate the zero/sign extension. This is not completely wrong.
> 
> unsigned short s;
> s.1_3 = (short unsigned int) l.0_2;
> l.0_2: VARYING
> s.1_3: [0, +INF]

Note that [0, +INF] is the same as VARYING and [-INF, +INF] and VARYING for
l.0_2 is the same as [-INF, +INF].

> Similarly (extracted form a testcase)
> 
> unsigned char _4;
> unsigned char _2;
> unsigned char _5;
> 
>   _5 = _4 + _2;
> value range extracted for expression (_4 + _2) extract_range_from_binary_expr
> is VARYING and
> _5 has value range [0 +INF] or [0, 255] after set_value_range_to_nonnegative
> is done.

See above.

> 
> > > I can use the rhs value range in the above case. We can also eliminate
> > > redundant zero/sign extensions for gimple binary and ternary stmts. In
> > > this
> > > case we will have to calculate the value range.  We will have to reuse
> > > these
> > > logic in tree-vrp.
> > 
> > I fail to see the issue given no concrete example.
> > 
> 
> I hope I have explained it better this time.

Not really.  What's the desired value-range and what's the value-range
that you get from the lattice?

> > > Other option is to add another attribute in range_info_t to indicate if
> > > set_value_range_to_nonnegative is used in value range extraction.
> > 
> > Why should the result of this not be accurately represented in the lattice?
> > 
> > > What is your preferred solution please.
> > 
> > I don't know because I do not understand the problem at hand.
> > 
> 
> Could you please suggest the preferred way now.

Use the value-range from the lattice.

Richard.

> > I suspect that the right answer is to instead do
> > 
> > GTY ((desc (%1.ptr_info && ...)))
> > 
> > that is, make sure the pointer is not NULL.  Or push the union into the
> > pointer target instead.
> > 
> > Do others have a better solution?  The issue is that the descriptor for
> > the GT machinery is not valid if the "field" (either of the pointers in the
> > union) is NULL.  But then it wouldn't matter anyway.  The GTY machinery
> > doesn't seem to handle this special-case (all-pointers in the union).

Micha just suggested

  union vrp_info_type {
    /* Pointer attributes used for alias analysis.  */
    struct GTY ((tag ("0"))) ptr_info_def *ptr_info;
    /* Value range attributes used for zero/sign extension elimination.  
*/
    struct GTY ((tag ("1"))) range_info_def *range_info;
  } GTY ((desc ("%1.typed.type ? !POINTER_TYPE_P (TREE_TYPE 
((tree)&%1)) : 2"))) vrp

that is, if TREE_TYPE is NULL (released SSA names), do not walk
either.

Richard.

> > Richard.
> > 
> > > make[2]: *** [_mulsc3.o] Error 1
> > > 0x97755f crash_signal
> > >          /home/kugan/work/sources/gcc-fsf/test/gcc/toplev.c:335
> > > 0x55f7d1 gt_ggc_mx_lang_tree_node(void*)
> > >          ./gt-c-c-decl.h:531
> > > 0x802e36 gt_ggc_mx<tree_node*>
> > >          /home/kugan/work/sources/gcc-fsf/test/gcc/vec.h:1152
> > > 0x802e36 gt_ggc_mx_vec_tree_va_gc_(void*)
> > > 
> > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1205
> > > 0x8081ed gt_ggc_mx_gimple_df(void*)
> > > 
> > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1066
> > > 0x80825f gt_ggc_mx_function
> > > 
> > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1280
> > > 0x80825f gt_ggc_mx_function(void*)
> > > 
> > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:1272
> > > 0x55f692 gt_ggc_mx_lang_tree_node(void*)
> > >          ./gt-c-c-decl.h:389
> > > 0x807dd5 gt_ggc_mx_symtab_node_def(void*)
> > > 
> > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:709
> > > 0x807fb0 gt_ggc_m_P15symtab_node_def4htab(void*)
> > > 
> > > /home/kugan/work/builds/gcc-fsf-test/obj-arm-none-linux-gnueabi/gcc1/gcc/gtype-desc.c:2928
> > > 0x7b7915 ggc_mark_root_tab
> > >          /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:133
> > > 0x7b7c60 ggc_mark_roots()
> > >          /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-common.c:152
> > > 0x615669 ggc_collect()
> > >          /home/kugan/work/sources/gcc-fsf/test/gcc/ggc-page.c:2077
> > > 
> > > 
> > > 
> > > 
> > > Thanks a lot.
> > > 
> > > Kugan
> > > 
> > > 
> > > > Richard.
> > > > 
> > > > > > +void
> > > > > > +set_range_info (tree name, double_int min,
> > > > > > +                          double_int max, bool vr_range)
> > > > > > 
> > > > > > you have some whitespace issues here (please properly use tabs)
> > > > > > 
> > > > > 
> > > > > I will change it.
> > > > > 
> > > > > > +  /* Allocate if not available.  */
> > > > > > +  if (ri == NULL)
> > > > > > +    {
> > > > > > +      ri = ggc_alloc_cleared_range_info_def ();
> > > > > > +      mark_range_info_unknown (ri);
> > > > > > 
> > > > > > that looks superfluous to me.
> > > > > > 
> > > > > > +      SSA_NAME_RANGE_INFO (name) = ri;
> > > > > > 
> > > > > > -  /* Pointer attributes used for alias analysis.  */
> > > > > > -  struct ptr_info_def *ptr_info;
> > > > > > +  /* Value range information.  */
> > > > > > +  union vrp_info_type {
> > > > > > +    /* Pointer attributes used for alias analysis.  */
> > > > > > +    struct GTY ((tag ("0"))) ptr_info_def *ptr_info;
> > > > > > +    /* Value range attributes used for zero/sign extension
> > > > > > elimination.  */
> > > > > > +    struct GTY ((tag ("1"))) range_info_def *range_info;
> > > > > > +  } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE
> > > > > > ((tree)&%1))"))) vrp;
> > > > > > 
> > > > > > please change vrp_info_type and vrp to other names - this is not vrp
> > > > > > specific info
> > > > > > after all, I suggest ssa_name_info_type and info.
> > > > > > 
> > > > > 
> > > > > I will change this too.
> > > > > > 
> > > > > > The genric bits otherwise look ok to me, the VRP bits still look
> > > > > > wrong
> > > > > > (see my
> > > > > > above question) and need explanation.
> > > > > > 
> > > > > > Thanks,
> > > > > > Richard.
> > > > > > 
> > > > > > > 
> > > > > > > Thanks,
> > > > > > > Kugan
> > > > > 
> > > > > 
> > > > > 
> > > > > Thanks,
> > > > > Kugan
> > > > > 
> > > > 
> > > 
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]