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 "AirTmpWidth.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirCode.h"
32#include "AirInstInlines.h"
33#include <wtf/ListDump.h>
34
35namespace JSC { namespace B3 { namespace Air {
36
37TmpWidth::TmpWidth()
38{
39}
40
41TmpWidth::TmpWidth(Code& code)
42{
43 recompute(code);
44}
45
46TmpWidth::~TmpWidth()
47{
48}
49
50void TmpWidth::recompute(Code& code)
51{
52 // Set this to true to cause this analysis to always return pessimistic results.
53 const bool beCareful = false;
54
55 const bool verbose = false;
56
57 if (verbose) {
58 dataLog("Code before TmpWidth:\n");
59 dataLog(code);
60 }
61
62 m_width.clear();
63
64 auto assumeTheWorst = [&] (Tmp tmp) {
65 Widths& widths = m_width.add(tmp, Widths()).iterator->value;
66 Bank bank = Arg(tmp).bank();
67 widths.use = conservativeWidth(bank);
68 widths.def = conservativeWidth(bank);
69 };
70
71 // Assume the worst for registers.
72 RegisterSet::allRegisters().forEach(
73 [&] (Reg reg) {
74 assumeTheWorst(Tmp(reg));
75 });
76
77 if (beCareful) {
78 code.forAllTmps(assumeTheWorst);
79
80 // We fall through because the fixpoint that follows can only make things even more
81 // conservative. This mode isn't meant to be fast, just safe.
82 }
83
84 // Now really analyze everything but Move's over Tmp's, but set aside those Move's so we can find
85 // them quickly during the fixpoint below. Note that we can make this analysis stronger by
86 // recognizing more kinds of Move's or anything that has Move-like behavior, though it's probably not
87 // worth it.
88 Vector<Inst*> moves;
89 for (BasicBlock* block : code) {
90 for (Inst& inst : *block) {
91 if (inst.kind.opcode == Move && inst.args[1].isTmp()) {
92 if (inst.args[0].isTmp()) {
93 // Make sure that both sides of the Move have a width already initialized. The
94 // fixpoint below assumes that it never has to add things to the HashMap.
95 m_width.add(inst.args[0].tmp(), Widths(GP));
96 m_width.add(inst.args[1].tmp(), Widths(GP));
97
98 moves.append(&inst);
99 continue;
100 }
101 if (inst.args[0].isImm()
102 && inst.args[0].value() >= 0) {
103 Tmp tmp = inst.args[1].tmp();
104 Widths& widths = m_width.add(tmp, Widths(GP)).iterator->value;
105
106 if (inst.args[0].value() <= std::numeric_limits<int8_t>::max())
107 widths.def = std::max(widths.def, Width8);
108 else if (inst.args[0].value() <= std::numeric_limits<int16_t>::max())
109 widths.def = std::max(widths.def, Width16);
110 else if (inst.args[0].value() <= std::numeric_limits<int32_t>::max())
111 widths.def = std::max(widths.def, Width32);
112 else
113 widths.def = std::max(widths.def, Width64);
114
115 continue;
116 }
117 }
118 inst.forEachTmp(
119 [&] (Tmp& tmp, Arg::Role role, Bank bank, Width width) {
120 Widths& widths = m_width.add(tmp, Widths(bank)).iterator->value;
121
122 if (Arg::isAnyUse(role))
123 widths.use = std::max(widths.use, width);
124
125 if (Arg::isZDef(role))
126 widths.def = std::max(widths.def, width);
127 else if (Arg::isAnyDef(role))
128 widths.def = conservativeWidth(bank);
129 });
130 }
131 }
132
133 // Finally, fixpoint over the Move's.
134 bool changed = true;
135 while (changed) {
136 changed = false;
137 for (Inst* move : moves) {
138 ASSERT(move->kind.opcode == Move);
139 ASSERT(move->args[0].isTmp());
140 ASSERT(move->args[1].isTmp());
141
142 // We already ensure that both tmps are added to the width map. That's important
143 // because you cannot add both tmps here while simultaneously getting a reference to
144 // their values, since the second add would invalidate the reference returned by the
145 // first one.
146 Widths& srcWidths = m_width.find(move->args[0].tmp())->value;
147 Widths& dstWidths = m_width.find(move->args[1].tmp())->value;
148
149 // Legend:
150 //
151 // Move %src, %dst
152
153 // defWidth(%dst) is a promise about how many high bits are zero. The smaller the width, the
154 // stronger the promise. This Move may weaken that promise if we know that %src is making a
155 // weaker promise. Such forward flow is the only thing that determines defWidth().
156 if (dstWidths.def < srcWidths.def) {
157 dstWidths.def = srcWidths.def;
158 changed = true;
159 }
160
161 // srcWidth(%src) is a promise about how many high bits are ignored. The smaller the width,
162 // the stronger the promise. This Move may weaken that promise if we know that %dst is making
163 // a weaker promise. Such backward flow is the only thing that determines srcWidth().
164 if (srcWidths.use < dstWidths.use) {
165 srcWidths.use = dstWidths.use;
166 changed = true;
167 }
168 }
169 }
170
171 if (verbose)
172 dataLog("width: ", mapDump(m_width), "\n");
173}
174
175void TmpWidth::Widths::dump(PrintStream& out) const
176{
177 out.print("{use = ", use, ", def = ", def, "}");
178}
179
180} } } // namespace JSC::B3::Air
181
182#endif // ENABLE(B3_JIT)
183
184