1/*
2 * Copyright (C) 2015 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 "AirSimplifyCFG.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirCode.h"
32#include "AirInstInlines.h"
33#include "AirPhaseScope.h"
34
35namespace JSC { namespace B3 { namespace Air {
36
37bool simplifyCFG(Code& code)
38{
39 const bool verbose = false;
40
41 PhaseScope phaseScope(code, "simplifyCFG");
42
43 // We have three easy simplification rules:
44 //
45 // 1) If a successor is a block that just jumps to another block, then jump directly to
46 // that block.
47 //
48 // 2) If all successors are the same and the operation has no effects, then use a jump
49 // instead.
50 //
51 // 3) If you jump to a block that is not you and has one predecessor, then merge.
52 //
53 // Note that because of the first rule, this phase may introduce critical edges. That's fine.
54 // If you need broken critical edges, then you have to break them yourself.
55
56 bool result = false;
57 for (;;) {
58 if (verbose) {
59 dataLog("Air before an iteration of simplifyCFG:\n");
60 dataLog(code);
61 }
62
63 bool changed = false;
64 for (BasicBlock* block : code) {
65 // We rely on predecessors being conservatively correct. Verify this here.
66 if (shouldValidateIRAtEachPhase()) {
67 for (BasicBlock* block : code) {
68 for (BasicBlock* successor : block->successorBlocks())
69 RELEASE_ASSERT(successor->containsPredecessor(block));
70 }
71 }
72
73 // We don't care about blocks that don't have successors.
74 if (!block->numSuccessors())
75 continue;
76
77 // First check if any of the successors of this block can be forwarded over.
78 for (BasicBlock*& successor : block->successorBlocks()) {
79 if (successor != block
80 && successor->size() == 1
81 && successor->last().kind.opcode == Jump) {
82 BasicBlock* newSuccessor = successor->successorBlock(0);
83 if (newSuccessor != successor) {
84 if (verbose) {
85 dataLog(
86 "Replacing ", pointerDump(block), "->", pointerDump(successor),
87 " with ", pointerDump(block), "->", pointerDump(newSuccessor), "\n");
88 }
89 // Note that we do not do replacePredecessor() because the block we're
90 // skipping will still have newSuccessor as its successor.
91 newSuccessor->addPredecessor(block);
92 successor = newSuccessor;
93 changed = true;
94 }
95 }
96 }
97
98 // Now check if the block's terminal can be replaced with a jump. The terminal must not
99 // have weird effects.
100 if (block->numSuccessors() > 1
101 && !block->last().hasNonControlEffects()) {
102 // All of the successors must be the same.
103 bool allSame = true;
104 BasicBlock* firstSuccessor = block->successorBlock(0);
105 for (unsigned i = 1; i < block->numSuccessors(); ++i) {
106 if (block->successorBlock(i) != firstSuccessor) {
107 allSame = false;
108 break;
109 }
110 }
111 if (allSame) {
112 if (verbose)
113 dataLog("Changing ", pointerDump(block), "'s terminal to a Jump.\n");
114 block->last() = Inst(Jump, block->last().origin);
115 block->successors().resize(1);
116 block->successors()[0].frequency() = FrequencyClass::Normal;
117 changed = true;
118 }
119 }
120
121 // Finally handle jumps to a block with one predecessor.
122 if (block->numSuccessors() == 1
123 && !block->last().hasNonControlEffects()) {
124 BasicBlock* successor = block->successorBlock(0);
125 if (successor != block && successor->numPredecessors() == 1) {
126 RELEASE_ASSERT(successor->predecessor(0) == block);
127
128 // We can merge the two blocks because the predecessor only jumps to the successor
129 // and the successor is only reachable from the predecessor.
130
131 // Remove the terminal.
132 Value* origin = block->insts().takeLast().origin;
133
134 // Append the full contents of the successor to the predecessor.
135 block->insts().reserveCapacity(block->size() + successor->size());
136 for (Inst& inst : *successor)
137 block->appendInst(WTFMove(inst));
138
139 // Make sure that our successors are the successor's successors.
140 block->successors() = WTFMove(successor->successors());
141
142 // Make sure that the successor has nothing left in it except an oops.
143 successor->resize(1);
144 successor->last() = Inst(Oops, origin);
145 successor->successors().clear();
146
147 // Ensure that the predecessors of block's new successors know what's up.
148 for (BasicBlock* newSuccessor : block->successorBlocks())
149 newSuccessor->replacePredecessor(successor, block);
150
151 if (verbose)
152 dataLog("Merged ", pointerDump(block), "->", pointerDump(successor), "\n");
153 changed = true;
154 }
155 }
156 }
157
158 if (!changed)
159 break;
160 result = true;
161 code.resetReachability();
162 }
163
164 return result;
165}
166
167} } } // namespace JSC::B3::Air
168
169#endif // ENABLE(B3_JIT)
170
171
172