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