mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/CompilerScope.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Microsoft Public License. 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  Microsoft Public License, 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 Microsoft Public License.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15 using System; using Microsoft;
  16
  17
  18 using System.Collections.Generic;
  19 using System.Collections.ObjectModel;
  20 using System.Diagnostics;
  21 using System.Reflection.Emit;
  22 using System.Runtime.CompilerServices;
  23 #if !CODEPLEX_40
  24 using Microsoft.Runtime.CompilerServices;
  25 #endif
  26
  27 #if CODEPLEX_40
  28 using System.Dynamic;
  29 using System.Dynamic.Utils;
  30 #else
  31 using Microsoft.Scripting;
  32 using Microsoft.Scripting.Utils;
  33 #endif
  34
  35 #if CODEPLEX_40
  36 namespace System.Linq.Expressions.Compiler {
  37 #else
  38 namespace Microsoft.Linq.Expressions.Compiler {
  39 #endif
  40     internal enum VariableStorageKind {
  41         Local,
  42         Hoisted
  43     }
  44
  45     /// <summary>
  46     /// CompilerScope is the data structure which the Compiler keeps information
  47     /// related to compiling scopes. It stores the following information:
  48     ///   1. Parent relationship (for resolving variables)
  49     ///   2. Information about hoisted variables
  50     ///   3. Information for resolving closures
  51     ///
  52     /// Instances are produced by VariableBinder, which does a tree walk
  53     /// looking for scope nodes: LambdaExpression and BlockExpression.
  54     /// </summary>
  55     internal sealed partial class CompilerScope {
  56         /// <summary>
  57         /// parent scope, if any
  58         /// </summary>
  59         private CompilerScope _parent;
  60
  61         /// <summary>
  62         /// The expression node for this scope
  63         /// Can be LambdaExpression, BlockExpression, or CatchBlock
  64         /// </summary>
  65         internal readonly object Node;
  66
  67         /// <summary>
  68         /// True if this node corresponds to an IL method.
  69         /// Can only be true if the Node is a LambdaExpression.
  70         /// But inlined lambdas will have it set to false.
  71         /// </summary>
  72         internal readonly bool IsMethod;
  73
  74         /// <summary>
  75         /// Does this scope (or any inner scope) close over variables from any
  76         /// parent scope?
  77         /// Populated by VariableBinder
  78         /// </summary>
  79         internal bool NeedsClosure;
  80
  81         /// <summary>
  82         /// Variables defined in this scope, and whether they're hoisted or not
  83         /// Populated by VariableBinder
  84         /// </summary>
  85         internal readonly Dictionary<ParameterExpression, VariableStorageKind> Definitions = new Dictionary<ParameterExpression, VariableStorageKind>();
  86
  87         /// <summary>
  88         /// Each variable referenced within this scope, and how often it was referenced
  89         /// Populated by VariableBinder
  90         /// </summary>
  91         internal Dictionary<ParameterExpression, int> ReferenceCount;
  92
  93         /// <summary>
  94         /// Scopes whose variables were merged into this one
  95         ///
  96         /// Created lazily as we create hundreds of compiler scopes w/o merging scopes when compiling rules.
  97         /// </summary>
  98         internal Set<object> MergedScopes;
  99
 100         /// <summary>
 101         /// The scope's hoisted locals, if any.
 102         /// Provides storage for variables that are referenced from nested lambdas
 103         /// </summary>
 104         private HoistedLocals _hoistedLocals;
 105
 106         /// <summary>
 107         /// The closed over hoisted locals
 108         /// </summary>
 109         private HoistedLocals _closureHoistedLocals;
 110
 111         /// <summary>
 112         /// Mutable dictionary that maps non-hoisted variables to either local
 113         /// slots or argument slots
 114         /// </summary>
 115         private readonly Dictionary<ParameterExpression, Storage> _locals = new Dictionary<ParameterExpression, Storage>();
 116
 117         internal CompilerScope(object node, bool isMethod) {
 118             Node = node;
 119             IsMethod = isMethod;
 120             var variables = GetVariables(node);
 121
 122             Definitions = new Dictionary<ParameterExpression, VariableStorageKind>(variables.Count);
 123             foreach (var v in variables) {
 124                 Definitions.Add(v, VariableStorageKind.Local);
 125             }
 126         }
 127
 128         /// <summary>
 129         /// This scope's hoisted locals, or the closed over locals, if any
 130         /// Equivalent to: _hoistedLocals ?? _closureHoistedLocals
 131         /// </summary>
 132         internal HoistedLocals NearestHoistedLocals {
 133             get { return _hoistedLocals ?? _closureHoistedLocals; }
 134         }
 135
 136         /// <summary>
 137         /// Called when entering a lambda/block. Performs all variable allocation
 138         /// needed, including creating hoisted locals and IL locals for accessing
 139         /// parent locals
 140         /// </summary>
 141         internal CompilerScope Enter(LambdaCompiler lc, CompilerScope parent) {
 142             SetParent(lc, parent);
 143
 144             AllocateLocals(lc);
 145
 146             if (IsMethod && _closureHoistedLocals != null) {
 147                 EmitClosureAccess(lc, _closureHoistedLocals);
 148             }
 149
 150             EmitNewHoistedLocals(lc);
 151
 152             if (IsMethod) {
 153                 EmitCachedVariables();
 154             }
 155
 156             return this;
 157         }
 158
 159         /// <summary>
 160         /// Frees unnamed locals, clears state associated with this compiler
 161         /// </summary>
 162         internal CompilerScope Exit() {
 163             // free scope's variables
 164             if (!IsMethod) {
 165                 foreach (Storage storage in _locals.Values) {
 166                     storage.FreeLocal();
 167                 }
 168             }
 169
 170             // Clear state that is associated with this parent
 171             // (because the scope can be reused in another context)
 172             CompilerScope parent = _parent;
 173             _parent = null;
 174             _hoistedLocals = null;
 175             _closureHoistedLocals = null;
 176             _locals.Clear();
 177
 178             return parent;
 179         }
 180
 181         #region LocalScopeExpression support
 182
 183         internal void EmitVariableAccess(LambdaCompiler lc, ReadOnlyCollection<ParameterExpression> vars) {
 184             if (NearestHoistedLocals != null) {
 185                 // Find what array each variable is on & its index
 186                 var indexes = new List<long>(vars.Count);
 187
 188                 foreach (var variable in vars) {
 189                     // For each variable, find what array it's defined on
 190                     ulong parents = 0;
 191                     HoistedLocals locals = NearestHoistedLocals;
 192                     while (!locals.Indexes.ContainsKey(variable)) {
 193                         parents++;
 194                         locals = locals.Parent;
 195                         Debug.Assert(locals != null);
 196                     }
 197
 198                     // combine the number of parents we walked, with the
 199                     // real index of variable to get the index to emit.
 200                     ulong index = (parents << 32) | (uint)locals.Indexes[variable];
 201
 202                     indexes.Add((long)index);
 203                 }
 204
 205                 if (indexes.Count > 0) {
 206                     EmitGet(NearestHoistedLocals.SelfVariable);
 207                     lc.EmitConstantArray(indexes.ToArray());
 208                     lc.IL.Emit(OpCodes.Call, typeof(RuntimeOps).GetMethod("CreateRuntimeVariables", new[] { typeof(object[]), typeof(long[]) }));
 209                     return;
 210                 }
 211             }
 212
 213             // No visible variables
 214             lc.IL.Emit(OpCodes.Call, typeof(RuntimeOps).GetMethod("CreateRuntimeVariables", Type.EmptyTypes));
 215             return;
 216         }
 217
 218         #endregion
 219
 220         #region Variable access
 221
 222         /// <summary>
 223         /// Adds a new virtual variable corresponding to an IL local
 224         /// </summary>
 225         internal void AddLocal(LambdaCompiler gen, ParameterExpression variable) {
 226             _locals.Add(variable, new LocalStorage(gen, variable));
 227         }
 228
 229         internal void EmitGet(ParameterExpression variable) {
 230             ResolveVariable(variable).EmitLoad();
 231         }
 232
 233         internal void EmitSet(ParameterExpression variable) {
 234             ResolveVariable(variable).EmitStore();
 235         }
 236
 237         internal void EmitAddressOf(ParameterExpression variable) {
 238             ResolveVariable(variable).EmitAddress();
 239         }
 240
 241         private Storage ResolveVariable(ParameterExpression variable) {
 242             return ResolveVariable(variable, NearestHoistedLocals);
 243         }
 244
 245         /// <summary>
 246         /// Resolve a local variable in this scope or a closed over scope
 247         /// Throws if the variable is defined
 248         /// </summary>
 249         private Storage ResolveVariable(ParameterExpression variable, HoistedLocals hoistedLocals) {
 250             // Search IL locals and arguments, but only in this lambda
 251             for (CompilerScope s = this; s != null; s = s._parent) {
 252                 Storage storage;
 253                 if (s._locals.TryGetValue(variable, out storage)) {
 254                     return storage;
 255                 }
 256
 257                 // if this is a lambda, we're done
 258                 if (s.IsMethod) {
 259                     break;
 260                 }
 261             }
 262
 263             // search hoisted locals
 264             for (HoistedLocals h = hoistedLocals; h != null; h = h.Parent) {
 265                 int index;
 266                 if (h.Indexes.TryGetValue(variable, out index)) {
 267                     return new ElementBoxStorage(
 268                         ResolveVariable(h.SelfVariable, hoistedLocals),
 269                         index,
 270                         variable
 271                     );
 272                 }
 273             }
 274
 275             //
 276             // If this is an unbound variable in the lambda, the error will be
 277             // thrown from VariableBinder. So an error here is generally caused
 278             // by an internal error, e.g. a scope was created but it bypassed
 279             // VariableBinder.
 280             //
 281             throw Error.UndefinedVariable(variable.Name, variable.Type, CurrentLambdaName);
 282         }
 283
 284         #endregion
 285
 286         private void SetParent(LambdaCompiler lc, CompilerScope parent) {
 287             Debug.Assert(_parent == null && parent != this);
 288             _parent = parent;
 289
 290             if (NeedsClosure && _parent != null) {
 291                 _closureHoistedLocals = _parent.NearestHoistedLocals;
 292             }
 293
 294             var hoistedVars = GetVariables().Where(p => Definitions[p] == VariableStorageKind.Hoisted).ToReadOnly();
 295
 296             if (hoistedVars.Count > 0) {
 297                 _hoistedLocals = new HoistedLocals(_closureHoistedLocals, hoistedVars);
 298                 AddLocal(lc, _hoistedLocals.SelfVariable);
 299             }
 300         }
 301
 302         // Emits creation of the hoisted local storage
 303         private void EmitNewHoistedLocals(LambdaCompiler lc) {
 304             if (_hoistedLocals == null) {
 305                 return;
 306             }
 307
 308             // create the array
 309             lc.IL.EmitInt(_hoistedLocals.Variables.Count);
 310             lc.IL.Emit(OpCodes.Newarr, typeof(object));
 311
 312             // initialize all elements
 313             int i = 0;
 314             foreach (ParameterExpression v in _hoistedLocals.Variables) {
 315                 // array[i] = new StrongBox<T>(...);
 316                 lc.IL.Emit(OpCodes.Dup);
 317                 lc.IL.EmitInt(i++);
 318                 Type boxType = typeof(StrongBox<>).MakeGenericType(v.Type);
 319
 320                 if (IsMethod && lc.Parameters.Contains(v)) {
 321                     // array[i] = new StrongBox<T>(argument);
 322                     int index = lc.Parameters.IndexOf(v);
 323                     lc.EmitLambdaArgument(index);
 324                     lc.IL.Emit(OpCodes.Newobj, boxType.GetConstructor(new Type[] { v.Type }));
 325                 } else if (v == _hoistedLocals.ParentVariable) {
 326                     // array[i] = new StrongBox<T>(closure.Locals);
 327                     ResolveVariable(v, _closureHoistedLocals).EmitLoad();
 328                     lc.IL.Emit(OpCodes.Newobj, boxType.GetConstructor(new Type[] { v.Type }));
 329                 } else {
 330                     // array[i] = new StrongBox<T>();
 331                     lc.IL.Emit(OpCodes.Newobj, boxType.GetConstructor(Type.EmptyTypes));
 332                 }
 333                 // if we want to cache this into a local, do it now
 334                 if (ShouldCache(v)) {
 335                     lc.IL.Emit(OpCodes.Dup);
 336                     CacheBoxToLocal(lc, v);
 337                 }
 338                 lc.IL.Emit(OpCodes.Stelem_Ref);
 339             }
 340
 341             // store it
 342             EmitSet(_hoistedLocals.SelfVariable);
 343         }
 344
 345         // If hoisted variables are referenced "enough", we cache the
 346         // StrongBox<T> in an IL local, which saves an array index and a cast
 347         // when we go to look it up later
 348         private void EmitCachedVariables() {
 349             if (ReferenceCount == null) {
 350                 return;
 351             }
 352
 353             foreach (var refCount in ReferenceCount) {
 354                 if (ShouldCache(refCount.Key, refCount.Value)) {
 355                     var storage = ResolveVariable(refCount.Key) as ElementBoxStorage;
 356                     if (storage != null) {
 357                         storage.EmitLoadBox();
 358                         CacheBoxToLocal(storage.Compiler, refCount.Key);
 359                     }
 360                 }
 361             }
 362         }
 363
 364         private bool ShouldCache(ParameterExpression v, int refCount) {
 365             // This caching is too aggressive in the face of conditionals and
 366             // switch. Also, it is too conservative for variables used inside
 367             // of loops.
 368             return refCount > 2 && !_locals.ContainsKey(v);
 369         }
 370
 371         private bool ShouldCache(ParameterExpression v) {
 372             if (ReferenceCount == null) {
 373                 return false;
 374             }
 375
 376             int refCount;
 377             return ReferenceCount.TryGetValue(v, out refCount) && ShouldCache(v, refCount);
 378         }
 379
 380         private void CacheBoxToLocal(LambdaCompiler lc, ParameterExpression v) {
 381             Debug.Assert(ShouldCache(v) && !_locals.ContainsKey(v));
 382             var local = new LocalBoxStorage(lc, v);
 383             local.EmitStoreBox();
 384             _locals.Add(v, local);
 385         }
 386
 387         // Creates IL locals for accessing closures
 388         private void EmitClosureAccess(LambdaCompiler lc, HoistedLocals locals) {
 389             if (locals == null) {
 390                 return;
 391             }
 392
 393             EmitClosureToVariable(lc, locals);
 394
 395             while ((locals = locals.Parent) != null) {
 396                 var v =  locals.SelfVariable;
 397                 var local = new LocalStorage(lc, v);
 398                 local.EmitStore(ResolveVariable(v));
 399                 _locals.Add(v, local);
 400             }
 401         }
 402
 403         private void EmitClosureToVariable(LambdaCompiler lc, HoistedLocals locals) {
 404             lc.EmitClosureArgument();
 405             lc.IL.Emit(OpCodes.Ldfld, typeof(Closure).GetField("Locals"));
 406             AddLocal(lc, locals.SelfVariable);
 407             EmitSet(locals.SelfVariable);
 408         }
 409
 410         // Allocates slots for IL locals or IL arguments
 411         private void AllocateLocals(LambdaCompiler lc) {
 412             foreach (ParameterExpression v in GetVariables()) {
 413                 if (Definitions[v] == VariableStorageKind.Local) {
 414                     //
 415                     // If v is in lc.Parameters, it is a parameter.
 416                     // Otherwise, it is a local variable.
 417                     //
 418                     // Also, for inlined lambdas we'll create a local, which
 419                     // is possibly a byref local if the parameter is byref.
 420                     //
 421                     Storage s;
 422                     if (IsMethod && lc.Parameters.Contains(v)) {
 423                         s = new ArgumentStorage(lc, v);
 424                     } else {
 425                         s = new LocalStorage(lc, v);
 426                     }
 427                     _locals.Add(v, s);
 428                 }
 429             }
 430         }
 431
 432         private IList<ParameterExpression> GetVariables() {
 433             var vars = GetVariables(Node);
 434             if (MergedScopes == null) {
 435                 return vars;
 436             }
 437             var list = new List<ParameterExpression>(vars);
 438             foreach (var scope in MergedScopes) {
 439                 list.AddRange(GetVariables(scope));
 440             }
 441             return list;
 442         }
 443
 444         private static IList<ParameterExpression> GetVariables(object scope) {
 445             var lambda = scope as LambdaExpression;
 446             if (lambda != null) {
 447                 return lambda.Parameters;
 448             }
 449             var block = scope as BlockExpression;
 450             if (block != null) {
 451                 return block.Variables;
 452             }
 453             return new[] { ((CatchBlock)scope).Variable };
 454         }
 455
 456         private string CurrentLambdaName {
 457             get {
 458                 CompilerScope s = this;
 459                 while (true) {
 460                     var lambda = s.Node as LambdaExpression;
 461                     if (lambda != null) {
 462                         return lambda.Name;
 463                     }
 464                 }
 465             }
 466         }
 467     }
 468 }