diff mbox

[C++] Detect UB in shifts in constexpr functions

Message ID 20141124135114.GO29446@redhat.com
State New
Headers show

Commit Message

Marek Polacek Nov. 24, 2014, 1:51 p.m. UTC 
Constant expressions can't contain undefined behavior, which means that
using an expression containing UB in a context requiring a constant
expression makes the program invalid and we're required to diagnose that.
We fail to diagnose UB if using shifts, because fold_binary_loc returns
zero for a shift containing UB.  So I wrote a function that checks whether
the shift operation is ok.
I'm not sure yet if anything else needs similar treatment.

Bootstrapped/regtested on ppc64-linux, ok for trunk?

2014-11-24  Marek Polacek  <polacek@redhat.com>

	* constexpr.c (cxx_eval_check_shift_p): New function.
	(cxx_eval_binary_expression): Call it.

	* g++.dg/cpp0x/constexpr-shift1.C: New test.


	Marek

Comments

Jakub Jelinek Nov. 24, 2014, 3:49 p.m. UTC | #1 
On Mon, Nov 24, 2014 at 02:51:14PM +0100, Marek Polacek wrote:
> --- gcc/cp/constexpr.c
> +++ gcc/cp/constexpr.c
> @@ -1451,6 +1451,43 @@ verify_constant (tree t, bool allow_non_constant, bool *non_constant_p,
>    return *non_constant_p;
>  }
>  
> +/* Return true if the shift operation on LHS and RHS is undefined.  */
> +
> +static bool
> +cxx_eval_check_shift_p (enum tree_code code, tree lhs, tree rhs)
> +{
> +  if (code != LSHIFT_EXPR && code != RSHIFT_EXPR)
> +    return false;
> +
> +  tree lhstype = TREE_TYPE (lhs);
> +  unsigned HOST_WIDE_INT uprec = TYPE_PRECISION (TREE_TYPE (lhs));
> +
> +  /* [expr.shift] The behavior is undefined if the right operand
> +     is negative, or greater than or equal to the length in bits
> +     of the promoted left operand.  */
> +  if (tree_int_cst_sgn (rhs) == -1 || compare_tree_int (rhs, uprec) >= 0)
> +    return true;

I think VERIFY_CONSTANT doesn't guarantee both operands are INTEGER_CSTs.
Consider say:

constexpr int p = 1;
constexpr int foo (int a)
{
  return a << (int) &p;
}
constexpr int bar (int a)
{
  return ((int) &p) << a;
}
constexpr int q = foo (5);
constexpr int r = bar (2);
constexpr int s = bar (0);

Now, for foo (5) and bar (2) fold_binary_loc returns NULL and thus
your cxx_eval_check_shift_p is not called, for bar (0) it returns
non-NULL and while the result still is not a constant expression and
right now is diagnosed, with your patch it would ICE.

So, I'd just return false if either lhs or rhs are not INTEGER_CSTs.

> +
> +  /* The value of E1 << E2 is E1 left-shifted E2 bit positions; [...]
> +     if E1 has a signed type and non-negative value, and E1x2^E2 is
> +     representable in the corresponding unsigned type of the result type,
> +     then that value, converted to the result type, is the resulting value;
> +     otherwise, the behavior is undefined.  */
> +  if (code == LSHIFT_EXPR && !TYPE_UNSIGNED (lhstype))
> +    {
> +      if (tree_int_cst_sgn (lhs) == -1)
> +	return true;
> +      tree t = build_int_cst (unsigned_type_node, uprec - 1);
> +      t = fold_build2 (MINUS_EXPR, unsigned_type_node, t, rhs);
> +      tree ulhs = fold_convert (unsigned_type_for (lhstype), lhs);
> +      t = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ulhs), ulhs, t);
> +      if (tree_int_cst_lt (integer_one_node, t))
> +	return true;

I'll leave to Jason whether this shouldn't be using the various
cxx_eval_*_expression calls instead, or perhaps int_const_binop or wide_int
stuff directly.

	Jakub
Marek Polacek Nov. 24, 2014, 3:58 p.m. UTC | #2 
On Mon, Nov 24, 2014 at 04:49:25PM +0100, Jakub Jelinek wrote:
> On Mon, Nov 24, 2014 at 02:51:14PM +0100, Marek Polacek wrote:
> > --- gcc/cp/constexpr.c
> > +++ gcc/cp/constexpr.c
> > @@ -1451,6 +1451,43 @@ verify_constant (tree t, bool allow_non_constant, bool *non_constant_p,
> >    return *non_constant_p;
> >  }
> >  
> > +/* Return true if the shift operation on LHS and RHS is undefined.  */
> > +
> > +static bool
> > +cxx_eval_check_shift_p (enum tree_code code, tree lhs, tree rhs)
> > +{
> > +  if (code != LSHIFT_EXPR && code != RSHIFT_EXPR)
> > +    return false;
> > +
> > +  tree lhstype = TREE_TYPE (lhs);
> > +  unsigned HOST_WIDE_INT uprec = TYPE_PRECISION (TREE_TYPE (lhs));
> > +
> > +  /* [expr.shift] The behavior is undefined if the right operand
> > +     is negative, or greater than or equal to the length in bits
> > +     of the promoted left operand.  */
> > +  if (tree_int_cst_sgn (rhs) == -1 || compare_tree_int (rhs, uprec) >= 0)
> > +    return true;
> 
> I think VERIFY_CONSTANT doesn't guarantee both operands are INTEGER_CSTs.

Oh well.  I ran the testsuite with an assert checking that I always have
INTEGER_CSTs and didn't see any ICEs.

> Consider say:
> 
> constexpr int p = 1;
> constexpr int foo (int a)
> {
>   return a << (int) &p;
> }
> constexpr int bar (int a)
> {
>   return ((int) &p) << a;
> }
> constexpr int q = foo (5);
> constexpr int r = bar (2);
> constexpr int s = bar (0);
> 
> Now, for foo (5) and bar (2) fold_binary_loc returns NULL and thus
> your cxx_eval_check_shift_p is not called, for bar (0) it returns
> non-NULL and while the result still is not a constant expression and
> right now is diagnosed, with your patch it would ICE.
> 
> So, I'd just return false if either lhs or rhs are not INTEGER_CSTs.
 
Ok, I'll add that.  Thank for pointing that out.

> > +
> > +  /* The value of E1 << E2 is E1 left-shifted E2 bit positions; [...]
> > +     if E1 has a signed type and non-negative value, and E1x2^E2 is
> > +     representable in the corresponding unsigned type of the result type,
> > +     then that value, converted to the result type, is the resulting value;
> > +     otherwise, the behavior is undefined.  */
> > +  if (code == LSHIFT_EXPR && !TYPE_UNSIGNED (lhstype))
> > +    {
> > +      if (tree_int_cst_sgn (lhs) == -1)
> > +	return true;
> > +      tree t = build_int_cst (unsigned_type_node, uprec - 1);
> > +      t = fold_build2 (MINUS_EXPR, unsigned_type_node, t, rhs);
> > +      tree ulhs = fold_convert (unsigned_type_for (lhstype), lhs);
> > +      t = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ulhs), ulhs, t);
> > +      if (tree_int_cst_lt (integer_one_node, t))
> > +	return true;
> 
> I'll leave to Jason whether this shouldn't be using the various
> cxx_eval_*_expression calls instead, or perhaps int_const_binop or wide_int
> stuff directly.

ISTR int_const_binop calls wide_int routines wi::rshift/wi::lshift and these
return 0 and do not have any overflow flag, so that might not help (?).

	Marek
Jakub Jelinek Nov. 24, 2014, 4:05 p.m. UTC | #3 
On Mon, Nov 24, 2014 at 04:58:22PM +0100, Marek Polacek wrote:
> > Consider say:
> > 
> > constexpr int p = 1;
> > constexpr int foo (int a)
> > {
> >   return a << (int) &p;
> > }
> > constexpr int bar (int a)
> > {
> >   return ((int) &p) << a;
> > }
> > constexpr int q = foo (5);
> > constexpr int r = bar (2);
> > constexpr int s = bar (0);
> > 
> > Now, for foo (5) and bar (2) fold_binary_loc returns NULL and thus
> > your cxx_eval_check_shift_p is not called, for bar (0) it returns
> > non-NULL and while the result still is not a constant expression and
> > right now is diagnosed, with your patch it would ICE.
> > 
> > So, I'd just return false if either lhs or rhs are not INTEGER_CSTs.
>  
> Ok, I'll add that.  Thank for pointing that out.

Note, the above only with -m32 obviously, or supposedly for bar
you could change return type and the cast and type of r/s to
__PTRDIFF_TYPE__ or so.  foo, as gcc always casts the shift count to int,
would supposedly need to stay the way it is and might produce different
diagnostics between -m32 and -m64.
> 
> > > +
> > > +  /* The value of E1 << E2 is E1 left-shifted E2 bit positions; [...]
> > > +     if E1 has a signed type and non-negative value, and E1x2^E2 is
> > > +     representable in the corresponding unsigned type of the result type,
> > > +     then that value, converted to the result type, is the resulting value;
> > > +     otherwise, the behavior is undefined.  */
> > > +  if (code == LSHIFT_EXPR && !TYPE_UNSIGNED (lhstype))
> > > +    {
> > > +      if (tree_int_cst_sgn (lhs) == -1)
> > > +	return true;
> > > +      tree t = build_int_cst (unsigned_type_node, uprec - 1);
> > > +      t = fold_build2 (MINUS_EXPR, unsigned_type_node, t, rhs);
> > > +      tree ulhs = fold_convert (unsigned_type_for (lhstype), lhs);
> > > +      t = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ulhs), ulhs, t);
> > > +      if (tree_int_cst_lt (integer_one_node, t))
> > > +	return true;
> > 
> > I'll leave to Jason whether this shouldn't be using the various
> > cxx_eval_*_expression calls instead, or perhaps int_const_binop or wide_int
> > stuff directly.
> 
> ISTR int_const_binop calls wide_int routines wi::rshift/wi::lshift and these
> return 0 and do not have any overflow flag, so that might not help (?).

I meant for the above computation, there you don't check any overflow.

	Jakub
diff mbox

Patch

diff --git gcc/cp/constexpr.c gcc/cp/constexpr.c
index 2678223..2047a09 100644
--- gcc/cp/constexpr.c
+++ gcc/cp/constexpr.c
@@ -1451,6 +1451,43 @@  verify_constant (tree t, bool allow_non_constant, bool *non_constant_p,
   return *non_constant_p;
 }
 
+/* Return true if the shift operation on LHS and RHS is undefined.  */
+
+static bool
+cxx_eval_check_shift_p (enum tree_code code, tree lhs, tree rhs)
+{
+  if (code != LSHIFT_EXPR && code != RSHIFT_EXPR)
+    return false;
+
+  tree lhstype = TREE_TYPE (lhs);
+  unsigned HOST_WIDE_INT uprec = TYPE_PRECISION (TREE_TYPE (lhs));
+
+  /* [expr.shift] The behavior is undefined if the right operand
+     is negative, or greater than or equal to the length in bits
+     of the promoted left operand.  */
+  if (tree_int_cst_sgn (rhs) == -1 || compare_tree_int (rhs, uprec) >= 0)
+    return true;
+
+  /* The value of E1 << E2 is E1 left-shifted E2 bit positions; [...]
+     if E1 has a signed type and non-negative value, and E1x2^E2 is
+     representable in the corresponding unsigned type of the result type,
+     then that value, converted to the result type, is the resulting value;
+     otherwise, the behavior is undefined.  */
+  if (code == LSHIFT_EXPR && !TYPE_UNSIGNED (lhstype))
+    {
+      if (tree_int_cst_sgn (lhs) == -1)
+	return true;
+      tree t = build_int_cst (unsigned_type_node, uprec - 1);
+      t = fold_build2 (MINUS_EXPR, unsigned_type_node, t, rhs);
+      tree ulhs = fold_convert (unsigned_type_for (lhstype), lhs);
+      t = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ulhs), ulhs, t);
+      if (tree_int_cst_lt (integer_one_node, t))
+	return true;
+    }
+
+  return false;
+}
+
 /* Subroutine of cxx_eval_constant_expression.
    Attempt to reduce the unary expression tree T to a compile time value.
    If successful, return the value.  Otherwise issue a diagnostic
@@ -1506,7 +1543,7 @@  cxx_eval_binary_expression (const constexpr_ctx *ctx, tree t,
   enum tree_code code = TREE_CODE (t);
   tree type = TREE_TYPE (t);
   r = fold_binary_loc (loc, code, type, lhs, rhs);
-  if (r == NULL_TREE)
+  if (r == NULL_TREE || cxx_eval_check_shift_p (code, lhs, rhs))
     {
       if (lhs == orig_lhs && rhs == orig_rhs)
 	r = t;
diff --git gcc/testsuite/g++.dg/cpp0x/constexpr-shift1.C gcc/testsuite/g++.dg/cpp0x/constexpr-shift1.C
index e69de29..2551fbe 100644
--- gcc/testsuite/g++.dg/cpp0x/constexpr-shift1.C
+++ gcc/testsuite/g++.dg/cpp0x/constexpr-shift1.C
@@ -0,0 +1,73 @@ 
+// { dg-do compile { target c++11 } }
+
+constexpr int
+fn1 (int i, int j)
+{
+  return i << j; // { dg-error "is not a constant expression" }
+}
+
+constexpr int i1 = fn1 (1, -1);
+
+constexpr int
+fn2 (int i, int j)
+{
+  return i << j; // { dg-error "is not a constant expression" }
+}
+
+constexpr int i2 = fn2 (1, 200);
+
+constexpr int
+fn3 (int i, int j)
+{
+  return i << j; // { dg-error "is not a constant expression" }
+}
+
+constexpr int i3 = fn3 (-1, 2);
+
+constexpr int
+fn4 (int i, int j)
+{
+  return i << j; // { dg-error "is not a constant expression" }
+}
+
+constexpr int i4 = fn4 (__INT_MAX__, 2);
+
+constexpr int
+fn5 (int i, int j)
+{
+  return i << j;
+}
+
+constexpr int i5 = fn5 (__INT_MAX__, 1);
+
+constexpr int
+fn6 (unsigned int i, unsigned int j)
+{
+  return i << j; // { dg-error "is not a constant expression" }
+}
+
+constexpr int i6 = fn6 (1, -1);
+
+constexpr int
+fn7 (int i, int j)
+{
+  return i >> j; // { dg-error "is not a constant expression" }
+}
+
+constexpr int i7 = fn7 (1, -1);
+
+constexpr int
+fn8 (int i, int j)
+{
+  return i >> j;
+}
+
+constexpr int i8 = fn8 (-1, 1);
+
+constexpr int
+fn9 (int i, int j)
+{
+  return i >> j;  // { dg-error "is not a constant expression" }
+}
+
+constexpr int i9 = fn9 (1, 200);