1/*
2 * Copyright (C) 2015-2019 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "B3EliminateDeadCode.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3PhaseScope.h"
32#include "B3ProcedureInlines.h"
33#include "B3ValueInlines.h"
34#include "B3Variable.h"
35#include "B3VariableValue.h"
36#include <wtf/GraphNodeWorklist.h>
37#include <wtf/IndexSet.h>
38#include <wtf/Vector.h>
39
40namespace JSC { namespace B3 {
41
42// FIXME: this pass currently only eliminates values and variables, it does not seem to eliminate dead blocks.
43
44bool eliminateDeadCodeImpl(Procedure& proc)
45{
46 bool changed = false;
47 GraphNodeWorklist<Value*, IndexSet<Value*>> worklist;
48 Vector<UpsilonValue*, 64> upsilons;
49 for (BasicBlock* block : proc) {
50 for (Value* value : *block) {
51 Effects effects;
52 // We don't care about effects of SSA operations, since we model them more
53 // accurately than the effects() method does.
54 if (value->opcode() != Phi && value->opcode() != Upsilon)
55 effects = value->effects();
56
57 if (effects.mustExecute())
58 worklist.push(value);
59
60 if (UpsilonValue* upsilon = value->as<UpsilonValue>())
61 upsilons.append(upsilon);
62 }
63 }
64 for (;;) {
65 while (Value* value = worklist.pop()) {
66 for (Value* child : value->children())
67 worklist.push(child);
68 }
69
70 bool didPush = false;
71 for (size_t upsilonIndex = 0; upsilonIndex < upsilons.size(); ++upsilonIndex) {
72 UpsilonValue* upsilon = upsilons[upsilonIndex];
73 if (worklist.saw(upsilon->phi())) {
74 worklist.push(upsilon);
75 upsilons[upsilonIndex--] = upsilons.last();
76 upsilons.takeLast();
77 didPush = true;
78 }
79 }
80 if (!didPush)
81 break;
82 }
83
84 IndexSet<Variable*> liveVariables;
85
86 for (BasicBlock* block : proc) {
87 size_t sourceIndex = 0;
88 size_t targetIndex = 0;
89 while (sourceIndex < block->size()) {
90 Value* value = block->at(sourceIndex++);
91 if (worklist.saw(value)) {
92 if (VariableValue* variableValue = value->as<VariableValue>())
93 liveVariables.add(variableValue->variable());
94 block->at(targetIndex++) = value;
95 } else {
96 proc.deleteValue(value);
97 changed = true;
98 }
99 }
100 block->values().resize(targetIndex);
101 }
102
103 for (Variable* variable : proc.variables()) {
104 if (!liveVariables.contains(variable))
105 proc.deleteVariable(variable);
106 }
107 return changed;
108}
109
110bool eliminateDeadCode(Procedure& proc)
111{
112 PhaseScope phaseScope(proc, "eliminateDeadCode");
113 return eliminateDeadCodeImpl(proc);
114}
115
116} } // namespace JSC::B3
117
118#endif // ENABLE(B3_JIT)
119