mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/StackSpiller.Temps.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 #if CODEPLEX_40
  22 using System.Dynamic.Utils;
  23 #else
  24 using Microsoft.Scripting.Utils;
  25 #endif
  26
  27 #if CODEPLEX_40
  28 namespace System.Linq.Expressions.Compiler {
  29 #else
  30 namespace Microsoft.Linq.Expressions.Compiler {
  31 #endif
  32
  33     internal partial class StackSpiller {
  34
  35         private class TempMaker {
  36             /// <summary>
  37             /// Current temporary variable
  38             /// </summary>
  39             private int _temp;
  40
  41             /// <summary>
  42             /// List of free temporary variables. These can be recycled for new temps.
  43             /// </summary>
  44             private List<ParameterExpression> _freeTemps;
  45
  46             /// <summary>
  47             /// Stack of currently active temporary variables.
  48             /// </summary>
  49             private Stack<ParameterExpression> _usedTemps;
  50
  51             /// <summary>
  52             /// List of all temps created by stackspiller for this rule/lambda
  53             /// </summary>
  54             private List<ParameterExpression> _temps = new List<ParameterExpression>();
  55
  56             internal List<ParameterExpression> Temps {
  57                 get { return _temps; }
  58             }
  59
  60             internal ParameterExpression Temp(Type type) {
  61                 ParameterExpression temp;
  62                 if (_freeTemps != null) {
  63                     // Recycle from the free-list if possible.
  64                     for (int i = _freeTemps.Count - 1; i >= 0; i--) {
  65                         temp = _freeTemps[i];
  66                         if (temp.Type == type) {
  67                             _freeTemps.RemoveAt(i);
  68                             return UseTemp(temp);
  69                         }
  70                     }
  71                 }
  72                 // Not on the free-list, create a brand new one.
  73                 temp = Expression.Variable(type, "$temp$" + _temp++);
  74                 _temps.Add(temp);
  75                 return UseTemp(temp);
  76             }
  77
  78             private ParameterExpression UseTemp(ParameterExpression temp) {
  79                 Debug.Assert(_freeTemps == null || !_freeTemps.Contains(temp));
  80                 Debug.Assert(_usedTemps == null || !_usedTemps.Contains(temp));
  81
  82                 if (_usedTemps == null) {
  83                     _usedTemps = new Stack<ParameterExpression>();
  84                 }
  85                 _usedTemps.Push(temp);
  86                 return temp;
  87             }
  88
  89             private void FreeTemp(ParameterExpression temp) {
  90                 Debug.Assert(_freeTemps == null || !_freeTemps.Contains(temp));
  91                 if (_freeTemps == null) {
  92                     _freeTemps = new List<ParameterExpression>();
  93                 }
  94                 _freeTemps.Add(temp);
  95             }
  96
  97             internal int Mark() {
  98                 return _usedTemps != null ? _usedTemps.Count : 0;
  99             }
 100
 101             // Free temporaries created since the last marking.
 102             // This is a performance optimization to lower the overall number of tempories needed.
 103             internal void Free(int mark) {
 104                 // (_usedTemps != null) ==> (mark <= _usedTemps.Count)
 105                 Debug.Assert(_usedTemps == null || mark <= _usedTemps.Count);
 106                 // (_usedTemps == null) ==> (mark == 0)
 107                 Debug.Assert(mark == 0 || _usedTemps != null);
 108
 109                 if (_usedTemps != null) {
 110                     while (mark < _usedTemps.Count) {
 111                         FreeTemp(_usedTemps.Pop());
 112                     }
 113                 }
 114             }
 115
 116             [Conditional("DEBUG")]
 117             [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
 118             internal void VerifyTemps() {
 119                 Debug.Assert(_usedTemps == null || _usedTemps.Count == 0);
 120             }
 121         }
 122
 123
 124         /// <summary>
 125         /// Rewrites child expressions, spilling them into temps if needed. The
 126         /// stack starts in the inital state, and after the first subexpression
 127         /// is added it is change to non-empty. This behavior can be overridden
 128         /// by setting the stack manually between adds.
 129         ///
 130         /// When all children have been added, the caller should rewrite the
 131         /// node if Rewrite is true. Then, it should call Finish with etiher
 132         /// the orignal expression or the rewritten expression. Finish will call
 133         /// Expression.Comma if necessary and return a new Result.
 134         /// </summary>
 135         private class ChildRewriter {
 136             private readonly StackSpiller _self;
 137             private readonly Expression[] _expressions;
 138             private int _expressionsCount;
 139             private List<Expression> _comma;
 140             private RewriteAction _action;
 141             private Stack _stack;
 142             private bool _done;
 143
 144             internal ChildRewriter(StackSpiller self, Stack stack, int count) {
 145                 _self = self;
 146                 _stack = stack;
 147                 _expressions = new Expression[count];
 148             }
 149
 150             internal void Add(Expression node) {
 151                 Debug.Assert(!_done);
 152
 153                 if (node == null) {
 154                     _expressions[_expressionsCount++] = null;
 155                     return;
 156                 }
 157
 158                 Result exp = _self.RewriteExpression(node, _stack);
 159                 _action |= exp.Action;
 160                 _stack = Stack.NonEmpty;
 161
 162                 // track items in case we need to copy or spill stack
 163                 _expressions[_expressionsCount++] = exp.Node;
 164             }
 165
 166             internal void Add(IList<Expression> expressions) {
 167                 for (int i = 0, count = expressions.Count; i < count; i++) {
 168                     Add(expressions[i]);
 169                 }
 170             }
 171
 172             internal void AddArguments(IArgumentProvider expressions) {
 173                 for (int i = 0, count = expressions.ArgumentCount; i < count; i++) {
 174                     Add(expressions.GetArgument(i));
 175                 }
 176             }
 177
 178             private void EnsureDone() {
 179                 // done adding arguments, build the comma if necessary
 180                 if (!_done) {
 181                     _done = true;
 182
 183                     if (_action == RewriteAction.SpillStack) {
 184                         Expression[] clone = _expressions;
 185                         int count = clone.Length;
 186                         List<Expression> comma = new List<Expression>(count + 1);
 187                         for (int i = 0; i < count; i++) {
 188                             if (clone[i] != null) {
 189                                 Expression temp;
 190                                 clone[i] = _self.ToTemp(clone[i], out temp);
 191                                 comma.Add(temp);
 192                             }
 193                         }
 194                         comma.Capacity = comma.Count + 1;
 195                         _comma = comma;
 196                     }
 197                 }
 198             }
 199
 200             internal bool Rewrite {
 201                 get { return _action != RewriteAction.None; }
 202             }
 203
 204             internal RewriteAction Action {
 205                 get { return _action; }
 206             }
 207
 208             internal Result Finish(Expression expr) {
 209                 EnsureDone();
 210
 211                 if (_action == RewriteAction.SpillStack) {
 212                     Debug.Assert(_comma.Capacity == _comma.Count + 1);
 213                     _comma.Add(expr);
 214                     expr = MakeBlock(_comma);
 215                 }
 216
 217                 return new Result(_action, expr);
 218             }
 219
 220             internal Expression this[int index] {
 221                 get {
 222                     EnsureDone();
 223                     if (index < 0) {
 224                         index += _expressions.Length;
 225                     }
 226                     return _expressions[index];
 227                 }
 228             }
 229
 230             internal Expression[] this[int first, int last] {
 231                 get {
 232                     EnsureDone();
 233                     if (last < 0) {
 234                         last += _expressions.Length;
 235                     }
 236                     int count = last - first + 1;
 237                     ContractUtils.RequiresArrayRange(_expressions, first, count, "first", "last");
 238
 239                     if (count == _expressions.Length) {
 240                         Debug.Assert(first == 0);
 241                         // if the entire array is requested just return it so we don't make a new array
 242                         return _expressions;
 243                     }
 244
 245                     Expression[] clone = new Expression[count];
 246                     Array.Copy(_expressions, first, clone, 0, count);
 247                     return clone;
 248                 }
 249             }
 250         }
 251
 252
 253         private ParameterExpression MakeTemp(Type type) {
 254             return _tm.Temp(type);
 255         }
 256
 257         private int Mark() {
 258             return _tm.Mark();
 259         }
 260
 261         private void Free(int mark) {
 262             _tm.Free(mark);
 263         }
 264
 265         [Conditional("DEBUG")]
 266         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
 267         private void VerifyTemps() {
 268             _tm.VerifyTemps();
 269         }
 270
 271         /// <summary>
 272         /// Will perform:
 273         ///     save: temp = expression
 274         ///     return value: temp
 275         /// </summary>
 276         private ParameterExpression ToTemp(Expression expression, out Expression save) {
 277             ParameterExpression temp = MakeTemp(expression.Type);
 278             save = Expression.Assign(temp, expression);
 279             return temp;
 280         }
 281
 282         /// <summary>
 283         /// Creates a special block that is marked as not allowing jumps in.
 284         /// This should not be used for rewriting BlockExpression itself, or
 285         /// anything else that supports jumping.
 286         /// </summary>
 287         private static Expression MakeBlock(params Expression[] expressions) {
 288             return MakeBlock((IList<Expression>)expressions);
 289         }
 290
 291         /// <summary>
 292         /// Creates a special block that is marked as not allowing jumps in.
 293         /// This should not be used for rewriting BlockExpression itself, or
 294         /// anything else that supports jumping.
 295         /// </summary>
 296         private static Expression MakeBlock(IList<Expression> expressions) {
 297             return new SpilledExpressionBlock(expressions);
 298         }
 299     }
 300
 301     /// <summary>
 302     /// A special subtype of BlockExpression that indicates to the compiler
 303     /// that this block is a spilled expression and should not allow jumps in.
 304     /// </summary>
 305     internal sealed class SpilledExpressionBlock : BlockN {
 306         internal SpilledExpressionBlock(IList<Expression> expressions)
 307             : base(expressions) {
 308         }
 309         internal override BlockExpression Rewrite(ReadOnlyCollection<ParameterExpression> variables, Expression[] args) {
 310             throw ContractUtils.Unreachable;
 311         }
 312     }
 313 }