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  }