Single use rule for chained node in pattern matcher


I’m trying to write a pattern for a truncating strict​*floating-point instruction that broadcast the result in the resulting register. However the pattern is not recognized by the pattern matcher because the any_fpround node is used more than once due to the broadcasting. I’m not quite sure I understand the reason behind that single use rule [1] (introduced by commit [2]) but all the uses are within the same pattern, as arguments of the same node even. Is there a way to relax the single use rule to allow uses in the same node? If not, how would you suggest I go about implementing pattern matching for this instruction?



Thanks in advance for your help. Best regards,


Single-use is an easy condition to check, easier than analyzing the consequences of folding a sub-DAG on a case by case basis.

In general, chain edges can appear. Consider this case (with arrows being chains):

A --> C
\ /

The chains are A->C, B->C, assume B has multiple uses, but A and C are single-use. If ABC gets matched to T, B must remain due to the extra uses, and we end up with T having a cyclic chain edges with B.

Hi Krzysztof,

Thanks for the explanation. How about adding the requirement that not only all those uses are by the same node but also that the node is within the sub-DAG being matched?

Best regards,


One problem with this approach is that it’s difficult to actually formulate the proper condition under which such a match would be legal and desirable. Consider this scenario: C is a node with a chain, and let U be the user with multiple uses of it. What you’re proposing would work for U(C, C) alone, but would fail if there was another user V(C, C). As a matter of fact, if would work at first when you only have U, but would fail for both once you add V.

My bigger concern is that even if such a satisfactory condition was created, it would potentially add a lot of complexity to the matcher (and the matcher generator). Right now the matcher is kind of like a state machine—it tries to match one node at a time, and it’s not really aware of what source pattern it came from. The matcher starts as a machine trying to match a sub-DAG rooted at a given node against all existing patterns: if the target defines 5000 patterns, the matcher will be ready to try all of them every time. For example, if you have a pattern (add x, (sub y, z)), first it will check the root: “is it add?”, and then move on to different things depending on whether it matched or not. If it did match, it’ll go and check the operand against “sub y, z”, otherwise it will go check the root of the next pattern, and so on. The sub-DAG at this point it everything under the root node, but a match may only cover a part of it (creating more roots for further matching).

Personally, I would be very hesitant to make such a change to the matcher/generator, and I’d try to solve this problem in a different way. If you think it’s still a good idea, go for it, but please be aware that there may be undesirable consequences that are far from obvious initially, but will need to be addressed.

Many thanks Krzysztof,

Your explanation is very clear and convincing. I’ll think of something else as you suggested.

Best regards,