This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][RFC] Conservative alignment extraction & propagation (2nd try)
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 6 Aug 2010 17:30:40 +0200 (CEST)
- Subject: [PATCH][RFC] Conservative alignment extraction & propagation (2nd try)
This is a second variant of alignment extraction and propagation building
on bit-CCP. The key feature is that get_{pointer,object}_alignment now
return conservative correct answers (see PRs 39954 and 44903 for bugs
that show issues with the way we handle alignment).
The infrastructure this provides allows to replace MISALIGNED_INDIRECT_REF
(a followup patch which I have already completed) which in turn requires
a way to generally handle misaligned loads and stores with non-BLKmode.
Yes, we can loose alignment information the same way we can loose
points-to information, but the default is conservatively correct
(no known alignment). We also miss a CCP pass after loop optimizers
to update knowledge for new generated code or induction variables.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Comments?
Thanks,
Richard.
2010-08-06 Richard Guenther <rguenther@suse.de>
* tree-flow.h (struct ptr_info_def): Add align and misalign fields.
* tree-ssa-alias.c (get_ptr_info): Move ...
* tree-ssanames.c (get_ptr_info): ... here. Initialize
align and misalign fields conservatively.
* tree-ssa-ccp.c (ccp_finalize): From partially constant pointers
derive alignment information.
(evaluate_stmt): Derive alignment information from memory
allocation functions.
* builtins.c (get_object_alignment): Make conservative and use
alignment information we have computed for pointers. Handle
MEM_REF and TARGET_MEM_REF properly.
(get_pointer_alignment): Likewise.
* gimple-pretty-print.c (dump_gimple_phi): Alongside alias
information also dump pointer alignment knowledge.
(dump_gimple_stmt): Likewise.
Index: trunk/gcc/builtins.c
===================================================================
*** trunk.orig/gcc/builtins.c 2010-08-06 12:26:37.000000000 +0200
--- trunk/gcc/builtins.c 2010-08-06 17:19:17.000000000 +0200
*************** called_as_built_in (tree node)
*** 273,347 ****
int
get_object_alignment (tree exp, unsigned int align, unsigned int max_align)
{
! unsigned int inner;
! inner = max_align;
! if (handled_component_p (exp))
! {
! HOST_WIDE_INT bitsize, bitpos;
! tree offset;
! enum machine_mode mode;
! int unsignedp, volatilep;
!
! exp = get_inner_reference (exp, &bitsize, &bitpos, &offset,
! &mode, &unsignedp, &volatilep, true);
! if (bitpos)
! inner = MIN (inner, (unsigned) (bitpos & -bitpos));
! while (offset)
! {
! tree next_offset;
!
! if (TREE_CODE (offset) == PLUS_EXPR)
! {
! next_offset = TREE_OPERAND (offset, 0);
! offset = TREE_OPERAND (offset, 1);
! }
! else
! next_offset = NULL;
! if (host_integerp (offset, 1))
! {
! /* Any overflow in calculating offset_bits won't change
! the alignment. */
! unsigned offset_bits
! = ((unsigned) tree_low_cst (offset, 1) * BITS_PER_UNIT);
!
! if (offset_bits)
! inner = MIN (inner, (offset_bits & -offset_bits));
! }
! else if (TREE_CODE (offset) == MULT_EXPR
! && host_integerp (TREE_OPERAND (offset, 1), 1))
! {
! /* Any overflow in calculating offset_factor won't change
! the alignment. */
! unsigned offset_factor
! = ((unsigned) tree_low_cst (TREE_OPERAND (offset, 1), 1)
! * BITS_PER_UNIT);
!
! if (offset_factor)
! inner = MIN (inner, (offset_factor & -offset_factor));
! }
! else
! {
! inner = MIN (inner, BITS_PER_UNIT);
! break;
! }
! offset = next_offset;
! }
! }
if (TREE_CODE (exp) == CONST_DECL)
exp = DECL_INITIAL (exp);
! if (DECL_P (exp)
! && TREE_CODE (exp) != LABEL_DECL)
! align = MIN (inner, DECL_ALIGN (exp));
! #ifdef CONSTANT_ALIGNMENT
else if (CONSTANT_CLASS_P (exp))
! align = MIN (inner, (unsigned)CONSTANT_ALIGNMENT (exp, align));
#endif
! else if (TREE_CODE (exp) == VIEW_CONVERT_EXPR
! || TREE_CODE (exp) == INDIRECT_REF)
! align = MIN (TYPE_ALIGN (TREE_TYPE (exp)), inner);
else
! align = MIN (align, inner);
return MIN (align, max_align);
}
--- 273,419 ----
int
get_object_alignment (tree exp, unsigned int align, unsigned int max_align)
{
! HOST_WIDE_INT bitsize, bitpos;
! tree offset;
! enum machine_mode mode;
! int unsignedp, volatilep;
! exp = get_inner_reference (exp, &bitsize, &bitpos, &offset,
! &mode, &unsignedp, &volatilep, true);
if (TREE_CODE (exp) == CONST_DECL)
exp = DECL_INITIAL (exp);
! if (INDIRECT_REF_P (exp)
! || TREE_CODE (exp) == MEM_REF)
! {
! struct ptr_info_def *pi;
! tree addr = TREE_OPERAND (exp, 0);
! HOST_WIDE_INT maskalign = BITS_PER_UNIT;
! if (TREE_CODE (addr) == BIT_AND_EXPR
! && TREE_CODE (TREE_OPERAND (addr, 1)) == INTEGER_CST)
! {
! maskalign = (TREE_INT_CST_LOW (TREE_OPERAND (addr, 1))
! & -TREE_INT_CST_LOW (TREE_OPERAND (addr, 1)));
! maskalign *= BITS_PER_UNIT;
! addr = TREE_OPERAND (addr, 0);
! }
! if (TREE_CODE (addr) == SSA_NAME
! && (pi = SSA_NAME_PTR_INFO (addr)))
! {
! bitpos += (pi->misalign * BITS_PER_UNIT) & ~(maskalign - 1);
! align = MAX (pi->align * BITS_PER_UNIT, maskalign);
! }
! else if (TREE_CODE (addr) == ADDR_EXPR)
! align = MAX (get_pointer_alignment (addr, max_align), maskalign);
! else
! align = maskalign;
! if (TREE_CODE (exp) == MEM_REF)
! bitpos += mem_ref_offset (exp).low * BITS_PER_UNIT;
! }
! else if (TREE_CODE (exp) == TARGET_MEM_REF
! && TMR_BASE (exp)
! && POINTER_TYPE_P (TREE_TYPE (TMR_BASE (exp))))
! {
! struct ptr_info_def *pi;
! tree addr = TMR_BASE (exp);
! HOST_WIDE_INT maskalign = BITS_PER_UNIT;
! if (TREE_CODE (addr) == BIT_AND_EXPR
! && TREE_CODE (TREE_OPERAND (addr, 1)) == INTEGER_CST)
! {
! maskalign = (TREE_INT_CST_LOW (TREE_OPERAND (addr, 1))
! & -TREE_INT_CST_LOW (TREE_OPERAND (addr, 1)));
! maskalign *= BITS_PER_UNIT;
! addr = TREE_OPERAND (addr, 0);
! }
! if (TREE_CODE (addr) == SSA_NAME
! && (pi = SSA_NAME_PTR_INFO (addr)))
! {
! bitpos += (pi->misalign * BITS_PER_UNIT) & ~(maskalign - 1);
! align = MAX (pi->align * BITS_PER_UNIT, maskalign);
! }
! else if (TREE_CODE (addr) == ADDR_EXPR)
! align = MAX (get_pointer_alignment (addr, max_align), maskalign);
! else
! align = maskalign;
! if (TMR_OFFSET (exp))
! bitpos += TREE_INT_CST_LOW (TMR_OFFSET (exp)) * BITS_PER_UNIT;
! if (TMR_INDEX (exp) && TMR_STEP (exp))
! {
! unsigned HOST_WIDE_INT step = TREE_INT_CST_LOW (TMR_STEP (exp));
! align = MIN (align, (step & -step) * BITS_PER_UNIT);
! }
! else if (TMR_INDEX (exp))
! align = BITS_PER_UNIT;
! }
! else if (TREE_CODE (exp) == TARGET_MEM_REF
! && TMR_SYMBOL (exp))
! {
! align = get_object_alignment (TMR_SYMBOL (exp), BITS_PER_UNIT, max_align);
! if (TMR_OFFSET (exp))
! bitpos += TREE_INT_CST_LOW (TMR_OFFSET (exp)) * BITS_PER_UNIT;
! if (TMR_INDEX (exp) && TMR_STEP (exp))
! {
! unsigned HOST_WIDE_INT step = TREE_INT_CST_LOW (TMR_STEP (exp));
! align = MIN (align, (step & -step) * BITS_PER_UNIT);
! }
! else if (TMR_INDEX (exp))
! align = BITS_PER_UNIT;
! }
! else if (DECL_P (exp)
! && TREE_CODE (exp) != LABEL_DECL)
! align = DECL_ALIGN (exp);
else if (CONSTANT_CLASS_P (exp))
! {
! align = TYPE_ALIGN (TREE_TYPE (exp));
! #ifdef CONSTANT_ALIGNMENT
! align = (unsigned)CONSTANT_ALIGNMENT (exp, align);
#endif
! }
else
! return BITS_PER_UNIT;
!
! if (bitpos)
! align = MIN (align, (unsigned) (bitpos & -bitpos));
!
! /* Try to be clever for the non-constant offset part. */
! while (offset)
! {
! tree next_offset;
!
! if (TREE_CODE (offset) == PLUS_EXPR)
! {
! next_offset = TREE_OPERAND (offset, 0);
! offset = TREE_OPERAND (offset, 1);
! }
! else
! next_offset = NULL;
! if (host_integerp (offset, 1))
! {
! /* Any overflow in calculating offset_bits won't change
! the alignment. */
! unsigned offset_bits
! = ((unsigned) tree_low_cst (offset, 1) * BITS_PER_UNIT);
!
! if (offset_bits)
! align = MIN (align, (offset_bits & -offset_bits));
! }
! else if (TREE_CODE (offset) == MULT_EXPR
! && host_integerp (TREE_OPERAND (offset, 1), 1))
! {
! /* Any overflow in calculating offset_factor won't change
! the alignment. */
! unsigned offset_factor
! = ((unsigned) tree_low_cst (TREE_OPERAND (offset, 1), 1)
! * BITS_PER_UNIT);
!
! if (offset_factor)
! align = MIN (align, (offset_factor & -offset_factor));
! }
! else
! return BITS_PER_UNIT;
!
! offset = next_offset;
! }
!
return MIN (align, max_align);
}
*************** can_trust_pointer_alignment (void)
*** 358,418 ****
/* Return the alignment in bits of EXP, a pointer valued expression.
But don't return more than MAX_ALIGN no matter what.
The alignment returned is, by default, the alignment of the thing that
! EXP points to. If it is not a POINTER_TYPE, 0 is returned.
!
! Otherwise, look at the expression to see if we can do better, i.e., if the
! expression is actually pointing at an object whose alignment is tighter. */
int
get_pointer_alignment (tree exp, unsigned int max_align)
{
! unsigned int align, inner;
!
! if (!can_trust_pointer_alignment ())
! return 0;
!
! if (!POINTER_TYPE_P (TREE_TYPE (exp)))
! return 0;
!
! align = TYPE_ALIGN (TREE_TYPE (TREE_TYPE (exp)));
! align = MIN (align, max_align);
! while (1)
{
! switch (TREE_CODE (exp))
! {
! CASE_CONVERT:
! exp = TREE_OPERAND (exp, 0);
! if (! POINTER_TYPE_P (TREE_TYPE (exp)))
! return align;
!
! inner = TYPE_ALIGN (TREE_TYPE (TREE_TYPE (exp)));
! align = MIN (inner, max_align);
! break;
!
! case POINTER_PLUS_EXPR:
! /* If sum of pointer + int, restrict our maximum alignment to that
! imposed by the integer. If not, we can't do any better than
! ALIGN. */
! if (! host_integerp (TREE_OPERAND (exp, 1), 1))
! return align;
!
! while (((tree_low_cst (TREE_OPERAND (exp, 1), 1))
! & (max_align / BITS_PER_UNIT - 1))
! != 0)
! max_align >>= 1;
!
! exp = TREE_OPERAND (exp, 0);
! break;
!
! case ADDR_EXPR:
! /* See what we are pointing at and look at its alignment. */
! return get_object_alignment (TREE_OPERAND (exp, 0), align, max_align);
!
! default:
! return align;
! }
}
}
/* Compute the length of a C string. TREE_STRING_LENGTH is not the right
--- 430,459 ----
/* Return the alignment in bits of EXP, a pointer valued expression.
But don't return more than MAX_ALIGN no matter what.
The alignment returned is, by default, the alignment of the thing that
! EXP points to. If it is not a POINTER_TYPE, 0 is returned. */
int
get_pointer_alignment (tree exp, unsigned int max_align)
{
! STRIP_NOPS (exp);
! if (TREE_CODE (exp) == ADDR_EXPR)
! return get_object_alignment (TREE_OPERAND (exp, 0),
! BITS_PER_UNIT, max_align);
! else if (TREE_CODE (exp) == SSA_NAME
! && POINTER_TYPE_P (TREE_TYPE (exp)))
{
! struct ptr_info_def *pi = SSA_NAME_PTR_INFO (exp);
! unsigned align;
! if (!pi)
! return BITS_PER_UNIT;
! align = pi->align;
! if (pi->misalign)
! align = MIN (align, (pi->misalign & -pi->misalign));
! return MIN (max_align, align * BITS_PER_UNIT);
}
+
+ return POINTER_TYPE_P (TREE_TYPE (exp)) ? BITS_PER_UNIT : 0;
}
/* Compute the length of a C string. TREE_STRING_LENGTH is not the right
Index: trunk/gcc/gimple-pretty-print.c
===================================================================
*** trunk.orig/gcc/gimple-pretty-print.c 2010-08-05 15:47:11.000000000 +0200
--- trunk/gcc/gimple-pretty-print.c 2010-08-06 14:10:28.000000000 +0200
*************** dump_gimple_phi (pretty_printer *buffer,
*** 1363,1370 ****
&& POINTER_TYPE_P (TREE_TYPE (lhs))
&& SSA_NAME_PTR_INFO (lhs))
{
pp_string (buffer, "PT = ");
! pp_points_to_solution (buffer, &SSA_NAME_PTR_INFO (lhs)->pt);
newline_and_indent (buffer, spc);
pp_string (buffer, "# ");
}
--- 1363,1375 ----
&& POINTER_TYPE_P (TREE_TYPE (lhs))
&& SSA_NAME_PTR_INFO (lhs))
{
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
pp_string (buffer, "PT = ");
! pp_points_to_solution (buffer, &pi->pt);
! newline_and_indent (buffer, spc);
! if (pi->align != 1)
! pp_printf (buffer, "# ALIGN = %u, MISALIGN = %u",
! pi->align, pi->misalign);
newline_and_indent (buffer, spc);
pp_string (buffer, "# ");
}
*************** dump_gimple_stmt (pretty_printer *buffer
*** 1650,1658 ****
&& POINTER_TYPE_P (TREE_TYPE (lhs))
&& SSA_NAME_PTR_INFO (lhs))
{
pp_string (buffer, "# PT = ");
! pp_points_to_solution (buffer, &SSA_NAME_PTR_INFO (lhs)->pt);
newline_and_indent (buffer, spc);
}
}
--- 1655,1670 ----
&& POINTER_TYPE_P (TREE_TYPE (lhs))
&& SSA_NAME_PTR_INFO (lhs))
{
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
pp_string (buffer, "# PT = ");
! pp_points_to_solution (buffer, &pi->pt);
newline_and_indent (buffer, spc);
+ if (pi->align != 1)
+ {
+ pp_printf (buffer, "# ALIGN = %u, MISALIGN = %u",
+ pi->align, pi->misalign);
+ newline_and_indent (buffer, spc);
+ }
}
}
Index: trunk/gcc/tree-flow.h
===================================================================
*** trunk.orig/gcc/tree-flow.h 2010-08-05 15:47:11.000000000 +0200
--- trunk/gcc/tree-flow.h 2010-08-06 14:10:28.000000000 +0200
*************** struct GTY(()) ptr_info_def
*** 119,124 ****
--- 119,129 ----
{
/* The points-to solution. */
struct pt_solution pt;
+
+ /* Alignment and misalignment of the pointer in bytes.
+ ptr & (align-1) == misalign. */
+ unsigned int align;
+ unsigned int misalign;
};
Index: trunk/gcc/tree-ssa-alias.c
===================================================================
*** trunk.orig/gcc/tree-ssa-alias.c 2010-08-05 15:47:11.000000000 +0200
--- trunk/gcc/tree-ssa-alias.c 2010-08-06 14:10:28.000000000 +0200
*************** debug_alias_info (void)
*** 368,394 ****
}
- /* Return the alias information associated with pointer T. It creates a
- new instance if none existed. */
-
- struct ptr_info_def *
- get_ptr_info (tree t)
- {
- struct ptr_info_def *pi;
-
- gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
-
- pi = SSA_NAME_PTR_INFO (t);
- if (pi == NULL)
- {
- pi = ggc_alloc_cleared_ptr_info_def ();
- pt_solution_reset (&pi->pt);
- SSA_NAME_PTR_INFO (t) = pi;
- }
-
- return pi;
- }
-
/* Dump the points-to set *PT into FILE. */
void
--- 368,373 ----
Index: trunk/gcc/tree-ssanames.c
===================================================================
*** trunk.orig/gcc/tree-ssanames.c 2010-08-05 15:47:11.000000000 +0200
--- trunk/gcc/tree-ssanames.c 2010-08-06 14:10:28.000000000 +0200
*************** release_ssa_name (tree var)
*** 240,259 ****
}
}
- /* Creates a duplicate of a ssa name NAME defined in statement STMT. */
! tree
! duplicate_ssa_name (tree name, gimple stmt)
{
! tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
! struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
! if (old_ptr_info)
! duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
! return new_name;
! }
/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
the SSA name NAME. */
--- 240,268 ----
}
}
! /* Return the alias information associated with pointer T. It creates a
! new instance if none existed. */
!
! struct ptr_info_def *
! get_ptr_info (tree t)
{
! struct ptr_info_def *pi;
! gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
! pi = SSA_NAME_PTR_INFO (t);
! if (pi == NULL)
! {
! pi = ggc_alloc_cleared_ptr_info_def ();
! pt_solution_reset (&pi->pt);
! pi->align = 1;
! pi->misalign = 0;
! SSA_NAME_PTR_INFO (t) = pi;
! }
+ return pi;
+ }
/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
the SSA name NAME. */
*************** duplicate_ssa_name_ptr_info (tree name,
*** 276,281 ****
--- 285,305 ----
}
+ /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT. */
+
+ tree
+ duplicate_ssa_name (tree name, gimple stmt)
+ {
+ tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
+ struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
+
+ if (old_ptr_info)
+ duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+
+ return new_name;
+ }
+
+
/* Release all the SSA_NAMEs created by STMT. */
void
Index: trunk/gcc/tree-ssa-ccp.c
===================================================================
*** trunk.orig/gcc/tree-ssa-ccp.c 2010-08-06 13:48:55.000000000 +0200
--- trunk/gcc/tree-ssa-ccp.c 2010-08-06 17:17:41.000000000 +0200
*************** static bool
*** 840,847 ****
--- 840,879 ----
ccp_finalize (void)
{
bool something_changed;
+ unsigned i;
do_dbg_cnt ();
+
+ /* Derive alignment and misalignment information from partially
+ constant pointers in the lattice. */
+ for (i = 1; i < num_ssa_names; ++i)
+ {
+ tree name = ssa_name (i);
+ prop_value_t *val;
+ struct ptr_info_def *pi;
+ unsigned int tem, align;
+
+ if (!name
+ || !POINTER_TYPE_P (TREE_TYPE (name)))
+ continue;
+
+ val = get_value (name);
+ if (val->lattice_val != CONSTANT
+ || TREE_CODE (val->value) != INTEGER_CST)
+ continue;
+
+ /* Trailing constant bits specify the alignment, trailing value
+ bits the misalignment. */
+ tem = val->mask.low;
+ align = (tem & -tem);
+ if (align == 1)
+ continue;
+
+ pi = get_ptr_info (name);
+ pi->align = align;
+ pi->misalign = TREE_INT_CST_LOW (val->value) & (align - 1);
+ }
+
/* Perform substitutions based on the known constant values. */
something_changed = substitute_and_fold (get_constant_value,
ccp_fold_stmt, true);
*************** evaluate_stmt (gimple stmt)
*** 1982,1987 ****
--- 2014,2020 ----
&& !is_constant)
{
enum gimple_code code = gimple_code (stmt);
+ tree fndecl;
val.lattice_val = VARYING;
val.value = NULL_TREE;
val.mask = double_int_minus_one;
*************** evaluate_stmt (gimple stmt)
*** 2027,2032 ****
--- 2060,2092 ----
|| POINTER_TYPE_P (TREE_TYPE (rhs1)))
val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
}
+ else if (code == GIMPLE_CALL
+ && (fndecl = gimple_call_fndecl (stmt))
+ && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
+ {
+ switch (DECL_FUNCTION_CODE (fndecl))
+ {
+ case BUILT_IN_MALLOC:
+ case BUILT_IN_REALLOC:
+ case BUILT_IN_CALLOC:
+ val.lattice_val = CONSTANT;
+ val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
+ val.mask = shwi_to_double_int
+ (~(((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT)
+ / BITS_PER_UNIT - 1));
+ break;
+
+ case BUILT_IN_ALLOCA:
+ val.lattice_val = CONSTANT;
+ val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
+ val.mask = shwi_to_double_int
+ (~(((HOST_WIDE_INT) BIGGEST_ALIGNMENT)
+ / BITS_PER_UNIT - 1));
+ break;
+
+ default:;
+ }
+ }
is_constant = (val.lattice_val == CONSTANT);
}