GVN (MemDep): Unbounded recursion in getNonLocalPointerDepFromBB #165004
Description
Example IR: https://gist.github.com/danilaml/2c0fb2da1f427ca4a6f7e64fbdbb50f6
If I trace the recursion I get
getNonLocalPointerDepFromBB: false.bb200
getNonLocalPointerDepFromBB: false.bb199
getNonLocalPointerDepFromBB: false.bb198
getNonLocalPointerDepFromBB: false.bb197
getNonLocalPointerDepFromBB: false.bb196
getNonLocalPointerDepFromBB: false.bb195
getNonLocalPointerDepFromBB: false.bb194
getNonLocalPointerDepFromBB: false.bb193
getNonLocalPointerDepFromBB: false.bb192
getNonLocalPointerDepFromBB: false.bb191
getNonLocalPointerDepFromBB: false.bb190
getNonLocalPointerDepFromBB: false.bb189
getNonLocalPointerDepFromBB: false.bb188
getNonLocalPointerDepFromBB: false.bb187
getNonLocalPointerDepFromBB: false.bb186
getNonLocalPointerDepFromBB: false.bb185
getNonLocalPointerDepFromBB: false.bb184
getNonLocalPointerDepFromBB: false.bb183
getNonLocalPointerDepFromBB: false.bb182
getNonLocalPointerDepFromBB: false.bb181
getNonLocalPointerDepFromBB: false.bb180
getNonLocalPointerDepFromBB: false.bb179
getNonLocalPointerDepFromBB: false.bb178
getNonLocalPointerDepFromBB: false.bb177
getNonLocalPointerDepFromBB: false.bb176
getNonLocalPointerDepFromBB: false.bb175
getNonLocalPointerDepFromBB: false.bb174
getNonLocalPointerDepFromBB: false.bb173
getNonLocalPointerDepFromBB: false.bb172
getNonLocalPointerDepFromBB: false.bb171
getNonLocalPointerDepFromBB: false.bb170
getNonLocalPointerDepFromBB: false.bb169
getNonLocalPointerDepFromBB: false.bb168
getNonLocalPointerDepFromBB: false.bb167
getNonLocalPointerDepFromBB: false.bb166
getNonLocalPointerDepFromBB: false.bb165
getNonLocalPointerDepFromBB: false.bb164
getNonLocalPointerDepFromBB: false.bb163
getNonLocalPointerDepFromBB: false.bb162
getNonLocalPointerDepFromBB: false.bb161
getNonLocalPointerDepFromBB: false.bb160
getNonLocalPointerDepFromBB: false.bb159
getNonLocalPointerDepFromBB: false.bb158
getNonLocalPointerDepFromBB: false.bb157
getNonLocalPointerDepFromBB: false.bb156
getNonLocalPointerDepFromBB: false.bb155
getNonLocalPointerDepFromBB: false.bb154
getNonLocalPointerDepFromBB: false.bb153
getNonLocalPointerDepFromBB: false.bb152
getNonLocalPointerDepFromBB: false.bb151
getNonLocalPointerDepFromBB: false.bb150
getNonLocalPointerDepFromBB: false.bb149
getNonLocalPointerDepFromBB: false.bb148
getNonLocalPointerDepFromBB: false.bb147
getNonLocalPointerDepFromBB: false.bb146
getNonLocalPointerDepFromBB: false.bb145
getNonLocalPointerDepFromBB: false.bb144
getNonLocalPointerDepFromBB: false.bb143
getNonLocalPointerDepFromBB: false.bb142
getNonLocalPointerDepFromBB: false.bb141
getNonLocalPointerDepFromBB: false.bb140
getNonLocalPointerDepFromBB: false.bb139
getNonLocalPointerDepFromBB: false.bb138
getNonLocalPointerDepFromBB: false.bb137
getNonLocalPointerDepFromBB: false.bb136
getNonLocalPointerDepFromBB: false.bb135
getNonLocalPointerDepFromBB: false.bb134
getNonLocalPointerDepFromBB: false.bb133
getNonLocalPointerDepFromBB: false.bb132
getNonLocalPointerDepFromBB: false.bb131
getNonLocalPointerDepFromBB: false.bb130
getNonLocalPointerDepFromBB: false.bb129
getNonLocalPointerDepFromBB: false.bb128
getNonLocalPointerDepFromBB: false.bb127
getNonLocalPointerDepFromBB: false.bb126
getNonLocalPointerDepFromBB: false.bb125
getNonLocalPointerDepFromBB: false.bb124
getNonLocalPointerDepFromBB: false.bb123
getNonLocalPointerDepFromBB: false.bb122
getNonLocalPointerDepFromBB: false.bb121
getNonLocalPointerDepFromBB: false.bb120
getNonLocalPointerDepFromBB: false.bb119
getNonLocalPointerDepFromBB: false.bb118
getNonLocalPointerDepFromBB: false.bb117
getNonLocalPointerDepFromBB: false.bb116
getNonLocalPointerDepFromBB: false.bb115
getNonLocalPointerDepFromBB: false.bb114
getNonLocalPointerDepFromBB: false.bb113
getNonLocalPointerDepFromBB: false.bb112
getNonLocalPointerDepFromBB: false.bb111
getNonLocalPointerDepFromBB: false.bb110
getNonLocalPointerDepFromBB: false.bb109
getNonLocalPointerDepFromBB: false.bb108
getNonLocalPointerDepFromBB: false.bb107
getNonLocalPointerDepFromBB: false.bb106
getNonLocalPointerDepFromBB: false.bb105
getNonLocalPointerDepFromBB: false.bb104
getNonLocalPointerDepFromBB: false.bb103
getNonLocalPointerDepFromBB: false.bb102
getNonLocalPointerDepFromBB: false.bb101
getNonLocalPointerDepFromBB: false.bb100
getNonLocalPointerDepFromBB: false.bb99
getNonLocalPointerDepFromBB: false.bb98
getNonLocalPointerDepFromBB: false.bb97
getNonLocalPointerDepFromBB: false.bb96
getNonLocalPointerDepFromBB: false.bb95
getNonLocalPointerDepFromBB: false.bb94
getNonLocalPointerDepFromBB: false.bb93
getNonLocalPointerDepFromBB: false.bb92
getNonLocalPointerDepFromBB: false.bb91
getNonLocalPointerDepFromBB: false.bb90
getNonLocalPointerDepFromBB: false.bb89
getNonLocalPointerDepFromBB: false.bb88
getNonLocalPointerDepFromBB: false.bb87
getNonLocalPointerDepFromBB: false.bb86
getNonLocalPointerDepFromBB: false.bb85
getNonLocalPointerDepFromBB: false.bb84
getNonLocalPointerDepFromBB: false.bb83
getNonLocalPointerDepFromBB: false.bb82
getNonLocalPointerDepFromBB: false.bb81
getNonLocalPointerDepFromBB: false.bb80
getNonLocalPointerDepFromBB: false.bb79
getNonLocalPointerDepFromBB: false.bb78
getNonLocalPointerDepFromBB: false.bb77
getNonLocalPointerDepFromBB: false.bb76
getNonLocalPointerDepFromBB: false.bb75
getNonLocalPointerDepFromBB: false.bb74
getNonLocalPointerDepFromBB: false.bb73
getNonLocalPointerDepFromBB: false.bb72
getNonLocalPointerDepFromBB: false.bb71
getNonLocalPointerDepFromBB: false.bb70
getNonLocalPointerDepFromBB: false.bb69
getNonLocalPointerDepFromBB: false.bb68
getNonLocalPointerDepFromBB: false.bb67
getNonLocalPointerDepFromBB: false.bb66
getNonLocalPointerDepFromBB: false.bb65
getNonLocalPointerDepFromBB: false.bb64
getNonLocalPointerDepFromBB: false.bb63
getNonLocalPointerDepFromBB: false.bb62
getNonLocalPointerDepFromBB: false.bb61
getNonLocalPointerDepFromBB: false.bb60
getNonLocalPointerDepFromBB: false.bb59
getNonLocalPointerDepFromBB: false.bb58
getNonLocalPointerDepFromBB: false.bb57
getNonLocalPointerDepFromBB: false.bb56
getNonLocalPointerDepFromBB: false.bb55
getNonLocalPointerDepFromBB: false.bb54
getNonLocalPointerDepFromBB: false.bb53
getNonLocalPointerDepFromBB: false.bb52
getNonLocalPointerDepFromBB: false.bb51
getNonLocalPointerDepFromBB: false.bb50
getNonLocalPointerDepFromBB: false.bb49
getNonLocalPointerDepFromBB: false.bb48
getNonLocalPointerDepFromBB: false.bb47
getNonLocalPointerDepFromBB: false.bb46
getNonLocalPointerDepFromBB: false.bb45
getNonLocalPointerDepFromBB: false.bb44
getNonLocalPointerDepFromBB: false.bb43
getNonLocalPointerDepFromBB: false.bb42
getNonLocalPointerDepFromBB: false.bb41
getNonLocalPointerDepFromBB: false.bb40
getNonLocalPointerDepFromBB: false.bb39
getNonLocalPointerDepFromBB: false.bb38
getNonLocalPointerDepFromBB: false.bb37
getNonLocalPointerDepFromBB: false.bb36
getNonLocalPointerDepFromBB: false.bb35
getNonLocalPointerDepFromBB: false.bb34
getNonLocalPointerDepFromBB: false.bb33
getNonLocalPointerDepFromBB: false.bb32
getNonLocalPointerDepFromBB: false.bb31
getNonLocalPointerDepFromBB: false.bb30
getNonLocalPointerDepFromBB: false.bb29
getNonLocalPointerDepFromBB: false.bb28
getNonLocalPointerDepFromBB: false.bb27
getNonLocalPointerDepFromBB: false.bb26
getNonLocalPointerDepFromBB: false.bb25
getNonLocalPointerDepFromBB: false.bb24
getNonLocalPointerDepFromBB: false.bb23
getNonLocalPointerDepFromBB: false.bb22
getNonLocalPointerDepFromBB: false.bb21
getNonLocalPointerDepFromBB: false.bb20
getNonLocalPointerDepFromBB: false.bb19
getNonLocalPointerDepFromBB: false.bb18
getNonLocalPointerDepFromBB: false.bb17
getNonLocalPointerDepFromBB: false.bb16
getNonLocalPointerDepFromBB: false.bb15
getNonLocalPointerDepFromBB: false.bb14
getNonLocalPointerDepFromBB: false.bb13
getNonLocalPointerDepFromBB: false.bb12
getNonLocalPointerDepFromBB: false.bb11
getNonLocalPointerDepFromBB: false.bb10
getNonLocalPointerDepFromBB: false.bb9
getNonLocalPointerDepFromBB: false.bb8
getNonLocalPointerDepFromBB: false.bb7
getNonLocalPointerDepFromBB: false.bb6
getNonLocalPointerDepFromBB: false.bb5
getNonLocalPointerDepFromBB: false.bb4
getNonLocalPointerDepFromBB: false.bb3
getNonLocalPointerDepFromBB: false.bb2
getNonLocalPointerDepFromBB: false.bb1
getNonLocalPointerDepFromBB: false.bb0
getNonLocalPointerDepFromBB: true.bb1
getNonLocalPointerDepFromBB: true.bb2
getNonLocalPointerDepFromBB: true.bb3
getNonLocalPointerDepFromBB: true.bb4
getNonLocalPointerDepFromBB: true.bb5
getNonLocalPointerDepFromBB: true.bb6
getNonLocalPointerDepFromBB: true.bb7
getNonLocalPointerDepFromBB: true.bb8
getNonLocalPointerDepFromBB: true.bb9
getNonLocalPointerDepFromBB: true.bb10
getNonLocalPointerDepFromBB: true.bb11
getNonLocalPointerDepFromBB: true.bb12
getNonLocalPointerDepFromBB: true.bb13
getNonLocalPointerDepFromBB: true.bb14
getNonLocalPointerDepFromBB: true.bb15
getNonLocalPointerDepFromBB: true.bb16
getNonLocalPointerDepFromBB: true.bb17
getNonLocalPointerDepFromBB: true.bb18
getNonLocalPointerDepFromBB: true.bb19
getNonLocalPointerDepFromBB: true.bb20
getNonLocalPointerDepFromBB: true.bb21
getNonLocalPointerDepFromBB: true.bb22
getNonLocalPointerDepFromBB: true.bb23
getNonLocalPointerDepFromBB: true.bb24
getNonLocalPointerDepFromBB: true.bb25
getNonLocalPointerDepFromBB: true.bb26
getNonLocalPointerDepFromBB: true.bb27
getNonLocalPointerDepFromBB: true.bb28
getNonLocalPointerDepFromBB: true.bb29
getNonLocalPointerDepFromBB: true.bb30
getNonLocalPointerDepFromBB: true.bb31
getNonLocalPointerDepFromBB: true.bb32
getNonLocalPointerDepFromBB: true.bb33
getNonLocalPointerDepFromBB: true.bb34
getNonLocalPointerDepFromBB: true.bb35
getNonLocalPointerDepFromBB: true.bb36
getNonLocalPointerDepFromBB: true.bb37
getNonLocalPointerDepFromBB: true.bb38
getNonLocalPointerDepFromBB: true.bb39
getNonLocalPointerDepFromBB: true.bb40
getNonLocalPointerDepFromBB: true.bb41
getNonLocalPointerDepFromBB: true.bb42
getNonLocalPointerDepFromBB: true.bb43
getNonLocalPointerDepFromBB: true.bb44
getNonLocalPointerDepFromBB: true.bb45
getNonLocalPointerDepFromBB: true.bb46
getNonLocalPointerDepFromBB: true.bb47
getNonLocalPointerDepFromBB: true.bb48
getNonLocalPointerDepFromBB: true.bb49
getNonLocalPointerDepFromBB: true.bb50
getNonLocalPointerDepFromBB: true.bb51
getNonLocalPointerDepFromBB: true.bb52
getNonLocalPointerDepFromBB: true.bb53
getNonLocalPointerDepFromBB: true.bb54
getNonLocalPointerDepFromBB: true.bb55
getNonLocalPointerDepFromBB: true.bb56
getNonLocalPointerDepFromBB: true.bb57
getNonLocalPointerDepFromBB: true.bb58
getNonLocalPointerDepFromBB: true.bb59
getNonLocalPointerDepFromBB: true.bb60
getNonLocalPointerDepFromBB: true.bb61
getNonLocalPointerDepFromBB: true.bb62
getNonLocalPointerDepFromBB: true.bb63
getNonLocalPointerDepFromBB: true.bb64
getNonLocalPointerDepFromBB: true.bb65
getNonLocalPointerDepFromBB: true.bb66
getNonLocalPointerDepFromBB: true.bb67
getNonLocalPointerDepFromBB: true.bb68
getNonLocalPointerDepFromBB: true.bb69
getNonLocalPointerDepFromBB: true.bb70
getNonLocalPointerDepFromBB: true.bb71
getNonLocalPointerDepFromBB: true.bb72
getNonLocalPointerDepFromBB: true.bb73
getNonLocalPointerDepFromBB: true.bb74
getNonLocalPointerDepFromBB: true.bb75
getNonLocalPointerDepFromBB: true.bb76
getNonLocalPointerDepFromBB: true.bb77
getNonLocalPointerDepFromBB: true.bb78
getNonLocalPointerDepFromBB: true.bb79
getNonLocalPointerDepFromBB: true.bb80
getNonLocalPointerDepFromBB: true.bb81
getNonLocalPointerDepFromBB: true.bb82
getNonLocalPointerDepFromBB: true.bb83
getNonLocalPointerDepFromBB: true.bb84
getNonLocalPointerDepFromBB: true.bb85
getNonLocalPointerDepFromBB: true.bb86
getNonLocalPointerDepFromBB: true.bb87
getNonLocalPointerDepFromBB: true.bb88
getNonLocalPointerDepFromBB: true.bb89
getNonLocalPointerDepFromBB: true.bb90
getNonLocalPointerDepFromBB: true.bb91
getNonLocalPointerDepFromBB: true.bb92
getNonLocalPointerDepFromBB: true.bb93
getNonLocalPointerDepFromBB: true.bb94
getNonLocalPointerDepFromBB: true.bb95
getNonLocalPointerDepFromBB: true.bb96
getNonLocalPointerDepFromBB: true.bb97
getNonLocalPointerDepFromBB: true.bb98
getNonLocalPointerDepFromBB: true.bb99
getNonLocalPointerDepFromBB: true.bb100
getNonLocalPointerDepFromBB: true.bb101
getNonLocalPointerDepFromBB: true.bb102
getNonLocalPointerDepFromBB: true.bb103
getNonLocalPointerDepFromBB: true.bb104
getNonLocalPointerDepFromBB: true.bb105
getNonLocalPointerDepFromBB: true.bb106
getNonLocalPointerDepFromBB: true.bb107
getNonLocalPointerDepFromBB: true.bb108
getNonLocalPointerDepFromBB: true.bb109
getNonLocalPointerDepFromBB: true.bb110
getNonLocalPointerDepFromBB: true.bb111
getNonLocalPointerDepFromBB: true.bb112
getNonLocalPointerDepFromBB: true.bb113
getNonLocalPointerDepFromBB: true.bb114
getNonLocalPointerDepFromBB: true.bb115
getNonLocalPointerDepFromBB: true.bb116
getNonLocalPointerDepFromBB: true.bb117
getNonLocalPointerDepFromBB: true.bb118
getNonLocalPointerDepFromBB: true.bb119
getNonLocalPointerDepFromBB: true.bb120
getNonLocalPointerDepFromBB: true.bb121
getNonLocalPointerDepFromBB: true.bb122
getNonLocalPointerDepFromBB: true.bb123
getNonLocalPointerDepFromBB: true.bb124
getNonLocalPointerDepFromBB: true.bb125
getNonLocalPointerDepFromBB: true.bb126
getNonLocalPointerDepFromBB: true.bb127
getNonLocalPointerDepFromBB: true.bb128
getNonLocalPointerDepFromBB: true.bb129
getNonLocalPointerDepFromBB: true.bb130
getNonLocalPointerDepFromBB: true.bb131
getNonLocalPointerDepFromBB: true.bb132
getNonLocalPointerDepFromBB: true.bb133
getNonLocalPointerDepFromBB: true.bb134
getNonLocalPointerDepFromBB: true.bb135
getNonLocalPointerDepFromBB: true.bb136
getNonLocalPointerDepFromBB: true.bb137
getNonLocalPointerDepFromBB: true.bb138
getNonLocalPointerDepFromBB: true.bb139
getNonLocalPointerDepFromBB: true.bb140
getNonLocalPointerDepFromBB: true.bb141
getNonLocalPointerDepFromBB: true.bb142
getNonLocalPointerDepFromBB: true.bb143
getNonLocalPointerDepFromBB: true.bb144
getNonLocalPointerDepFromBB: true.bb145
getNonLocalPointerDepFromBB: true.bb146
getNonLocalPointerDepFromBB: true.bb147
getNonLocalPointerDepFromBB: true.bb148
getNonLocalPointerDepFromBB: true.bb149
getNonLocalPointerDepFromBB: true.bb150
getNonLocalPointerDepFromBB: true.bb151
getNonLocalPointerDepFromBB: true.bb152
getNonLocalPointerDepFromBB: true.bb153
getNonLocalPointerDepFromBB: true.bb154
getNonLocalPointerDepFromBB: true.bb155
getNonLocalPointerDepFromBB: true.bb156
getNonLocalPointerDepFromBB: true.bb157
getNonLocalPointerDepFromBB: true.bb158
getNonLocalPointerDepFromBB: true.bb159
getNonLocalPointerDepFromBB: true.bb160
getNonLocalPointerDepFromBB: true.bb161
getNonLocalPointerDepFromBB: true.bb162
getNonLocalPointerDepFromBB: true.bb163
getNonLocalPointerDepFromBB: true.bb164
getNonLocalPointerDepFromBB: true.bb165
getNonLocalPointerDepFromBB: true.bb166
getNonLocalPointerDepFromBB: true.bb167
getNonLocalPointerDepFromBB: true.bb168
getNonLocalPointerDepFromBB: true.bb169
getNonLocalPointerDepFromBB: true.bb170
getNonLocalPointerDepFromBB: true.bb171
getNonLocalPointerDepFromBB: true.bb172
getNonLocalPointerDepFromBB: true.bb173
getNonLocalPointerDepFromBB: true.bb174
getNonLocalPointerDepFromBB: true.bb175
getNonLocalPointerDepFromBB: true.bb176
getNonLocalPointerDepFromBB: true.bb177
getNonLocalPointerDepFromBB: true.bb178
getNonLocalPointerDepFromBB: true.bb179
getNonLocalPointerDepFromBB: true.bb180
getNonLocalPointerDepFromBB: true.bb181
getNonLocalPointerDepFromBB: true.bb182
getNonLocalPointerDepFromBB: true.bb183
getNonLocalPointerDepFromBB: true.bb184
getNonLocalPointerDepFromBB: true.bb185
getNonLocalPointerDepFromBB: true.bb186
getNonLocalPointerDepFromBB: true.bb187
getNonLocalPointerDepFromBB: true.bb188
getNonLocalPointerDepFromBB: true.bb189
getNonLocalPointerDepFromBB: true.bb190
getNonLocalPointerDepFromBB: true.bb191
getNonLocalPointerDepFromBB: true.bb192
getNonLocalPointerDepFromBB: true.bb193
getNonLocalPointerDepFromBB: true.bb194
getNonLocalPointerDepFromBB: true.bb195
getNonLocalPointerDepFromBB: true.bb196
getNonLocalPointerDepFromBB: true.bb197
getNonLocalPointerDepFromBB: true.bb198
getNonLocalPointerDepFromBB: true.bb199
getNonLocalPointerDepFromBB: true.bb200
By increasing the number of BBs I can get arbitrary deep stack depth (without uselists it'll alternate between false and true blocks bailing out after reaching ~100 results).
We saw this manifesting as stack overflow in practice.