llvm / llvm/llvm-project

GVN (MemDep): Unbounded recursion in getNonLocalPointerDepFromBB

Open
#165,004 4 comments 0 reactions 0 assignees View on GitHub
llvm:analysis llvm:GVN
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

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.

Contributor guide

Open the contributing guide

Research direction

Start with the GVN MemDep implementation containing getNonLocalPointerDepFromBB and reproduce the issue using the linked IR example. Trace the recursive traversal shown in the report and identify why it does not terminate; done means the reproducer no longer causes unbounded recursion or stack exhaustion.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.