4fa149cfe8af — Leonard Ritter 23 days ago
* UVM: added sweep & mark gc mechanism test
1 files changed, 175 insertions(+), 0 deletions(-)

A => testing/test_node4.sc
A => testing/test_node4.sc +175 -0
@@ 0,0 1,175 @@ 
+using import struct
+using import Array
+using import String
+
+inline firstbit (mask bit)
+    mask & (~ (mask - bit))
+
+inline nextbit (mask bit)
+    mask & (~ (mask - (bit << 1)))
+
+fn prevbit (mask bit)
+    mask := mask & (bit - 1)
+    mask := mask | mask >> 1
+    mask := mask | mask >> 2
+    mask := mask | mask >> 4
+    mask := mask | mask >> 8
+    mask := mask | mask >> 16
+    mask & ((mask >> 1) + 1)
+
+"""" enumerate the mask bits of integer, starting with maskbit `start`
+inline... itermaskbits (value : integer, start = 1)
+    T := (typeof value)
+    let start = (start as T)
+    Generator
+        inline () (firstbit value start)
+        inline (pos) (pos != 0)
+        inline (pos) pos
+        inline (pos) (nextbit value pos)
+
+"""" enumerate the mask bits of integer in reverse, starting with maskbit `start`
+inline... ritermaskbits (value : integer, start = 0)
+    T := (typeof value)
+    let start = (start as T)
+    Generator
+        inline () (prevbit value start)
+        inline (pos) (pos != 0)
+        inline (pos) pos
+        inline (pos) (prevbit value pos)
+
+################################################################################
+
+struct Module
+    WordType := u32
+    Id := WordType
+    BitWordType := WordType
+    BitWordWidth := (bitcountof BitWordType)
+
+    p : (Array WordType)
+    # 1 word -> 32 words
+    # bits indicate the start of a sequence
+    sep : (Array BitWordType)
+    # reference bits
+    ref : (Array BitWordType)
+
+    inline __typecall (cls)
+        local self = (super-type.__typecall cls)
+        'append self.p 0:u32
+        'append self.sep 1:u32
+        'append self.ref 0:u32
+        deref self
+
+    fn id2bitpos (id)
+        _ (id // BitWordWidth) (id & (BitWordWidth - 1))
+
+    fn bitpos2id (bitwordofs bitofs)
+        bitwordofs * BitWordWidth + bitofs
+
+    fn alloc (self wordcount)
+        count := (countof self.p)
+        id := (count as u32)
+        let bitwordofs bitofs = (id2bitpos id)
+        count := count + wordcount
+        'resize self.p count (nullof WordType)
+        bitcount := (count + BitWordWidth - 1) // BitWordWidth
+        sep := self.sep
+        'resize sep bitcount (nullof BitWordType)
+        'resize self.ref bitcount (nullof BitWordType)
+        sep @ bitwordofs |= (1 as BitWordType) << bitofs
+        id
+
+    fn... setref (self, targetid : Id, sourceid : Id)
+        self.p @ targetid = sourceid
+        bitwordofs := (targetid // BitWordWidth)
+        bitofs := targetid & (BitWordWidth - 1)
+        self.ref @ bitwordofs |= (1 as BitWordType) << bitofs
+        ;
+
+    fn... collect (self, root : Id)
+        let bitwordofs bitofs = (id2bitpos root)
+        # dirty flags
+        local used : (Array BitWordType)
+        maxwordofs := ((countof self.sep) as u32)
+        'resize used maxwordofs 0:u32
+
+        fn mark (self used id)
+            print "mark:" id
+            let bitwordofs bitofs = (id2bitpos id)
+            used @ bitwordofs |= (1 as BitWordType) << bitofs
+
+        fn visit (self used bitwordofs bitofsmask maxwordofs)
+            let p sep ref = self.p self.sep self.ref
+            loop (bitwordofs bitofsmask = bitwordofs bitofsmask)
+                w := (deref (ref @ bitwordofs))
+                # terminate at next separator or next used bit
+                s := (sep @ bitwordofs) | (used @ bitwordofs)
+                endofsmask := (nextbit s bitofsmask)
+                vvv bind bitwordofs bitofsmask
+                loop (bitofsmask = bitofsmask)
+                    bitofsmask := (firstbit w bitofsmask)
+                    if (endofsmask == 0) # no terminator in this word
+                        if (bitofsmask == 0) # more refs in next word
+                            break (bitwordofs + 1) 1:u32
+                    else # terminator in this word
+                        if ((bitofsmask == 0) | (bitofsmask >= endofsmask)) # no more refs
+                            return;
+                    if (w & bitofsmask)
+                        # is a ref
+                        mark self used
+                            p @ (bitpos2id bitwordofs (findlsb bitofsmask))
+                    else
+                        report "miss"
+                    # go to next ref in this word
+                    repeat (bitofsmask << 1)
+                if (bitwordofs >= maxwordofs)
+                    break;
+                else
+                    repeat bitwordofs bitofsmask
+
+        mark self used root
+        bitofsmask := (1:u32 << bitofs)
+
+        #let p sep ref = self.p self.sep self.ref
+        loop (bitwordofs bitofsmask = bitwordofs bitofsmask)
+            w := (used @ bitwordofs)
+            vvv bind bitwordofs bitofsmask
+            loop (bitofsmask = bitofsmask)
+                if (w & bitofsmask)
+                    print "visit:" (bitpos2id bitwordofs (findlsb bitofsmask))
+                    # is used
+                    visit self used bitwordofs bitofsmask maxwordofs
+                else
+                    report "used miss"
+                bitofsmask := (prevbit w bitofsmask)
+                if (bitofsmask == 0) # more used bits in prev word?
+                    break (bitwordofs - 1) 0:u32
+                # go to prev used bit in this word
+                repeat bitofsmask
+            if (bitwordofs >= maxwordofs)
+                break;
+            w := (used @ bitwordofs)
+            repeat bitwordofs (prevbit w bitofsmask)
+
+local module : Module
+print "n1="
+    n1 := ('alloc module 5)
+print "n2="
+    n2 := ('alloc module 10)
+print "n3="
+    n3 := ('alloc module 16)
+print "n4="
+    n4 := ('alloc module 16)
+print "n5="
+    n5 := ('alloc module 40)
+'setref module (n5 + 2) n4
+'setref module (n5 + 35) n3
+'setref module (n3 + 0) (n1 + 2)
+'setref module (n3 + 1) (n2 + 3)
+'setref module (n2 + 2) n1
+'collect module n5
+
+
+
+
+;
+