Structural equal doesn't catch different orders of ANF

Questions
1

See the following runnable example:

import tvm
from tvm import relay

from tvm.relay.scope_builder import ScopeBuilder

shape = (5, 5)

sb1 = ScopeBuilder()
p0 = relay.var("p0", shape=shape)
p1 = relay.var("p1", shape=shape)
a0 = sb1.let("a0", relay.add(p0, relay.const(1)))
a1 = sb1.let("a1", relay.add(p1, relay.const(1)))
a2 = sb1.let("a2", relay.add(a0, a1))
sb1.ret(a2)
func1 = relay.Function([p0, p1], sb1.get())
print(func1)

sb2 = ScopeBuilder()
p0 = relay.var("p0", shape=shape)
p1 = relay.var("p1", shape=shape)
a1 = sb2.let("a1", relay.add(p1, relay.const(1)))
a0 = sb2.let("a0", relay.add(p0, relay.const(1)))
a2 = sb2.let("a2", relay.add(a0, a1))
sb2.ret(a2)
func2 = relay.Function([p0, p1], sb2.get())
print(func2)

# Should fail but didn't
tvm.ir.structural_equal(func1, func2)

I guess this is because structural equal recursively traverses the node arguments from the graph output for whatever dataflow graph or A-Normal form. It this an expected behavior or should we somehow fix structural equal to let it catch this difference?

@tqchen @jroesch @zhiics @yzhliu @junrushao

1 Like
2

Hi @comaniac ,

What happens if you try with different consts for the additions (i.e. to make the ordering change obvious) ? Would it still pass ?

3

You mean add(a, b) and add(b, a)? Yes it will still pass. I also tried to add one more parameter and even changed the constant value, but surprisingly it sill passed.

import tvm
from tvm import relay

from tvm.relay.scope_builder import ScopeBuilder

shape = (5, 5)

sb1 = ScopeBuilder()
p0 = relay.var("p0", shape=shape)
p1 = relay.var("p1", shape=shape)
p2 = relay.var("p2", shape=shape)
a0 = sb1.let("a0", relay.add(p0, relay.const(1)))
a1 = sb1.let("a1", relay.add(p1, p2))
a2 = sb1.let("a2", relay.add(a0, a1))
sb1.ret(a2)
func1 = relay.Function([p0, p1, p2], sb1.get())
print(func1)

sb2 = ScopeBuilder()
p0 = relay.var("p0", shape=shape)
p1 = relay.var("p1", shape=shape)
p2 = relay.var("p2", shape=shape)
a1 = sb2.let("a1", relay.add(p2, p1))
a0 = sb2.let("a0", relay.add(relay.const(2), p0))
a2 = sb2.let("a2", relay.add(a1, a0))
sb2.ret(a2)
func2 = relay.Function([p0, p1, p2], sb2.get())
print(func2)

# Should fail
tvm.ir.structural_equal(func1, func2)
print("passed")

Output

fn (%p0: Tensor[(5, 5), float32], %p1: Tensor[(5, 5), float32], %p2: Tensor[(5, 5), float32]) {
  let %a0 = add(%p0, 1);
  let %a1 = add(%p1, %p2);
  let %a2 = add(%a0, %a1);
  %a2
}
fn (%p0: Tensor[(5, 5), float32], %p1: Tensor[(5, 5), float32], %p2: Tensor[(5, 5), float32]) {
  let %a1 = add(%p2, %p1);
  let %a0 = add(2, %p0);
  let %a2 = add(%a1, %a0);
  %a2
}
passed
4

Hmm…I also tried to change the shape of one parameter but still pass.

def @main(%p0: Tensor[(5, 5), float32], %p1: Tensor[(5, 5), float32], %p2: Tensor[(1, 5), float32]) -> Tensor[(5, 5), float32] {
  let %a0: Tensor[(5, 5), float32] = add(%p0, 1f /* ty=float32 */) /* ty=Tensor[(5, 5), float32] */;
  let %a1: Tensor[(5, 5), float32] = add(%p1, %p2) /* ty=Tensor[(5, 5), float32] */;
  let %a2: Tensor[(5, 5), float32] = add(%a0, %a1) /* ty=Tensor[(5, 5), float32] */;
  %a2
}

def @main(%p0: Tensor[(5, 5), float32], %p1: Tensor[(5, 5), float32], %p2: Tensor[(1, 5), float32]) -> Tensor[(5, 5), float32] {
  let %a1: Tensor[(5, 5), float32] = add(%p2, %p1) /* ty=Tensor[(5, 5), float32] */;
  let %a0: Tensor[(5, 5), float32] = add(2f /* ty=float32 */, %p0) /* ty=Tensor[(5, 5), float32] */;
  let %a2: Tensor[(5, 5), float32] = add(%a1, %a0) /* ty=Tensor[(5, 5), float32] */;
  %a2
}

passed
5

I see.

Yes I was trying disambiguate between free-var swaps and ordering determined by ANF. I think it is made clear structural_equal checks ignore the let bindings. Is that what you are thinking as well ?

6

I’m not sure if it just ignores let bindings or it doesn’t care the order (whatever the binding order or argument order). I have an impression that structural equal doesn’t care the constant value tho.

7

Yeah this looks wrong to me, will check on it tomorrow and respond/have some one else dig into it.

1 Like
8

I’ll try to get to this today.

1 Like
9

No luck reproing Cody, sent you https://github.com/apache/tvm/pull/9745 for unit test.

1 Like
10

Thanks @mbs-octoml for the time! It’s weird that you cannot reproduce it. Maybe there’s something wrong on my side…I’ll double check again later.

11

Maybe CI will prove me wrong :slight_smile: