1 /*
2  * Copyright (c) 2011, 2019, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 
25 package org.graalvm.compiler.virtual.phases.ea;
26 
27 import java.util.ArrayList;
28 import java.util.List;
29 
30 import jdk.internal.vm.compiler.collections.EconomicMap;
31 import jdk.internal.vm.compiler.collections.EconomicSet;
32 import jdk.internal.vm.compiler.collections.Equivalence;
33 import org.graalvm.compiler.core.common.cfg.BlockMap;
34 import org.graalvm.compiler.core.common.cfg.Loop;
35 import org.graalvm.compiler.core.common.type.Stamp;
36 import org.graalvm.compiler.debug.DebugContext;
37 import org.graalvm.compiler.debug.GraalError;
38 import org.graalvm.compiler.debug.Indent;
39 import org.graalvm.compiler.graph.Node;
40 import org.graalvm.compiler.graph.NodeBitMap;
41 import org.graalvm.compiler.graph.NodeMap;
42 import org.graalvm.compiler.graph.iterators.NodeIterable;
43 import org.graalvm.compiler.nodes.AbstractMergeNode;
44 import org.graalvm.compiler.nodes.FixedWithNextNode;
45 import org.graalvm.compiler.nodes.IfNode;
46 import org.graalvm.compiler.nodes.LogicConstantNode;
47 import org.graalvm.compiler.nodes.LogicNode;
48 import org.graalvm.compiler.nodes.LoopBeginNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.PhiNode;
51 import org.graalvm.compiler.nodes.ProxyNode;
52 import org.graalvm.compiler.nodes.StructuredGraph;
53 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
54 import org.graalvm.compiler.nodes.ValueNode;
55 import org.graalvm.compiler.nodes.ValuePhiNode;
56 import org.graalvm.compiler.nodes.cfg.Block;
57 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
58 import org.graalvm.compiler.nodes.extended.BoxNode;
59 import org.graalvm.compiler.nodes.util.GraphUtil;
60 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
61 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
62 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
63 import org.graalvm.compiler.options.OptionValues;
64 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
65 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
66 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.LoopInfo;
67 import jdk.internal.vm.compiler.word.LocationIdentity;
68 
69 public abstract class EffectsClosure<BlockT extends EffectsBlockState<BlockT>> extends EffectsPhase.Closure<BlockT> {
70 
71     protected final ControlFlowGraph cfg;
72     protected final ScheduleResult schedule;
73 
74     /**
75      * If a node has an alias, this means that it was replaced with another node during analysis.
76      * Nodes can be replaced by normal ("scalar") nodes, e.g., a LoadIndexedNode with a
77      * ConstantNode, or by virtual nodes, e.g., a NewInstanceNode with a VirtualInstanceNode. A node
78      * was replaced with a virtual value iff the alias is a subclass of VirtualObjectNode.
79      *
80      * This alias map exists only once and is not part of the block state, so that during iterative
81      * loop processing the alias of a node may be changed to another value.
82      */
83     protected final NodeMap<ValueNode> aliases;
84 
85     /**
86      * This set allows for a quick check whether a node has inputs that were replaced with "scalar"
87      * values.
88      */
89     private final NodeBitMap hasScalarReplacedInputs;
90 
91     /*
92      * TODO: if it was possible to introduce your own subclasses of Block and Loop, these maps would
93      * not be necessary. We could merge the GraphEffectsList logic into them.
94      */
95 
96     /**
97      * The effects accumulated during analysis of nodes. They may be cleared and re-filled during
98      * iterative loop processing.
99      */
100     protected final BlockMap<GraphEffectList> blockEffects;
101 
102     /**
103      * Effects that can only be applied after the effects from within the loop have been applied and
104      * that must be applied before any effect from after the loop is applied. E.g., updating phis.
105      */
106     protected final EconomicMap<Loop<Block>, GraphEffectList> loopMergeEffects = EconomicMap.create(Equivalence.IDENTITY);
107 
108     /**
109      * The entry state of loops is needed when loop proxies are processed.
110      */
111     private final EconomicMap<LoopBeginNode, BlockT> loopEntryStates = EconomicMap.create(Equivalence.IDENTITY);
112 
113     // Intended to be used by read-eliminating phases based on the effects phase.
114     protected final EconomicMap<Loop<Block>, LoopKillCache> loopLocationKillCache = EconomicMap.create(Equivalence.IDENTITY);
115 
116     protected boolean changed;
117     protected final DebugContext debug;
118 
EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg)119     public EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg) {
120         this.schedule = schedule;
121         this.cfg = cfg;
122         this.aliases = cfg.graph.createNodeMap();
123         this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap();
124         this.blockEffects = new BlockMap<>(cfg);
125         this.debug = cfg.graph.getDebug();
126         for (Block block : cfg.getBlocks()) {
127             blockEffects.put(block, new GraphEffectList(debug));
128         }
129     }
130 
131     @Override
hasChanged()132     public boolean hasChanged() {
133         return changed;
134     }
135 
136     @Override
needsApplyEffects()137     public boolean needsApplyEffects() {
138         return true;
139     }
140 
141     @Override
applyEffects()142     public void applyEffects() {
143         final StructuredGraph graph = cfg.graph;
144         final ArrayList<Node> obsoleteNodes = new ArrayList<>(0);
145         final ArrayList<GraphEffectList> effectList = new ArrayList<>();
146         /*
147          * Effects are applied during a ordered iteration over the blocks to apply them in the
148          * correct order, e.g., apply the effect that adds a node to the graph before the node is
149          * used.
150          */
151         BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() {
152 
153             @Override
154             protected Void getInitialState() {
155                 return null;
156             }
157 
158             private void apply(GraphEffectList effects) {
159                 if (effects != null && !effects.isEmpty()) {
160                     effectList.add(effects);
161                 }
162             }
163 
164             @Override
165             protected Void processBlock(Block block, Void currentState) {
166                 apply(blockEffects.get(block));
167                 return currentState;
168             }
169 
170             @Override
171             protected Void merge(Block merge, List<Void> states) {
172                 return null;
173             }
174 
175             @Override
176             protected Void cloneState(Void oldState) {
177                 return oldState;
178             }
179 
180             @Override
181             protected List<Void> processLoop(Loop<Block> loop, Void initialState) {
182                 LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState);
183                 apply(loopMergeEffects.get(loop));
184                 return info.exitStates;
185             }
186         };
187         ReentrantBlockIterator.apply(closure, cfg.getStartBlock());
188         for (GraphEffectList effects : effectList) {
189             effects.apply(graph, obsoleteNodes, false);
190         }
191         /*
192          * Effects that modify the cfg (e.g., removing a branch for an if that got a constant
193          * condition) need to be performed after all other effects, because they change phi value
194          * indexes.
195          */
196         for (GraphEffectList effects : effectList) {
197             effects.apply(graph, obsoleteNodes, true);
198         }
199         debug.dump(DebugContext.DETAILED_LEVEL, graph, "After applying effects");
200         assert VirtualUtil.assertNonReachable(graph, obsoleteNodes);
201         for (Node node : obsoleteNodes) {
202             if (node.isAlive() && node.hasNoUsages()) {
203                 if (node instanceof FixedWithNextNode) {
204                     assert ((FixedWithNextNode) node).next() == null;
205                 }
206                 node.replaceAtUsages(null);
207                 GraphUtil.killWithUnusedFloatingInputs(node);
208             }
209         }
210     }
211 
212     @Override
processBlock(Block block, BlockT state)213     protected BlockT processBlock(Block block, BlockT state) {
214         if (!state.isDead()) {
215             GraphEffectList effects = blockEffects.get(block);
216 
217             /*
218              * If we enter an if branch that is known to be unreachable, we mark it as dead and
219              * cease to do any more analysis on it. At merges, these dead branches will be ignored.
220              */
221             if (block.getBeginNode().predecessor() instanceof IfNode) {
222                 IfNode ifNode = (IfNode) block.getBeginNode().predecessor();
223                 LogicNode condition = ifNode.condition();
224                 Node alias = getScalarAlias(condition);
225                 if (alias instanceof LogicConstantNode) {
226                     LogicConstantNode constant = (LogicConstantNode) alias;
227                     boolean isTrueSuccessor = block.getBeginNode() == ifNode.trueSuccessor();
228 
229                     if (constant.getValue() != isTrueSuccessor) {
230                         state.markAsDead();
231                         effects.killIfBranch(ifNode, constant.getValue());
232                         return state;
233                     }
234                 }
235             }
236 
237             OptionValues options = block.getBeginNode().getOptions();
238             VirtualUtil.trace(options, debug, "\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors());
239 
240             // a lastFixedNode is needed in case we want to insert fixed nodes
241             FixedWithNextNode lastFixedNode = null;
242             Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes();
243             for (Node node : nodes) {
244                 // reset the aliases (may be non-null due to iterative loop processing)
245                 aliases.set(node, null);
246                 if (node instanceof LoopExitNode) {
247                     LoopExitNode loopExit = (LoopExitNode) node;
248                     for (ProxyNode proxy : loopExit.proxies()) {
249                         aliases.set(proxy, null);
250                         changed |= processNode(proxy, state, effects, lastFixedNode) && isSignificantNode(node);
251                     }
252                     processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block));
253                 }
254                 changed |= processNode(node, state, effects, lastFixedNode) && isSignificantNode(node);
255                 if (node instanceof FixedWithNextNode) {
256                     lastFixedNode = (FixedWithNextNode) node;
257                 }
258                 if (state.isDead()) {
259                     break;
260                 }
261             }
262             VirtualUtil.trace(options, debug, ")\n    end state: %s\n", state);
263         }
264         return state;
265     }
266 
267     /**
268      * Changes to {@link CommitAllocationNode}s, {@link AllocatedObjectNode}s and {@link BoxNode}s
269      * are not considered to be "important". If only changes to those nodes are discovered during
270      * analysis, the effects need not be applied.
271      */
isSignificantNode(Node node)272     private static boolean isSignificantNode(Node node) {
273         return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode);
274     }
275 
276     /**
277      * Collects the effects of virtualizing the given node.
278      *
279      * @return {@code true} if the effects include removing the node, {@code false} otherwise.
280      */
processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode)281     protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode);
282 
283     @Override
merge(Block merge, List<BlockT> states)284     protected BlockT merge(Block merge, List<BlockT> states) {
285         assert blockEffects.get(merge).isEmpty();
286         MergeProcessor processor = createMergeProcessor(merge);
287         doMergeWithoutDead(processor, states);
288         blockEffects.get(merge).addAll(processor.mergeEffects);
289         blockEffects.get(merge).addAll(processor.afterMergeEffects);
290         return processor.newState;
291     }
292 
293     @Override
294     @SuppressWarnings("try")
processLoop(Loop<Block> loop, BlockT initialState)295     protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
296         if (initialState.isDead()) {
297             ArrayList<BlockT> states = new ArrayList<>();
298             for (int i = 0; i < loop.getLoopExits().size(); i++) {
299                 states.add(initialState);
300             }
301             return states;
302         }
303         /*
304          * Special case nested loops: To avoid an exponential runtime for nested loops we try to
305          * only process them as little times as possible.
306          *
307          * In the first iteration of an outer most loop we go into the inner most loop(s). We run
308          * the first iteration of the inner most loop and then, if necessary, a second iteration.
309          *
310          * We return from the recursion and finish the first iteration of the outermost loop. If we
311          * have to do a second iteration in the outer most loop we go again into the inner most
312          * loop(s) but this time we already know all states that are killed by the loop so inside
313          * the loop we will only have those changes that propagate from the first iteration of the
314          * outer most loop into the current loop. We strip the initial loop state for the inner most
315          * loops and do the first iteration with the (possible) changes from outer loops. If there
316          * are no changes we only have to do 1 iteration and are done.
317          *
318          */
319         BlockT initialStateRemovedKilledLocations = stripKilledLoopLocations(loop, cloneState(initialState));
320         BlockT loopEntryState = initialStateRemovedKilledLocations;
321         BlockT lastMergedState = cloneState(initialStateRemovedKilledLocations);
322         processInitialLoopState(loop, lastMergedState);
323         MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader());
324         /*
325          * Iterative loop processing: we take the predecessor state as the loop's starting state,
326          * processing the loop contents, merge the states of all loop ends, and check whether the
327          * resulting state is equal to the starting state. If it is, the loop processing has
328          * finished, if not, another iteration is needed.
329          *
330          * This processing converges because the merge processing always makes the starting state
331          * more generic, e.g., adding phis instead of non-phi values.
332          */
333         for (int iteration = 0; iteration < 10; iteration++) {
334             try (Indent i = debug.logAndIndent("================== Process Loop Effects Closure: block:%s begin node:%s", loop.getHeader(), loop.getHeader().getBeginNode())) {
335                 LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState));
336 
337                 List<BlockT> states = new ArrayList<>();
338                 states.add(initialStateRemovedKilledLocations);
339                 states.addAll(info.endStates);
340                 doMergeWithoutDead(mergeProcessor, states);
341 
342                 debug.log("MergeProcessor New State: %s", mergeProcessor.newState);
343                 debug.log("===== vs.");
344                 debug.log("Last Merged State: %s", lastMergedState);
345 
346                 if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
347                     blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0);
348                     loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
349 
350                     assert info.exitStates.size() == loop.getLoopExits().size();
351                     loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState);
352                     assert assertExitStatesNonEmpty(loop, info);
353 
354                     processKilledLoopLocations(loop, initialStateRemovedKilledLocations, mergeProcessor.newState);
355                     return info.exitStates;
356                 } else {
357                     lastMergedState = mergeProcessor.newState;
358                     for (Block block : loop.getBlocks()) {
359                         blockEffects.get(block).clear();
360                         if (block.isLoopHeader()) {
361                             final GraphEffectList loopEffects = loopMergeEffects.get(block.getLoop());
362                             if (loopEffects != null) {
363                                 loopEffects.clear();
364                             }
365                         }
366                     }
367                 }
368             }
369         }
370         throw new GraalError("too many iterations at %s", loop);
371     }
372 
373     @SuppressWarnings("unused")
stripKilledLoopLocations(Loop<Block> loop, BlockT initialState)374     protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) {
375         return initialState;
376     }
377 
378     @SuppressWarnings("unused")
processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates)379     protected void processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates) {
380         // nothing to do
381     }
382 
383     @SuppressWarnings("unused")
processInitialLoopState(Loop<Block> loop, BlockT initialState)384     protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
385         // nothing to do
386     }
387 
doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states)388     private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) {
389         int alive = 0;
390         for (BlockT state : states) {
391             if (!state.isDead()) {
392                 alive++;
393             }
394         }
395         if (alive == 0) {
396             mergeProcessor.setNewState(states.get(0));
397         } else if (alive == states.size()) {
398             int[] stateIndexes = new int[states.size()];
399             for (int i = 0; i < stateIndexes.length; i++) {
400                 stateIndexes[i] = i;
401             }
402             mergeProcessor.setStateIndexes(stateIndexes);
403             mergeProcessor.setNewState(getInitialState());
404             mergeProcessor.merge(states);
405         } else {
406             ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
407             int[] stateIndexes = new int[alive];
408             for (int i = 0; i < states.size(); i++) {
409                 if (!states.get(i).isDead()) {
410                     stateIndexes[aliveStates.size()] = i;
411                     aliveStates.add(states.get(i));
412                 }
413             }
414             mergeProcessor.setStateIndexes(stateIndexes);
415             mergeProcessor.setNewState(getInitialState());
416             mergeProcessor.merge(aliveStates);
417         }
418     }
419 
assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info)420     private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
421         for (int i = 0; i < loop.getLoopExits().size(); i++) {
422             assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getLoopExits().get(i) + " / " + loop.getHeader();
423         }
424         return true;
425     }
426 
processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects)427     protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects);
428 
createMergeProcessor(Block merge)429     protected abstract MergeProcessor createMergeProcessor(Block merge);
430 
431     /**
432      * The main workhorse for merging states, both for loops and for normal merges.
433      */
434     protected abstract class MergeProcessor {
435 
436         private final Block mergeBlock;
437         protected final AbstractMergeNode merge;
438 
439         protected final GraphEffectList mergeEffects;
440         protected final GraphEffectList afterMergeEffects;
441 
442         /**
443          * The indexes are used to map from an index in the list of active (non-dead) predecessors
444          * to an index in the list of all predecessors (the latter may be larger).
445          */
446         private int[] stateIndexes;
447         protected BlockT newState;
448 
MergeProcessor(Block mergeBlock)449         public MergeProcessor(Block mergeBlock) {
450             this.mergeBlock = mergeBlock;
451             this.merge = (AbstractMergeNode) mergeBlock.getBeginNode();
452             this.mergeEffects = new GraphEffectList(debug);
453             this.afterMergeEffects = new GraphEffectList(debug);
454         }
455 
456         /**
457          * @param states the states that should be merged.
458          */
merge(List<BlockT> states)459         protected abstract void merge(List<BlockT> states);
460 
setNewState(BlockT state)461         private void setNewState(BlockT state) {
462             newState = state;
463             mergeEffects.clear();
464             afterMergeEffects.clear();
465         }
466 
setStateIndexes(int[] stateIndexes)467         private void setStateIndexes(int[] stateIndexes) {
468             this.stateIndexes = stateIndexes;
469         }
470 
getPredecessor(int index)471         protected final Block getPredecessor(int index) {
472             return mergeBlock.getPredecessors()[stateIndexes[index]];
473         }
474 
getPhis()475         protected final NodeIterable<PhiNode> getPhis() {
476             return merge.phis();
477         }
478 
getPhiValueAt(PhiNode phi, int index)479         protected final ValueNode getPhiValueAt(PhiNode phi, int index) {
480             return phi.valueAt(stateIndexes[index]);
481         }
482 
createValuePhi(Stamp stamp)483         protected final ValuePhiNode createValuePhi(Stamp stamp) {
484             return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]);
485         }
486 
setPhiInput(PhiNode phi, int index, ValueNode value)487         protected final void setPhiInput(PhiNode phi, int index, ValueNode value) {
488             afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value);
489         }
490 
graph()491         protected final StructuredGraph graph() {
492             return merge.graph();
493         }
494 
495         @Override
toString()496         public String toString() {
497             return "MergeProcessor@" + merge;
498         }
499     }
500 
addScalarAlias(ValueNode node, ValueNode alias)501     public void addScalarAlias(ValueNode node, ValueNode alias) {
502         assert !(alias instanceof VirtualObjectNode);
503         aliases.set(node, alias);
504         for (Node usage : node.usages()) {
505             if (!hasScalarReplacedInputs.isNew(usage)) {
506                 hasScalarReplacedInputs.mark(usage);
507             }
508         }
509     }
510 
hasScalarReplacedInputs(Node node)511     protected final boolean hasScalarReplacedInputs(Node node) {
512         return hasScalarReplacedInputs.isMarked(node);
513     }
514 
getScalarAlias(ValueNode node)515     public ValueNode getScalarAlias(ValueNode node) {
516         assert !(node instanceof VirtualObjectNode);
517         if (node == null || !node.isAlive() || aliases.isNew(node)) {
518             return node;
519         }
520         ValueNode result = aliases.get(node);
521         return (result == null || result instanceof VirtualObjectNode) ? node : result;
522     }
523 
524     protected static final class LoopKillCache {
525         private int visits;
526         private LocationIdentity firstLocation;
527         private EconomicSet<LocationIdentity> killedLocations;
528         private boolean killsAll;
529 
LoopKillCache(int visits)530         protected LoopKillCache(int visits) {
531             this.visits = visits;
532         }
533 
visited()534         protected void visited() {
535             visits++;
536         }
537 
visits()538         protected int visits() {
539             return visits;
540         }
541 
setKillsAll()542         protected void setKillsAll() {
543             killsAll = true;
544             firstLocation = null;
545             killedLocations = null;
546         }
547 
containsLocation(LocationIdentity locationIdentity)548         protected boolean containsLocation(LocationIdentity locationIdentity) {
549             if (killsAll) {
550                 return true;
551             }
552             if (firstLocation == null) {
553                 return false;
554             }
555             if (!firstLocation.equals(locationIdentity)) {
556                 return killedLocations != null ? killedLocations.contains(locationIdentity) : false;
557             }
558             return true;
559         }
560 
rememberLoopKilledLocation(LocationIdentity locationIdentity)561         protected void rememberLoopKilledLocation(LocationIdentity locationIdentity) {
562             if (killsAll) {
563                 return;
564             }
565             if (firstLocation == null || firstLocation.equals(locationIdentity)) {
566                 firstLocation = locationIdentity;
567             } else {
568                 if (killedLocations == null) {
569                     killedLocations = EconomicSet.create(Equivalence.IDENTITY);
570                 }
571                 killedLocations.add(locationIdentity);
572             }
573         }
574 
loopKillsLocations()575         protected boolean loopKillsLocations() {
576             if (killsAll) {
577                 return true;
578             }
579             return firstLocation != null;
580         }
581     }
582 
583 }
584