Skip to content

Commit e29d6d0

Browse files
rakudramacommit-bot@chromium.org
rakudrama
authored and
[email protected]
committed
[dart2js] HValidator - k-limit inputs and usedBy validation
Change-Id: I73207f8bb82e70222ac058ac2fcf9cbb026cbad3 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/112603 Commit-Queue: Stephen Adams <[email protected]> Reviewed-by: Mayank Patke <[email protected]>
1 parent 9713ce1 commit e29d6d0

File tree

2 files changed

+38
-33
lines changed

2 files changed

+38
-33
lines changed

‎pkg/compiler/lib/src/ssa/validate.dart‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -133,9 +133,17 @@ class HValidator extends HInstructionVisitor {
133133
super.visitBasicBlock(block);
134134
}
135135

136+
// Limit for the size of `inputs` and `usedBy` lists. We assume lists longer
137+
// than this are OK in order to avoid the O(N^2) validation getting out of
138+
// hand.
139+
//
140+
// Poster child: corelib_2/regexp/pcre_test.dart, which has a 7KLOC main().
141+
static const int kMaxValidatedInstructionListLength = 1000;
142+
136143
/// Verifies [instruction] is contained in [instructions] [count] times.
137144
static bool checkInstructionCount(
138145
List<HInstruction> instructions, HInstruction instruction, int count) {
146+
if (instructions.length > kMaxValidatedInstructionListLength) return true;
139147
int result = 0;
140148
for (int i = 0; i < instructions.length; i++) {
141149
if (identical(instructions[i], instruction)) result++;
@@ -146,7 +154,9 @@ class HValidator extends HInstructionVisitor {
146154
/// Returns true if the predicate returns true for every instruction in the
147155
/// list. The argument to [f] is an instruction with the count of how often
148156
/// it appeared in the list [instructions].
149-
static bool everyInstruction(List<HInstruction> instructions, Function f) {
157+
static bool everyInstruction(
158+
List<HInstruction> instructions, bool Function(HInstruction, int) f) {
159+
if (instructions.length > kMaxValidatedInstructionListLength) return true;
150160
var copy = new List<HInstruction>.from(instructions);
151161
// TODO(floitsch): there is currently no way to sort HInstructions before
152162
// we have assigned an ID. The loop is therefore O(n^2) for now.

‎tests/compiler/dart2js/analyses/dart2js_allowed.json‎

Lines changed: 27 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -146,6 +146,15 @@
146146
"Dynamic invocation of '-'.": 1,
147147
"Dynamic invocation of '+'.": 1
148148
},
149+
"pkg/compiler/lib/src/serialization/binary_sink.dart": {
150+
"Dynamic access of 'index'.": 1
151+
},
152+
"pkg/compiler/lib/src/native/behavior.dart": {
153+
"Dynamic invocation of 'add'.": 1
154+
},
155+
"pkg/compiler/lib/src/util/enumset.dart": {
156+
"Dynamic access of 'index'.": 4
157+
},
149158
"pkg/compiler/lib/src/constants/constant_system.dart": {
150159
"Dynamic invocation of '&'.": 1,
151160
"Dynamic invocation of '|'.": 1,
@@ -165,9 +174,6 @@
165174
"Dynamic invocation of '>='.": 1,
166175
"Dynamic invocation of 'codeUnitAt'.": 1
167176
},
168-
"pkg/compiler/lib/src/serialization/binary_sink.dart": {
169-
"Dynamic access of 'index'.": 1
170-
},
171177
"third_party/pkg/dart2js_info/lib/json_info_codec.dart": {
172178
"Dynamic invocation of '[]'.": 11,
173179
"Dynamic invocation of 'forEach'.": 2,
@@ -177,12 +183,6 @@
177183
"third_party/pkg/dart2js_info/lib/binary_serialization.dart": {
178184
"Dynamic invocation of 'cast'.": 1
179185
},
180-
"pkg/compiler/lib/src/util/enumset.dart": {
181-
"Dynamic access of 'index'.": 4
182-
},
183-
"pkg/compiler/lib/src/native/enqueue.dart": {
184-
"Dynamic access of 'isDynamic'.": 1
185-
},
186186
"pkg/compiler/lib/src/inferrer/inferrer_engine.dart": {
187187
"Dynamic access of 'isVoid'.": 1,
188188
"Dynamic access of 'isDynamic'.": 1,
@@ -195,8 +195,8 @@
195195
"pkg/compiler/lib/src/universe/side_effects.dart": {
196196
"Dynamic access of 'universe.side_effects::_flags'.": 1
197197
},
198-
"pkg/compiler/lib/src/native/behavior.dart": {
199-
"Dynamic invocation of 'add'.": 1
198+
"pkg/compiler/lib/src/native/enqueue.dart": {
199+
"Dynamic access of 'isDynamic'.": 1
200200
},
201201
"pkg/compiler/lib/src/ssa/builder_kernel.dart": {
202202
"Dynamic update to 'instantiatedTypes'.": 1,
@@ -211,17 +211,11 @@
211211
"Dynamic access of 'treatAsDynamic'.": 1,
212212
"Dynamic access of 'element'.": 1
213213
},
214-
"pkg/compiler/lib/src/ssa/validate.dart": {
215-
"Dynamic invocation of 'isInBasicBlock'.": 2,
216-
"Dynamic access of 'usedBy'.": 2,
217-
"Dynamic access of 'inputs'.": 1
218-
},
219-
"third_party/pkg/dart2js_info/lib/src/util.dart": {
220-
"Dynamic access of 'name'.": 1,
221-
"Dynamic invocation of '-'.": 1
222-
},
223-
"third_party/pkg/dart2js_info/lib/src/binary/sink.dart": {
224-
"Dynamic access of 'index'.": 1
214+
"pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart": {
215+
"Dynamic access of 'keys'.": 1,
216+
"Dynamic invocation of 'toSet'.": 1,
217+
"Dynamic invocation of '[]='.": 1,
218+
"Dynamic invocation of 'add'.": 1
225219
},
226220
"pkg/js_ast/lib/src/builder.dart": {
227221
"Dynamic invocation of 'call'.": 2
@@ -235,6 +229,13 @@
235229
"Dynamic invocation of '[]'.": 9,
236230
"Dynamic invocation of 'toStatement'.": 3
237231
},
232+
"third_party/pkg/dart2js_info/lib/src/util.dart": {
233+
"Dynamic access of 'name'.": 1,
234+
"Dynamic invocation of '-'.": 1
235+
},
236+
"third_party/pkg/dart2js_info/lib/src/binary/sink.dart": {
237+
"Dynamic access of 'index'.": 1
238+
},
238239
"pkg/compiler/lib/src/inferrer/type_graph_nodes.dart": {
239240
"Dynamic invocation of 'add'.": 1,
240241
"Dynamic invocation of 'remove'.": 1,
@@ -250,16 +251,14 @@
250251
"Dynamic access of 'named'.": 2,
251252
"Dynamic invocation of '[]'.": 2
252253
},
253-
"pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart": {
254-
"Dynamic access of 'keys'.": 1,
255-
"Dynamic invocation of 'toSet'.": 1,
256-
"Dynamic invocation of '[]='.": 1,
257-
"Dynamic invocation of 'add'.": 1
258-
},
259254
"pkg/compiler/lib/src/universe/function_set.dart": {
260255
"Dynamic access of 'selector'.": 1,
261256
"Dynamic access of 'receiver'.": 1
262257
},
258+
"pkg/compiler/lib/src/js_emitter/startup_emitter/fragment_emitter.dart": {
259+
"Dynamic access of 'superclass'.": 1,
260+
"Dynamic access of 'needsTearOff'.": 1
261+
},
263262
"pkg/compiler/lib/src/ssa/variable_allocator.dart": {
264263
"Dynamic access of 'usedBy'.": 1,
265264
"Dynamic access of 'isEmpty'.": 1,
@@ -275,9 +274,5 @@
275274
},
276275
"pkg/compiler/lib/src/ssa/value_set.dart": {
277276
"Dynamic invocation of 'add'.": 2
278-
},
279-
"pkg/compiler/lib/src/js_emitter/startup_emitter/fragment_emitter.dart": {
280-
"Dynamic access of 'superclass'.": 1,
281-
"Dynamic access of 'needsTearOff'.": 1
282277
}
283278
}

0 commit comments

Comments
 (0)