User account creation filtered due to spam.

Bug 37869 - PTA results wrong for "non-pointer" variables
Summary: PTA results wrong for "non-pointer" variables
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.4.0
: P3 normal
Target Milestone: 4.4.0
Assignee: Not yet assigned to anyone
URL:
Keywords: alias, wrong-code
Depends on:
Blocks: 36509
  Show dependency treegraph
 
Reported: 2008-10-18 22:13 UTC by Richard Biener
Modified: 2008-11-26 09:47 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.4.0
Known to fail: 4.3.2
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2008-10-18 22:13:57 UTC
For the testcase

typedef struct cpp_token { int type; } cpp_token;
typedef struct _cpp_buff { struct _cpp_buff *next; } _cpp_buff;
extern cpp_token *cpp_get_token ();
extern _cpp_buff *cpp_get_buff ();
static void collect_args (_cpp_buff **pragma_buff)
{
  cpp_token *token = _cpp_get_token ();
  do {
      if (*pragma_buff == ((void *)0))
        {
          _cpp_buff *next = *pragma_buff;
          *pragma_buff = _cpp_get_buff ();
          (*pragma_buff)->next = next;
        }
      token = cpp_get_token ();
  } while (token->type != 0);
}
void enter_macro_context ()
{
  _cpp_buff *pragma_buff = ((void *)0);
  collect_args (&pragma_buff);
}

PTA figures that one of the SSA_NAMEs of pragma_buff is a "non-pointer"
variable which makes it ignore its constraints.  We end up with an empty
PTA solution even though we do dereference this pointer:

pragma_buff_4 = &ANYTHING
pragma_buff_11 = pragma_buff_4
pragma_buff_5 = pragma_buff_11
*pragma_buff_5 = pragma_buff_2

Equivalence classes for Direct node node id 16:pragma_buff_5 are pointer: 0, location:0

pragma_buff_5 is a non-pointer variable, eliminating edges.

pragma_buff_5 is a non-pointer variable,ignoring constraint:pragma_buff_5 = pragma_buff_11
pragma_buff_5 is a non-pointer variable,ignoring constraint:*pragma_buff_5 = pragma_buff_2

pragma_buff_5 = { }

<bb 4>:
  pragma_buff_2 = pragma_buff_8;
  D.1263_3 = _cpp_get_buff ();
  pragma_buff_4 = (struct _cpp_buff *) D.1263_3;
  pragma_buff_11 = pragma_buff_4;
  pragma_buff_5 = pragma_buff_11;
  pragma_buff_5->next = pragma_buff_2;


We are "safe" from this error only because an empty points-to solution is
treated the same as a points-to-anything solution by the operand scanner.
Comment 1 Richard Biener 2008-11-25 11:58:29 UTC
Simpler testcase at -O

void
foo (unsigned long *start, unsigned long *end)
{
  unsigned long *temp = end - 1;

  while (end > start)
    *end-- = *temp--;
}

blocks alias-improvements branch (causes the store and load to be deleted).
Comment 2 Richard Biener 2008-11-25 12:22:08 UTC
On the branch I am installing the following as a stop-gap measure:

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c      (revision 142149)
+++ tree-ssa-structalias.c      (working copy)
@@ -230,6 +230,9 @@ struct variable_info
      variable.  This is used for C++ placement new.  */
   unsigned int no_tbaa_pruning : 1;
 
+  /* If found to be a non-pointer variable.  */
+  unsigned int is_nonpointer_var : 1;
+
   /* Variable id this was collapsed to due to type unsafety.  Zero if
      this variable was not collapsed.  This should be unused completely
      after build_succ_graph, or something is broken.  */
@@ -377,6 +380,7 @@ new_var_info (tree t, unsigned int id, c
   ret->is_special_var = false;
   ret->is_unknown_size_var = false;
   ret->is_full_var = false;
+  ret->is_nonpointer_var = false;
   var = t;
   if (TREE_CODE (var) == SSA_NAME)
     var = SSA_NAME_VAR (var);
@@ -2175,6 +2179,7 @@ perform_var_substitution (constraint_gra
                     "%s is a non-pointer variable, eliminating edges.\n",
                     get_varinfo (node)->name);
          stats.nonpointer_vars++;
+         get_varinfo (i)->is_nonpointer_var = true;
          clear_edges_for_node (graph, node);
        }
     }
@@ -4752,6 +4755,11 @@ find_what_p_points_to (tree p)
       if (vi->is_artificial_var)
        return false;
 
+      /* ???  Some real variables get eliminated as non-pointers.
+        Workaround this.  See PR37869.  */
+      if (vi->is_nonpointer_var)
+       return false;
+
       /* See if this is a field or a structure.  */
       if (vi->size != vi->fullsize)
        {
Comment 3 Richard Biener 2008-11-25 20:29:10 UTC
Subject: Bug 37869

Author: rguenth
Date: Tue Nov 25 20:27:44 2008
New Revision: 142202

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=142202
Log:
2008-11-25  Richard Guenther  <rguenther@suse.de>

	* tree-data-ref.c (dr_may_alias_p): Use the alias-oracle.

	* tree-tailcall.c (tree_optimize_tail_calls_1): Also split the
	edge from the entry block if we have degenerate PHI nodes in
	the first basic block.

	* gimple.c (gimple_set_bb): Fix off-by-one error.
	* tree-cfg.c (move_block_to_fn): Likewise.

	PR tree-optimization/37869
	* tree-ssa-structalias.c (struct variable_info): Add
	is_nonpointer_var flag.
	(new_var_info): Clear it.
	(perform_var_substitution): Set it.
	(find_what_p_points_to): Use it.

Modified:
    branches/alias-improvements/gcc/ChangeLog.alias
    branches/alias-improvements/gcc/gimple.c
    branches/alias-improvements/gcc/tree-cfg.c
    branches/alias-improvements/gcc/tree-data-ref.c
    branches/alias-improvements/gcc/tree-ssa-structalias.c
    branches/alias-improvements/gcc/tree-tailcall.c

Comment 4 Richard Biener 2008-11-25 21:23:50 UTC
Testcase from comment #1 has wrong points-to sets on the trunk as well (-O).

end = &NONLOCAL
temp_4 = end
end_7 = end_1
temp_8 = temp_2
end_1 = end
end_1 = end_7
temp_2 = temp_4
temp_2 = temp_8

...

end_7 is a non-pointer variable, eliminating edges.
end_7 is a non-pointer variable, eliminating edges.
end_7 is a non-pointer variable,ignoring constraint:end_7 = end_1
end_1 is a non-pointer variable,ignoring constraint:end_1 = end
end_1 is a non-pointer variable,ignoring constraint:end_1 = end_7

...

end_7 = { }
end_1 = { }

...


<bb 2>:
  temp_4 = end_3(D) + -4;
  goto <bb 4>;

<bb 3>:
  D.1238_6 = *temp_2;
  *end_1 = D.1238_6;
  end_7 = end_1 + -4;
  temp_8 = temp_2 + -4;

<bb 4>:
  # end_1 = PHI <end_3(D)(2), end_7(3)>
  # temp_2 = PHI <temp_4(2), temp_8(3)>
  if (end_1 > start_5(D))
    goto <bb 3>;
  else
    goto <bb 5>;
Comment 5 Richard Biener 2008-11-25 21:45:43 UTC
Simpler testcase:

void
foo (unsigned long *end)
{
  unsigned long *temp = end - 1;

  while (1)
    *end-- = *temp;
}
Comment 6 Richard Biener 2008-11-26 09:47:05 UTC
Fixed.
Comment 7 Richard Biener 2008-11-26 09:47:47 UTC
Subject: Bug 37869

Author: rguenth
Date: Wed Nov 26 09:46:23 2008
New Revision: 142213

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=142213
Log:
2008-11-25  Daniel Berlin  <dberlin@dberlin.org>
	Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/37869
	* tree-ssa-structalias.c (struct constraint_graph): Remove
	pt_used and number_incoming members.
	(build_pred_graph): Do not allocate them.
	(condense_visit): Do not use them.
	(label_visit): Likewise.
	(free_var_substitution_info): Do not free them.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-structalias.c