1 /*
2  * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining
5  * a copy of this software and associated documentation files (the
6  * "Software"), to deal in the Software without restriction, including
7  * without limitation the rights to use, copy, modify, merge, publish,
8  * distribute, sublicense, and/or sell copies of the Software, and to
9  * permit persons to whom the Software is furnished to do so, subject to
10  * the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be
13  * included in all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 
25 using System;
26 using System.Collections.Generic;
27 
28 /*
29  * The implementation for interpreted words.
30  */
31 
32 class WordInterpreted : Word {
33 
34 	/*
35 	 * Get the number of local variables for this word.
36 	 */
37 	internal int NumLocals {
38 		get; private set;
39 	}
40 
41 	/*
42 	 * Get the sequence of opcodes for this word.
43 	 */
44 	internal Opcode[] Code {
45 		get; private set;
46 	}
47 
48 	string[] toResolve;
49 
50 	internal WordInterpreted(T0Comp owner, string name,
51 		int numLocals, Opcode[] code, string[] toResolve)
52 		: base(owner, name)
53 	{
54 		this.Code = code;
55 		this.toResolve = toResolve;
56 		NumLocals = numLocals;
57 	}
58 
59 	internal override void Resolve()
60 	{
61 		if (toResolve == null) {
62 			return;
63 		}
64 		for (int i = 0; i < toResolve.Length; i ++) {
65 			string tt = toResolve[i];
66 			if (tt == null) {
67 				continue;
68 			}
69 			Code[i].ResolveTarget(TC.Lookup(tt));
70 		}
71 		toResolve = null;
72 	}
73 
74 	internal override void Run(CPU cpu)
75 	{
76 		Resolve();
77 		cpu.Enter(Code, NumLocals);
78 	}
79 
80 	internal override List<Word> GetReferences()
81 	{
82 		Resolve();
83 		List<Word> r = new List<Word>();
84 		foreach (Opcode op in Code) {
85 			Word w = op.GetReference(TC);
86 			if (w != null) {
87 				r.Add(w);
88 			}
89 		}
90 		return r;
91 	}
92 
93 	internal override List<ConstData> GetDataBlocks()
94 	{
95 		Resolve();
96 		List<ConstData> r = new List<ConstData>();
97 		foreach (Opcode op in Code) {
98 			ConstData cd = op.GetDataBlock(TC);
99 			if (cd != null) {
100 				r.Add(cd);
101 			}
102 		}
103 		return r;
104 	}
105 
106 	internal override void GenerateCodeElements(List<CodeElement> dst)
107 	{
108 		Resolve();
109 		int n = Code.Length;
110 		CodeElement[] gcode = new CodeElement[n];
111 		for (int i = 0; i < n; i ++) {
112 			gcode[i] = Code[i].ToCodeElement();
113 		}
114 		for (int i = 0; i < n; i ++) {
115 			Code[i].FixUp(gcode, i);
116 		}
117 		dst.Add(new CodeElementUInt((uint)NumLocals));
118 		for (int i = 0; i < n; i ++) {
119 			dst.Add(gcode[i]);
120 		}
121 	}
122 
123 	int flowAnalysis;
124 	int maxDataStack;
125 	int maxReturnStack;
126 
127 	bool MergeSA(int[] sa, int j, int c)
128 	{
129 		if (sa[j] == Int32.MinValue) {
130 			sa[j] = c;
131 			return true;
132 		} else if (sa[j] != c) {
133 			throw new Exception(string.Format(
134 				"In word '{0}', offset {1}:"
135 				+ " stack action mismatch ({2} / {3})",
136 				Name, j, sa[j], c));
137 		} else {
138 			return false;
139 		}
140 	}
141 
142 	internal override void AnalyseFlow()
143 	{
144 		switch (flowAnalysis) {
145 		case 0:
146 			break;
147 		case 1:
148 			return;
149 		default:
150 			throw new Exception("recursive call detected in '"
151 				+ Name + "'");
152 		}
153 		flowAnalysis = 2;
154 		int n = Code.Length;
155 		int[] sa = new int[n];
156 		for (int i = 0; i < n; i ++) {
157 			sa[i] = Int32.MinValue;
158 		}
159 		sa[0] = 0;
160 		int[] toExplore = new int[n];
161 		int tX = 0, tY = 0;
162 		int off = 0;
163 
164 		int exitSA = Int32.MinValue;
165 		int mds = 0;
166 		int mrs = 0;
167 
168 		int maxDepth = 0;
169 
170 		for (;;) {
171 			Opcode op = Code[off];
172 			bool mft = op.MayFallThrough;
173 			int c = sa[off];
174 			int a;
175 			if (op is OpcodeCall) {
176 				Word w = op.GetReference(TC);
177 				w.AnalyseFlow();
178 				SType se = w.StackEffect;
179 				if (!se.IsKnown) {
180 					throw new Exception(string.Format(
181 						"call from '{0}' to '{1}'"
182 						+ " with unknown stack effect",
183 						Name, w.Name));
184 				}
185 				if (se.NoExit) {
186 					mft = false;
187 					a = 0;
188 				} else {
189 					a = se.DataOut - se.DataIn;
190 				}
191 				mds = Math.Max(mds, c + w.MaxDataStack);
192 				mrs = Math.Max(mrs, w.MaxReturnStack);
193 				maxDepth = Math.Min(maxDepth, c - se.DataIn);
194 			} else if (op is OpcodeRet) {
195 				if (exitSA == Int32.MinValue) {
196 					exitSA = c;
197 				} else if (exitSA != c) {
198 					throw new Exception(string.Format(
199 						"'{0}': exit stack action"
200 						+ " mismatch: {1} / {2}"
201 						+ " (offset {3})",
202 						Name, exitSA, c, off));
203 				}
204 				a = 0;
205 			} else {
206 				a = op.StackAction;
207 				mds = Math.Max(mds, c + a);
208 			}
209 			c += a;
210 			maxDepth = Math.Min(maxDepth, c);
211 
212 			int j = op.JumpDisp;
213 			if (j != 0) {
214 				j += off + 1;
215 				toExplore[tY ++] = j;
216 				MergeSA(sa, j, c);
217 			}
218 			off ++;
219 			if (!mft || !MergeSA(sa, off, c)) {
220 				if (tX < tY) {
221 					off = toExplore[tX ++];
222 				} else {
223 					break;
224 				}
225 			}
226 		}
227 
228 		maxDataStack = mds;
229 		maxReturnStack = 1 + NumLocals + mrs;
230 
231 		/*
232 		 * TODO: see about this warning. Usage of a 'fail'
233 		 * word (that does not exit) within a 'case..endcase'
234 		 * structure will make an unreachable opcode. In a future
235 		 * version we might want to automatically remove dead
236 		 * opcodes.
237 		for (int i = 0; i < n; i ++) {
238 			if (sa[i] == Int32.MinValue) {
239 				Console.WriteLine("warning: word '{0}',"
240 					+ " offset {1}: unreachable opcode",
241 					Name, i);
242 				continue;
243 			}
244 		}
245 		 */
246 
247 		SType computed;
248 		if (exitSA == Int32.MinValue) {
249 			computed = new SType(-maxDepth, -1);
250 		} else {
251 			computed = new SType(-maxDepth, -maxDepth + exitSA);
252 		}
253 
254 		if (StackEffect.IsKnown) {
255 			if (!computed.IsSubOf(StackEffect)) {
256 				throw new Exception(string.Format(
257 					"word '{0}':"
258 					+ " computed stack effect {1}"
259 					+ " does not match declared {2}",
260 					Name, computed.ToString(),
261 					StackEffect.ToString()));
262 			}
263 		} else {
264 			StackEffect = computed;
265 		}
266 
267 		flowAnalysis = 1;
268 	}
269 
270 	internal override int MaxDataStack {
271 		get {
272 			AnalyseFlow();
273 			return maxDataStack;
274 		}
275 	}
276 
277 	internal override int MaxReturnStack {
278 		get {
279 			AnalyseFlow();
280 			return maxReturnStack;
281 		}
282 	}
283 }
284