1 /// Copyright: Copyright (c) 2018-2019 Andrey Penechko. 2 /// License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 3 /// Authors: Andrey Penechko. 4 module vox.be.reg_alloc.live_range; 5 6 import vox.all; 7 8 /// exclusive end doesn't prevent register from being used by another interval 9 /// ranges within one interval never have ranges[i].to == ranges[i+1].from 10 /// When split prev range's end get's offset by 1 so [0; 10) becomes [0; 3) [4; 10) 11 /// When looking if instruction is covered by range the end position is inclusive 12 /// Splits must always occur on odd positions 13 /// We forbid creation of [10; 10) ranges 14 /// invariant: from < to 15 /// [from; to) 16 struct LiveRange 17 { 18 uint from; 19 uint to; 20 21 bool contains(uint pos) { 22 if (pos < from) return false; 23 if (pos >= to) return false; 24 return true; 25 } 26 void merge(LiveRange other) { 27 from = min(from, other.from); 28 to = max(to, other.to); 29 } 30 bool canBeMergedWith(const LiveRange other) { 31 if (to + 2 < other.from) return false; 32 if (from > other.to + 2) return false; 33 return true; 34 } 35 36 bool intersectsWith(const LiveRange other) { 37 if (to <= other.from) return false; 38 if (from >= other.to) return false; 39 return true; 40 } 41 42 void toString(scope void delegate(const(char)[]) sink) { 43 import std.format : formattedWrite; 44 sink.formattedWrite("[%s; %s)", from, to); 45 } 46 } 47 48 struct LiveRangeIndex { 49 this(size_t id) { this.id = cast(uint)id; } 50 enum LiveRangeIndex NULL = LiveRangeIndex(uint.max); 51 uint id = uint.max; 52 bool isNull() { return id == NULL; } 53 alias id this; 54 55 void toString(scope void delegate(const(char)[]) sink) { 56 import std.format : formattedWrite; 57 if (id == uint.max) sink("max"); 58 else sink.formattedWrite("%s", id); 59 } 60 }