1  using ARMeilleure.IntermediateRepresentation;
  2  using System;
  3  using System.Collections.Generic;
  4  using System.Diagnostics;
  5  
  6  namespace ARMeilleure.CodeGen.RegisterAllocators
  7  {
  8      unsafe readonly struct LiveInterval : IComparable<LiveInterval>
  9      {
 10          public const int NotFound = -1;
 11  
 12          private struct Data
 13          {
 14              public int End;
 15              public int SpillOffset;
 16  
 17              public LiveRange FirstRange;
 18              public LiveRange PrevRange;
 19              public LiveRange CurrRange;
 20  
 21              public LiveInterval Parent;
 22              public LiveInterval CopySource;
 23  
 24              public UseList Uses;
 25              public LiveIntervalList Children;
 26  
 27              public Operand Local;
 28              public Register Register;
 29  
 30              public bool IsFixed;
 31              public bool IsFixedAndUsed;
 32          }
 33  
 34          private readonly Data* _data;
 35  
 36          private ref int End => ref _data->End;
 37          private ref LiveRange FirstRange => ref _data->FirstRange;
 38          private ref LiveRange CurrRange => ref _data->CurrRange;
 39          private ref LiveRange PrevRange => ref _data->PrevRange;
 40          private ref LiveInterval Parent => ref _data->Parent;
 41          private ref LiveInterval CopySource => ref _data->CopySource;
 42          private ref UseList Uses => ref _data->Uses;
 43          private ref LiveIntervalList Children => ref _data->Children;
 44  
 45          public Operand Local => _data->Local;
 46          public ref Register Register => ref _data->Register;
 47          public ref int SpillOffset => ref _data->SpillOffset;
 48  
 49          public bool IsFixed => _data->IsFixed;
 50          public ref bool IsFixedAndUsed => ref _data->IsFixedAndUsed;
 51          public bool IsEmpty => FirstRange == default;
 52          public bool IsSplit => Children.Count != 0;
 53          public bool IsSpilled => SpillOffset != -1;
 54  
 55          public int UsesCount => Uses.Count;
 56  
 57          public LiveInterval(Operand local = default, LiveInterval parent = default)
 58          {
 59              _data = Allocators.LiveIntervals.Allocate<Data>();
 60              *_data = default;
 61  
 62              _data->IsFixed = false;
 63              _data->Local = local;
 64  
 65              Parent = parent == default ? this : parent;
 66              Uses = new UseList();
 67              Children = new LiveIntervalList();
 68  
 69              FirstRange = default;
 70              CurrRange = default;
 71              PrevRange = default;
 72  
 73              SpillOffset = -1;
 74          }
 75  
 76          public LiveInterval(Register register) : this(local: default, parent: default)
 77          {
 78              _data->IsFixed = true;
 79  
 80              Register = register;
 81          }
 82  
 83          public void SetCopySource(LiveInterval copySource)
 84          {
 85              CopySource = copySource;
 86          }
 87  
 88          public bool TryGetCopySourceRegister(out int copySourceRegIndex)
 89          {
 90              if (CopySource._data != null)
 91              {
 92                  copySourceRegIndex = CopySource.Register.Index;
 93  
 94                  return true;
 95              }
 96  
 97              copySourceRegIndex = 0;
 98  
 99              return false;
100          }
101  
102          public void Reset()
103          {
104              PrevRange = default;
105              CurrRange = FirstRange;
106          }
107  
108          public void Forward(int position)
109          {
110              LiveRange prev = PrevRange;
111              LiveRange curr = CurrRange;
112  
113              while (curr != default && curr.Start < position && !curr.Overlaps(position))
114              {
115                  prev = curr;
116                  curr = curr.Next;
117              }
118  
119              PrevRange = prev;
120              CurrRange = curr;
121          }
122  
123          public int GetStart()
124          {
125              Debug.Assert(!IsEmpty, "Empty LiveInterval cannot have a start position.");
126  
127              return FirstRange.Start;
128          }
129  
130          public void SetStart(int position)
131          {
132              if (FirstRange != default)
133              {
134                  Debug.Assert(position != FirstRange.End);
135  
136                  FirstRange.Start = position;
137              }
138              else
139              {
140                  FirstRange = new LiveRange(position, position + 1);
141                  End = position + 1;
142              }
143          }
144  
145          public int GetEnd()
146          {
147              Debug.Assert(!IsEmpty, "Empty LiveInterval cannot have an end position.");
148  
149              return End;
150          }
151  
152          public void AddRange(int start, int end)
153          {
154              Debug.Assert(start < end, $"Invalid range start position {start}, {end}");
155  
156              if (FirstRange != default)
157              {
158                  // If the new range ends exactly where the first range start, then coalesce together.
159                  if (end == FirstRange.Start)
160                  {
161                      FirstRange.Start = start;
162  
163                      return;
164                  }
165                  // If the new range is already contained, then coalesce together.
166                  else if (FirstRange.Overlaps(start, end))
167                  {
168                      FirstRange.Start = Math.Min(FirstRange.Start, start);
169                      FirstRange.End = Math.Max(FirstRange.End, end);
170                      End = Math.Max(End, end);
171  
172                      Debug.Assert(FirstRange.Next == default || !FirstRange.Overlaps(FirstRange.Next));
173                      return;
174                  }
175              }
176  
177              FirstRange = new LiveRange(start, end, FirstRange);
178              End = Math.Max(End, end);
179  
180              Debug.Assert(FirstRange.Next == default || !FirstRange.Overlaps(FirstRange.Next));
181          }
182  
183          public void AddUsePosition(int position)
184          {
185              Uses.Add(position);
186          }
187  
188          public bool Overlaps(int position)
189          {
190              LiveRange curr = CurrRange;
191  
192              while (curr != default && curr.Start <= position)
193              {
194                  if (curr.Overlaps(position))
195                  {
196                      return true;
197                  }
198  
199                  curr = curr.Next;
200              }
201  
202              return false;
203          }
204  
205          public bool Overlaps(LiveInterval other)
206          {
207              return GetOverlapPosition(other) != NotFound;
208          }
209  
210          public int GetOverlapPosition(LiveInterval other)
211          {
212              LiveRange a = CurrRange;
213              LiveRange b = other.CurrRange;
214  
215              while (a != default)
216              {
217                  while (b != default && b.Start < a.Start)
218                  {
219                      if (a.Overlaps(b))
220                      {
221                          return a.Start;
222                      }
223  
224                      b = b.Next;
225                  }
226  
227                  if (b == default)
228                  {
229                      break;
230                  }
231                  else if (a.Overlaps(b))
232                  {
233                      return a.Start;
234                  }
235  
236                  a = a.Next;
237              }
238  
239              return NotFound;
240          }
241  
242          public ReadOnlySpan<LiveInterval> SplitChildren()
243          {
244              return Parent.Children.Span;
245          }
246  
247          public ReadOnlySpan<int> UsePositions()
248          {
249              return Uses.Span;
250          }
251  
252          public int FirstUse()
253          {
254              return Uses.FirstUse;
255          }
256  
257          public int NextUseAfter(int position)
258          {
259              return Uses.NextUse(position);
260          }
261  
262          public LiveInterval Split(int position)
263          {
264              LiveInterval result = new(Local, Parent)
265              {
266                  End = End,
267              };
268  
269              LiveRange prev = PrevRange;
270              LiveRange curr = CurrRange;
271  
272              while (curr != default && curr.Start < position && !curr.Overlaps(position))
273              {
274                  prev = curr;
275                  curr = curr.Next;
276              }
277  
278              if (curr.Start >= position)
279              {
280                  prev.Next = default;
281  
282                  result.FirstRange = curr;
283  
284                  End = prev.End;
285              }
286              else
287              {
288                  result.FirstRange = new LiveRange(position, curr.End, curr.Next);
289  
290                  curr.End = position;
291                  curr.Next = default;
292  
293                  End = curr.End;
294              }
295  
296              result.Uses = Uses.Split(position);
297  
298              AddSplitChild(result);
299  
300              Debug.Assert(!IsEmpty, "Left interval is empty after split.");
301              Debug.Assert(!result.IsEmpty, "Right interval is empty after split.");
302  
303              // Make sure the iterator in the new split is pointing to the start.
304              result.Reset();
305  
306              return result;
307          }
308  
309          private void AddSplitChild(LiveInterval child)
310          {
311              Debug.Assert(!child.IsEmpty, "Trying to insert an empty interval.");
312  
313              Parent.Children.Add(child);
314          }
315  
316          public LiveInterval GetSplitChild(int position)
317          {
318              if (Overlaps(position))
319              {
320                  return this;
321              }
322  
323              foreach (LiveInterval splitChild in SplitChildren())
324              {
325                  if (splitChild.Overlaps(position))
326                  {
327                      return splitChild;
328                  }
329                  else if (splitChild.GetStart() > position)
330                  {
331                      break;
332                  }
333              }
334  
335              return default;
336          }
337  
338          public bool TrySpillWithSiblingOffset()
339          {
340              foreach (LiveInterval splitChild in SplitChildren())
341              {
342                  if (splitChild.IsSpilled)
343                  {
344                      Spill(splitChild.SpillOffset);
345  
346                      return true;
347                  }
348              }
349  
350              return false;
351          }
352  
353          public void Spill(int offset)
354          {
355              SpillOffset = offset;
356          }
357  
358          public int CompareTo(LiveInterval interval)
359          {
360              if (FirstRange == default || interval.FirstRange == default)
361              {
362                  return 0;
363              }
364  
365              return GetStart().CompareTo(interval.GetStart());
366          }
367  
368          public bool Equals(LiveInterval interval)
369          {
370              return interval._data == _data;
371          }
372  
373          public override bool Equals(object obj)
374          {
375              return obj is LiveInterval interval && Equals(interval);
376          }
377  
378          public static bool operator ==(LiveInterval a, LiveInterval b)
379          {
380              return a.Equals(b);
381          }
382  
383          public static bool operator !=(LiveInterval a, LiveInterval b)
384          {
385              return !a.Equals(b);
386          }
387  
388          public override int GetHashCode()
389          {
390              return HashCode.Combine((IntPtr)_data);
391          }
392  
393          public override string ToString()
394          {
395              LiveInterval self = this;
396  
397              IEnumerable<string> GetRanges()
398              {
399                  LiveRange curr = self.CurrRange;
400  
401                  while (curr != default)
402                  {
403                      if (curr == self.CurrRange)
404                      {
405                          yield return "*" + curr;
406                      }
407                      else
408                      {
409                          yield return curr.ToString();
410                      }
411  
412                      curr = curr.Next;
413                  }
414              }
415  
416              return string.Join(", ", GetRanges());
417          }
418      }
419  }