/*
 * These methods traverse the entire IR tree. For equality of reference, use
 * Expr::same_as. If you're comparing non-CSE'd Exprs, use graph_equal or
 * graph_less_than, which is safe for nasty graphs of IR nodes.
 */

HALIDE_ALWAYS_INLINE
bool equal(const IRNode &a, const IRNode &b) {
    if (&a == &b) {
        return true;
    } else if (a.node_type != b.node_type) {
        return false;
    } else {
        return equal_impl(a, b);
    }
}

HALIDE_ALWAYS_INLINE
bool graph_equal(const IRNode &a, const IRNode &b) {
    if (&a == &b) {
        return true;
    } else if (a.node_type != b.node_type) {
        return false;
    } else {
        return equal_impl(a, b);
    }
}

/** Check if two possibly-undefined Stmts or Exprs are equal. Safe to call on
 * Exprs that haven't been passed to common_subexpression_elimination. */
HALIDE_ALWAYS_INLINE
bool graph_equal(const IRHandle &a, const IRHandle &b) {
    if (!a.defined()) {
        return !b.defined();
    } else if (!b.defined()) {
        return false;
    } else {
        return equal(*(a.get()), *(b.get()));
    }
}

#include "Halide.h"

using namespace Halide;

int main(int argc, char *argv[]) {
	Var x;
	Expr e1 = x;
	for (int i = 0; i < 100; i++) {
		e1 = e1 * e1;
	}
	Expr e2 = x;
	for (int i = 0; i < 100; i++) {
		e2 = e2 * e2;
	}
        // Uncomment the following two lines fixes the problem.
	// e1 = simplify(common_subexpression_elimination(e1));
	// e2 = simplify(common_subexpression_elimination(e2));
	Internal::graph_equal(e1, e2); // This line takes forever to compute.
        // Using graph_equal_impl also fixes the problem.
	// Internal::graph_equal_impl(e1, e2);
	return 0;
}