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