Why does order of patterns matter while appending them to pattern list for MergeComposite pass

Troubleshooting
#1

Hi all , i was exploring MergeComposite pass and pattern language, when i discovered this strange behaviour.
Lets say , we have 2 patterns to be matched and fused if found:

  1. Dense + add
  2. Dense + add + relu.

After we create patterns for both of them using tvm pattern language , we append them to the pattern list and send this list to MergeComposite pass.
But it seems that the order of the patterns in the list plays a significant role in what pattern is getting recognised in case there are similar patterns in the list.

for ex :
If i create a pattern list = [dense_bias_pattern , dense_bias_relu_pattern] :
then i would never be able to match Dense+Bias_add+relu pattern , because as soon as pattern matcher figures out that dense_bias_pattern has been matched , then it stops matching the patterns altogether.
As a obvious solution , we need to append the patterns with higher depth first into the list (dense_bias_relu) , followed by patterns with smaller depth (dense_bias),.
Which i am not sure :
if this is the supposed way of creating a list of patterns , or is it a BUG?

#2

Hi yogeesh,

What you describe seems to be the intended behaviour. The documentation of the MergeComposite pass mentions this about the pattern_table argument:

The order of the patterns in the list will determine the order of priority in which they are matched.

#3

hi @yrjo thanks for bringing this point into light. solves the confusion i had.