Skip to content

Commit a8538a4

Browse files
kripkenkripken
authored
fix an ssa bug: we can't assume that even if all set locations assign to the same local that it is ok to read that local, as locals may also be written elsewhere (WebAssembly#1423)
1 parent a40f145 commit a8538a4

4 files changed

Lines changed: 154 additions & 69 deletions

File tree

‎src/ir/local-graph.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@ struct LocalGraph {
4242

4343
// externally useful information
4444
GetSetses getSetses; // the sets affecting each get. a nullptr set means the initial
45-
// value (0 for a var, the received value for a param)
45+
// value (0 for a var, the received value for a param)
4646
Locations locations; // where each get and set is (for easy replacing)
4747

4848
// optional computation: compute the influence graphs between sets and gets

‎src/passes/SSAify.cpp‎

Lines changed: 28 additions & 58 deletions
Original file line numberDiff line numberDiff line change
@@ -99,68 +99,38 @@ struct SSAify : public Pass {
9999
continue;
100100
}
101101
// more than 1 set, need a phi: a new local written to at each of the sets
102-
// if there is already a local with that property, reuse it
103-
auto gatherIndexes = [](SetLocal* set) {
104-
std::set<Index> ret;
105-
while (set) {
106-
ret.insert(set->index);
107-
set = set->value->dynCast<SetLocal>();
108-
}
109-
return ret;
110-
};
111-
auto indexes = gatherIndexes(*sets.begin());
102+
auto new_ = addLocal(get->type);
103+
auto old = get->index;
104+
get->index = new_;
105+
Builder builder(*module);
106+
// write to the local in each of our sets
112107
for (auto* set : sets) {
113-
if (set == *sets.begin()) continue;
114-
auto currIndexes = gatherIndexes(set);
115-
std::vector<Index> intersection;
116-
std::set_intersection(indexes.begin(), indexes.end(),
117-
currIndexes.begin(), currIndexes.end(),
118-
std::back_inserter(intersection));
119-
indexes.clear();
120-
if (intersection.empty()) break;
121-
// TODO: or keep sorted vectors?
122-
for (Index i : intersection) {
123-
indexes.insert(i);
124-
}
125-
}
126-
if (!indexes.empty()) {
127-
// we found an index, use it
128-
get->index = *indexes.begin();
129-
} else {
130-
// we need to create a local for this phi'ing
131-
auto new_ = addLocal(get->type);
132-
auto old = get->index;
133-
get->index = new_;
134-
Builder builder(*module);
135-
// write to the local in each of our sets
136-
for (auto* set : sets) {
137-
if (set) {
138-
// a set exists, just add a tee of its value
139-
auto* value = set->value;
140-
auto* tee = builder.makeTeeLocal(
108+
if (set) {
109+
// a set exists, just add a tee of its value
110+
auto* value = set->value;
111+
auto* tee = builder.makeTeeLocal(
112+
new_,
113+
value
114+
);
115+
set->value = tee;
116+
// the value may have been something we tracked the location
117+
// of. if so, update that, since we moved it into the tee
118+
if (graph.locations.count(value) > 0) {
119+
assert(graph.locations[value] == &set->value);
120+
graph.locations[value] = &tee->value;
121+
}
122+
} else {
123+
// this is a param or the zero init value.
124+
if (func->isParam(old)) {
125+
// we add a set with the proper
126+
// param value at the beginning of the function
127+
auto* set = builder.makeSetLocal(
141128
new_,
142-
value
129+
builder.makeGetLocal(old, func->getLocalType(old))
143130
);
144-
set->value = tee;
145-
// the value may have been something we tracked the location
146-
// of. if so, update that, since we moved it into the tee
147-
if (graph.locations.count(value) > 0) {
148-
assert(graph.locations[value] == &set->value);
149-
graph.locations[value] = &tee->value;
150-
}
131+
functionPrepends.push_back(set);
151132
} else {
152-
// this is a param or the zero init value.
153-
if (func->isParam(old)) {
154-
// we add a set with the proper
155-
// param value at the beginning of the function
156-
auto* set = builder.makeSetLocal(
157-
new_,
158-
builder.makeGetLocal(old, func->getLocalType(old))
159-
);
160-
functionPrepends.push_back(set);
161-
} else {
162-
// this is a zero init, so we don't need to do anything actually
163-
}
133+
// this is a zero init, so we don't need to do anything actually
164134
}
165135
}
166136
}

‎test/passes/ssa.txt‎

Lines changed: 81 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -442,9 +442,12 @@
442442
(local $4 i32)
443443
(local $5 i32)
444444
(local $6 i32)
445+
(local $7 i32)
445446
(set_local $3
446-
(tee_local $6
447-
(get_local $param)
447+
(tee_local $7
448+
(tee_local $6
449+
(get_local $param)
450+
)
448451
)
449452
)
450453
(loop $more
@@ -460,15 +463,17 @@
460463
)
461464
)
462465
(set_local $5
463-
(tee_local $6
464-
(get_local $4)
466+
(tee_local $7
467+
(tee_local $6
468+
(get_local $4)
469+
)
465470
)
466471
)
467472
(br $more)
468473
)
469474
)
470475
(drop
471-
(get_local $6)
476+
(get_local $7)
472477
)
473478
)
474479
(func $real-loop-outblock (; 9 ;) (type $0) (param $param i32)
@@ -478,9 +483,12 @@
478483
(local $4 i32)
479484
(local $5 i32)
480485
(local $6 i32)
486+
(local $7 i32)
481487
(set_local $3
482-
(tee_local $6
483-
(get_local $param)
488+
(tee_local $7
489+
(tee_local $6
490+
(get_local $param)
491+
)
484492
)
485493
)
486494
(block $stop
@@ -496,15 +504,17 @@
496504
)
497505
)
498506
(set_local $5
499-
(tee_local $6
500-
(get_local $4)
507+
(tee_local $7
508+
(tee_local $6
509+
(get_local $4)
510+
)
501511
)
502512
)
503513
(br $more)
504514
)
505515
)
506516
(drop
507-
(get_local $6)
517+
(get_local $7)
508518
)
509519
)
510520
(func $loop-loop-param (; 10 ;) (type $0) (param $param i32)
@@ -726,4 +736,65 @@
726736
(br $label$1)
727737
)
728738
)
739+
(func $ssa-merge-tricky (; 15 ;) (type $2) (result i32)
740+
(local $var$0 i32)
741+
(local $var$1 i32)
742+
(local $2 i32)
743+
(local $3 i32)
744+
(local $4 i32)
745+
(local $5 i32)
746+
(local $6 i32)
747+
(local $7 i32)
748+
(local $8 i32)
749+
(set_local $2
750+
(tee_local $8
751+
(tee_local $3
752+
(tee_local $7
753+
(i32.const 0)
754+
)
755+
)
756+
)
757+
)
758+
(loop $label$1
759+
(if
760+
(i32.eqz
761+
(get_global $global$0)
762+
)
763+
(return
764+
(i32.const 12345)
765+
)
766+
)
767+
(set_global $global$0
768+
(i32.const 0)
769+
)
770+
(if
771+
(i32.eqz
772+
(get_local $7)
773+
)
774+
(br_if $label$1
775+
(i32.eqz
776+
(tee_local $4
777+
(tee_local $7
778+
(i32.const 1)
779+
)
780+
)
781+
)
782+
)
783+
)
784+
(br_if $label$1
785+
(i32.eqz
786+
(tee_local $5
787+
(tee_local $8
788+
(tee_local $6
789+
(tee_local $7
790+
(get_local $8)
791+
)
792+
)
793+
)
794+
)
795+
)
796+
)
797+
)
798+
(i32.const -54)
799+
)
729800
)

‎test/passes/ssa.wast‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -339,5 +339,49 @@
339339
(br $label$1) ;; back to the top, where we will return the zero
340340
)
341341
)
342+
(func $ssa-merge-tricky (result i32)
343+
(local $var$0 i32)
344+
(local $var$1 i32)
345+
(set_local $var$1
346+
(tee_local $var$0
347+
(i32.const 0) ;; both vars start out identical
348+
)
349+
)
350+
(loop $label$1
351+
(if
352+
(i32.eqz
353+
(get_global $global$0)
354+
)
355+
(return
356+
(i32.const 12345)
357+
)
358+
)
359+
(set_global $global$0
360+
(i32.const 0)
361+
)
362+
(if
363+
(i32.eqz
364+
(get_local $var$0) ;; check $0 here. this will get a phi var
365+
)
366+
(br_if $label$1
367+
(i32.eqz
368+
(tee_local $var$0 ;; set $0 to 1. here the two diverge. for the phi, we'll get a set here and above
369+
(i32.const 1)
370+
)
371+
)
372+
)
373+
)
374+
(br_if $label$1
375+
(i32.eqz ;; indeed equal, enter loop again, and then hang prevention kicks in
376+
(tee_local $var$1 ;; set them all to 0
377+
(tee_local $var$0
378+
(get_local $var$1) ;; this must get $1, not the phis, as even though the sets appear in both sources, we only execute 1.
379+
)
380+
)
381+
)
382+
)
383+
)
384+
(i32.const -54)
385+
)
342386
)
343387

0 commit comments

Comments
 (0)