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