Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / ARES-6 / Air / liveness.js
1 /*
2  * Copyright (C) 2016 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 "use strict";
26
27 class Liveness {
28     constructor(thing, code)
29     {
30         this._thing = thing;
31         this._code = code;
32         
33         this._liveAtHead = new Map();
34         this._liveAtTail = new Map();
35         
36         for (let block of code) {
37             this._liveAtHead.set(block, new Set());
38             
39             let liveAtTail = new Set();
40             this._liveAtTail.set(block, liveAtTail);
41             
42             block.last.forEach(
43                 thing,
44                 (value, role, type, width) => {
45                     if (Arg.isLateUse(role))
46                         liveAtTail.add(value);
47                 });
48         }
49         
50         let dirtyBlocks = new Set(code);
51         
52         let changed;
53         do {
54             changed = false;
55             
56             for (let blockIndex = code.size; blockIndex--;) {
57                 let block = code.at(blockIndex);
58                 if (!block)
59                     continue;
60                 
61                 if (!dirtyBlocks.delete(block))
62                     continue;
63                 
64                 let localCalc = this.localCalc(block);
65                 for (let instIndex = block.size; instIndex--;)
66                     localCalc.execute(instIndex);
67                 
68                 // Handle the early def's of the first instruction.
69                 block.at(0).forEach(
70                     thing,
71                     (value, role, type, width) => {
72                         if (Arg.isEarlyDef(role))
73                             localCalc.liveSet.remove(value);
74                     });
75                 
76                 let liveAtHead = this._liveAtHead.get(block);
77                 
78                 if (!mergeIntoSet(liveAtHead, localCalc.liveSet))
79                     continue;
80                 
81                 for (let predecessor of block.predecessors) {
82                     if (mergeIntoSet(this._liveAtTail.get(predecessor), liveAtHead)) {
83                         dirtyBlocks.add(predecessor);
84                         changed = true;
85                     }
86                 }
87             }
88         } while (changed);
89     }
90     
91     get thing() { return this._thing; }
92     get code() { return this._code; }
93     get liveAtHead() { return this._liveAtHead; }
94     get liveAtTail() { return this._liveAtTail; }
95     
96     localCalc(block)
97     {
98         let liveness = this;
99         class LocalCalc {
100             constructor()
101             {
102                 this._liveSet = new Set(liveness.liveAtTail.get(block));
103             }
104             
105             get liveSet() { return this._liveSet; }
106             
107             execute(instIndex)
108             {
109                 let inst = block.at(instIndex);
110                 
111                 // First handle the early defs of the next instruction.
112                 if (instIndex + 1 < block.size) {
113                     block.at(instIndex + 1).forEach(
114                         liveness.thing,
115                         (value, role, type, width) => {
116                             if (Arg.isEarlyDef(role))
117                                 this._liveSet.delete(value);
118                         });
119                 }
120                 
121                 // Then handle defs.
122                 inst.forEach(
123                     liveness.thing,
124                     (value, role, type, width) => {
125                         if (Arg.isLateDef(role))
126                             this._liveSet.delete(value);
127                     });
128                 
129                 // Then handle uses.
130                 inst.forEach(
131                     liveness.thing,
132                     (value, role, type, width) => {
133                         if (Arg.isEarlyUse(role))
134                             this._liveSet.add(value);
135                     });
136                 
137                 // Finally handle the late uses of the previous instruction.
138                 if (instIndex - 1 >= 0) {
139                     block.at(instIndex - 1).forEach(
140                         liveness.thing,
141                         (value, role, type, width) => {
142                             if (Arg.isLateUse(role))
143                                 this._liveSet.add(value);
144                         });
145                 }
146             }
147         }
148         
149         return new LocalCalc();
150     }
151 }
152