blob: 2f976cd4ae77baec54be818fe5618317945f0740 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
// Copyright (c) .NET Foundation and contributors. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
using System;
using System.Collections.Generic;
using ILLink.Shared.DataFlow;
using Mono.Linker.Dataflow;
namespace ILLink.Shared.TrimAnalysis
{
// These are extension methods because we want to allow the use of them on null 'this' pointers.
internal static class SingleValueExtensions
{
/// <summary>
/// Returns true if a ValueNode graph contains a cycle
/// </summary>
/// <param name="node">Node to evaluate</param>
/// <param name="seenNodes">Set of nodes previously seen on the current arc. Callers may pass a non-empty set
/// to test whether adding that set to this node would create a cycle. Contents will be modified by the walk
/// and should not be used by the caller after returning</param>
/// <param name="allNodesSeen">Optional. The set of all nodes encountered during a walk after DetectCycle returns</param>
/// <returns></returns>
public static bool DetectCycle (this SingleValue node, HashSet<SingleValue> seenNodes, HashSet<SingleValue>? allNodesSeen)
{
if (node == null)
return false;
if (seenNodes.Contains (node))
return true;
seenNodes.Add (node);
allNodesSeen?.Add (node);
bool foundCycle = false;
switch (node) {
//
// Leaf nodes
//
case UnknownValue:
case NullValue:
case SystemTypeValue:
case RuntimeTypeHandleValue:
case KnownStringValue:
case ConstIntValue:
case MethodParameterValue:
case MethodReturnValue:
case GenericParameterValue:
case RuntimeTypeHandleForGenericParameterValue:
case SystemReflectionMethodBaseValue:
case RuntimeMethodHandleValue:
case FieldValue:
break;
//
// Nodes with children
//
case ArrayValue:
ArrayValue av = (ArrayValue) node;
foundCycle = av.Size.DetectCycle (seenNodes, allNodesSeen);
foreach (ValueBasicBlockPair pair in av.IndexValues.Values) {
foreach (var v in pair.Value) {
foundCycle |= v.DetectCycle (seenNodes, allNodesSeen);
}
}
break;
case RuntimeTypeHandleForNullableValueWithDynamicallyAccessedMembers value:
foundCycle = value.UnderlyingTypeValue.DetectCycle (seenNodes, allNodesSeen);
break;
case NullableValueWithDynamicallyAccessedMembers value:
foundCycle = value.UnderlyingTypeValue.DetectCycle (seenNodes, allNodesSeen);
break;
default:
throw new Exception (String.Format ("Unknown node type: {0}", node.GetType ().Name));
}
seenNodes.Remove (node);
return foundCycle;
}
}
}
|