/* ****************************************************************************
*
* Copyright (c) Microsoft Corporation.
*
* This source code is subject to terms and conditions of the Microsoft Public License. A
* copy of the license can be found in the License.html file at the root of this distribution. If
* you cannot locate the Microsoft Public License, please send an email to
* dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
* by the terms of the Microsoft Public License.
*
* You must not remove this notice, or any other, from this software.
*
*
* ***************************************************************************/
#if !CLR2
using System.Linq.Expressions;
#endif
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;
using Microsoft.Scripting.Ast;
using Microsoft.Scripting.Utils;
namespace Microsoft.Scripting.Interpreter{
using LoopFunc = Func<object[], StrongBox<object>[], InterpretedFrame, int>;
internal abstract class OffsetInstruction : Instruction {
internal const int Unknown = Int32.MinValue;
internal const int CacheSize = 32;
// the offset to jump to (relative to this instruction):
protected int _offset = Unknown;
public int Offset { get { return _offset; } }
public abstract Instruction[] Cache { get; }
public virtual Instruction Fixup(int offset, int targetContinuationDepth, int targetStackDepth) {
Debug.Assert(_offset == Unknown && offset != Unknown);
_offset = offset;
var cache = Cache;
if (cache != null && offset >= 0 && offset < cache.Length) {
return cache[offset] ?? (cache[offset] = this);
}
return this;
}
public override string ToDebugString(int instructionIndex, object cookie, Func<int, int> labelIndexer, IList<object> objects) {
return ToString() + (_offset != Unknown ? " -> " + (instructionIndex + _offset).ToString() : "");
}
public override string ToString() {
return InstructionName + (_offset == Unknown ? "(?)" : "(" + _offset + ")");
}
}
internal sealed class BranchFalseInstruction : OffsetInstruction {
private static Instruction[] _cache;
public override Instruction[] Cache {
get {
if (_cache == null) {
_cache = new Instruction[CacheSize];
}
return _cache;
}
}
internal BranchFalseInstruction() {
}
public override int ConsumedStack { get { return 1; } }
public override int Run(InterpretedFrame frame) {
Debug.Assert(_offset != Unknown);
if (!(bool)frame.Pop()) {
return _offset;
}
return +1;
}
}
internal sealed class BranchTrueInstruction : OffsetInstruction {
private static Instruction[] _cache;
public override Instruction[] Cache {
get {
if (_cache == null) {
_cache = new Instruction[CacheSize];
}
return _cache;
}
}
internal BranchTrueInstruction() {
}
public override int ConsumedStack { get { return 1; } }
public override int Run(InterpretedFrame frame) {
Debug.Assert(_offset != Unknown);
if ((bool)frame.Pop()) {
return _offset;
}
return +1;
}
}
internal sealed class CoalescingBranchInstruction : OffsetInstruction {
private static Instruction[] _cache;
public override Instruction[] Cache {
get {
if (_cache == null) {
_cache = new Instruction[CacheSize];
}
return _cache;
}
}
internal CoalescingBranchInstruction() {
}
public override int ConsumedStack { get { return 1; } }
public override int ProducedStack { get { return 1; } }
public override int Run(InterpretedFrame frame) {
Debug.Assert(_offset != Unknown);
if (frame.Peek() != null) {
return _offset;
}
return +1;
}
}
internal class BranchInstruction : OffsetInstruction {
private static Instruction[][][] _caches;
public override Instruction[] Cache {
get {
if (_caches == null) {
_caches = new Instruction[2][][] { new Instruction[2][], new Instruction[2][] };
}
return _caches[ConsumedStack][ProducedStack] ?? (_caches[ConsumedStack][ProducedStack] = new Instruction[CacheSize]);
}
}
internal readonly bool _hasResult;
internal readonly bool _hasValue;
internal BranchInstruction()
: this(false, false) {
}
public BranchInstruction(bool hasResult, bool hasValue) {
_hasResult = hasResult;
_hasValue = hasValue;
}
public override int ConsumedStack {
get { return _hasValue ? 1 : 0; }
}
public override int ProducedStack {
get { return _hasResult ? 1 : 0; }
}
public override int Run(InterpretedFrame frame) {
Debug.Assert(_offset != Unknown);
return _offset;
}
}
internal abstract class IndexedBranchInstruction : Instruction {
protected const int CacheSize = 32;
internal readonly int _labelIndex;
public IndexedBranchInstruction(int labelIndex) {
_labelIndex = labelIndex;
}
public RuntimeLabel GetLabel(InterpretedFrame frame) {
return frame.Interpreter._labels[_labelIndex];
}
public override string ToDebugString(int instructionIndex, object cookie, Func<int, int> labelIndexer, IList<object> objects) {
int targetIndex = labelIndexer(_labelIndex);
return ToString() + (targetIndex != BranchLabel.UnknownIndex ? " -> " + targetIndex.ToString() : "");
}
public override string ToString() {
return InstructionName + "[" + _labelIndex + "]";
}
}
/// <summary>
/// This instruction implements a goto expression that can jump out of any expression.
/// It pops values (arguments) from the evaluation stack that the expression tree nodes in between
/// the goto expression and the target label node pushed and not consumed yet.
/// A goto expression can jump into a node that evaluates arguments only if it carries
/// a value and jumps right after the first argument (the carried value will be used as the first argument).
/// Goto can jump into an arbitrary child of a BlockExpression since the block doesnt accumulate values
/// on evaluation stack as its child expressions are being evaluated.
///
/// Goto needs to execute any finally blocks on the way to the target label.
/// <example>
/// {
/// f(1, 2, try { g(3, 4, try { goto L } finally { ... }, 6) } finally { ... }, 7, 8)
/// L: ...
/// }
/// </example>
/// The goto expression here jumps to label L while having 4 items on evaluation stack (1, 2, 3 and 4).
/// The jump needs to execute both finally blocks, the first one on stack level 4 the
/// second one on stack level 2. So, it needs to jump the first finally block, pop 2 items from the stack,
/// run second finally block and pop another 2 items from the stack and set instruction pointer to label L.
///
/// Goto also needs to rethrow ThreadAbortException iff it jumps out of a catch handler and
/// the current thread is in "abort requested" state.
/// </summary>
internal sealed class GotoInstruction : IndexedBranchInstruction {
private const int Variants = 4;
private static readonly GotoInstruction[] Cache = new GotoInstruction[Variants * CacheSize];
private readonly bool _hasResult;
// TODO: We can remember hasValue in label and look it up when calculating stack balance. That would save some cache.
private readonly bool _hasValue;
// The values should technically be Consumed = 1, Produced = 1 for gotos that target a label whose continuation depth
// is different from the current continuation depth. However, in case of forward gotos, we don't not know that is the
// case until the label is emitted. By then the consumed and produced stack information is useless.
// The important thing here is that the stack balance is 0.
public override int ConsumedContinuations { get { return 0; } }
public override int ProducedContinuations { get { return 0; } }
public override int ConsumedStack {
get { return _hasValue ? 1 : 0; }
}
public override int ProducedStack {
get { return _hasResult ? 1 : 0; }
}
private GotoInstruction(int targetIndex, bool hasResult, bool hasValue)
: base(targetIndex) {
_hasResult = hasResult;
_hasValue = hasValue;
}
internal static GotoInstruction Create(int labelIndex, bool hasResult, bool hasValue) {
if (labelIndex < CacheSize) {
var index = Variants * labelIndex | (hasResult ? 2 : 0) | (hasValue ? 1 : 0);
return Cache[index] ?? (Cache[index] = new GotoInstruction(labelIndex, hasResult, hasValue));
}
return new GotoInstruction(labelIndex, hasResult, hasValue);
}
public override int Run(InterpretedFrame frame) {
// Are we jumping out of catch/finally while aborting the current thread?
Interpreter.AbortThreadIfRequested(frame, _labelIndex);
// goto the target label or the current finally continuation:
return frame.Goto(_labelIndex, _hasValue ? frame.Pop() : Interpreter.NoValue);
}
}
internal sealed class EnterTryFinallyInstruction : IndexedBranchInstruction {
private readonly static EnterTryFinallyInstruction[] Cache = new EnterTryFinallyInstruction[CacheSize];
public override int ProducedContinuations { get { return 1; } }
private EnterTryFinallyInstruction(int targetIndex)
: base(targetIndex) {
}
internal static EnterTryFinallyInstruction Create(int labelIndex) {
if (labelIndex < CacheSize) {
return Cache[labelIndex] ?? (Cache[labelIndex] = new EnterTryFinallyInstruction(labelIndex));
}
return new EnterTryFinallyInstruction(labelIndex);
}
public override int Run(InterpretedFrame frame) {
// Push finally.
frame.PushContinuation(_labelIndex);
return 1;
}
}
/// <summary>
/// The first instruction of finally block.
/// </summary>
internal sealed class EnterFinallyInstruction : Instruction {
internal static readonly Instruction Instance = new EnterFinallyInstruction();
public override int ProducedStack { get { return 2; } }
public override int ConsumedContinuations { get { return 1; } }
private EnterFinallyInstruction() {
}
public override int Run(InterpretedFrame frame) {
frame.PushPendingContinuation();
frame.RemoveContinuation();
return 1;
}
}
/// <summary>
/// The last instruction of finally block.
/// </summary>
internal sealed class LeaveFinallyInstruction : Instruction {
internal static readonly Instruction Instance = new LeaveFinallyInstruction();
public override int ConsumedStack { get { return 2; } }
private LeaveFinallyInstruction() {
}
public override int Run(InterpretedFrame frame) {
frame.PopPendingContinuation();
// jump to goto target or to the next finally:
return frame.YieldToPendingContinuation();
}
}
// no-op: we need this just to balance the stack depth.
internal sealed class EnterExceptionHandlerInstruction : Instruction {
internal static readonly EnterExceptionHandlerInstruction Void = new EnterExceptionHandlerInstruction(false);
internal static readonly EnterExceptionHandlerInstruction NonVoid = new EnterExceptionHandlerInstruction(true);
// True if try-expression is non-void.
private readonly bool _hasValue;
private EnterExceptionHandlerInstruction(bool hasValue) {
_hasValue = hasValue;
}
// If an exception is throws in try-body the expression result of try-body is not evaluated and loaded to the stack.
// So the stack doesn't contain the try-body's value when we start executing the handler.
// However, while emitting instructions try block falls thru the catch block with a value on stack.
// We need to declare it consumed so that the stack state upon entry to the handler corresponds to the real
// stack depth after throw jumped to this catch block.
public override int ConsumedStack { get { return _hasValue ? 1 : 0; } }
// A variable storing the current exception is pushed to the stack by exception handling.
// Catch handlers: The value is immediately popped and stored into a local.
// Fault handlers: The value is kept on stack during fault handler evaluation.
public override int ProducedStack { get { return 1; } }
public override int Run(InterpretedFrame frame) {
// nop (the exception value is pushed by the interpreter in HandleCatch)
return 1;
}
}
/// <summary>
/// The last instruction of a catch exception handler.
/// </summary>
internal sealed class LeaveExceptionHandlerInstruction : IndexedBranchInstruction {
private static LeaveExceptionHandlerInstruction[] Cache = new LeaveExceptionHandlerInstruction[2 * CacheSize];
private readonly bool _hasValue;
// The catch block yields a value if the body is non-void. This value is left on the stack.
public override int ConsumedStack {
get { return _hasValue ? 1 : 0; }
}
public override int ProducedStack {
get { return _hasValue ? 1 : 0; }
}
private LeaveExceptionHandlerInstruction(int labelIndex, bool hasValue)
: base(labelIndex) {
_hasValue = hasValue;
}
internal static LeaveExceptionHandlerInstruction Create(int labelIndex, bool hasValue) {
if (labelIndex < CacheSize) {
int index = (2 * labelIndex) | (hasValue ? 1 : 0);
return Cache[index] ?? (Cache[index] = new LeaveExceptionHandlerInstruction(labelIndex, hasValue));
}
return new LeaveExceptionHandlerInstruction(labelIndex, hasValue);
}
public override int Run(InterpretedFrame frame) {
// CLR rethrows ThreadAbortException when leaving catch handler if abort is requested on the current thread.
Interpreter.AbortThreadIfRequested(frame, _labelIndex);
return GetLabel(frame).Index - frame.InstructionIndex;
}
}
/// <summary>
/// The last instruction of a fault exception handler.
/// </summary>
internal sealed class LeaveFaultInstruction : Instruction {
internal static readonly Instruction NonVoid = new LeaveFaultInstruction(true);
internal static readonly Instruction Void = new LeaveFaultInstruction(false);
private readonly bool _hasValue;
// The fault block has a value if the body is non-void, but the value is never used.
// We compile the body of a fault block as void.
// However, we keep the exception object that was pushed upon entering the fault block on the stack during execution of the block
// and pop it at the end.
public override int ConsumedStack {
get { return 1; }
}
// While emitting instructions a non-void try-fault expression is expected to produce a value.
public override int ProducedStack {
get { return _hasValue ? 1 : 0; }
}
private LeaveFaultInstruction(bool hasValue) {
_hasValue = hasValue;
}
public override int Run(InterpretedFrame frame) {
// TODO: ThreadAbortException ?
object exception = frame.Pop();
ExceptionHandler handler;
return frame.Interpreter.GotoHandler(frame, exception, out handler);
}
}
internal sealed class ThrowInstruction : Instruction {
internal static readonly ThrowInstruction Throw = new ThrowInstruction(true);
internal static readonly ThrowInstruction VoidThrow = new ThrowInstruction(false);
private readonly bool _hasResult;
private ThrowInstruction(bool hasResult) {
_hasResult = hasResult;
}
public override int ProducedStack {
get { return _hasResult ? 1 : 0; }
}
public override int ConsumedStack {
get { return 1; }
}
public override int Run(InterpretedFrame frame) {
throw (Exception)frame.Pop();
}
}
internal sealed class SwitchInstruction : Instruction {
private readonly Dictionary<int, int> _cases;
internal SwitchInstruction(Dictionary<int, int> cases) {
Assert.NotNull(cases);
_cases = cases;
}
public override int ConsumedStack { get { return 1; } }
public override int ProducedStack { get { return 0; } }
public override int Run(InterpretedFrame frame) {
int target;
return _cases.TryGetValue((int)frame.Pop(), out target) ? target : 1;
}
}
internal sealed class EnterLoopInstruction : Instruction {
private readonly int _instructionIndex;
private LoopExpression _loop;
private int _loopEnd;
private int _compilationThreshold;
internal EnterLoopInstruction(LoopExpression loop, int compilationThreshold, int instructionIndex) {
_loop = loop;
_compilationThreshold = compilationThreshold;
_instructionIndex = instructionIndex;
}
internal void FinishLoop(int loopEnd) {
_loopEnd = loopEnd;
}
public override int Run(InterpretedFrame frame) {
// Don't lock here, it's a frequently hit path.
//
// There could be multiple threads racing, but that is okay.
// Two bad things can happen:
// * We miss decrements (some thread sets the counter forward)
// * We might enter the "if" branch more than once.
//
// The first is okay, it just means we take longer to compile.
// The second we explicitly guard against inside of Compile().
//
// We can't miss 0. The first thread that writes -1 must have read 0 and hence start compilation.
if (unchecked(_compilationThreshold--) == 0) {
if (frame.Interpreter.CompileSynchronously) {
Compile(frame);
} else {
// Kick off the compile on another thread so this one can keep going
ThreadPool.QueueUserWorkItem(Compile, frame);
}
}
return 1;
}
private bool Compiled {
get { return _loop == null; }
}
private void Compile(object frameObj) {
if (Compiled) {
return;
}
lock (this) {
if (Compiled) {
return;
}
PerfTrack.NoteEvent(PerfTrack.Categories.Compiler, "Interpreted loop compiled");
InterpretedFrame frame = (InterpretedFrame)frameObj;
var compiler = new LoopCompiler(_loop, frame.Interpreter.LabelMapping, frame.Interpreter.Locals, _instructionIndex, _loopEnd);
var instructions = frame.Interpreter.Instructions.Instructions;
// replace this instruction with an optimized one:
instructions[_instructionIndex] = new CompiledLoopInstruction(compiler.CreateDelegate());
// invalidate this instruction, some threads may still hold on it:
_loop = null;
}
}
}
internal sealed class CompiledLoopInstruction : Instruction {
private readonly LoopFunc _compiledLoop;
public CompiledLoopInstruction(LoopFunc compiledLoop) {
Assert.NotNull(compiledLoop);
_compiledLoop = compiledLoop;
}
public override int Run(InterpretedFrame frame) {
return _compiledLoop(frame.Data, frame.Closure, frame);
}
}
}
|