contrib/bearssl/T0/WordInterpreted.cs

   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 }