- case iro_Confirm: {
- ir_node* const v = get_Confirm_value(irn);
- bitinfo* const b = get_bitinfo(v);
- /* TODO Use bound and relation. */
- z = b->z;
- o = b->o;
- break;
+ if (b == NULL || b->z == f) {
+undefined:
+ z = get_tarval_null(m);
+ o = get_tarval_all_one(m);
+ } else if (is_Phi(irn)) {
+ ir_node* const block = get_nodes_block(irn);
+ int const arity = get_Phi_n_preds(irn);
+ int i;
+
+ z = get_tarval_null(m);
+ o = get_tarval_all_one(m);
+ for (i = 0; i != arity; ++i) {
+ bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
+ if (b_cfg != NULL && b_cfg->z != f) {
+ bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
+ /* Only use input if it's not undefined. */
+ if (!is_undefined(b)) {
+ z = tarval_or( z, b->z);
+ o = tarval_and(o, b->o);
+ }
+ }
+ }
+ } else {
+ int const arity = get_irn_arity(irn);
+ int i;
+
+ /* Undefined if any input is undefined. */
+ for (i = 0; i != arity; ++i) {
+ ir_node* const pred = get_irn_n(irn, i);
+ bitinfo* const pred_b = get_bitinfo(pred);
+ if (pred_b != NULL && is_undefined(pred_b))
+ goto undefined;
- case iro_Shr: {
- bitinfo* const l = get_bitinfo(get_Shr_left(irn));
- bitinfo* const r = get_bitinfo(get_Shr_right(irn));
- ir_tarval* const rz = r->z;
- if (rz == r->o) {
- z = tarval_shr(l->z, rz);
- o = tarval_shr(l->o, rz);
- } else {
- goto cannot_analyse;
+ case iro_Confirm: {
+ ir_node* const v = get_Confirm_value(irn);
+ bitinfo* const b = get_bitinfo(v);
+ /* TODO Use bound and relation. */
+ z = b->z;
+ o = b->o;
+ if ((get_Confirm_relation(irn) & ~ir_relation_unordered) == ir_relation_equal) {
+ bitinfo* const bound_b = get_bitinfo(get_Confirm_bound(irn));
+ z = tarval_and(z, bound_b->z);
+ o = tarval_or( o, bound_b->o);
+ }
+ break;
- case iro_Add: {
- bitinfo* const l = get_bitinfo(get_Add_left(irn));
- bitinfo* const r = get_bitinfo(get_Add_right(irn));
- ir_tarval* const lz = l->z;
- ir_tarval* const lo = l->o;
- ir_tarval* const rz = r->z;
- ir_tarval* const ro = r->o;
- if (lz == lo && rz == ro) {
- z = o = tarval_add(lz, rz);
- } else {
- // TODO improve: can only do lower disjoint bits
- /* Determine where any of the operands has zero bits, i.e. where no
- * carry out is generated if there is not carry in */
- ir_tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
- /* Generate a mask of the lower consecutive zeroes: x | -x. In this
- * range the addition is disjoint and therefore Add behaves like Or.
- */
- ir_tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
- ir_tarval* const low_one_mask = tarval_not(low_zero_mask);
- z = tarval_or( tarval_or(lz, rz), low_zero_mask);
- o = tarval_and(tarval_or(lo, ro), low_one_mask);
+ case iro_Shrs: {
+ bitinfo* const l = get_bitinfo(get_Shrs_left(irn));
+ bitinfo* const r = get_bitinfo(get_Shrs_right(irn));
+ ir_tarval* const rz = r->z;
+ if (rz == r->o) {
+ z = tarval_shrs(l->z, rz);
+ o = tarval_shrs(l->o, rz);
+ } else {
+ goto cannot_analyse;
+ }
+ break;
+ // TODO improve: can only do lower disjoint bits
+ /* Determine where any of the operands has zero bits, i.e. where no
+ * carry out is generated if there is not carry in */
+ ir_tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
+ /* Generate a mask of the lower consecutive zeroes: x | -x. In this
+ * range the addition is disjoint and therefore Add behaves like Or.
+ */
+ ir_tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
+ ir_tarval* const low_one_mask = tarval_not(low_zero_mask);
+ z = tarval_or( tarval_or(lz, rz), low_zero_mask);
+ o = tarval_and(tarval_or(lo, ro), low_one_mask);
- case iro_Mul: {
- bitinfo* const l = get_bitinfo(get_Mul_left(irn));
- bitinfo* const r = get_bitinfo(get_Mul_right(irn));
- ir_tarval* const lz = l->z;
- ir_tarval* const lo = l->o;
- ir_tarval* const rz = r->z;
- ir_tarval* const ro = r->o;
- if (lz == lo && rz == ro) {
- z = o = tarval_mul(lz, rz);
- } else {
- // TODO improve
- // Determine safe lower zeroes: x | -x.
- ir_tarval* const lzn = tarval_or(lz, tarval_neg(lz));
- ir_tarval* const rzn = tarval_or(rz, tarval_neg(rz));
- // Concatenate safe lower zeroes.
- if (tarval_cmp(lzn, rzn) == ir_relation_less) {
- z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
+ case iro_Sub: {
+ bitinfo* const l = get_bitinfo(get_Sub_left(irn));
+ bitinfo* const r = get_bitinfo(get_Sub_right(irn));
+ if (l != NULL && r != NULL) { // Sub might subtract pointers.
+ ir_tarval* const lz = l->z;
+ ir_tarval* const lo = l->o;
+ ir_tarval* const rz = r->z;
+ ir_tarval* const ro = r->o;
+ if (lz == lo && rz == ro) {
+ z = o = tarval_sub(lz, rz, NULL);
+ } else if (tarval_is_null(tarval_andnot(rz, lo))) {
+ /* Every possible one of the subtrahend is backed by a safe one of the
+ * minuend, i.e. there are no borrows. */
+ // TODO extend no-borrow like carry for Add above
+ z = tarval_andnot(lz, ro);
+ o = tarval_andnot(lo, rz);
+ } else {
+ goto cannot_analyse;
+ }
- case iro_Minus: {
- bitinfo* const b = get_bitinfo(get_Minus_op(irn));
- if (b->z == b->o) {
- z = o = tarval_neg(b->z);
- } else {
- goto cannot_analyse;
+ case iro_Mul: {
+ bitinfo* const l = get_bitinfo(get_Mul_left(irn));
+ bitinfo* const r = get_bitinfo(get_Mul_right(irn));
+ ir_tarval* const lz = l->z;
+ ir_tarval* const lo = l->o;
+ ir_tarval* const rz = r->z;
+ ir_tarval* const ro = r->o;
+ if (lz == lo && rz == ro) {
+ z = o = tarval_mul(lz, rz);
+ } else {
+ // TODO improve
+ // Determine safe lower zeroes: x | -x.
+ ir_tarval* const lzn = tarval_or(lz, tarval_neg(lz));
+ ir_tarval* const rzn = tarval_or(rz, tarval_neg(rz));
+ // Concatenate safe lower zeroes.
+ if (tarval_cmp(lzn, rzn) == ir_relation_less) {
+ z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
+ } else {
+ z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn);
+ }
+ o = get_tarval_null(m);
+ }
+ break;
- case iro_Eor: {
- bitinfo* const l = get_bitinfo(get_Eor_left(irn));
- bitinfo* const r = get_bitinfo(get_Eor_right(irn));
- ir_tarval* const lz = l->z;
- ir_tarval* const lo = l->o;
- ir_tarval* const rz = r->z;
- ir_tarval* const ro = r->o;
- z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
- o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
- break;
- }
+ case iro_Or: {
+ bitinfo* const l = get_bitinfo(get_Or_left(irn));
+ bitinfo* const r = get_bitinfo(get_Or_right(irn));
+ z = tarval_or(l->z, r->z);
+ o = tarval_or(l->o, r->o);
+ break;
+ }
- case iro_Phi: {
- ir_node* const block = get_nodes_block(irn);
- int const arity = get_Phi_n_preds(irn);
- int i;
-
- z = get_tarval_null(m);
- o = get_tarval_all_one(m);
- for (i = 0; i != arity; ++i) {
- bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
- if (b_cfg != NULL && b_cfg->z != f) {
- bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
- z = tarval_or( z, b->z);
- o = tarval_and(o, b->o);
+ case iro_Mux: {
+ bitinfo* const bf = get_bitinfo(get_Mux_false(irn));
+ bitinfo* const bt = get_bitinfo(get_Mux_true(irn));
+ bitinfo* const c = get_bitinfo(get_Mux_sel(irn));
+ if (c->o == t) {
+ z = bt->z;
+ o = bt->o;
+ } else if (c->z == f) {
+ z = bf->z;
+ o = bf->o;
+ } else {
+ z = tarval_or( bf->z, bt->z);
+ o = tarval_and(bf->o, bt->o);
- case iro_Cmp: {
- bitinfo* const l = get_bitinfo(get_Cmp_left(irn));
- bitinfo* const r = get_bitinfo(get_Cmp_right(irn));
- if (l == NULL || r == NULL) {
- goto result_unknown; // Cmp compares something we cannot evaluate.
- } else {
- ir_tarval* const lz = l->z;
- ir_tarval* const lo = l->o;
- ir_tarval* const rz = r->z;
- ir_tarval* const ro = r->o;
- ir_relation const relation = get_Cmp_relation(irn);
- switch (relation) {
- case ir_relation_less_greater:
- if (!tarval_is_null(tarval_andnot(ro, lz)) ||
- !tarval_is_null(tarval_andnot(lo, rz))) {
- // At least one bit differs.
- z = o = t;
- } else if (lz == lo && rz == ro && lz == rz) {
- z = o = f;
- } else {
- goto result_unknown;
- }
- break;
-
- case ir_relation_equal:
- if (!tarval_is_null(tarval_andnot(ro, lz)) ||
- !tarval_is_null(tarval_andnot(lo, rz))) {
- // At least one bit differs.
- z = o = f;
- } else if (lz == lo && rz == ro && lz == rz) {
- z = o = t;
- } else {
- goto result_unknown;
- }
- break;
-
- case ir_relation_less_equal:
- case ir_relation_less:
- /* TODO handle negative values */
- if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
- tarval_is_negative(rz) || tarval_is_negative(ro))
- goto result_unknown;
-
- if (tarval_cmp(lz, ro) & relation) {
- /* Left upper bound is smaller(/equal) than right lower bound. */
- z = o = t;
- } else if (!(tarval_cmp(lo, rz) & relation)) {
- /* Left lower bound is not smaller(/equal) than right upper bound. */
- z = o = f;
- } else {
- goto result_unknown;
- }
- break;
-
- case ir_relation_greater_equal:
- case ir_relation_greater:
- /* TODO handle negative values */
- if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
- tarval_is_negative(rz) || tarval_is_negative(ro))
- goto result_unknown;
-
- if (!(tarval_cmp(lz, ro) & relation)) {
- /* Left upper bound is not greater(/equal) than right lower bound. */
- z = o = f;
- } else if (tarval_cmp(lo, rz) & relation) {
- /* Left lower bound is greater(/equal) than right upper bound. */
- z = o = t;
- } else {
- goto result_unknown;
- }
- break;
-
- default:
- goto cannot_analyse;
+ case iro_Cmp: {
+ bitinfo* const l = get_bitinfo(get_Cmp_left(irn));
+ bitinfo* const r = get_bitinfo(get_Cmp_right(irn));
+ if (l == NULL || r == NULL) {
+ goto result_unknown; // Cmp compares something we cannot evaluate.
+ } else {
+ ir_tarval* const lz = l->z;
+ ir_tarval* const lo = l->o;
+ ir_tarval* const rz = r->z;
+ ir_tarval* const ro = r->o;
+ ir_relation const relation = get_Cmp_relation(irn);
+ switch (relation) {
+ case ir_relation_less_greater:
+ if (!tarval_is_null(tarval_andnot(ro, lz)) ||
+ !tarval_is_null(tarval_andnot(lo, rz))) {
+ // At least one bit differs.
+ z = o = t;
+ } else if (lz == lo && rz == ro && lz == rz) {
+ z = o = f;
+ } else {
+ goto result_unknown;
+ }
+ break;
+
+ case ir_relation_equal:
+ if (!tarval_is_null(tarval_andnot(ro, lz)) ||
+ !tarval_is_null(tarval_andnot(lo, rz))) {
+ // At least one bit differs.
+ z = o = f;
+ } else if (lz == lo && rz == ro && lz == rz) {
+ z = o = t;
+ } else {
+ goto result_unknown;
+ }
+ break;
+
+ case ir_relation_less_equal:
+ case ir_relation_less:
+ /* TODO handle negative values */
+ if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
+ tarval_is_negative(rz) || tarval_is_negative(ro))
+ goto result_unknown;
+
+ if (tarval_cmp(lz, ro) & relation) {
+ /* Left upper bound is smaller(/equal) than right lower bound. */
+ z = o = t;
+ } else if (!(tarval_cmp(lo, rz) & relation)) {
+ /* Left lower bound is not smaller(/equal) than right upper bound. */
+ z = o = f;
+ } else {
+ goto result_unknown;
+ }
+ break;
+
+ case ir_relation_greater_equal:
+ case ir_relation_greater:
+ /* TODO handle negative values */
+ if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
+ tarval_is_negative(rz) || tarval_is_negative(ro))
+ goto result_unknown;
+
+ if (!(tarval_cmp(lz, ro) & relation)) {
+ /* Left upper bound is not greater(/equal) than right lower bound. */
+ z = o = f;
+ } else if (tarval_cmp(lo, rz) & relation) {
+ /* Left lower bound is greater(/equal) than right upper bound. */
+ z = o = t;
+ } else {
+ goto result_unknown;
+ }
+ break;
+
+ default:
+ goto cannot_analyse;
+ }