Changeset a5873bd

Timestamp:

Jun 10, 2020, 12:13:18 PM (4 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

97392b69

Parents:

6089f4d (diff), 5f259f3 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'relaxed_ready' of plg.uwaterloo.ca:software/cfa/cfa-cc into relaxed_ready

Location:

doc/theses/thierry_delisle_PhD/code

Files:

• bitbench/select.cpp (added)
• relaxed_list.hpp (modified) (1 diff)
• snzm.hpp (modified) (5 diffs)

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -222 +222 @@
                                         if(maski == 0 && maskj == 0) continue;
 
-                                        unsigned bi = rand_bit(ri >> snzm.depth, maski);
-                                        unsigned bj = rand_bit(rj >> snzm.depth, maskj);
-
-                                        assertf(bi < 64, "%zu %u", maski, bi);
-                                        assertf(bj < 64, "%zu %u", maskj, bj);
+                                        #if defined(__BMI2__)
+                                                uint64_t idxsi = _pext_u64(snzm.indexes, maski);
+                                                uint64_t idxsj = _pext_u64(snzm.indexes, maskj);
+
+                                                auto pi = __builtin_popcountll(maski);
+                                                auto pj = __builtin_popcountll(maskj);
+
+                                                ri = pi ? ri & ((pi >> 3) - 1) : 0;
+                                                rj = pj ? rj & ((pj >> 3) - 1) : 0;
+
+                                                unsigned bi = (idxsi >> (ri << 3)) & 0xff;
+                                                unsigned bj = (idxsj >> (rj << 3)) & 0xff;
+                                        #else
+                                                unsigned bi = rand_bit(ri >> snzm.depth, maski);
+                                                unsigned bj = rand_bit(rj >> snzm.depth, maskj);
+                                        #endif
 
                                         i = (bi << snzm.depth) | wdxi;
                                         j = (bj << snzm.depth) | wdxj;
 
-                                        assertf(i < numLists, "%u %u", bj, wdxi);
-                                        assertf(j < numLists, "%u %u", bj, wdxj);
+                                        /* paranoid */ assertf(i < numLists, "%u %u", bj, wdxi);
+                                        /* paranoid */ assertf(j < numLists, "%u %u", bj, wdxj);
                                 }
 

doc/theses/thierry_delisle_PhD/code/snzm.hpp

@@ -12 +12 @@
         std::unique_ptr<snzm_t::node[]> nodes;
 
+        #if defined(__BMI2__)
+                const uint64_t indexes = 0x0706050403020100;
+        #endif
+
         snzm_t(unsigned numLists);
 
@@ -28 +32 @@
         }
 
-        size_t masks( unsigned node ) {
+        uint64_t masks( unsigned node ) {
                 /* paranoid */ assert( (node & mask) == node );
-                return nodes[node].mask;
+                #if defined(__BMI2__)
+                        return nodes[node].mask_all;
+                #else
+                        return nodes[node].mask;
+                #endif
         }
 
@@ -140 +148 @@
         private:
                 volatile val_t value;
-                volatile size_t mask = 0;
+                #if defined(__BMI2__)
+                        union __attribute__((packed)) {
+                                volatile uint8_t mask[8];
+                                volatile uint64_t mask_all;
+                        };
+                #else
+                        volatile size_t mask = 0;
+                #endif
+
                 class node * parent = nullptr;
                 bool is_leaf = false;
@@ -151 +167 @@
                 void arrive( int bit ) {
                         /* paranoid */ assert( is_leaf );
-                        /* paranoid */ assert( (mask & ( 1 << bit )) == 0 );
 
                         arrive_h();
-                        __atomic_fetch_add( &mask, 1 << bit, __ATOMIC_RELAXED );
-                        // bts( (std::atomic_size_t&)mask, bit );
+                        #if defined(__BMI2__)
+                                /* paranoid */ assert( bit < 8 );
+                                mask[bit] = 0xff;
+                        #else
+                                /* paranoid */ assert( (mask & ( 1 << bit )) == 0 );
+                                __atomic_fetch_add( &mask, 1 << bit, __ATOMIC_RELAXED );
+                        #endif
 
                 }
@@ -161 +181 @@
                 void depart( int bit ) {
                         /* paranoid */ assert( is_leaf );
-                        /* paranoid */ assert( (mask & ( 1 << bit )) != 0 );
-
-                        // btr( (std::atomic_size_t&)mask, bit );
-                        __atomic_fetch_sub( &mask, 1 << bit, __ATOMIC_RELAXED );
+
+                        #if defined(__BMI2__)
+                                /* paranoid */ assert( bit < 8 );
+                                mask[bit] = 0x00;
+                        #else
+                                /* paranoid */ assert( (mask & ( 1 << bit )) != 0 );
+                                __atomic_fetch_sub( &mask, 1 << bit, __ATOMIC_RELAXED );
+                        #endif
                         depart_h();
                 }