+/**
+ * Apply one LFTR edge operation.
+ * Return NULL if the transformation cannot be done safely without
+ * an Overflow.
+ *
+ * @param iv the induction variable
+ * @param rc the constant that should be translated
+ * @param e the LFTR edge
+ * @param env the IV environment
+ *
+ * @return the translated region constant or NULL
+ * if the translation was not possible
+ *
+ * @note
+ * In the current implementation only the last edge is stored, so
+ * only one chain exists. That's why we might miss some opportunities.
+ */
+static ir_node *applyOneEdge(ir_node *iv, ir_node *rc, LFTR_edge *e, iv_env *env) {
+ if (env->flags & osr_flag_lftr_with_ov_check) {
+ tarval *tv_l, *tv_r, *tv, *tv_init, *tv_incr;
+ tarval_int_overflow_mode_t ovmode;
+ scc *pscc;
+
+ if (! is_counter_iv(iv, env)) {
+ DB((dbg, LEVEL_4, " not counter IV"));
+ return NULL;
+ }
+
+ /* overflow can only be decided for Consts */
+ if (! is_Const(e->rc)) {
+ DB((dbg, LEVEL_4, " = UNKNOWN (%+F)", e->rc));
+ return NULL;
+ }
+
+ tv_l = get_Const_tarval(rc);
+ tv_r = get_Const_tarval(e->rc);
+
+ ovmode = tarval_get_integer_overflow_mode();
+ tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
+
+ pscc = get_iv_scc(iv, env);
+ tv_incr = pscc->incr;
+ tv_init = pscc->init;
+
+ /*
+ * Check that no overflow occurs:
+ * init must be transformed without overflow
+ * the new rc must be transformed without overflow
+ * rc +/- incr must be possible without overflow
+ */
+ switch (e->code) {
+ case iro_Mul:
+ tv = tarval_mul(tv_l, tv_r);
+ tv_init = tarval_mul(tv_init, tv_r);
+ tv_incr = tarval_mul(tv_incr, tv_r);
+ DB((dbg, LEVEL_4, " * %+F", tv_r));
+ break;
+ case iro_Add:
+ tv = tarval_add(tv_l, tv_r);
+ tv_init = tarval_add(tv_init, tv_r);
+ DB((dbg, LEVEL_4, " + %+F", tv_r));
+ break;
+ case iro_Sub:
+ tv = tarval_sub(tv_l, tv_r, NULL);
+ tv_init = tarval_sub(tv_init, tv_r, NULL);
+ DB((dbg, LEVEL_4, " - %+F", tv_r));
+ break;
+ default:
+ panic("Unsupported opcode");
+ tv = tarval_bad;
+ }
+
+ if (pscc->code == iro_Add) {
+ tv = tarval_add(tv, tv_incr);
+ } else {
+ assert(pscc->code == iro_Sub);
+ tv = tarval_sub(tv, tv_incr, NULL);
+ }
+
+ tarval_set_integer_overflow_mode(ovmode);
+
+ if (tv == tarval_bad || tv_init == tarval_bad) {
+ DB((dbg, LEVEL_4, " = OVERFLOW"));
+ return NULL;
+ }
+ return new_Const(tv);
+ }
+ return do_apply(e->code, NULL, rc, e->rc, get_irn_mode(rc));
+}
+
+/**
+ * Applies the operations represented by the LFTR edges to a
+ * region constant and returns the value.
+ * Return NULL if the transformation cannot be done safely without
+ * an Overflow.
+ *
+ * @param iv the IV node that starts the LFTR edge chain
+ * @param rc the region constant that should be translated
+ * @param env the IV environment
+ *
+ * @return the translated region constant or NULL
+ * if the translation was not possible
+ */
+static ir_node *applyEdges(ir_node *iv, ir_node *rc, iv_env *env) {
+ if (env->flags & osr_flag_lftr_with_ov_check) {
+ /* overflow can only be decided for Consts */
+ if (! is_counter_iv(iv, env)) {
+ DB((dbg, LEVEL_4, "not counter IV\n", rc));
+ return NULL;
+ }
+ if (! is_Const(rc)) {
+ DB((dbg, LEVEL_4, " = UNKNOWN (%+F)\n", rc));
+ return NULL;
+ }
+ DB((dbg, LEVEL_4, "%+F", get_Const_tarval(rc)));
+ }
+
+ for (; rc;) {
+ LFTR_edge *e = LFTR_find(iv, env);
+ if (e) {
+ rc = applyOneEdge(iv, rc, e, env);
+ iv = e->dst;
+ }
+ else
+ break;
+ }
+ DB((dbg, LEVEL_3, "\n"));
+ return rc;
+}
+
+/**
+ * Walker, finds Cmp(iv, rc) or Cmp(rc, iv)
+ * and tries to optimize them.
+ */
+static void do_lftr(ir_node *cmp, void *ctx) {
+ iv_env *env = ctx;
+ ir_node *left, *right, *liv, *riv;
+ ir_node *iv, *rc;
+ ir_node *nleft = NULL, *nright = NULL;
+
+ if (!is_Cmp(cmp))