114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===// 214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// The LLVM Compiler Infrastructure 414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This file is distributed under the University of Illinois Open Source 614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// License. See LICENSE.TXT for details. 714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===----------------------------------------------------------------------===// 914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 1014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// LiveIntervalUnion is a union of live segments across multiple live virtual 1114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// registers. This may be used during coalescing to represent a congruence 1214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// class, or during register allocation to model liveness of a physical 1314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// register. 1414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 1514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===----------------------------------------------------------------------===// 1614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 17674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H 18674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_LIVEINTERVALUNION_H 1914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 20953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen#include "llvm/ADT/IntervalMap.h" 2114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include "llvm/CodeGen/LiveInterval.h" 2214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 2314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Tricknamespace llvm { 2414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 254a84cce3ed0008baf72ccc6831a046215addd2d7Jakob Stoklund Olesenclass TargetRegisterInfo; 264a84cce3ed0008baf72ccc6831a046215addd2d7Jakob Stoklund Olesen 27071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick#ifndef NDEBUG 28071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick// forward declaration 29071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Tricktemplate <unsigned Element> class SparseBitVector; 3018c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Tricktypedef SparseBitVector<128> LiveVirtRegBitSet; 31071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick#endif 32071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick 33953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen/// Compare a live virtual register segment to a LiveIntervalUnion segment. 34953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Oleseninline bool 35331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braunoverlap(const LiveInterval::Segment &VRSeg, 36953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { 37953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; 38953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen} 39953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen 4014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// Union of live intervals that are strong candidates for coalescing into a 4114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// single register (either physical or virtual depending on the context). We 4214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// expect the constituent live intervals to be disjoint, although we may 4314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// eventually make exceptions to handle value-based interference. 4414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickclass LiveIntervalUnion { 4514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // A set of live virtual register segments that supports fast insertion, 4618c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick // intersection, and removal. 47953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen // Mapping SlotIndex intervals to virtual register numbers. 48953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments; 4914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 5014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickpublic: 5114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // SegmentIter can advance to the next segment ordered by starting position 5214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // which may belong to a different live virtual register. We also must be able 5314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // to reach the current segment's containing virtual register. 5414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick typedef LiveSegments::iterator SegmentIter; 5514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 56953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen // LiveIntervalUnions share an external allocator. 57953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen typedef LiveSegments::Allocator Allocator; 58953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen 5914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick class Query; 6014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 6114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickprivate: 624f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen unsigned Tag; // unique tag for current contents. 63953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen LiveSegments Segments; // union of virtual reg segments 6414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 6514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickpublic: 662fd0923593c4d30691a45ade1e8b0bd484896c3fJakob Stoklund Olesen explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {} 6714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 68e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // Iterate over all segments in the union of live virtual registers ordered 69e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // by their starting position. 7018c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick SegmentIter begin() { return Segments.begin(); } 7118c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick SegmentIter end() { return Segments.end(); } 72a35cce1a14d8eee7e250e02b03903a5096d22c2fJakob Stoklund Olesen SegmentIter find(SlotIndex x) { return Segments.find(x); } 73bfce678de7b509a497ac6d91f29e749adab7e40cJakob Stoklund Olesen bool empty() const { return Segments.empty(); } 74bfce678de7b509a497ac6d91f29e749adab7e40cJakob Stoklund Olesen SlotIndex startIndex() const { return Segments.start(); } 7514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 76ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen // Provide public access to the underlying map to allow overlap iteration. 77ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef LiveSegments Map; 78ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen const Map &getMap() { return Segments; } 79ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 804f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen /// getTag - Return an opaque tag representing the current state of the union. 814f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen unsigned getTag() const { return Tag; } 824f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen 834f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen /// changedSince - Return true if the union change since getTag returned tag. 844f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen bool changedSince(unsigned tag) const { return tag != Tag; } 854f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen 86e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // Add a live virtual register to this union and merge its segments. 8718c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick void unify(LiveInterval &VirtReg); 8814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 89e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick // Remove a live virtual register's segments from this union. 90953af2c3c560a13bd5eeb676c128b7e362dca684Jakob Stoklund Olesen void extract(LiveInterval &VirtReg); 9114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 92560ab9ebf78532df11188770c916c4eb6dcce1b2Jakob Stoklund Olesen // Remove all inserted virtual registers. 93560ab9ebf78532df11188770c916c4eb6dcce1b2Jakob Stoklund Olesen void clear() { Segments.clear(); ++Tag; } 94560ab9ebf78532df11188770c916c4eb6dcce1b2Jakob Stoklund Olesen 954a84cce3ed0008baf72ccc6831a046215addd2d7Jakob Stoklund Olesen // Print union, using TRI to translate register names 964a84cce3ed0008baf72ccc6831a046215addd2d7Jakob Stoklund Olesen void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; 97071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick 98071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick#ifndef NDEBUG 99071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick // Verify the live intervals in this union and add them to the visited set. 10018c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick void verify(LiveVirtRegBitSet& VisitedVRegs); 101071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick#endif 102071d1c063f1080c70a7141d947a96cf511a1ba45Andrew Trick 10314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick /// Query interferences between a single live virtual register and a live 10414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick /// interval union. 10514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick class Query { 10618c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick LiveIntervalUnion *LiveUnion; 10718c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick LiveInterval *VirtReg; 108fe026e182993a94381d197f140b19b999c3e17ecJakob Stoklund Olesen LiveInterval::iterator VirtRegI; // current position in VirtReg 109fe026e182993a94381d197f140b19b999c3e17ecJakob Stoklund Olesen SegmentIter LiveUnionI; // current position in LiveUnion 11018c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick SmallVector<LiveInterval*,4> InterferingVRegs; 111a35cce1a14d8eee7e250e02b03903a5096d22c2fJakob Stoklund Olesen bool CheckedFirstInterference; 11218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick bool SeenAllInterferences; 11318c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick bool SeenUnspillableVReg; 1142926733240d0766fbd45df6eb609ad2328f0307dJakob Stoklund Olesen unsigned Tag, UserTag; 11514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 11614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick public: 117314a3ef502c67e9be7a67c9be7ea3ecffce8298bJakob Stoklund Olesen Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} 118e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick 11918c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick Query(LiveInterval *VReg, LiveIntervalUnion *LIU): 120a0382c629093a2edd175dc256750667c296d3a43Jakob Stoklund Olesen LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), 121a0382c629093a2edd175dc256750667c296d3a43Jakob Stoklund Olesen SeenAllInterferences(false), SeenUnspillableVReg(false) 12218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick {} 123e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick 124e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick void clear() { 125dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LiveUnion = nullptr; 126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VirtReg = nullptr; 12718c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick InterferingVRegs.clear(); 128a35cce1a14d8eee7e250e02b03903a5096d22c2fJakob Stoklund Olesen CheckedFirstInterference = false; 12918c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick SeenAllInterferences = false; 13018c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick SeenUnspillableVReg = false; 1314f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen Tag = 0; 1322926733240d0766fbd45df6eb609ad2328f0307dJakob Stoklund Olesen UserTag = 0; 133e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick } 13418c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick 1352926733240d0766fbd45df6eb609ad2328f0307dJakob Stoklund Olesen void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { 136a0382c629093a2edd175dc256750667c296d3a43Jakob Stoklund Olesen assert(VReg && LIU && "Invalid arguments"); 1372926733240d0766fbd45df6eb609ad2328f0307dJakob Stoklund Olesen if (UserTag == UTag && VirtReg == VReg && 1382926733240d0766fbd45df6eb609ad2328f0307dJakob Stoklund Olesen LiveUnion == LIU && !LIU->changedSince(Tag)) { 139e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick // Retain cached results, e.g. firstInterference. 140e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick return; 141e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick } 14218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick clear(); 14318c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick LiveUnion = LIU; 14418c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick VirtReg = VReg; 1454f6364fd3f2af74330b1bc4e545173af074707a5Jakob Stoklund Olesen Tag = LIU->getTag(); 1462926733240d0766fbd45df6eb609ad2328f0307dJakob Stoklund Olesen UserTag = UTag; 147e141a4960f702bef957b28abde3801ec64e32d87Andrew Trick } 14814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 14918c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick LiveInterval &virtReg() const { 15018c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick assert(VirtReg && "uninitialized"); 15118c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick return *VirtReg; 15218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick } 15314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 15418c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick // Does this live virtual register interfere with the union? 1559942ba9c0ed45c77298cdeb7a9326f04745d5709Jakob Stoklund Olesen bool checkInterference() { return collectInterferingVRegs(1); } 15614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 157f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick // Count the virtual registers in this union that interfere with this 158f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick // query's live virtual register, up to maxInterferingRegs. 15951458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); 160f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick 161f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick // Was this virtual register visited during collectInterferingVRegs? 16218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick bool isSeenInterference(LiveInterval *VReg) const; 16318c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick 16418c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick // Did collectInterferingVRegs collect all interferences? 16518c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick bool seenAllInterferences() const { return SeenAllInterferences; } 166f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick 167f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick // Did collectInterferingVRegs encounter an unspillable vreg? 16818c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick bool seenUnspillableVReg() const { return SeenUnspillableVReg; } 169f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick 170f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick // Vector generated by collectInterferingVRegs. 171f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { 17218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick return InterferingVRegs; 173f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick } 17418c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick 17514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick private: 17686a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper Query(const Query&) LLVM_DELETED_FUNCTION; 17786a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper void operator=(const Query&) LLVM_DELETED_FUNCTION; 17814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick }; 1790e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen 1800e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen // Array of LiveIntervalUnions. 1810e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen class Array { 1820e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen unsigned Size; 1830e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen LiveIntervalUnion *LIUs; 1840e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen public: 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Array() : Size(0), LIUs(nullptr) {} 1860e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen ~Array() { clear(); } 1870e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen 1880e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen // Initialize the array to have Size entries. 1890e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen // Reuse an existing allocation if the size matches. 1900e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen void init(LiveIntervalUnion::Allocator&, unsigned Size); 1910e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen 1920e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen unsigned size() const { return Size; } 1930e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen 1940e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen void clear(); 1950e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen 1960e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen LiveIntervalUnion& operator[](unsigned idx) { 1970e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen assert(idx < Size && "idx out of bounds"); 1980e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen return LIUs[idx]; 1990e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen } 2000e5a60b4ebc06a4fe6bb58f0200acf130d7be685Jakob Stoklund Olesen }; 20114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick}; 20214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 20314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick} // end namespace llvm 20414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 205674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION_H) 206