Fix exponential explosion in gtTreeHasSideEffects.
authorEugene Rozenfeld <erozen@microsoft.com>
Thu, 31 Mar 2016 22:35:34 +0000 (15:35 -0700)
committerEugene Rozenfeld <erozen@microsoft.com>
Fri, 1 Apr 2016 00:04:43 +0000 (17:04 -0700)
commitf8c8dc2b6df8ebdfede6302b9b08d4d1ac82bae8
treeae9ee3ea0772e092cbfd32e7998efc8d48206031
parent8ac11d8e0680092d1f9aafc6e57c1d9eb0982738
Fix exponential explosion in gtTreeHasSideEffects.

gtTreeHasSideEffects has special code to deal with helper calls.
If the helper satisfies certain properties and its arguments don't have relevant
side effects, than the tree corresponding to the helper call is considered not to have
side effects. The bug was that both gtTreeHasSideEffects and gtNodeHasSideEffects
(called by gtTreeHasSideEffects and calling gtTreeHasSideEffects) had code to check
the helper arguments for side effects. That made the algorithm exponential (2^n)
for a tree like the one below.
Because of that ngen would take days to compile the method with such trees.
The fix is to remove the argument checking code from gtTreeHasSideEffects since it always
calls gtNodeHasSideEffects. Compilation time goes back to milliseconds or seconds.

I ran full desktop testing and verified no SuperPMI diffs.

No measurable impact on cqNGenTP.

Fixes #3768.

N139 (255,169)              [000064] --CXG-------             *  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $179
N137 (255,163)              [000062] --CXG------- arg0 in rcx \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $177
N135 (255,157)              [000060] --CXG------- arg0 in rcx    \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $175
N133 (255,151)              [000058] --CXG------- arg0 in rcx       \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $173
N131 (255,145)              [000056] --CXG------- arg0 in rcx          \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $171
N129 (255,139)              [000054] --CXG------- arg0 in rcx             \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $16f
N127 (255,133)              [000052] --CXG------- arg0 in rcx                \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $16d
N125 (255,127)              [000050] --CXG------- arg0 in rcx                   \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $16b
N123 (255,121)              [000048] --CXG------- arg0 in rcx                      \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $169
N121 (255,115)              [000046] --CXG------- arg0 in rcx                         \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $167
N119 (253,109)              [000044] --CXG------- arg0 in rcx                            \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $165
N117 (239,103)              [000042] --CXG------- arg0 in rcx                               \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $163
N115 (225, 97)              [000040] --CXG------- arg0 in rcx                                  \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $161
N113 (211, 91)              [000038] --CXG------- arg0 in rcx                                     \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $15f
N111 (197, 85)              [000036] --CXG------- arg0 in rcx                                        \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $15d
N109 (183, 79)              [000034] --CXG------- arg0 in rcx                                           \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $15b
N107 (169, 73)              [000032] --CXG------- arg0 in rcx                                              \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $159
N105 (155, 67)              [000030] --CXG------- arg0 in rcx                                                 \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $157
N103 (141, 61)              [000028] --CXG------- arg0 in rcx                                                    \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $155
N101 (127, 55)              [000026] --CXG------- arg0 in rcx                                                       \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $153
N099 (113, 49)              [000024] --CXG------- arg0 in rcx                                                          \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $151
N097 ( 99, 43)              [000022] --CXG------- arg0 in rcx                                                             \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $14f
N095 ( 85, 37)              [000020] --CXG------- arg0 in rcx                                                                \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $14d
N093 ( 71, 31)              [000018] --CXG------- arg0 in rcx                                                                   \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $14b
N091 ( 57, 25)              [000016] --CXG------- arg0 in rcx                                                                      \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $149
N089 ( 43, 19)              [000014] --CXG------- arg0 in rcx                                                                         \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $147
N087 ( 29, 13)              [000012] --CXG------- arg0 in rcx                                                                            \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $145
N085 ( 15,  7)              [000010] --CXG------- arg0 in rcx                                                                               \--*  call help ref    HELPER.CORINFO_HELP_READYTORUN_CHKCAST $143
N083 (  1,  1)              [000008] ------------ arg0 in rcx                                                                                  \--*  lclVar    ref    V00 tmp0         u:2 (last use) $140
src/jit/gentree.cpp