+ max = tree_to_double_int (maxt);
+
+ switch (TREE_CODE (val))
+ {
+ case INTEGER_CST:
+ return tree_to_double_int (val);
+
+ case NOP_EXPR:
+ case CONVERT_EXPR:
+ op0 = TREE_OPERAND (val, 0);
+ subtype = TREE_TYPE (op0);
+ if (!TYPE_UNSIGNED (subtype)
+ /* If TYPE is also signed, the fact that VAL is nonnegative implies
+ that OP0 is nonnegative. */
+ && TYPE_UNSIGNED (type)
+ && !implies_nonnegative_p (additional, op0))
+ {
+ /* If we cannot prove that the casted expression is nonnegative,
+ we cannot establish more useful upper bound than the precision
+ of the type gives us. */
+ return max;
+ }
+
+ /* We now know that op0 is an nonnegative value. Try deriving an upper
+ bound for it. */
+ bnd = derive_constant_upper_bound (op0, additional);
+
+ /* If the bound does not fit in TYPE, max. value of TYPE could be
+ attained. */
+ if (double_int_ucmp (max, bnd) < 0)
+ return max;
+
+ return bnd;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ op0 = TREE_OPERAND (val, 0);
+ op1 = TREE_OPERAND (val, 1);
+
+ if (TREE_CODE (op1) != INTEGER_CST
+ || !implies_nonnegative_p (additional, op0))
+ return max;
+
+ /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
+ choose the most logical way how to treat this constant regardless
+ of the signedness of the type. */
+ cst = tree_to_double_int (op1);
+ cst = double_int_sext (cst, TYPE_PRECISION (type));
+ if (TREE_CODE (val) == PLUS_EXPR)
+ cst = double_int_neg (cst);
+
+ bnd = derive_constant_upper_bound (op0, additional);
+
+ if (double_int_negative_p (cst))
+ {
+ cst = double_int_neg (cst);
+ /* Avoid CST == 0x80000... */
+ if (double_int_negative_p (cst))
+ return max;;
+
+ /* OP0 + CST. We need to check that
+ BND <= MAX (type) - CST. */
+
+ mmax = double_int_add (max, double_int_neg (cst));
+ if (double_int_ucmp (bnd, mmax) > 0)
+ return max;
+
+ return double_int_add (bnd, cst);
+ }
+ else
+ {
+ /* OP0 - CST, where CST >= 0.
+
+ If TYPE is signed, we have already verified that OP0 >= 0, and we
+ know that the result is nonnegative. This implies that
+ VAL <= BND - CST.
+
+ If TYPE is unsigned, we must additionally know that OP0 >= CST,
+ otherwise the operation underflows.
+ */
+
+ /* This should only happen if the type is unsigned; however, for
+ programs that use overflowing signed arithmetics even with
+ -fno-wrapv, this condition may also be true for signed values. */
+ if (double_int_ucmp (bnd, cst) < 0)
+ return max;
+
+ if (TYPE_UNSIGNED (type)
+ && !implies_ge_p (additional,
+ op0, double_int_to_tree (type, cst)))
+ return max;
+
+ bnd = double_int_add (bnd, double_int_neg (cst));
+ }
+
+ return bnd;
+
+ case FLOOR_DIV_EXPR:
+ case EXACT_DIV_EXPR:
+ op0 = TREE_OPERAND (val, 0);
+ op1 = TREE_OPERAND (val, 1);
+ if (TREE_CODE (op1) != INTEGER_CST
+ || tree_int_cst_sign_bit (op1))
+ return max;
+
+ bnd = derive_constant_upper_bound (op0, additional);
+ return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
+
+ case BIT_AND_EXPR:
+ op1 = TREE_OPERAND (val, 1);
+ if (TREE_CODE (op1) != INTEGER_CST
+ || tree_int_cst_sign_bit (op1))
+ return max;
+ return tree_to_double_int (op1);
+
+ case SSA_NAME:
+ stmt = SSA_NAME_DEF_STMT (val);
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
+ || GIMPLE_STMT_OPERAND (stmt, 0) != val)
+ return max;
+ return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1),
+ additional);
+
+ default:
+ return max;
+ }
+}
+
+/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. The
+ additional condition ADDITIONAL is recorded with the bound. IS_EXIT
+ is true if the loop is exited immediately after STMT, and this exit
+ is taken at last when the STMT is executed BOUND + 1 times.
+ REALISTIC is true if the estimate comes from a reliable source
+ (number of iterations analysis, or size of data accessed in the loop). */