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