1 //------------------------------------------------------------------------------
2 // GB_stringify_semiring: build strings for a semiring
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // Construct a string defining all macros for semiring, and its name.
11 // User-defined types are not handled.
12
13 #include "GB.h"
14 #include "GB_stringify.h"
15
16 //------------------------------------------------------------------------------
17 // GB_stringify_semiring: build strings for a semiring
18 //------------------------------------------------------------------------------
19
GB_stringify_semiring(char * semiring_macros,GrB_Semiring semiring,bool flipxy,GrB_Type ctype,GrB_Type mtype,GrB_Type atype,GrB_Type btype,bool Mask_struct,bool Mask_comp,int C_sparsity,int M_sparsity,int A_sparsity,int B_sparsity)20 void GB_stringify_semiring // build a semiring (name and code)
21 (
22 // output: (all of size at least GB_CUDA_STRLEN+1)
23 char *semiring_macros, // List of types and macro defs
24 // input:
25 GrB_Semiring semiring, // the semiring to stringify
26 bool flipxy, // multiplier is: mult(a,b) or mult(b,a)
27 GrB_Type ctype, // the type of C
28 GrB_Type mtype, // the type of M, or NULL if no mask
29 GrB_Type atype, // the type of A
30 GrB_Type btype, // the type of B
31 bool Mask_struct, // mask is structural
32 bool Mask_comp, // mask is complemented
33 int C_sparsity, // sparsity structure of C
34 int M_sparsity, // sparsity structure of M
35 int A_sparsity, // sparsity structure of A
36 int B_sparsity // sparsity structure of B
37 )
38 {
39
40 uint64_t scode ;
41 GB_enumify_semiring (&scode,
42 semiring, flipxy, ctype, mtype, atype, btype, Mask_struct, Mask_comp,
43 C_sparsity, M_sparsity, A_sparsity, B_sparsity) ;
44 GB_macrofy_semiring (semiring_macros, scode) ;
45 }
46
47 //------------------------------------------------------------------------------
48 // GB_enumify_semiring: enumerate a semiring
49 //------------------------------------------------------------------------------
50
GB_enumify_semiring(uint64_t * scode,GrB_Semiring semiring,bool flipxy,GrB_Type ctype,GrB_Type mtype,GrB_Type atype,GrB_Type btype,bool Mask_struct,bool Mask_comp,int C_sparsity,int M_sparsity,int A_sparsity,int B_sparsity)51 void GB_enumify_semiring // enumerate a semiring
52 (
53 // output:
54 uint64_t *scode, // unique encoding of the entire semiring
55 // input:
56 GrB_Semiring semiring, // the semiring to enumify
57 bool flipxy, // multiplier is: mult(a,b) or mult(b,a)
58 GrB_Type ctype, // the type of C
59 GrB_Type mtype, // the type of M, or NULL if no mask
60 GrB_Type atype, // the type of A
61 GrB_Type btype, // the type of B
62 bool Mask_struct, // mask is structural
63 bool Mask_comp, // mask is complemented
64 int C_sparsity, // sparsity structure of C
65 int M_sparsity, // sparsity structure of M
66 int A_sparsity, // sparsity structure of A
67 int B_sparsity // sparsity structure of B
68 )
69 {
70
71 //--------------------------------------------------------------------------
72 // get the semiring
73 //--------------------------------------------------------------------------
74
75 GrB_Monoid add = semiring->add ;
76 GrB_BinaryOp mult = semiring->multiply ;
77 GrB_BinaryOp addop = add->op ;
78 GrB_Type xtype = mult->xtype ;
79 GrB_Type ytype = mult->ytype ;
80 GrB_Type ztype = mult->ztype ;
81 GB_Opcode mult_opcode = mult->opcode ;
82 GB_Opcode add_opcode = addop->opcode ;
83 GB_Type_code xcode = xtype->code ;
84 GB_Type_code ycode = ytype->code ;
85 GB_Type_code zcode = ztype->code ;
86
87 // these must always be true for any semiring:
88 ASSERT (mult->ztype == addop->ztype) ;
89 ASSERT (addop->xtype == addop->ztype && addop->ytype == addop->ztype) ;
90
91 //--------------------------------------------------------------------------
92 // rename redundant boolean operators
93 //--------------------------------------------------------------------------
94
95 // consider z = op(x,y) where both x and y are boolean:
96 // DIV becomes FIRST
97 // RDIV becomes SECOND
98 // MIN and TIMES become LAND
99 // MAX and PLUS become LOR
100 // NE, ISNE, RMINUS, and MINUS become LXOR
101 // ISEQ becomes EQ
102 // ISGT becomes GT
103 // ISLT becomes LT
104 // ISGE becomes GE
105 // ISLE becomes LE
106
107 if (zcode == GB_BOOL_code)
108 {
109 // rename the monoid
110 add_opcode = GB_boolean_rename (add_opcode) ;
111 }
112
113 if (xcode == GB_BOOL_code) // && (ycode == GB_BOOL_code)
114 {
115 // rename the multiplicative operator
116 mult_opcode = GB_boolean_rename (mult_opcode) ;
117 }
118
119 //--------------------------------------------------------------------------
120 // handle the flip
121 //--------------------------------------------------------------------------
122
123 if (flipxy)
124 {
125 // z = fmult (b,a) will be computed: handle this by renaming the
126 // multiplicative operator, if possible.
127
128 // handle the flip
129 bool handled ;
130 mult_opcode = GB_binop_flip (mult_opcode, &handled) ;
131
132 if (handled)
133 {
134 // the flip is now handled completely, so discard flipxy
135 flipxy = false ;
136 }
137 }
138
139 // If flipxy is still true, then the multiplier must be used as fmult(b,a)
140 // inside the semiring, since it has no flipped equivalent.
141
142 //--------------------------------------------------------------------------
143 // determine if A and/or B are value-agnostic
144 //--------------------------------------------------------------------------
145
146 // These 1st, 2nd, and pair operators are all handled by the flip, so if
147 // flipxy is still true, all of these booleans will be false.
148 bool op_is_first = (mult_opcode == GB_FIRST_opcode ) ;
149 bool op_is_second = (mult_opcode == GB_SECOND_opcode) ;
150 bool op_is_pair = (mult_opcode == GB_PAIR_opcode) ;
151 bool A_is_pattern = op_is_second || op_is_pair ;
152 bool B_is_pattern = op_is_first || op_is_pair ;
153
154 //--------------------------------------------------------------------------
155 // enumify the multiplier
156 //--------------------------------------------------------------------------
157
158 int mult_ecode ;
159 GB_enumify_binop (&mult_ecode, mult_opcode, xcode, true) ;
160
161 //--------------------------------------------------------------------------
162 // enumify the monoid
163 //--------------------------------------------------------------------------
164
165 int add_ecode, id_ecode, term_ecode ;
166 GB_enumify_monoid (&add_code, &id_ecode, &term_ecode, ) ;
167
168 //--------------------------------------------------------------------------
169 // enumify the types
170 //--------------------------------------------------------------------------
171
172 int acode = A_is_pattern ? 0 : atype->code ; // 0 to 14
173 int bcode = B_is_pattern ? 0 : btype->code ; // 0 to 14
174 int ccode = ctype->code ; // 1 to 14
175
176 //--------------------------------------------------------------------------
177 // enumify the mask
178 //--------------------------------------------------------------------------
179
180 int mtype_code = (mtype == NULL) ? 0 : mtype->code ; // 0 to 14
181 int mask_ecode ;
182 GB_enumify_mask (&mask_ecode, mtype_code, Mask_struct, Mask_comp) ;
183
184 //--------------------------------------------------------------------------
185 // enumify the sparsity structures of C, M, A, and B
186 //--------------------------------------------------------------------------
187
188 int csparsity, msparsity, asparsity, bsparsity ;
189 GB_enumify_sparsity (&csparsity, C_sparsity) ;
190 GB_enumify_sparsity (&msparsity, M_sparsity) ;
191 GB_enumify_sparsity (&asparsity, A_sparsity) ;
192 GB_enumify_sparsity (&bsparsity, B_sparsity) ;
193
194 //--------------------------------------------------------------------------
195 // construct the semiring scode
196 //--------------------------------------------------------------------------
197
198 // total scode bits: 60
199
200 #define LSHIFT(x,k) (((uint64_t) x) << k)
201
202 (*scode) =
203 // range bits
204 // monoid
205 LSHIFT (add_ecode , 55) | // 0 to 22 5
206 LSHIFT (id_ecode , 50) | // 0 to 31 5
207 LSHIFT (term_ecode , 45) | // 0 to 31 5
208
209 // multiplier, z = f(x,y) or f(y,x)
210 LSHIFT (mult_ecode , 37) | // 0 to 139 8
211 LSHIFT (flipxy , 36) | // 0 to 1 1
212 LSHIFT (zcode , 32) | // 0 to 14 4
213 LSHIFT (xcode , 28) | // 0 to 14 4
214 LSHIFT (ycode , 24) | // 0 to 14 4
215
216 // mask
217 LSHIFT (mask_ecode , 20) | // 0 to 13 4
218
219 // types of C, A, and B (bool, int*, uint*, etc)
220 LSHIFT (ccode , 16) | // 1 to 14 4
221 LSHIFT (acode , 12) | // 0 to 14 4
222 LSHIFT (bcode , 8) | // 0 to 14 4
223
224 // sparsity structures of C, A, and B
225 LSHIFT (csparsity , 6) | // 0 to 3 2
226 LSHIFT (msparsity , 4) | // 0 to 3 2
227 LSHIFT (asparsity , 2) | // 0 to 3 2
228 LSHIFT (bsparsity , 0) ; // 0 to 3 2
229 }
230
231 //------------------------------------------------------------------------------
232 // GB_macrofy_semiring: construct all macros for a semiring
233 //------------------------------------------------------------------------------
234
GB_macrofy_semiring(char * semiring_macros,uint64_t scode)235 void GB_macrofy_semiring // construct all macros for a semiring
236 (
237 // output:
238 char *semiring_macros, // all macros that define the semiring
239 // input:
240 uint64_t scode
241 )
242 {
243
244 //--------------------------------------------------------------------------
245 // extract the semiring scode
246 //--------------------------------------------------------------------------
247
248 #define RSHIFT(x,k,b) (x >> k) && ((((uint64_t) 1) << b) - 1)
249
250 // monoid
251 int add_ecode = RSHIFT (scode, 55, 5) ;
252 int id_ecode = RSHIFT (scode, 50, 5) ;
253 int term_ecode = RSHIFT (scode, 45, 5) ;
254 bool is_term = (term_ecode < 30) ;
255
256 // multiplier
257 int mult_ecode = RSHIFT (scode, 37, 8) ;
258 bool flipxy = RSHIFT (scode, 36, 1) ;
259 int zcode = RSHIFT (scode, 32, 4) ;
260 int xcode = RSHIFT (scode, 28, 4) ;
261 int ycode = RSHIFT (scode, 24, 4) ;
262
263 // mask
264 int mask_ecode = RSHIFT (scode, 20, 4) ;
265
266 // types of C, A, and B
267 int acode = RSHIFT (scode, 16, 4) ;
268 int bcode = RSHIFT (scode, 12, 4) ;
269 int ccode = RSHIFT (scode, 8, 4) ;
270
271 // formats of C, A, and B
272 int csparsity = RSHIFT (scode, 6, 2) ;
273 int msparsity = RSHIFT (scode, 4, 2) ;
274 int asparsity = RSHIFT (scode, 2, 2) ;
275 int bsparsity = RSHIFT (scode, 0, 2) ;
276
277 //--------------------------------------------------------------------------
278 // construct macros to load scalars from A and B (and typecast) them
279 //--------------------------------------------------------------------------
280
281 // TODO: these need to be typecasted when loaded.
282 // if flipxy false: A is typecasted to x, and B is typecasted to y.
283 // if flipxy true: A is typecasted to y, and B is typecasted to x.
284
285 bool A_is_pattern = (acode == 0) ;
286 bool B_is_pattern = (bcode == 0) ;
287
288 char acast_macro [GB_CUDA_STRLEN+1] ;
289 char bcast_macro [GB_CUDA_STRLEN+1] ;
290 GB_stringify_load (acast_macro, "GB_GETA", A_is_pattern) ;
291 GB_stringify_load (bcast_macro, "GB_GETB", B_is_pattern) ;
292
293 //--------------------------------------------------------------------------
294 // construct macros for the multiply
295 //--------------------------------------------------------------------------
296
297 char s [GB_CUDA_STRLEN+1] ;
298 char mult_macro [GB_CUDA_STRLEN+1] ;
299 GB_charify_binop (&s, mult_ecode) ;
300 GB_macrofy_binop (mult_macro, "GB_MULT", s, flipxy) ;
301
302 //--------------------------------------------------------------------------
303 // construct the monoid macros
304 //--------------------------------------------------------------------------
305
306 char add_macro [GB_CUDA_STRLEN+1] ;
307 char identity_macro [GB_CUDA_STRLEN+1] ;
308 char terminal_expression_macro [GB_CUDA_STRLEN+1] ;
309 char terminal_statement_macro [GB_CUDA_STRLEN+1] ;
310 GB_macrofy_monoid (add_macro, identity_macro, terminal_expression_macro,
311 terminal_statement_macro, add_ecode, id_ecode, term_ecode) ;
312
313 //--------------------------------------------------------------------------
314 // macro to typecast the result back into C
315 //--------------------------------------------------------------------------
316
317 // for the ANY_PAIR semiring, "c_is_one" will be true, and Cx [0..cnz] will
318 // be filled with all 1's later.
319 bool c_is_one = false ;
320 // TODO:
321 // (add_ecode == GB_ANY_opcode && mult_opcode == GB_PAIR_opcode) ;
322 char ccast_macro [GB_CUDA_STRLEN+1] ;
323 GB_stringify_load (ccast_macro, "GB_PUTC", c_is_one) ;
324
325 //--------------------------------------------------------------------------
326 // construct the macros to access the mask (if any), and its name
327 //--------------------------------------------------------------------------
328
329 const char *mask_macros = "" ;
330 GB_macrofy_mask (&mask_macros, mask_ecode) ;
331
332 //--------------------------------------------------------------------------
333 // determine the sparsity formats of C, M, A, and B
334 //--------------------------------------------------------------------------
335
336 const char *csparsity_macros = "" ;
337 const char *msparsity_macros = "" ;
338 const char *asparsity_macros = "" ;
339 const char *bsparsity_macros = "" ;
340 GB_macrofy_sparsity (&csparsity_macros, "C", csparsity) ;
341 GB_macrofy_sparsity (&msparsity_macros, "M", csparsity) ;
342 GB_macrofy_sparsity (&asparsity_macros, "A", csparsity) ;
343 GB_macrofy_sparsity (&bsparsity_macros, "B", csparsity) ;
344
345 //--------------------------------------------------------------------------
346 // build the final string that defines all semiring macros
347 //--------------------------------------------------------------------------
348
349 snprintf (semiring_macros, GB_CUDA_STRLEN,
350 "%s\n" "%s\n" "%s\n" "%s\n" "%s\n" "%s\n" "%s\n" "%s\n" "%s\n" "%s\n"
351 "%s\n" "%s\n" "%s\n",
352 acast_macro, bcast_macro, mult_macro, add_macro, identity_macro,
353 terminal_expression_macro, terminal_statement_macro, ccast_macro,
354 mask_macros, csparsity_macros, msparsity_macros, asparsity_macros,
355 bsparsity_macros) ;
356 }
357
358