mcs/class/dlr/Runtime/Microsoft.Dynamic/Interpreter/Instructions/ControlFlowInstructions.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Apache License, Version 2.0, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Apache License, Version 2.0.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16 #if FEATURE_TASKS
  17 using System.Threading.Tasks;
  18 #endif
  19
  20 #if FEATURE_CORE_DLR
  21 using System.Linq.Expressions;
  22 #endif
  23
  24 using System;
  25 using System.Collections.Generic;
  26 using System.Diagnostics;
  27 using System.Runtime.CompilerServices;
  28 using System.Threading;
  29 using Microsoft.Scripting.Ast;
  30 using Microsoft.Scripting.Utils;
  31
  32 namespace Microsoft.Scripting.Interpreter {
  33     using LoopFunc = Func<object[], StrongBox<object>[], InterpretedFrame, int>;
  34
  35     internal abstract class OffsetInstruction : Instruction {
  36         internal const int Unknown = Int32.MinValue;
  37         internal const int CacheSize = 32;
  38
  39         // the offset to jump to (relative to this instruction):
  40         protected int _offset = Unknown;
  41
  42         public int Offset { get { return _offset; } }
  43         public abstract Instruction[] Cache { get; }
  44
  45         public Instruction Fixup(int offset) {
  46             Debug.Assert(_offset == Unknown && offset != Unknown);
  47             _offset = offset;
  48
  49             var cache = Cache;
  50             if (cache != null && offset >= 0 && offset < cache.Length) {
  51                 return cache[offset] ?? (cache[offset] = this);
  52             }
  53
  54             return this;
  55         }
  56
  57         public override string ToDebugString(int instructionIndex, object cookie, Func<int, int> labelIndexer, IList<object> objects) {
  58             return ToString() + (_offset != Unknown ? " -> " + (instructionIndex + _offset).ToString() : "");
  59         }
  60
  61         public override string ToString() {
  62             return InstructionName + (_offset == Unknown ? "(?)" : "(" + _offset + ")");
  63         }
  64     }
  65
  66     internal sealed class BranchFalseInstruction : OffsetInstruction {
  67         private static Instruction[] _cache;
  68
  69         public override Instruction[] Cache {
  70             get {
  71                 if (_cache == null) {
  72                     _cache = new Instruction[CacheSize];
  73                 }
  74                 return _cache;
  75             }
  76         }
  77
  78         internal BranchFalseInstruction() {
  79         }
  80
  81         public override int ConsumedStack { get { return 1; } }
  82
  83         public override int Run(InterpretedFrame frame) {
  84             Debug.Assert(_offset != Unknown);
  85
  86             if (!(bool)frame.Pop()) {
  87                 return _offset;
  88             }
  89
  90             return +1;
  91         }
  92     }
  93
  94     internal sealed class BranchTrueInstruction : OffsetInstruction {
  95         private static Instruction[] _cache;
  96
  97         public override Instruction[] Cache {
  98             get {
  99                 if (_cache == null) {
 100                     _cache = new Instruction[CacheSize];
 101                 }
 102                 return _cache;
 103             }
 104         }
 105
 106         internal BranchTrueInstruction() {
 107         }
 108
 109         public override int ConsumedStack { get { return 1; } }
 110
 111         public override int Run(InterpretedFrame frame) {
 112             Debug.Assert(_offset != Unknown);
 113
 114             if ((bool)frame.Pop()) {
 115                 return _offset;
 116             }
 117
 118             return +1;
 119         }
 120     }
 121
 122         internal sealed class BranchNullInstruction : OffsetInstruction {
 123                 private static Instruction[] _cache;
 124
 125                 public override Instruction[] Cache {
 126                         get {
 127                                 if (_cache == null) {
 128                                         _cache = new Instruction[CacheSize];
 129                                 }
 130                                 return _cache;
 131                         }
 132                 }
 133
 134                 internal BranchNullInstruction() {
 135                 }
 136
 137                 public override int ConsumedStack { get { return 1; } }
 138
 139                 public override int Run(InterpretedFrame frame) {
 140                         Debug.Assert(_offset != Unknown);
 141
 142                         if (frame.Pop() == null) {
 143                                 return _offset;
 144                         }
 145
 146                         return +1;
 147                 }
 148         }
 149
 150     internal sealed class CoalescingBranchInstruction : OffsetInstruction {
 151         private static Instruction[] _cache;
 152
 153         public override Instruction[] Cache {
 154             get {
 155                 if (_cache == null) {
 156                     _cache = new Instruction[CacheSize];
 157                 }
 158                 return _cache;
 159             }
 160         }
 161
 162         internal CoalescingBranchInstruction() {
 163         }
 164
 165         public override int ConsumedStack { get { return 1; } }
 166         public override int ProducedStack { get { return 1; } }
 167
 168         public override int Run(InterpretedFrame frame) {
 169             Debug.Assert(_offset != Unknown);
 170
 171             if (frame.Peek() != null) {
 172                 return _offset;
 173             }
 174
 175             return +1;
 176         }
 177     }
 178
 179     internal class BranchInstruction : OffsetInstruction {
 180         private static Instruction[][][] _caches;
 181
 182         public override Instruction[] Cache {
 183             get {
 184                 if (_caches == null) {
 185                     _caches = new Instruction[2][][] { new Instruction[2][], new Instruction[2][] };
 186                 }
 187                 return _caches[ConsumedStack][ProducedStack] ?? (_caches[ConsumedStack][ProducedStack] = new Instruction[CacheSize]);
 188             }
 189         }
 190
 191         internal readonly bool _hasResult;
 192         internal readonly bool _hasValue;
 193
 194         internal BranchInstruction()
 195             : this(false, false) {
 196         }
 197
 198         public BranchInstruction(bool hasResult, bool hasValue) {
 199             _hasResult = hasResult;
 200             _hasValue = hasValue;
 201         }
 202
 203         public override int ConsumedStack {
 204             get { return _hasValue ? 1 : 0; }
 205         }
 206
 207         public override int ProducedStack {
 208             get { return _hasResult ? 1 : 0; }
 209         }
 210
 211         public override int Run(InterpretedFrame frame) {
 212             Debug.Assert(_offset != Unknown);
 213
 214             return _offset;
 215         }
 216     }
 217
 218     internal abstract class IndexedBranchInstruction : Instruction {
 219         protected const int CacheSize = 32;
 220
 221         internal readonly int _labelIndex;
 222
 223         public IndexedBranchInstruction(int labelIndex) {
 224             _labelIndex = labelIndex;
 225         }
 226
 227         public RuntimeLabel GetLabel(InterpretedFrame frame) {
 228             return frame.Interpreter._labels[_labelIndex];
 229         }
 230
 231         public override string ToDebugString(int instructionIndex, object cookie, Func<int, int> labelIndexer, IList<object> objects) {
 232             int targetIndex = labelIndexer(_labelIndex);
 233             return ToString() + (targetIndex != BranchLabel.UnknownIndex ? " -> " + targetIndex.ToString() : "");
 234         }
 235
 236         public override string ToString() {
 237             return InstructionName + "[" + _labelIndex + "]";
 238         }
 239     }
 240
 241     /// <summary>
 242     /// This instruction implements a goto expression that can jump out of any expression.
 243     /// It pops values (arguments) from the evaluation stack that the expression tree nodes in between
 244     /// the goto expression and the target label node pushed and not consumed yet.
 245     /// A goto expression can jump into a node that evaluates arguments only if it carries
 246     /// a value and jumps right after the first argument (the carried value will be used as the first argument).
 247     /// Goto can jump into an arbitrary child of a BlockExpression since the block doesn’t accumulate values
 248     /// on evaluation stack as its child expressions are being evaluated.
 249     ///
 250     /// Goto needs to execute any finally blocks on the way to the target label.
 251     /// <example>
 252     /// {
 253     ///     f(1, 2, try { g(3, 4, try { goto L } finally { ... }, 6) } finally { ... }, 7, 8)
 254     ///     L: ...
 255     /// }
 256     /// </example>
 257     /// The goto expression here jumps to label L while having 4 items on evaluation stack (1, 2, 3 and 4).
 258     /// The jump needs to execute both finally blocks, the first one on stack level 4 the
 259     /// second one on stack level 2. So, it needs to jump the first finally block, pop 2 items from the stack,
 260     /// run second finally block and pop another 2 items from the stack and set instruction pointer to label L.
 261     ///
 262     /// Goto also needs to rethrow ThreadAbortException iff it jumps out of a catch handler and
 263     /// the current thread is in "abort requested" state.
 264     /// </summary>
 265     internal sealed class GotoInstruction : IndexedBranchInstruction {
 266         private const int Variants = 4;
 267         private static readonly GotoInstruction[] Cache = new GotoInstruction[Variants * CacheSize];
 268
 269         private readonly bool _hasResult;
 270
 271         // TODO: We can remember hasValue in label and look it up when calculating stack balance. That would save some cache.
 272         private readonly bool _hasValue;
 273
 274         // The values should technically be Consumed = 1, Produced = 1 for gotos that target a label whose continuation depth
 275         // is different from the current continuation depth. However, in case of forward gotos, we don't not know that is the
 276         // case until the label is emitted. By then the consumed and produced stack information is useless.
 277         // The important thing here is that the stack balance is 0.
 278         public override int ConsumedContinuations { get { return 0; } }
 279         public override int ProducedContinuations { get { return 0; } }
 280
 281         public override int ConsumedStack {
 282             get { return _hasValue ? 1 : 0; }
 283         }
 284
 285         public override int ProducedStack {
 286             get { return _hasResult ? 1 : 0; }
 287         }
 288
 289         private GotoInstruction(int targetIndex, bool hasResult, bool hasValue)
 290             : base(targetIndex) {
 291             _hasResult = hasResult;
 292             _hasValue = hasValue;
 293         }
 294
 295         internal static GotoInstruction Create(int labelIndex, bool hasResult, bool hasValue) {
 296             if (labelIndex < CacheSize) {
 297                 var index = Variants * labelIndex | (hasResult ? 2 : 0) | (hasValue ? 1 : 0);
 298                 return Cache[index] ?? (Cache[index] = new GotoInstruction(labelIndex, hasResult, hasValue));
 299             }
 300             return new GotoInstruction(labelIndex, hasResult, hasValue);
 301         }
 302
 303         public override int Run(InterpretedFrame frame) {
 304             // Are we jumping out of catch/finally while aborting the current thread?
 305             Interpreter.AbortThreadIfRequested(frame, _labelIndex);
 306
 307             // goto the target label or the current finally continuation:
 308             return frame.Goto(_labelIndex, _hasValue ? frame.Pop() : Interpreter.NoValue);
 309         }
 310     }
 311
 312     internal sealed class EnterTryFinallyInstruction : IndexedBranchInstruction {
 313         private readonly static EnterTryFinallyInstruction[] Cache = new EnterTryFinallyInstruction[CacheSize];
 314
 315         public override int ProducedContinuations { get { return 1; } }
 316
 317         private EnterTryFinallyInstruction(int targetIndex)
 318             : base(targetIndex) {
 319         }
 320
 321         internal static EnterTryFinallyInstruction Create(int labelIndex) {
 322             if (labelIndex < CacheSize) {
 323                 return Cache[labelIndex] ?? (Cache[labelIndex] = new EnterTryFinallyInstruction(labelIndex));
 324             }
 325             return new EnterTryFinallyInstruction(labelIndex);
 326         }
 327
 328         public override int Run(InterpretedFrame frame) {
 329             // Push finally.
 330             frame.PushContinuation(_labelIndex);
 331             return 1;
 332         }
 333     }
 334
 335     /// <summary>
 336     /// The first instruction of finally block.
 337     /// </summary>
 338     internal sealed class EnterFinallyInstruction : Instruction {
 339         internal static readonly Instruction Instance = new EnterFinallyInstruction();
 340
 341         public override int ProducedStack { get { return 2; } }
 342         public override int ConsumedContinuations { get { return 1; } }
 343
 344         private EnterFinallyInstruction() {
 345         }
 346
 347         public override int Run(InterpretedFrame frame) {
 348             frame.PushPendingContinuation();
 349             frame.RemoveContinuation();
 350             return 1;
 351         }
 352     }
 353
 354     /// <summary>
 355     /// The last instruction of finally block.
 356     /// </summary>
 357     internal sealed class LeaveFinallyInstruction : Instruction {
 358         internal static readonly Instruction Instance = new LeaveFinallyInstruction();
 359
 360         public override int ConsumedStack { get { return 2; } }
 361
 362         private LeaveFinallyInstruction() {
 363         }
 364
 365         public override int Run(InterpretedFrame frame) {
 366             frame.PopPendingContinuation();
 367
 368             // jump to goto target or to the next finally:
 369             return frame.YieldToPendingContinuation();
 370         }
 371     }
 372
 373     // no-op: we need this just to balance the stack depth.
 374     internal sealed class EnterExceptionHandlerInstruction : Instruction {
 375         internal static readonly EnterExceptionHandlerInstruction Void = new EnterExceptionHandlerInstruction(false);
 376         internal static readonly EnterExceptionHandlerInstruction NonVoid = new EnterExceptionHandlerInstruction(true);
 377
 378         // True if try-expression is non-void.
 379         private readonly bool _hasValue;
 380
 381         private EnterExceptionHandlerInstruction(bool hasValue) {
 382             _hasValue = hasValue;
 383         }
 384
 385         // If an exception is throws in try-body the expression result of try-body is not evaluated and loaded to the stack.
 386         // So the stack doesn't contain the try-body's value when we start executing the handler.
 387         // However, while emitting instructions try block falls thru the catch block with a value on stack.
 388         // We need to declare it consumed so that the stack state upon entry to the handler corresponds to the real
 389         // stack depth after throw jumped to this catch block.
 390         public override int ConsumedStack { get { return _hasValue ? 1 : 0; } }
 391
 392         // A variable storing the current exception is pushed to the stack by exception handling.
 393         // Catch handlers: The value is immediately popped and stored into a local.
 394         // Fault handlers: The value is kept on stack during fault handler evaluation.
 395         public override int ProducedStack { get { return 1; } }
 396
 397         public override int Run(InterpretedFrame frame) {
 398             // nop (the exception value is pushed by the interpreter in HandleCatch)
 399             return 1;
 400         }
 401     }
 402
 403     /// <summary>
 404     /// The last instruction of a catch exception handler.
 405     /// </summary>
 406     internal sealed class LeaveExceptionHandlerInstruction : IndexedBranchInstruction {
 407         private static LeaveExceptionHandlerInstruction[] Cache = new LeaveExceptionHandlerInstruction[2 * CacheSize];
 408
 409         private readonly bool _hasValue;
 410
 411         // The catch block yields a value if the body is non-void. This value is left on the stack.
 412         public override int ConsumedStack {
 413             get { return _hasValue ? 1 : 0; }
 414         }
 415
 416         public override int ProducedStack {
 417             get { return _hasValue ? 1 : 0; }
 418         }
 419
 420         private LeaveExceptionHandlerInstruction(int labelIndex, bool hasValue)
 421             : base(labelIndex) {
 422             _hasValue = hasValue;
 423         }
 424
 425         internal static LeaveExceptionHandlerInstruction Create(int labelIndex, bool hasValue) {
 426             if (labelIndex < CacheSize) {
 427                 int index = (2 * labelIndex) | (hasValue ? 1 : 0);
 428                 return Cache[index] ?? (Cache[index] = new LeaveExceptionHandlerInstruction(labelIndex, hasValue));
 429             }
 430             return new LeaveExceptionHandlerInstruction(labelIndex, hasValue);
 431         }
 432
 433         public override int Run(InterpretedFrame frame) {
 434             // CLR rethrows ThreadAbortException when leaving catch handler if abort is requested on the current thread.
 435             Interpreter.AbortThreadIfRequested(frame, _labelIndex);
 436             return GetLabel(frame).Index - frame.InstructionIndex;
 437         }
 438     }
 439
 440     /// <summary>
 441     /// The last instruction of a fault exception handler.
 442     /// </summary>
 443     internal sealed class LeaveFaultInstruction : Instruction {
 444         internal static readonly Instruction NonVoid = new LeaveFaultInstruction(true);
 445         internal static readonly Instruction Void = new LeaveFaultInstruction(false);
 446
 447         private readonly bool _hasValue;
 448
 449         // The fault block has a value if the body is non-void, but the value is never used.
 450         // We compile the body of a fault block as void.
 451         // However, we keep the exception object that was pushed upon entering the fault block on the stack during execution of the block
 452         // and pop it at the end.
 453         public override int ConsumedStack {
 454             get { return 1; }
 455         }
 456
 457         // While emitting instructions a non-void try-fault expression is expected to produce a value.
 458         public override int ProducedStack {
 459             get { return _hasValue ? 1 : 0; }
 460         }
 461
 462         private LeaveFaultInstruction(bool hasValue) {
 463             _hasValue = hasValue;
 464         }
 465
 466         public override int Run(InterpretedFrame frame) {
 467             // TODO: ThreadAbortException ?
 468
 469             object exception = frame.Pop();
 470             ExceptionHandler handler;
 471             return frame.Interpreter.GotoHandler(frame, exception, out handler);
 472         }
 473     }
 474
 475
 476     internal sealed class ThrowInstruction : Instruction {
 477         internal static readonly ThrowInstruction Throw = new ThrowInstruction(true, false);
 478         internal static readonly ThrowInstruction VoidThrow = new ThrowInstruction(false, false);
 479         internal static readonly ThrowInstruction Rethrow = new ThrowInstruction(true, true);
 480         internal static readonly ThrowInstruction VoidRethrow = new ThrowInstruction(false, true);
 481
 482         private readonly bool _hasResult, _rethrow;
 483
 484         private ThrowInstruction(bool hasResult, bool isRethrow) {
 485             _hasResult = hasResult;
 486             _rethrow = isRethrow;
 487         }
 488
 489         public override int ProducedStack {
 490             get { return _hasResult ? 1 : 0; }
 491         }
 492
 493         public override int ConsumedStack {
 494             get {
 495                 return 1;
 496             }
 497         }
 498
 499         public override int Run(InterpretedFrame frame) {
 500             var ex = (Exception)frame.Pop();
 501             if (_rethrow) {
 502                 ExceptionHandler handler;
 503                 return frame.Interpreter.GotoHandler(frame, ex, out handler);
 504             }
 505             throw ex;
 506         }
 507     }
 508
 509     internal sealed class SwitchInstruction : Instruction {
 510         private readonly Dictionary<int, int> _cases;
 511
 512         internal SwitchInstruction(Dictionary<int, int> cases) {
 513             Assert.NotNull(cases);
 514             _cases = cases;
 515         }
 516
 517         public override int ConsumedStack { get { return 1; } }
 518         public override int ProducedStack { get { return 0; } }
 519
 520         public override int Run(InterpretedFrame frame) {
 521             int target;
 522             return _cases.TryGetValue((int)frame.Pop(), out target) ? target : 1;
 523         }
 524     }
 525
 526     internal sealed class EnterLoopInstruction : Instruction {
 527         private readonly int _instructionIndex;
 528         private Dictionary<ParameterExpression, LocalVariable> _variables;
 529         private Dictionary<ParameterExpression, LocalVariable> _closureVariables;
 530         private LoopExpression _loop;
 531         private int _loopEnd;
 532         private int _compilationThreshold;
 533
 534         internal EnterLoopInstruction(LoopExpression loop, LocalVariables locals, int compilationThreshold, int instructionIndex) {
 535             _loop = loop;
 536             _variables = locals.CopyLocals();
 537             _closureVariables = locals.ClosureVariables;
 538             _compilationThreshold = compilationThreshold;
 539             _instructionIndex = instructionIndex;
 540         }
 541
 542         internal void FinishLoop(int loopEnd) {
 543             _loopEnd = loopEnd;
 544         }
 545
 546         public override int Run(InterpretedFrame frame) {
 547             // Don't lock here, it's a frequently hit path.
 548             //
 549             // There could be multiple threads racing, but that is okay.
 550             // Two bad things can happen:
 551             //   * We miss decrements (some thread sets the counter forward)
 552             //   * We might enter the "if" branch more than once.
 553             //
 554             // The first is okay, it just means we take longer to compile.
 555             // The second we explicitly guard against inside of Compile().
 556             //
 557             // We can't miss 0. The first thread that writes -1 must have read 0 and hence start compilation.
 558             if (unchecked(_compilationThreshold--) == 0) {
 559 #if SILVERLIGHT
 560                 if (PlatformAdaptationLayer.IsCompactFramework) {
 561                     _compilationThreshold = Int32.MaxValue;
 562                     return 1;
 563                 }
 564 #endif
 565                 if (frame.Interpreter.CompileSynchronously) {
 566                     Compile(frame);
 567                 } else {
 568                     // Kick off the compile on another thread so this one can keep going,
 569                     // Compile method backpatches the instruction when finished so we don't need to await the task.
 570 #if FEATURE_TASKS
 571                     new Task(Compile, frame).Start();
 572 #else
 573                     ThreadPool.QueueUserWorkItem(Compile, frame);
 574 #endif
 575                 }
 576             }
 577             return 1;
 578         }
 579
 580         private bool Compiled {
 581             get { return _loop == null; }
 582         }
 583
 584         private void Compile(object frameObj) {
 585             if (Compiled) {
 586                 return;
 587             }
 588
 589             lock (this) {
 590                 if (Compiled) {
 591                     return;
 592                 }
 593
 594                 PerfTrack.NoteEvent(PerfTrack.Categories.Compiler, "Interpreted loop compiled");
 595
 596                 InterpretedFrame frame = (InterpretedFrame)frameObj;
 597                 var compiler = new LoopCompiler(_loop, frame.Interpreter.LabelMapping, _variables, _closureVariables, _instructionIndex, _loopEnd);
 598                 var instructions = frame.Interpreter.Instructions.Instructions;
 599
 600                 // replace this instruction with an optimized one:
 601                 Interlocked.Exchange(ref instructions[_instructionIndex], new CompiledLoopInstruction(compiler.CreateDelegate()));
 602
 603                 // invalidate this instruction, some threads may still hold on it:
 604                 _loop = null;
 605                 _variables = null;
 606                 _closureVariables = null;
 607             }
 608         }
 609     }
 610
 611     internal sealed class CompiledLoopInstruction : Instruction {
 612         private readonly LoopFunc _compiledLoop;
 613
 614         public CompiledLoopInstruction(LoopFunc compiledLoop) {
 615             Assert.NotNull(compiledLoop);
 616             _compiledLoop = compiledLoop;
 617         }
 618
 619         public override int Run(InterpretedFrame frame) {
 620             return _compiledLoop(frame.Data, frame.Closure, frame);
 621         }
 622     }
 623 }