Message ID | 050001d78f5f$b7d650e0$2782f2a0$@nextmovesoftware.com |
---|---|
State | New |
Headers | show |
Series | Improved handling of MINUS_EXPR in bit CCP. | expand |
On Thu, Aug 12, 2021 at 11:52 AM Roger Sayle <roger@nextmovesoftware.com> wrote: > > > This patch improves the bit bounds for MINUS_EXPR during tree-ssa's > conditional constant propagation (CCP) pass (and as an added bonus > adds support for POINTER_DIFF_EXPR). > > The pessimistic assumptions made by the current algorithm are > demonstrated by considering 1 - (x&1). Intuitively this should > have possible values 0 and 1, and therefore an unknown mask of 1. > Alas by treating subtraction as a negation followed by addition, > the second operand first becomes 0 or -1, with an unknown mask > of all ones, which results in the addition containing no known bits. > > Improved bounds are achieved by using the same approach used for > PLUS_EXPR, determining the result with the minimum number of borrows, > the result from the maximum number of borrows, and examining the bits > they have in common. One additional benefit of this approach > is that it is applicable to POINTER_DIFF_EXPR, where previously the > negation of a pointer didn't/doesn't make sense. > > A more convincing example, where a transformation missed by .032t.cpp > isn't caught a few passes later by .038t.evrp, is the expression > (7 - (x&5)) & 2, which (in the new test case) currently survives the > tree-level optimizers but with this patch is now simplified to the > constant value 2. > > This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap" > and "make -k check" with no new failures. > > Ok for mainline? OK. Thanks, Richard. > 2021-08-12 Roger Sayle <roger@nextmovesoftware.com> > > gcc/ChangeLog > * tree-ssa-ccp.c (bit_value_binop) [MINUS_EXPR]: Use same > algorithm as PLUS_EXPR to improve subtraction bit bounds. > [POINTER_DIFF_EXPR]: Treat as synonymous with MINUS_EXPR. > > gcc/testsuite/ChangeLog > * gcc.dg/tree-ssa/ssa-ccp-40.c: New test case. > > > Roger > -- > Roger Sayle > NextMove Software > Cambridge, UK >
diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index 003c9c2..1223370 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -1398,7 +1398,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, widest_int *val, widest_int *mask, signop r1type_sgn, int r1type_precision, const widest_int &r1val, const widest_int &r1mask, - signop r2type_sgn, int r2type_precision, + signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED, const widest_int &r2val, const widest_int &r2mask) { bool swap_p = false; @@ -1445,7 +1445,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, } else { - if (wi::neg_p (shift)) + if (wi::neg_p (shift, r2type_sgn)) { shift = -shift; if (code == RROTATE_EXPR) @@ -1482,7 +1482,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, } else { - if (wi::neg_p (shift)) + if (wi::neg_p (shift, r2type_sgn)) break; if (code == RSHIFT_EXPR) { @@ -1522,13 +1522,16 @@ bit_value_binop (enum tree_code code, signop sgn, int width, } case MINUS_EXPR: + case POINTER_DIFF_EXPR: { - widest_int temv, temm; - bit_value_unop (NEGATE_EXPR, r2type_sgn, r2type_precision, &temv, &temm, - r2type_sgn, r2type_precision, r2val, r2mask); - bit_value_binop (PLUS_EXPR, sgn, width, val, mask, - r1type_sgn, r1type_precision, r1val, r1mask, - r2type_sgn, r2type_precision, temv, temm); + /* Subtraction is derived from the addition algorithm above. */ + widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask); + lo = wi::ext (lo, width, sgn); + widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask); + hi = wi::ext (hi, width, sgn); + *mask = r1mask | r2mask | (lo ^ hi); + *mask = wi::ext (*mask, width, sgn); + *val = lo; break; }