1 //------------------------------------------------------------------------------
2 // GB_emult_01_phase2: C=A.*B, C<M>=A.*B, or C<!M>=A.*B
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // GB_emult_01_phase2 computes C=A.*B, C<M>=A.*B, or C<!M>=A.*B. It is
11 // preceded first by GB_emult_01_phase0, which computes the list of vectors of
12 // C to compute (Ch) and their location in M, A, and B (C_to_[MAB]). Next,
13 // GB_emult_01_phase1 counts the entries in each vector C(:,j) and computes Cp.
14
15 // GB_emult_01_phase2 computes the pattern and values of each vector of C(:,j),
16 // entirely in parallel.
17
18 // C, M, A, and B can be have any sparsity structure. If M is sparse or
19 // hypersparse, and complemented, however, then it is not applied and not
20 // passed to this function. It is applied later, as determined by
21 // GB_emult_sparsity.
22
23 // This function either frees Cp or transplants it into C, as C->p. Either
24 // way, the caller must not free it.
25
26 #include "GB_ewise.h"
27 #include "GB_emult.h"
28 #include "GB_binop.h"
29 #include "GB_unused.h"
30 #ifndef GBCOMPACT
31 #include "GB_binop__include.h"
32 #endif
33
34 #define GB_FREE_ALL \
35 { \
36 GB_phbix_free (C) ; \
37 }
38
GB_emult_01_phase2(GrB_Matrix C,const GrB_Type ctype,const bool C_is_csc,const GrB_BinaryOp op,int64_t ** Cp_handle,size_t Cp_size,const int64_t Cnvec_nonempty,const GB_task_struct * restrict TaskList,const int C_ntasks,const int C_nthreads,const int64_t Cnvec,const int64_t * restrict Ch,size_t Ch_size,const int64_t * restrict C_to_M,const int64_t * restrict C_to_A,const int64_t * restrict C_to_B,const int C_sparsity,const int ewise_method,const GrB_Matrix M,const bool Mask_struct,const bool Mask_comp,const GrB_Matrix A,const GrB_Matrix B,GB_Context Context)39 GrB_Info GB_emult_01_phase2 // C=A.*B or C<M>=A.*B
40 (
41 GrB_Matrix C, // output matrix, static header
42 const GrB_Type ctype, // type of output matrix C
43 const bool C_is_csc, // format of output matrix C
44 const GrB_BinaryOp op, // op to perform C = op (A,B)
45 // from phase1:
46 int64_t **Cp_handle, // vector pointers for C
47 size_t Cp_size,
48 const int64_t Cnvec_nonempty, // # of non-empty vectors in C
49 // tasks from phase1a:
50 const GB_task_struct *restrict TaskList, // array of structs
51 const int C_ntasks, // # of tasks
52 const int C_nthreads, // # of threads to use
53 // analysis from phase0:
54 const int64_t Cnvec,
55 const int64_t *restrict Ch,
56 size_t Ch_size,
57 const int64_t *restrict C_to_M,
58 const int64_t *restrict C_to_A,
59 const int64_t *restrict C_to_B,
60 const int C_sparsity,
61 // from GB_emult_sparsity:
62 const int ewise_method,
63 // original input:
64 const GrB_Matrix M, // optional mask, may be NULL
65 const bool Mask_struct, // if true, use the only structure of M
66 const bool Mask_comp, // if true, use !M
67 const GrB_Matrix A,
68 const GrB_Matrix B,
69 GB_Context Context
70 )
71 {
72
73 //--------------------------------------------------------------------------
74 // check inputs
75 //--------------------------------------------------------------------------
76
77 ASSERT (C != NULL && C->static_header) ;
78
79 ASSERT_BINARYOP_OK (op, "op for emult phase2", GB0) ;
80 ASSERT_MATRIX_OK (A, "A for emult phase2", GB0) ;
81 ASSERT (!GB_ZOMBIES (A)) ;
82 ASSERT (!GB_JUMBLED (A)) ;
83 ASSERT (!GB_PENDING (A)) ;
84
85 ASSERT_MATRIX_OK (B, "B for emult phase2", GB0) ;
86 ASSERT (!GB_ZOMBIES (B)) ;
87 ASSERT (!GB_JUMBLED (B)) ;
88 ASSERT (!GB_PENDING (B)) ;
89
90 ASSERT_MATRIX_OK_OR_NULL (M, "M for emult phase2", GB0) ;
91 ASSERT (!GB_ZOMBIES (M)) ;
92 ASSERT (!GB_JUMBLED (M)) ;
93 ASSERT (!GB_PENDING (M)) ;
94
95 ASSERT (A->vdim == B->vdim) ;
96
97 ASSERT (Cp_handle != NULL) ;
98 int64_t *restrict Cp = (*Cp_handle) ;
99
100 //--------------------------------------------------------------------------
101 // get the opcode
102 //--------------------------------------------------------------------------
103
104 bool C_is_hyper = (C_sparsity == GxB_HYPERSPARSE) ;
105 bool C_is_sparse_or_hyper = (C_sparsity == GxB_SPARSE) || C_is_hyper ;
106 ASSERT (C_is_sparse_or_hyper == (Cp != NULL)) ;
107 ASSERT (C_is_hyper == (Ch != NULL)) ;
108
109 GB_Opcode opcode = op->opcode ;
110 bool op_is_positional = GB_OPCODE_IS_POSITIONAL (opcode) ;
111 bool op_is_first = (opcode == GB_FIRST_opcode) ;
112 bool op_is_second = (opcode == GB_SECOND_opcode) ;
113 bool op_is_pair = (opcode == GB_PAIR_opcode) ;
114
115 ASSERT (GB_Type_compatible (ctype, op->ztype)) ;
116 ASSERT (GB_IMPLIES (!(op_is_second || op_is_pair || op_is_positional),
117 GB_Type_compatible (A->type, op->xtype))) ;
118 ASSERT (GB_IMPLIES (!(op_is_first || op_is_pair || op_is_positional),
119 GB_Type_compatible (B->type, op->ytype))) ;
120
121 //--------------------------------------------------------------------------
122 // allocate the output matrix C
123 //--------------------------------------------------------------------------
124
125 int64_t cnz = (C_is_sparse_or_hyper) ? Cp [Cnvec] : (A->vlen*A->vdim) ;
126
127 // allocate the result C (but do not allocate C->p or C->h)
128 GrB_Info info = GB_new_bix (&C, true, // any sparsity, static header
129 ctype, A->vlen, A->vdim, GB_Ap_null, C_is_csc,
130 C_sparsity, true, A->hyper_switch, Cnvec, cnz, true, Context) ;
131 if (info != GrB_SUCCESS)
132 {
133 // out of memory; caller must free C_to_M, C_to_A, C_to_B
134 // Ch must not be freed since Ch is always shallow
135 GB_FREE (Cp_handle, Cp_size) ;
136 return (info) ;
137 }
138
139 // transplant Cp into C as the vector pointers, from GB_emult_01_phase1
140 if (C_is_sparse_or_hyper)
141 {
142 C->nvec_nonempty = Cnvec_nonempty ;
143 C->p = (int64_t *) Cp ; C->p_size = Cp_size ;
144 (*Cp_handle) = NULL ;
145 }
146
147 // add Ch as the hypersparse list for C, from GB_emult_01_phase0
148 if (C_is_hyper)
149 {
150 // C->h is currently shallow; a copy is made at the end
151 C->h = (int64_t *) Ch ; C->h_size = Ch_size ;
152 C->h_shallow = true ;
153 C->nvec = Cnvec ;
154 }
155
156 // Cp has been transplanted into C; so it is not freed here
157 ASSERT ((*Cp_handle) == NULL) ;
158 C->magic = GB_MAGIC ;
159 GB_Type_code ccode = ctype->code ;
160
161 //--------------------------------------------------------------------------
162 // check if the values of A and/or B are ignored
163 //--------------------------------------------------------------------------
164
165 // With C = ewisemult (A,B), only the intersection of A and B is used.
166 // If op is SECOND or PAIR, the values of A are never accessed.
167 // If op is FIRST or PAIR, the values of B are never accessed.
168 // If op is PAIR, the values of A and B are never accessed.
169 // Contrast with ewiseadd.
170
171 // A is passed as x, and B as y, in z = op(x,y)
172 bool A_is_pattern = op_is_second || op_is_pair || op_is_positional ;
173 bool B_is_pattern = op_is_first || op_is_pair || op_is_positional ;
174
175 //--------------------------------------------------------------------------
176 // using a built-in binary operator (except for positional operators)
177 //--------------------------------------------------------------------------
178
179 bool done = false ;
180
181 #ifndef GBCOMPACT
182
183 //----------------------------------------------------------------------
184 // define the worker for the switch factory
185 //----------------------------------------------------------------------
186
187 #define GB_AemultB_01(mult,xname) GB (_AemultB_01_ ## mult ## xname)
188
189 #define GB_BINOP_WORKER(mult,xname) \
190 { \
191 info = GB_AemultB_01(mult,xname) (C, C_sparsity, ewise_method, \
192 M, Mask_struct, Mask_comp, \
193 A, B, C_to_M, C_to_A, C_to_B, \
194 TaskList, C_ntasks, C_nthreads, Context) ; \
195 done = (info != GrB_NO_VALUE) ; \
196 } \
197 break ;
198
199 //----------------------------------------------------------------------
200 // launch the switch factory
201 //----------------------------------------------------------------------
202
203 GB_Type_code xcode, ycode, zcode ;
204 if (!op_is_positional &&
205 GB_binop_builtin (A->type, A_is_pattern, B->type, B_is_pattern,
206 op, false, &opcode, &xcode, &ycode, &zcode) && ccode == zcode)
207 {
208 #include "GB_binop_factory.c"
209 }
210
211 #endif
212
213 //--------------------------------------------------------------------------
214 // generic worker
215 //--------------------------------------------------------------------------
216
217 if (!done)
218 {
219 GB_BURBLE_MATRIX (C, "(generic emult: %s) ", op->name) ;
220 GB_ewise_generic (C, op, TaskList, C_ntasks, C_nthreads,
221 C_to_M, C_to_A, C_to_B, C_sparsity, ewise_method, NULL,
222 NULL, 0, 0, NULL, 0, 0, NULL, 0, 0,
223 M, Mask_struct, Mask_comp, A, B, Context) ;
224 }
225
226 //--------------------------------------------------------------------------
227 // construct the final C->h
228 //--------------------------------------------------------------------------
229
230 GB_OK (GB_hypermatrix_prune (C, Context)) ;
231
232 //--------------------------------------------------------------------------
233 // return result
234 //--------------------------------------------------------------------------
235
236 ASSERT_MATRIX_OK (C, "C output for emult phase2", GB0) ;
237 return (GrB_SUCCESS) ;
238 }
239
240