Skip to content

Internal::graph_equal does not call the right implementation #8610

Description

@BachiLi

Currently, the graph_equal implementations for comparing two expressions/statements behave exactly the same as equal:

https://github.com/halide/Halide/blob/main/src/IREquality.h#L69

/*
 * 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()));
    }
}

This makes graph_equal inefficient if the expressions are not CSE'd and/or simplified. The following code verifies the behavior:

#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;
}

Simply changing equal_impl and equal inside the graph_equal function calls into graph_equal_impl and equal_impl seems to solve the problem. A PR incoming -- this issue is here in case my fix is incorrect/incomplete...

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions