1/*
2 * Copyright (C) 2016-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 "B3PureCSE.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3Dominators.h"
32#include "B3PhaseScope.h"
33#include "B3Value.h"
34
35namespace JSC { namespace B3 {
36
37PureCSE::PureCSE()
38{
39}
40
41PureCSE::~PureCSE()
42{
43}
44
45void PureCSE::clear()
46{
47 m_map.clear();
48}
49
50Value* PureCSE::findMatch(const ValueKey& key, BasicBlock* block, Dominators& dominators)
51{
52 if (!key)
53 return nullptr;
54
55 auto iter = m_map.find(key);
56 if (iter == m_map.end())
57 return nullptr;
58
59 for (Value* match : iter->value) {
60 if (!match->owner)
61 continue;
62 if (dominators.dominates(match->owner, block))
63 return match;
64 }
65
66 return nullptr;
67}
68
69bool PureCSE::process(Value* value, Dominators& dominators)
70{
71 if (value->opcode() == Identity || value->isConstant())
72 return false;
73
74 ValueKey key = value->key();
75 if (!key)
76 return false;
77
78 Matches& matches = m_map.add(key, Matches()).iterator->value;
79
80 for (Value* match : matches) {
81 if (!match->owner)
82 continue;
83 if (dominators.dominates(match->owner, value->owner)) {
84 value->replaceWithIdentity(match);
85 return true;
86 }
87 }
88
89 matches.append(value);
90 return false;
91}
92
93bool pureCSE(Procedure& proc)
94{
95 PhaseScope phaseScope(proc, "pureCSE");
96
97 Dominators& dominators = proc.dominators();
98 PureCSE pureCSE;
99 bool result = false;
100 for (BasicBlock* block : proc.blocksInPreOrder()) {
101 for (Value* value : *block) {
102 result |= value->performSubstitution();
103 result |= pureCSE.process(value, dominators);
104 }
105 }
106
107 return result;
108}
109
110} } // namespace JSC::B3
111
112#endif // ENABLE(B3_JIT)
113
114