mcs/class/dlr/Runtime/Microsoft.Dynamic/Interpreter/LoopCompiler.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_CORE_DLR
  17 using System.Linq.Expressions;
  18 #endif
  19
  20 using System;
  21 using System.Collections.Generic;
  22 using System.Diagnostics;
  23 using System.Runtime.CompilerServices;
  24 using Microsoft.Scripting.Ast;
  25 using Microsoft.Scripting.Utils;
  26
  27 namespace Microsoft.Scripting.Interpreter {
  28     using AstUtils = Microsoft.Scripting.Ast.Utils;
  29     using LoopFunc = Func<object[], StrongBox<object>[], InterpretedFrame, int>;
  30     using System.Collections.ObjectModel;
  31
  32     internal sealed class LoopCompiler : ExpressionVisitor {
  33         private struct LoopVariable {
  34             public ExpressionAccess Access;
  35
  36             // a variable that holds on the strong box for closure variables:
  37             public ParameterExpression BoxStorage;
  38
  39             public LoopVariable(ExpressionAccess access, ParameterExpression box) {
  40                 Access = access;
  41                 BoxStorage = box;
  42             }
  43
  44             public override string ToString() {
  45                 return Access.ToString() + " " + BoxStorage;
  46             }
  47         }
  48
  49         private readonly ParameterExpression _frameDataVar;
  50         private readonly ParameterExpression _frameClosureVar;
  51         private readonly ParameterExpression _frameVar;
  52         private readonly LabelTarget _returnLabel;
  53         // locals and closure variables defined outside the loop
  54         private readonly Dictionary<ParameterExpression, LocalVariable> _outerVariables, _closureVariables;
  55         private readonly LoopExpression _loop;
  56         private ReadOnlyCollectionBuilder<ParameterExpression> _temps;
  57         // tracks variables that flow in and flow out for initialization and
  58         private readonly Dictionary<ParameterExpression, LoopVariable> _loopVariables;
  59         // variables which are defined and used within the loop
  60         private HashSet<ParameterExpression> _loopLocals;
  61
  62         private readonly HybridReferenceDictionary<LabelTarget, BranchLabel> _labelMapping;
  63         private readonly int _loopStartInstructionIndex;
  64         private readonly int _loopEndInstructionIndex;
  65
  66         internal LoopCompiler(LoopExpression loop, HybridReferenceDictionary<LabelTarget, BranchLabel> labelMapping, Dictionary<ParameterExpression, LocalVariable> locals,
  67             Dictionary<ParameterExpression, LocalVariable> closureVariables, int loopStartInstructionIndex, int loopEndInstructionIndex) {
  68             _loop = loop;
  69             _outerVariables = locals;
  70             _closureVariables = closureVariables;
  71             _frameDataVar = Expression.Parameter(typeof(object[]));
  72             _frameClosureVar = Expression.Parameter(typeof(StrongBox<object>[]));
  73             _frameVar = Expression.Parameter(typeof(InterpretedFrame));
  74             _loopVariables = new Dictionary<ParameterExpression, LoopVariable>();
  75             _returnLabel = Expression.Label(typeof(int));
  76             _labelMapping = labelMapping;
  77             _loopStartInstructionIndex = loopStartInstructionIndex;
  78             _loopEndInstructionIndex = loopEndInstructionIndex;
  79         }
  80
  81         internal LoopFunc CreateDelegate() {
  82             var loop = (LoopExpression)Visit(_loop);
  83             var body = new ReadOnlyCollectionBuilder<Expression>();
  84             var finallyClause = new ReadOnlyCollectionBuilder<Expression>();
  85
  86             foreach (var variable in _loopVariables) {
  87                 LocalVariable local;
  88                 if (!_outerVariables.TryGetValue(variable.Key, out local)) {
  89                     local = _closureVariables[variable.Key];
  90                 }
  91                 Expression elemRef = local.LoadFromArray(_frameDataVar, _frameClosureVar);
  92
  93                 if (local.InClosureOrBoxed) {
  94                     var box = variable.Value.BoxStorage;
  95                     Debug.Assert(box != null);
  96                     body.Add(Expression.Assign(box, elemRef));
  97                     AddTemp(box);
  98                 } else {
  99                     // Always initialize the variable even if it is only written to.
 100                     // If a write-only variable is actually not assigned during execution of the loop we will still write some value back.
 101                     // This value must be the original value, which we assign at entry.
 102                     body.Add(Expression.Assign(variable.Key, AstUtils.Convert(elemRef, variable.Key.Type)));
 103
 104                     if ((variable.Value.Access & ExpressionAccess.Write) != 0) {
 105                         finallyClause.Add(Expression.Assign(elemRef, AstUtils.Box(variable.Key)));
 106                     }
 107
 108                     AddTemp(variable.Key);
 109                 }
 110             }
 111
 112             if (finallyClause.Count > 0) {
 113                 body.Add(Expression.TryFinally(loop, Expression.Block(finallyClause)));
 114             } else {
 115                 body.Add(loop);
 116             }
 117
 118             body.Add(Expression.Label(_returnLabel, Expression.Constant(_loopEndInstructionIndex - _loopStartInstructionIndex)));
 119
 120             var lambda = Expression.Lambda<LoopFunc>(
 121                 _temps != null ? Expression.Block(_temps.ToReadOnlyCollection(), body) : Expression.Block(body),
 122                 new[] { _frameDataVar, _frameClosureVar, _frameVar }
 123             );
 124             return lambda.Compile();
 125         }
 126
 127         protected override Expression VisitExtension(Expression node) {
 128             // Reduce extensions before we visit them so that we operate on a plain DLR tree,
 129             // where we know relationships among the nodes (which nodes represent write context etc.).
 130             if (node.CanReduce) {
 131                 return Visit(node.Reduce());
 132             }
 133
 134             return base.VisitExtension(node);
 135         }
 136
 137         #region Gotos
 138
 139         protected override Expression VisitGoto(GotoExpression node) {
 140             BranchLabel label;
 141
 142             var target = node.Target;
 143             var value = Visit(node.Value);
 144
 145             // TODO: Is it possible for an inner reducible node of the loop to rely on nodes produced by reducing outer reducible nodes?
 146
 147             // Unknown label => must be within the loop:
 148             if (!_labelMapping.TryGetValue(target, out label)) {
 149                 return node.Update(target, value);
 150             }
 151
 152             // Known label within the loop:
 153             if (label.TargetIndex >= _loopStartInstructionIndex && label.TargetIndex < _loopEndInstructionIndex) {
 154                 return node.Update(target, value);
 155             }
 156
 157             return Expression.Return(_returnLabel,
 158                 (value != null) ?
 159                     Expression.Call(_frameVar, InterpretedFrame.GotoMethod, Expression.Constant(label.LabelIndex), AstUtils.Box(value)) :
 160                     Expression.Call(_frameVar, InterpretedFrame.VoidGotoMethod, Expression.Constant(label.LabelIndex)),
 161                 node.Type
 162            );
 163         }
 164
 165         #endregion
 166
 167         #region Local Variables
 168
 169         // Gather all outer variables accessed in the loop.
 170         // Determines which ones are read from and written to.
 171         // We will consider a variable as "read" if it is read anywhere in the loop even though
 172         // the first operation might actually always be "write". We could do better if we had CFG.
 173
 174         protected override Expression VisitBlock(BlockExpression node) {
 175             var variables = ((BlockExpression)node).Variables;
 176             var prevLocals = EnterVariableScope(variables);
 177
 178             var res = base.VisitBlock(node);
 179
 180             ExitVariableScope(prevLocals);
 181             return res;
 182         }
 183
 184         private HashSet<ParameterExpression> EnterVariableScope(ICollection<ParameterExpression> variables) {
 185             if (_loopLocals == null) {
 186                 _loopLocals = new HashSet<ParameterExpression>(variables);
 187                 return null;
 188             }
 189
 190             var prevLocals = new HashSet<ParameterExpression>(_loopLocals);
 191             _loopLocals.UnionWith(variables);
 192             return prevLocals;
 193         }
 194
 195         protected override CatchBlock VisitCatchBlock(CatchBlock node) {
 196             if (node.Variable != null) {
 197                 var prevLocals = EnterVariableScope(new[] { node.Variable });
 198                 var res = base.VisitCatchBlock(node);
 199                 ExitVariableScope(prevLocals);
 200                 return res;
 201             } else {
 202                 return base.VisitCatchBlock(node);
 203             }
 204         }
 205
 206         protected override Expression VisitLambda<T>(Expression<T> node) {
 207             var prevLocals = EnterVariableScope(node.Parameters);
 208             try {
 209                 return base.VisitLambda<T>(node);
 210             } finally {
 211                 ExitVariableScope(prevLocals);
 212             }
 213         }
 214
 215         private void ExitVariableScope(HashSet<ParameterExpression> prevLocals) {
 216             _loopLocals = prevLocals;
 217         }
 218
 219         protected override Expression VisitBinary(BinaryExpression node) {
 220             // reduce compound assignments:
 221             if (node.CanReduce) {
 222                 return Visit(node.Reduce());
 223             }
 224             Debug.Assert(!node.NodeType.IsReadWriteAssignment());
 225
 226             var param = node.Left as ParameterExpression;
 227             if (param != null && node.NodeType == ExpressionType.Assign) {
 228                 var left = VisitVariable(param, ExpressionAccess.Write);
 229                 var right = Visit(node.Right);
 230
 231                 // left parameter is a boxed variable:
 232                 if (left.Type != param.Type) {
 233                     Debug.Assert(left.Type == typeof(object));
 234
 235                     Expression rightVar;
 236                     if (right.NodeType != ExpressionType.Parameter) {
 237                         // { left.Value = (object)(rightVar = right), rightVar }
 238                         rightVar = AddTemp(Expression.Parameter(right.Type));
 239                         right = Expression.Assign(rightVar, right);
 240                     } else {
 241                         // { left.Value = (object)right, right }
 242                         rightVar = right;
 243                     }
 244
 245                     return Expression.Block(
 246                         node.Update(left, Expression.Convert(right, left.Type)),
 247                         rightVar
 248                     );
 249                 } else {
 250                     return node.Update(left, right);
 251                 }
 252
 253             } else {
 254                 return base.VisitBinary(node);
 255             }
 256         }
 257
 258         protected override Expression VisitUnary(UnaryExpression node) {
 259             // reduce inplace increment/decrement:
 260             if (node.CanReduce) {
 261                 return Visit(node.Reduce());
 262             }
 263             Debug.Assert(!node.NodeType.IsReadWriteAssignment());
 264             return base.VisitUnary(node);
 265         }
 266
 267         // TODO: if we supported ref/out parameter we would need to override
 268         // MethodCallExpression, VisitDynamic and VisitNew
 269
 270         protected override Expression VisitParameter(ParameterExpression node) {
 271             return VisitVariable(node, ExpressionAccess.Read);
 272         }
 273
 274         private Expression VisitVariable(ParameterExpression node, ExpressionAccess access) {
 275             ParameterExpression box;
 276             LoopVariable existing;
 277             LocalVariable loc;
 278
 279             if (_loopLocals.Contains(node)) {
 280                 // local to the loop - not propagated in or out
 281                 return node;
 282             } else if (_loopVariables.TryGetValue(node, out existing)) {
 283                 // existing outer variable that we are already tracking
 284                 box = existing.BoxStorage;
 285                 _loopVariables[node] = new LoopVariable(existing.Access | access, box);
 286             } else if (_outerVariables.TryGetValue(node, out loc) ||
 287                 (_closureVariables != null && _closureVariables.TryGetValue(node, out loc))) {
 288                 // not tracking this variable yet, but defined in outer scope and seen for the 1st time
 289                 box = loc.InClosureOrBoxed ? Expression.Parameter(typeof(StrongBox<object>), node.Name) : null;
 290                 _loopVariables[node] = new LoopVariable(access, box);
 291             } else {
 292                 // node is a variable defined in a nested lambda -> skip
 293                 return node;
 294             }
 295
 296             if (box != null) {
 297                 if ((access & ExpressionAccess.Write) != 0) {
 298                     // compound assignments were reduced:
 299                     Debug.Assert((access & ExpressionAccess.Read) == 0);
 300
 301                     // box.Value = (object)rhs
 302                     return LightCompiler.Unbox(box);
 303                 } else {
 304                     // (T)box.Value
 305                     return Expression.Convert(LightCompiler.Unbox(box), node.Type);
 306                 }
 307             }
 308
 309             return node;
 310         }
 311
 312         private ParameterExpression AddTemp(ParameterExpression variable) {
 313             if (_temps == null) {
 314                 _temps = new ReadOnlyCollectionBuilder<ParameterExpression>();
 315             }
 316
 317             _temps.Add(variable);
 318             return variable;
 319         }
 320
 321         #endregion
 322     }
 323 }