1/*
2 * Copyright (C) 2015-2017 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 "AirEliminateDeadCode.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirCode.h"
32#include "AirInstInlines.h"
33#include "AirPhaseScope.h"
34#include "AirTmpInlines.h"
35#include "AirTmpSet.h"
36#include <wtf/IndexSet.h>
37
38namespace JSC { namespace B3 { namespace Air {
39
40bool eliminateDeadCode(Code& code)
41{
42 PhaseScope phaseScope(code, "eliminateDeadCode");
43
44 TmpSet liveTmps;
45 IndexSet<StackSlot*> liveStackSlots;
46 bool changed { false };
47
48 auto isArgLive = [&] (const Arg& arg) -> bool {
49 switch (arg.kind()) {
50 case Arg::Tmp:
51 if (arg.isReg())
52 return true;
53 return liveTmps.contains(arg.tmp());
54 case Arg::Stack:
55 if (arg.stackSlot()->isLocked())
56 return true;
57 return liveStackSlots.contains(arg.stackSlot());
58 default:
59 return true;
60 }
61 };
62
63 auto isInstLive = [&] (Inst& inst) -> bool {
64 if (inst.hasNonArgEffects())
65 return true;
66
67 // This instruction should be presumed dead, if its Args are all dead.
68 bool storesToLive = false;
69 inst.forEachArg(
70 [&] (Arg& arg, Arg::Role role, Bank, Width) {
71 if (!Arg::isAnyDef(role))
72 return;
73 if (role == Arg::Scratch)
74 return;
75 storesToLive |= isArgLive(arg);
76 });
77 return storesToLive;
78 };
79
80 // Returns true if it's live.
81 auto handleInst = [&] (Inst& inst) -> bool {
82 if (!isInstLive(inst))
83 return false;
84
85 // We get here if the Inst is live. For simplicity we say that a live instruction forces
86 // liveness upon everything it mentions.
87 for (Arg& arg : inst.args) {
88 if (arg.isStack() && !arg.stackSlot()->isLocked())
89 changed |= liveStackSlots.add(arg.stackSlot());
90 arg.forEachTmpFast(
91 [&] (Tmp& tmp) {
92 if (!tmp.isReg())
93 changed |= liveTmps.add(tmp);
94 });
95 }
96 return true;
97 };
98
99 Vector<Inst*> possiblyDead;
100
101 for (BasicBlock* block : code) {
102 for (Inst& inst : *block) {
103 if (!handleInst(inst))
104 possiblyDead.append(&inst);
105 }
106 }
107
108 auto runForward = [&] () -> bool {
109 changed = false;
110 possiblyDead.removeAllMatching(
111 [&] (Inst* inst) -> bool {
112 bool result = handleInst(*inst);
113 changed |= result;
114 return result;
115 });
116 return changed;
117 };
118
119 auto runBackward = [&] () -> bool {
120 changed = false;
121 for (unsigned i = possiblyDead.size(); i--;) {
122 bool result = handleInst(*possiblyDead[i]);
123 if (result) {
124 possiblyDead[i] = possiblyDead.last();
125 possiblyDead.removeLast();
126 changed = true;
127 }
128 }
129 return changed;
130 };
131
132 for (;;) {
133 // Propagating backward is most likely to be profitable.
134 if (!runBackward())
135 break;
136 if (!runBackward())
137 break;
138
139 // Occasionally propagating forward greatly reduces the likelihood of pathologies.
140 if (!runForward())
141 break;
142 }
143
144 unsigned removedInstCount = 0;
145 for (BasicBlock* block : code) {
146 removedInstCount += block->insts().removeAllMatching(
147 [&] (Inst& inst) -> bool {
148 return !isInstLive(inst);
149 });
150 }
151
152 return !!removedInstCount;
153}
154
155} } } // namespace JSC::B3::Air
156
157#endif // ENABLE(B3_JIT)
158
159