mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/LabelInfo.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 #if CODEPLEX_40
  19 using ILGenerator = System.Linq.Expressions.Compiler.OffsetTrackingILGenerator;
  20 #else
  21 using ILGenerator = Microsoft.Linq.Expressions.Compiler.OffsetTrackingILGenerator;
  22 #endif
  23
  24 using System.Collections.Generic;
  25 using System.Diagnostics;
  26 #if CODEPLEX_40
  27 using System.Dynamic.Utils;
  28 #else
  29 using Microsoft.Scripting.Utils;
  30 #endif
  31 using System.Reflection.Emit;
  32
  33 #if CODEPLEX_40
  34 namespace System.Linq.Expressions.Compiler {
  35 #else
  36 namespace Microsoft.Linq.Expressions.Compiler {
  37 #endif
  38
  39     /// <summary>
  40     /// Contains compiler state corresponding to a LabelTarget
  41     /// See also LabelScopeInfo.
  42     /// </summary>
  43     internal sealed class LabelInfo {
  44         // The tree node representing this label
  45         private readonly LabelTarget _node;
  46
  47         // The IL label, will be mutated if Node is redefined
  48         private Label _label;
  49         private bool _labelDefined;
  50
  51         internal Label Label {
  52             get {
  53                 EnsureLabelAndValue();
  54                 return _label;
  55             }
  56         }
  57
  58         // The local that carries the label's value, if any
  59         private LocalBuilder _value;
  60
  61         // The blocks where this label is defined. If it has more than one item,
  62         // the blocks can't be jumped to except from a child block
  63         private readonly Set<LabelScopeInfo> _definitions = new Set<LabelScopeInfo>();
  64
  65         // Blocks that jump to this block
  66         private readonly List<LabelScopeInfo> _references = new List<LabelScopeInfo>();
  67
  68         // True if this label is the last thing in this block
  69         // (meaning we can emit a direct return)
  70         private readonly bool _canReturn;
  71
  72         // True if at least one jump is across blocks
  73         // If we have any jump across blocks to this label, then the
  74         // LabelTarget can only be defined in one place
  75         private bool _acrossBlockJump;
  76
  77         // Until we have more information, default to a leave instruction,
  78         // which always works. Note: leave spills the stack, so we need to
  79         // ensure that StackSpiller has guarenteed us an empty stack at this
  80         // point. Otherwise Leave and Branch are not equivalent
  81         private OpCode _opCode = OpCodes.Leave;
  82
  83         private readonly ILGenerator _ilg;
  84
  85         internal LabelInfo(ILGenerator il, LabelTarget node, bool canReturn) {
  86             _ilg = il;
  87             _node = node;
  88             _canReturn = canReturn;
  89         }
  90
  91         internal bool CanReturn {
  92             get { return _canReturn; }
  93         }
  94
  95         /// <summary>
  96         /// Indicates if it is legal to emit a "branch" instruction based on
  97         /// currently available information. Call the Reference method before
  98         /// using this property.
  99         /// </summary>
 100         internal bool CanBranch {
 101             get { return _opCode != OpCodes.Leave; }
 102         }
 103
 104         internal void Reference(LabelScopeInfo block) {
 105             _references.Add(block);
 106             if (_definitions.Count > 0) {
 107                 ValidateJump(block);
 108             }
 109         }
 110
 111         // Returns true if the label was successfully defined
 112         // or false if the label is now ambiguous
 113         internal void Define(LabelScopeInfo block) {
 114             // Prevent the label from being shadowed, which enforces cleaner
 115             // trees. Also we depend on this for simplicity (keeping only one
 116             // active IL Label per LabelInfo)
 117             for (LabelScopeInfo j = block; j != null; j = j.Parent) {
 118                 if (j.ContainsTarget(_node)) {
 119                     throw Error.LabelTargetAlreadyDefined(_node.Name);
 120                 }
 121             }
 122
 123             _definitions.Add(block);
 124             block.AddLabelInfo(_node, this);
 125
 126             // Once defined, validate all jumps
 127             if (_definitions.Count == 1) {
 128                 foreach (var r in _references) {
 129                     ValidateJump(r);
 130                 }
 131             } else {
 132                 // Was just redefined, if we had any across block jumps, they're
 133                 // now invalid
 134                 if (_acrossBlockJump) {
 135                     throw Error.AmbiguousJump(_node.Name);
 136                 }
 137                 // For local jumps, we need a new IL label
 138                 // This is okay because:
 139                 //   1. no across block jumps have been made or will be made
 140                 //   2. we don't allow the label to be shadowed
 141                 _labelDefined = false;
 142             }
 143         }
 144
 145         private void ValidateJump(LabelScopeInfo reference) {
 146             // Assume we can do a ret/branch
 147             _opCode = _canReturn ? OpCodes.Ret : OpCodes.Br;
 148
 149             // look for a simple jump out
 150             for (LabelScopeInfo j = reference; j != null; j = j.Parent) {
 151                 if (_definitions.Contains(j)) {
 152                     // found it, jump is valid!
 153                     return;
 154                 }
 155                 if (j.Kind == LabelScopeKind.Finally ||
 156                     j.Kind == LabelScopeKind.Filter) {
 157                     break;
 158                 }
 159                 if (j.Kind == LabelScopeKind.Try ||
 160                     j.Kind == LabelScopeKind.Catch) {
 161                     _opCode = OpCodes.Leave;
 162                 }
 163             }
 164
 165             _acrossBlockJump = true;
 166             if (_node != null && _node.Type != typeof(void)) {
 167                 throw Error.NonLocalJumpWithValue(_node.Name);
 168             }
 169
 170             if (_definitions.Count > 1) {
 171                 throw Error.AmbiguousJump(_node.Name);
 172             }
 173
 174             // We didn't find an outward jump. Look for a jump across blocks
 175             LabelScopeInfo def = _definitions.First();
 176             LabelScopeInfo common = Helpers.CommonNode(def, reference, b => b.Parent);
 177
 178             // Assume we can do a ret/branch
 179             _opCode = _canReturn ? OpCodes.Ret : OpCodes.Br;
 180
 181             // Validate that we aren't jumping across a finally
 182             for (LabelScopeInfo j = reference; j != common; j = j.Parent) {
 183                 if (j.Kind == LabelScopeKind.Finally) {
 184                     throw Error.ControlCannotLeaveFinally();
 185                 }
 186                 if (j.Kind == LabelScopeKind.Filter) {
 187                     throw Error.ControlCannotLeaveFilterTest();
 188                 }
 189                 if (j.Kind == LabelScopeKind.Try ||
 190                     j.Kind == LabelScopeKind.Catch) {
 191                     _opCode = OpCodes.Leave;
 192                 }
 193             }
 194
 195             // Valdiate that we aren't jumping into a catch or an expression
 196             for (LabelScopeInfo j = def; j != common; j = j.Parent) {
 197                 if (!j.CanJumpInto) {
 198                     if (j.Kind == LabelScopeKind.Expression) {
 199                         throw Error.ControlCannotEnterExpression();
 200                     } else {
 201                         throw Error.ControlCannotEnterTry();
 202                     }
 203                 }
 204             }
 205         }
 206
 207         internal void ValidateFinish() {
 208             // Make sure that if this label was jumped to, it is also defined
 209             if (_references.Count > 0 && _definitions.Count == 0) {
 210                 throw Error.LabelTargetUndefined(_node.Name);
 211             }
 212         }
 213
 214         internal void EmitJump() {
 215             // Return directly if we can
 216             if (_opCode == OpCodes.Ret) {
 217                 _ilg.Emit(OpCodes.Ret);
 218             } else {
 219                 StoreValue();
 220                 _ilg.Emit(_opCode, Label);
 221             }
 222         }
 223
 224         private void StoreValue() {
 225             EnsureLabelAndValue();
 226             if (_value != null) {
 227                 _ilg.Emit(OpCodes.Stloc, _value);
 228             }
 229         }
 230
 231         internal void Mark() {
 232             if (_canReturn) {
 233                 // Don't mark return labels unless they were actually jumped to
 234                 // (returns are last so we know for sure if anyone jumped to it)
 235                 if (!_labelDefined) {
 236                     // We don't even need to emit the "ret" because
 237                     // LambdaCompiler does that for us.
 238                     return;
 239                 }
 240
 241                 // Otherwise, emit something like:
 242                 // ret
 243                 // <marked label>:
 244                 // ldloc <value>
 245                 _ilg.Emit(OpCodes.Ret);
 246             } else {
 247
 248                 // For the normal case, we emit:
 249                 // stloc <value>
 250                 // <marked label>:
 251                 // ldloc <value>
 252                 StoreValue();
 253             }
 254             MarkWithEmptyStack();
 255         }
 256
 257         // Like Mark, but assumes the stack is empty
 258         internal void MarkWithEmptyStack() {
 259             _ilg.MarkLabel(Label);
 260             if (_value != null) {
 261                 // We always read the value from a local, because we don't know
 262                 // if there will be a "leave" instruction targeting it ("branch"
 263                 // preserves its stack, but "leave" empties the stack)
 264                 _ilg.Emit(OpCodes.Ldloc, _value);
 265             }
 266         }
 267
 268         private void EnsureLabelAndValue() {
 269             if (!_labelDefined) {
 270                 _labelDefined = true;
 271                 _label = _ilg.DefineLabel();
 272                 if (_node != null && _node.Type != typeof(void)) {
 273                     _value = _ilg.DeclareLocal(_node.Type);
 274                 }
 275             }
 276         }
 277     }
 278
 279     internal enum LabelScopeKind {
 280         // any "statement like" node that can be jumped into
 281         Statement,
 282
 283         // these correspond to the node of the same name
 284         Block,
 285         Switch,
 286         Lambda,
 287         Try,
 288
 289         // these correspond to the part of the try block we're in
 290         Catch,
 291         Finally,
 292         Filter,
 293
 294         // the catch-all value for any other expression type
 295         // (means we can't jump into it)
 296         Expression,
 297     }
 298
 299     //
 300     // Tracks scoping information for LabelTargets. Logically corresponds to a
 301     // "label scope". Even though we have arbitrary goto support, we still need
 302     // to track what kinds of nodes that gotos are jumping through, both to
 303     // emit property IL ("leave" out of a try block), and for validation, and
 304     // to allow labels to be duplicated in the tree, as long as the jumps are
 305     // considered "up only" jumps.
 306     //
 307     // We create one of these for every Expression that can be jumped into, as
 308     // well as creating them for the first expression we can't jump into. The
 309     // "Kind" property indicates what kind of scope this is.
 310     //
 311     internal sealed class LabelScopeInfo {
 312         private Dictionary<LabelTarget, LabelInfo> Labels; // lazily allocated, we typically use this only once every 6th-7th block
 313         internal readonly LabelScopeKind Kind;
 314         internal readonly LabelScopeInfo Parent;
 315
 316         internal LabelScopeInfo(LabelScopeInfo parent, LabelScopeKind kind) {
 317             Parent = parent;
 318             Kind = kind;
 319         }
 320
 321         /// <summary>
 322         /// Returns true if we can jump into this node
 323         /// </summary>
 324         internal bool CanJumpInto {
 325             get {
 326                 switch (Kind) {
 327                     case LabelScopeKind.Block:
 328                     case LabelScopeKind.Statement:
 329                     case LabelScopeKind.Switch:
 330                     case LabelScopeKind.Lambda:
 331                         return true;
 332                 }
 333                 return false;
 334             }
 335         }
 336
 337
 338         internal bool ContainsTarget(LabelTarget target) {
 339             if (Labels == null) {
 340                 return false;
 341             }
 342
 343             return Labels.ContainsKey(target);
 344         }
 345
 346         internal bool TryGetLabelInfo(LabelTarget target, out LabelInfo info) {
 347             if (Labels == null) {
 348                 info = null;
 349                 return false;
 350             }
 351
 352             return Labels.TryGetValue(target, out info);
 353         }
 354
 355         internal void AddLabelInfo(LabelTarget target, LabelInfo info) {
 356             Debug.Assert(CanJumpInto);
 357
 358             if (Labels == null) {
 359                 Labels = new Dictionary<LabelTarget, LabelInfo>();
 360             }
 361
 362             Labels.Add(target, info);
 363         }
 364     }
 365 }