1/*
2 * Copyright (C) 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 "AirRegLiveness.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirArgInlines.h"
32#include "AirInstInlines.h"
33
34namespace JSC { namespace B3 { namespace Air {
35
36RegLiveness::RegLiveness(Code& code)
37 : m_liveAtHead(code.size())
38 , m_liveAtTail(code.size())
39{
40 // The liveAtTail of each block automatically contains the LateUse's of the terminal.
41 for (BasicBlock* block : code) {
42 RegisterSet& liveAtTail = m_liveAtTail[block];
43
44 block->last().forEach<Reg>(
45 [&] (Reg& reg, Arg::Role role, Bank, Width) {
46 if (Arg::isLateUse(role))
47 liveAtTail.add(reg);
48 });
49 }
50
51 BitVector dirtyBlocks;
52 for (size_t blockIndex = code.size(); blockIndex--;)
53 dirtyBlocks.set(blockIndex);
54
55 bool changed;
56 do {
57 changed = false;
58
59 for (size_t blockIndex = code.size(); blockIndex--;) {
60 BasicBlock* block = code[blockIndex];
61 if (!block)
62 continue;
63
64 if (!dirtyBlocks.quickClear(blockIndex))
65 continue;
66
67 LocalCalc localCalc(*this, block);
68 for (size_t instIndex = block->size(); instIndex--;)
69 localCalc.execute(instIndex);
70
71 // Handle the early def's of the first instruction.
72 block->at(0).forEach<Reg>(
73 [&] (Reg& reg, Arg::Role role, Bank, Width) {
74 if (Arg::isEarlyDef(role))
75 localCalc.m_workset.remove(reg);
76 });
77
78 RegisterSet& liveAtHead = m_liveAtHead[block];
79 if (liveAtHead.subsumes(localCalc.m_workset))
80 continue;
81
82 liveAtHead.merge(localCalc.m_workset);
83
84 for (BasicBlock* predecessor : block->predecessors()) {
85 RegisterSet& liveAtTail = m_liveAtTail[predecessor];
86 if (liveAtTail.subsumes(localCalc.m_workset))
87 continue;
88
89 liveAtTail.merge(localCalc.m_workset);
90 dirtyBlocks.quickSet(predecessor->index());
91 changed = true;
92 }
93 }
94 } while (changed);
95}
96
97RegLiveness::~RegLiveness()
98{
99}
100
101void RegLiveness::LocalCalc::execute(unsigned instIndex)
102{
103 Inst& inst = m_block->at(instIndex);
104
105 // First handle the early def's of the next instruction.
106 if (instIndex + 1 < m_block->size()) {
107 Inst& nextInst = m_block->at(instIndex + 1);
108 nextInst.forEach<Reg>(
109 [&] (Reg& reg, Arg::Role role, Bank, Width) {
110 if (Arg::isEarlyDef(role))
111 m_workset.remove(reg);
112 });
113 }
114
115 // Then handle def's.
116 inst.forEach<Reg>(
117 [&] (Reg& reg, Arg::Role role, Bank, Width) {
118 if (Arg::isLateDef(role))
119 m_workset.remove(reg);
120 });
121
122 // Then handle use's.
123 inst.forEach<Reg>(
124 [&] (Reg& reg, Arg::Role role, Bank, Width) {
125 if (Arg::isEarlyUse(role))
126 m_workset.add(reg);
127 });
128
129 // And finally, handle the late use's of the previous instruction.
130 if (instIndex) {
131 Inst& prevInst = m_block->at(instIndex - 1);
132 prevInst.forEach<Reg>(
133 [&] (Reg& reg, Arg::Role role, Bank, Width) {
134 if (Arg::isLateUse(role))
135 m_workset.add(reg);
136 });
137 }
138}
139
140} } } // namespace JSC::B3::Air
141
142#endif // ENABLE(B3_JIT)
143