1  using System;
  2  using System.Collections.Generic;
  3  using System.Runtime.CompilerServices;
  4  
  5  namespace ARMeilleure.IntermediateRepresentation
  6  {
  7      class BasicBlock : IEquatable<BasicBlock>, IIntrusiveListNode<BasicBlock>
  8      {
  9          private const uint MaxSuccessors = 2;
 10  
 11          private int _succCount;
 12          private BasicBlock _succ0;
 13          private readonly BasicBlock _succ1;
 14          private HashSet<BasicBlock> _domFrontiers;
 15  
 16          public int Index { get; set; }
 17          public BasicBlockFrequency Frequency { get; set; }
 18          public BasicBlock ListPrevious { get; set; }
 19          public BasicBlock ListNext { get; set; }
 20          public IntrusiveList<Operation> Operations { get; }
 21          public List<BasicBlock> Predecessors { get; }
 22          public BasicBlock ImmediateDominator { get; set; }
 23  
 24          public int SuccessorsCount => _succCount;
 25  
 26          public HashSet<BasicBlock> DominanceFrontiers
 27          {
 28              get
 29              {
 30                  _domFrontiers ??= new HashSet<BasicBlock>();
 31  
 32                  return _domFrontiers;
 33              }
 34          }
 35  
 36          public BasicBlock() : this(index: -1) { }
 37  
 38          public BasicBlock(int index)
 39          {
 40              Operations = new IntrusiveList<Operation>();
 41              Predecessors = new List<BasicBlock>();
 42  
 43              Index = index;
 44          }
 45  
 46          public void AddSuccessor(BasicBlock block)
 47          {
 48              ArgumentNullException.ThrowIfNull(block);
 49  
 50              if ((uint)_succCount + 1 > MaxSuccessors)
 51              {
 52                  ThrowSuccessorOverflow();
 53              }
 54  
 55              block.Predecessors.Add(this);
 56  
 57              GetSuccessorUnsafe(_succCount++) = block;
 58          }
 59  
 60          public void RemoveSuccessor(int index)
 61          {
 62              if ((uint)index >= (uint)_succCount)
 63              {
 64                  ThrowOutOfRange(nameof(index));
 65              }
 66  
 67              ref BasicBlock oldBlock = ref GetSuccessorUnsafe(index);
 68  
 69              oldBlock.Predecessors.Remove(this);
 70              oldBlock = null;
 71  
 72              if (index == 0)
 73              {
 74                  _succ0 = _succ1;
 75              }
 76  
 77              _succCount--;
 78          }
 79  
 80          public BasicBlock GetSuccessor(int index)
 81          {
 82              if ((uint)index >= (uint)_succCount)
 83              {
 84                  ThrowOutOfRange(nameof(index));
 85              }
 86  
 87              return GetSuccessorUnsafe(index);
 88          }
 89  
 90          private ref BasicBlock GetSuccessorUnsafe(int index)
 91          {
 92              return ref Unsafe.Add(ref _succ0, index);
 93          }
 94  
 95          public void SetSuccessor(int index, BasicBlock block)
 96          {
 97              ArgumentNullException.ThrowIfNull(block);
 98  
 99              if ((uint)index >= (uint)_succCount)
100              {
101                  ThrowOutOfRange(nameof(index));
102              }
103  
104              ref BasicBlock oldBlock = ref GetSuccessorUnsafe(index);
105  
106              oldBlock.Predecessors.Remove(this);
107              block.Predecessors.Add(this);
108  
109              oldBlock = block;
110          }
111  
112          public void Append(Operation node)
113          {
114              Operation last = Operations.Last;
115  
116              // Append node before terminal or to end if no terminal.
117              if (last == default)
118              {
119                  Operations.AddLast(node);
120  
121                  return;
122              }
123  
124              switch (last.Instruction)
125              {
126                  case Instruction.Return:
127                  case Instruction.Tailcall:
128                  case Instruction.BranchIf:
129                      Operations.AddBefore(last, node);
130                      break;
131  
132                  default:
133                      Operations.AddLast(node);
134                      break;
135              }
136          }
137  
138          private static void ThrowOutOfRange(string name) => throw new ArgumentOutOfRangeException(name);
139          private static void ThrowSuccessorOverflow() => throw new OverflowException($"BasicBlock can only have {MaxSuccessors} successors.");
140  
141          public bool Equals(BasicBlock other)
142          {
143              return other == this;
144          }
145  
146          public override bool Equals(object obj)
147          {
148              return Equals(obj as BasicBlock);
149          }
150  
151          public override int GetHashCode()
152          {
153              return base.GetHashCode();
154          }
155      }
156  }