Josh Sharp via llvm-dev
2019-Feb-09 20:35 UTC
[llvm-dev] Question about pattern matching process
Hi, I'd like to understand the order in which patterns are searched during ISEL. In the example below, indices are searched in ascending order from 808 to 3305, then it goes back to 3259 and eventually it matches the wrong instruction. Why did go back from 3305 to 3259? In my XXXGenDAGISel.inc, I can see that the correct instruction is at index 3420 but it never got there. ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 3, continuing at 808 Skipped scope entry (due to false predicate) at index 809, continuing at 865 Skipped scope entry (due to false predicate) at index 867, continuing at 1091 Skipped scope entry (due to false predicate) at index 1093, continuing at 1578 Skipped scope entry (due to false predicate) at index 1579, continuing at 1605 Skipped scope entry (due to false predicate) at index 1606, continuing at 1668 Skipped scope entry (due to false predicate) at index 1670, continuing at 2369 Skipped scope entry (due to false predicate) at index 2370, continuing at 2397 Skipped scope entry (due to false predicate) at index 2398, continuing at 2451 Skipped scope entry (due to false predicate) at index 2452, continuing at 2562 Skipped scope entry (due to false predicate) at index 2563, continuing at 2641 Skipped scope entry (due to false predicate) at index 2642, continuing at 2669 Skipped scope entry (due to false predicate) at index 2670, continuing at 2696 Skipped scope entry (due to false predicate) at index 2697, continuing at 2779 Skipped scope entry (due to false predicate) at index 2780, continuing at 2835 Skipped scope entry (due to false predicate) at index 2836, continuing at 2891 Skipped scope entry (due to false predicate) at index 2892, continuing at 2947 Skipped scope entry (due to false predicate) at index 2948, continuing at 2999 Skipped scope entry (due to false predicate) at index 3000, continuing at 3032 Skipped scope entry (due to false predicate) at index 3033, continuing at 3053 Skipped scope entry (due to false predicate) at index 3054, continuing at 3085 Skipped scope entry (due to false predicate) at index 3086, continuing at 3114 Skipped scope entry (due to false predicate) at index 3115, continuing at 3171 Skipped scope entry (due to false predicate) at index 3172, continuing at 3201 Skipped scope entry (due to false predicate) at index 3202, continuing at 3253 Skipped scope entry (due to false predicate) at index 3261, continuing at 3272 Skipped scope entry (due to false predicate) at index 3273, continuing at 3284 Skipped scope entry (due to false predicate) at index 3285, continuing at 3305 Match failed at index 3259 Continuing at 3306 Match failed at index 3307 Continuing at 3327 Match failed at index 3328 Continuing at 3361 Morphed node: t17: i32 = MOVRR t17 ISEL: Match complete! Thanks. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190209/e46a9dea/attachment.html>
Craig Topper via llvm-dev
2019-Feb-09 22:06 UTC
[llvm-dev] Question about pattern matching process
I don't think it really went backwards. The "failed at index" uses a cached index not the current index the table is looking at. The index points to the last index that was processed by the opcode decoding switch. I suspect in your case 3259 is the start of an Opc_Scope. An Opc_Scope has multiple children. There's an optimization in Opc_Scope handler to walk each child and see if its even possibly feasible. This avoids pushing the scope stack only to immediately pop it again. This walking of the children and rejecting them prints the "Skipped Scope Entry" messages. Unfortunately, there's no message to indicate when the scope is actually pushed. I suspect in your case all of the children of the Opc_Scope at 3259 were rejected. This would be messages at 3261, 3273, and 3285. So the entire scope fails and prints the "Match failed at index 3259" since that's where the Opc_Scope it was processing started. 3305 should be the end marker for the scope. Then the stack pops which prints the continuing at 3306 message. Are you able to share your XXXGenDAGISel.inc? ~Craig On Sat, Feb 9, 2019 at 12:35 PM Josh Sharp via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Hi, > I'd like to understand the order in which patterns are searched during > ISEL. In the example below, indices are searched in ascending order from > 808 to 3305, then it goes back to 3259 and eventually it matches the wrong > instruction. Why did go back from 3305 to 3259? In my XXXGenDAGISel.inc, I > can see that the correct instruction is at index 3420 but it never got > there. > > ISEL: Starting pattern match > Skipped scope entry (due to false predicate) at index 3, continuing at > 808 > Skipped scope entry (due to false predicate) at index 809, continuing at > 865 > Skipped scope entry (due to false predicate) at index 867, continuing at > 1091 > Skipped scope entry (due to false predicate) at index 1093, continuing > at 1578 > Skipped scope entry (due to false predicate) at index 1579, continuing > at 1605 > Skipped scope entry (due to false predicate) at index 1606, continuing > at 1668 > Skipped scope entry (due to false predicate) at index 1670, continuing > at 2369 > Skipped scope entry (due to false predicate) at index 2370, continuing > at 2397 > Skipped scope entry (due to false predicate) at index 2398, continuing > at 2451 > Skipped scope entry (due to false predicate) at index 2452, continuing > at 2562 > Skipped scope entry (due to false predicate) at index 2563, continuing > at 2641 > Skipped scope entry (due to false predicate) at index 2642, continuing > at 2669 > Skipped scope entry (due to false predicate) at index 2670, continuing > at 2696 > Skipped scope entry (due to false predicate) at index 2697, continuing > at 2779 > Skipped scope entry (due to false predicate) at index 2780, continuing > at 2835 > Skipped scope entry (due to false predicate) at index 2836, continuing > at 2891 > Skipped scope entry (due to false predicate) at index 2892, continuing > at 2947 > Skipped scope entry (due to false predicate) at index 2948, continuing > at 2999 > Skipped scope entry (due to false predicate) at index 3000, continuing > at 3032 > Skipped scope entry (due to false predicate) at index 3033, continuing > at 3053 > Skipped scope entry (due to false predicate) at index 3054, continuing > at 3085 > Skipped scope entry (due to false predicate) at index 3086, continuing > at 3114 > Skipped scope entry (due to false predicate) at index 3115, continuing > at 3171 > Skipped scope entry (due to false predicate) at index 3172, continuing > at 3201 > Skipped scope entry (due to false predicate) at index 3202, continuing > at 3253 > Skipped scope entry (due to false predicate) at index 3261, continuing > at 3272 > Skipped scope entry (due to false predicate) at index 3273, continuing > at 3284 > Skipped scope entry (due to false predicate) at index 3285, continuing > at 3305 > Match failed at index 3259 > Continuing at 3306 > Match failed at index 3307 > Continuing at 3327 > Match failed at index 3328 > Continuing at 3361 > Morphed node: t17: i32 = MOVRR t17 > ISEL: Match complete! > > > Thanks. > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190209/82ccc433/attachment.html>
Josh Sharp via llvm-dev
2019-Feb-09 23:18 UTC
[llvm-dev] Question about pattern matching process
Thanks, Craig. Unfortunately I can't. But I tried moving the definition of MOVRR to the bottom of the XXXInstrInfo.td file and it worked. Now the correct instruction comes first in array in XXXGenDAGISel.inc and it gets properly selected during ISEL. Is this the right way to solve this kind of problem? Josh ________________________________ From: Craig Topper <craig.topper at gmail.com> Sent: Saturday, February 9, 2019 2:06 PM To: Josh Sharp Cc: via llvm-dev Subject: Re: [llvm-dev] Question about pattern matching process I don't think it really went backwards. The "failed at index" uses a cached index not the current index the table is looking at. The index points to the last index that was processed by the opcode decoding switch. I suspect in your case 3259 is the start of an Opc_Scope. An Opc_Scope has multiple children. There's an optimization in Opc_Scope handler to walk each child and see if its even possibly feasible. This avoids pushing the scope stack only to immediately pop it again. This walking of the children and rejecting them prints the "Skipped Scope Entry" messages. Unfortunately, there's no message to indicate when the scope is actually pushed. I suspect in your case all of the children of the Opc_Scope at 3259 were rejected. This would be messages at 3261, 3273, and 3285. So the entire scope fails and prints the "Match failed at index 3259" since that's where the Opc_Scope it was processing started. 3305 should be the end marker for the scope. Then the stack pops which prints the continuing at 3306 message. Are you able to share your XXXGenDAGISel.inc? ~Craig On Sat, Feb 9, 2019 at 12:35 PM Josh Sharp via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote: Hi, I'd like to understand the order in which patterns are searched during ISEL. In the example below, indices are searched in ascending order from 808 to 3305, then it goes back to 3259 and eventually it matches the wrong instruction. Why did go back from 3305 to 3259? In my XXXGenDAGISel.inc, I can see that the correct instruction is at index 3420 but it never got there. ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 3, continuing at 808 Skipped scope entry (due to false predicate) at index 809, continuing at 865 Skipped scope entry (due to false predicate) at index 867, continuing at 1091 Skipped scope entry (due to false predicate) at index 1093, continuing at 1578 Skipped scope entry (due to false predicate) at index 1579, continuing at 1605 Skipped scope entry (due to false predicate) at index 1606, continuing at 1668 Skipped scope entry (due to false predicate) at index 1670, continuing at 2369 Skipped scope entry (due to false predicate) at index 2370, continuing at 2397 Skipped scope entry (due to false predicate) at index 2398, continuing at 2451 Skipped scope entry (due to false predicate) at index 2452, continuing at 2562 Skipped scope entry (due to false predicate) at index 2563, continuing at 2641 Skipped scope entry (due to false predicate) at index 2642, continuing at 2669 Skipped scope entry (due to false predicate) at index 2670, continuing at 2696 Skipped scope entry (due to false predicate) at index 2697, continuing at 2779 Skipped scope entry (due to false predicate) at index 2780, continuing at 2835 Skipped scope entry (due to false predicate) at index 2836, continuing at 2891 Skipped scope entry (due to false predicate) at index 2892, continuing at 2947 Skipped scope entry (due to false predicate) at index 2948, continuing at 2999 Skipped scope entry (due to false predicate) at index 3000, continuing at 3032 Skipped scope entry (due to false predicate) at index 3033, continuing at 3053 Skipped scope entry (due to false predicate) at index 3054, continuing at 3085 Skipped scope entry (due to false predicate) at index 3086, continuing at 3114 Skipped scope entry (due to false predicate) at index 3115, continuing at 3171 Skipped scope entry (due to false predicate) at index 3172, continuing at 3201 Skipped scope entry (due to false predicate) at index 3202, continuing at 3253 Skipped scope entry (due to false predicate) at index 3261, continuing at 3272 Skipped scope entry (due to false predicate) at index 3273, continuing at 3284 Skipped scope entry (due to false predicate) at index 3285, continuing at 3305 Match failed at index 3259 Continuing at 3306 Match failed at index 3307 Continuing at 3327 Match failed at index 3328 Continuing at 3361 Morphed node: t17: i32 = MOVRR t17 ISEL: Match complete! Thanks. _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190209/e60f673b/attachment.html>