1 /* reducer_opor.h -*- C++ -*- 2 * 3 * @copyright 4 * Copyright (C) 2009-2013, Intel Corporation 5 * All rights reserved. 6 * 7 * @copyright 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * * Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * * Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the 17 * distribution. 18 * * Neither the name of Intel Corporation nor the names of its 19 * contributors may be used to endorse or promote products derived 20 * from this software without specific prior written permission. 21 * 22 * @copyright 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 30 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY 33 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 * POSSIBILITY OF SUCH DAMAGE. 35 */ 36 37 /** @file reducer_opor.h 38 * 39 * @brief Defines classes for doing parallel bitwise or reductions. 40 * 41 * @ingroup ReducersOr 42 * 43 * @see ReducersOr 44 */ 45 46 #ifndef REDUCER_OPOR_H_INCLUDED 47 #define REDUCER_OPOR_H_INCLUDED 48 49 #include <cilk/reducer.h> 50 51 /** @defgroup ReducersOr Bitwise Or Reducers 52 * 53 * Bitwise and reducers allow the computation of the bitwise and of a set of 54 * values in parallel. 55 * 56 * @ingroup Reducers 57 * 58 * You should be familiar with @ref pagereducers "Cilk reducers", described in 59 * file `reducers.md`, and particularly with @ref reducers_using, before trying 60 * to use the information in this file. 61 * 62 * @section redopor_usage Usage Example 63 * 64 * cilk::reducer< cilk::op_or<unsigned> > r; 65 * cilk_for (int i = 0; i != N; ++i) { 66 * *r |= a[i]; 67 * } 68 * unsigned result; 69 * r.move_out(result); 70 * 71 * @section redopor_monoid The Monoid 72 * 73 * @subsection redopor_monoid_values Value Set 74 * 75 * The value set of a bitwise or reducer is the set of values of `Type`, which 76 * is expected to be a builtin integer type which has a representation as a 77 * sequence of bits (or something like it, such as `bool` or `std::bitset`). 78 * 79 * @subsection redopor_monoid_operator Operator 80 * 81 * The operator of a bitwise or reducer is the bitwise or operator, defined by 82 * the “`|`” binary operator on `Type`. 83 * 84 * @subsection redopor_monoid_identity Identity 85 * 86 * The identity value of the reducer is the value whose representation 87 * contains all 0-bits. This is expected to be the value of the default 88 * constructor `Type()`. 89 * 90 * @section redopor_operations Operations 91 * 92 * @subsection redopor_constructors Constructors 93 * 94 * reducer() // identity 95 * reducer(const Type& value) 96 * reducer(move_in(Type& variable)) 97 * 98 * @subsection redopor_get_set Set and Get 99 * 100 * r.set_value(const Type& value) 101 * const Type& = r.get_value() const 102 * r.move_in(Type& variable) 103 * r.move_out(Type& variable) 104 * 105 * @subsection redopor_initial Initial Values 106 * 107 * If a bitwise or reducer is constructed without an explicit initial value, 108 * then its initial value will be its identity value, as long as `Type` 109 * satisfies the requirements of @ref redopor_types. 110 * 111 * @subsection redopor_view_ops View Operations 112 * 113 * *r |= a 114 * *r = *r | a 115 * *r = *r | a1 | a2 … | an 116 * 117 * @section redopor_types Type and Operator Requirements 118 * 119 * `Type` must be `Copy Constructible`, `Default Constructible`, and 120 * `Assignable`. 121 * 122 * The operator “`|=`” must be defined on `Type`, with `x |= a` having the 123 * same meaning as `x = x | a`. 124 * 125 * The expression `Type()` must be a valid expression which yields the 126 * identity value (the value of `Type` whose representation consists of all 127 * 0-bits). 128 * 129 * @section redopor_in_c Bitwise Or Reducers in C 130 * 131 * The @ref CILK_C_REDUCER_OPOR and @ref CILK_C_REDUCER_OPOR_TYPE macros can 132 * be used to do bitwise or reductions in C. For example: 133 * 134 * CILK_C_REDUCER_OPOR(r, uint, 0); 135 * CILK_C_REGISTER_REDUCER(r); 136 * cilk_for(int i = 0; i != n; ++i) { 137 * REDUCER_VIEW(r) |= a[i]; 138 * } 139 * CILK_C_UNREGISTER_REDUCER(r); 140 * printf("The bitwise OR of the elements of a is %x\n", REDUCER_VIEW(r)); 141 * 142 * See @ref reducers_c_predefined. 143 */ 144 145 #ifdef __cplusplus 146 147 namespace cilk { 148 149 /** The bitwise or reducer view class. 150 * 151 * This is the view class for reducers created with 152 * `cilk::reducer< cilk::op_or<Type> >`. It holds the accumulator variable for 153 * the reduction, and allows only `or` operations to be performed on it. 154 * 155 * @note The reducer “dereference” operation (`reducer::operator *()`) 156 * yields a reference to the view. Thus, for example, the view class’s 157 * `|=` operation would be used in an expression like `*r |= a`, where 158 * `r` is an opmod reducer variable. 159 * 160 * @tparam Type The type of the contained accumulator variable. This will 161 * be the value type of a monoid_with_view that is 162 * instantiated with this view. 163 * 164 * @see ReducersOr 165 * @see op_or 166 * 167 * @ingroup ReducersOr 168 */ 169 template <typename Type> 170 class op_or_view : public scalar_view<Type> 171 { 172 typedef scalar_view<Type> base; 173 174 public: 175 /** Class to represent the right-hand side of `*reducer = *reducer | value`. 176 * 177 * The only assignment operator for the op_or_view class takes an 178 * rhs_proxy as its operand. This results in the syntactic restriction 179 * that the only expressions that can be assigned to an op_or_view are 180 * ones which generate an rhs_proxy — that is, expressions of the form 181 * `op_or_view | value ... | value`. 182 * 183 * @warning 184 * The lhs and rhs views in such an assignment must be the same; 185 * otherwise, the behavior will be undefined. (I.e., `v1 = v1 | x` is 186 * legal; `v1 = v2 | x` is illegal.) This condition will be checked with 187 * a runtime assertion when compiled in debug mode. 188 * 189 * @see op_or_view 190 */ 191 class rhs_proxy { 192 friend class op_or_view; 193 194 const op_or_view* m_view; 195 Type m_value; 196 197 // Constructor is invoked only from op_or_view::operator|(). 198 // rhs_proxy(const op_or_view * view,const Type & value)199 rhs_proxy(const op_or_view* view, const Type& value) : m_view(view), m_value(value) {} 200 201 rhs_proxy& operator=(const rhs_proxy&); // Disable assignment operator 202 rhs_proxy(); // Disable default constructor 203 204 public: 205 /** Bitwise or with an additional rhs value. If `v` is an op_or_view 206 * and `a1` is a value, then the expression `v | a1` invokes the 207 * view’s `operator|()` to create an rhs_proxy for `(v, a1)`; then 208 * `v | a1 | a2` invokes the rhs_proxy’s `operator|()` to create a new 209 * rhs_proxy for `(v, a1|a2)`. This allows the right-hand side of an 210 * assignment to be not just `view | value`, but 211 ( `view | value | value ... | value`. The effect is that 212 * 213 * v = v | a1 | a2 ... | an; 214 * 215 * is evaluated as 216 * 217 * v = v | (a1 | a2 ... | an); 218 */ 219 rhs_proxy& operator|(const Type& x) { m_value |= x; return *this; } 220 }; 221 222 223 /** Default/identity constructor. This constructor initializes the 224 * contained value to `Type()`. 225 */ op_or_view()226 op_or_view() : base() {} 227 228 /** Construct with a specified initial value. 229 */ op_or_view(const Type & v)230 explicit op_or_view(const Type& v) : base(v) {} 231 232 /** Reduction operation. 233 * 234 * This function is invoked by the @ref op_or monoid to combine the views 235 * of two strands when the right strand merges with the left one. It 236 * “ors” the value contained in the left-strand view by the value 237 * contained in the right-strand view, and leaves the value in the 238 * right-strand view undefined. 239 * 240 * @param right A pointer to the right-strand view. (`this` points to 241 * the left-strand view.) 242 * 243 * @note Used only by the @ref op_or monoid to implement the monoid 244 * reduce operation. 245 */ reduce(op_or_view * right)246 void reduce(op_or_view* right) { this->m_value |= right->m_value; } 247 248 /** @name Accumulator variable updates. 249 * 250 * These functions support the various syntaxes for “oring” the 251 * accumulator variable contained in the view with some value. 252 */ 253 //@{ 254 255 /** Or the accumulator variable with @a x. 256 */ 257 op_or_view& operator|=(const Type& x) { this->m_value |= x; return *this; } 258 259 /** Create an object representing `*this | x`. 260 * 261 * @see rhs_proxy 262 */ 263 rhs_proxy operator|(const Type& x) const { return rhs_proxy(this, x); } 264 265 /** Assign the result of a `view | value` expression to the view. Note that 266 * this is the only assignment operator for this class. 267 * 268 * @see rhs_proxy 269 */ 270 op_or_view& operator=(const rhs_proxy& rhs) { 271 __CILKRTS_ASSERT(this == rhs.m_view); 272 this->m_value |= rhs.m_value; 273 return *this; 274 } 275 276 //@} 277 }; 278 279 /** Monoid class for bitwise or reductions. Instantiate the cilk::reducer 280 * template class with an op_or monoid to create a bitwise or reducer 281 * class. For example, to compute the bitwise or of a set of `unsigned long` 282 * values: 283 * 284 * cilk::reducer< cilk::op_or<unsigned long> > r; 285 * 286 * @tparam Type The reducer value type. 287 * @tparam Align If `false` (the default), reducers instantiated on this 288 * monoid will be naturally aligned (the Cilk library 1.0 289 * behavior). If `true`, reducers instantiated on this monoid 290 * will be cache-aligned for binary compatibility with 291 * reducers in Cilk library version 0.9. 292 * 293 * @see ReducersOr 294 * @see op_or_view 295 * 296 * @ingroup ReducersOr 297 */ 298 template <typename Type, bool Align = false> 299 struct op_or : public monoid_with_view<op_or_view<Type>, Align> {}; 300 301 /** Deprecated bitwise or reducer class. 302 * 303 * reducer_opor is the same as @ref reducer<@ref op_or>, except that 304 * reducer_opor is a proxy for the contained view, so that accumulator 305 * variable update operations can be applied directly to the reducer. For 306 * example, a value is ored with a `reducer<%op_or>` with `*r |= a`, but a 307 * value can be ored with a `%reducer_opor` with `r |= a`. 308 * 309 * @deprecated Users are strongly encouraged to use `reducer<monoid>` 310 * reducers rather than the old wrappers like reducer_opor. 311 * The `reducer<monoid>` reducers show the reducer/monoid/view 312 * architecture more clearly, are more consistent in their 313 * implementation, and present a simpler model for new 314 * user-implemented reducers. 315 * 316 * @note Implicit conversions are provided between `%reducer_opor` 317 * and `reducer<%op_or>`. This allows incremental code 318 * conversion: old code that used `%reducer_opor` can pass a 319 * `%reducer_opor` to a converted function that now expects a 320 * pointer or reference to a `reducer<%op_or>`, and vice 321 * versa. 322 * 323 * @tparam Type The value type of the reducer. 324 * 325 * @see op_or 326 * @see reducer 327 * @see ReducersOr 328 * 329 * @ingroup ReducersOr 330 */ 331 template <typename Type> 332 class reducer_opor : public reducer< op_or<Type, true> > 333 { 334 typedef reducer< op_or<Type, true> > base; 335 using base::view; 336 337 public: 338 /// The view type for the reducer. 339 typedef typename base::view_type view_type; 340 341 /// The view’s rhs proxy type. 342 typedef typename view_type::rhs_proxy rhs_proxy; 343 344 /// The view type for the reducer. 345 typedef view_type View; 346 347 /// The monoid type for the reducer. 348 typedef typename base::monoid_type Monoid; 349 350 /** @name Constructors 351 */ 352 //@{ 353 354 /** Default (identity) constructor. 355 * 356 * Constructs the wrapper with the default initial value of `Type()`. 357 */ reducer_opor()358 reducer_opor() {} 359 360 /** Value constructor. 361 * 362 * Constructs the wrapper with a specified initial value. 363 */ reducer_opor(const Type & initial_value)364 explicit reducer_opor(const Type& initial_value) : base(initial_value) {} 365 366 //@} 367 368 /** @name Forwarded functions 369 * @details Functions that update the contained accumulator variable are 370 * simply forwarded to the contained @ref op_and_view. */ 371 //@{ 372 373 /// @copydoc op_or_view::operator|=(const Type&) 374 reducer_opor& operator|=(const Type& x) 375 { 376 view() |= x; return *this; 377 } 378 379 // The legacy definition of reducer_opor::operator|() has different 380 // behavior and a different return type than this definition. The legacy 381 // version is defined as a member function, so this new version is defined 382 // as a free function to give it a different signature, so that they won’t 383 // end up sharing a single object file entry. 384 385 /// @copydoc op_or_view::operator|(const Type&) const 386 friend rhs_proxy operator|(const reducer_opor& r, const Type& x) 387 { 388 return r.view() | x; 389 } 390 391 /// @copydoc op_and_view::operator=(const rhs_proxy&) 392 reducer_opor& operator=(const rhs_proxy& temp) 393 { 394 view() = temp; return *this; 395 } 396 //@} 397 398 /** @name Dereference 399 * @details Dereferencing a wrapper is a no-op. It simply returns the 400 * wrapper. Combined with the rule that the wrapper forwards view 401 * operations to its contained view, this means that view operations can 402 * be written the same way on reducers and wrappers, which is convenient 403 * for incrementally converting old code using wrappers to use reducers 404 * instead. That is: 405 * 406 * reducer< op_and<int> > r; 407 * *r &= a; // *r returns the view 408 * // operator &= is a view member function 409 * 410 * reducer_opand<int> w; 411 * *w &= a; // *w returns the wrapper 412 * // operator &= is a wrapper member function that 413 * // calls the corresponding view function 414 */ 415 //@{ 416 reducer_opor& operator*() { return *this; } 417 reducer_opor const& operator*() const { return *this; } 418 419 reducer_opor* operator->() { return this; } 420 reducer_opor const* operator->() const { return this; } 421 //@} 422 423 /** @name Upcast 424 * @details In Cilk library 0.9, reducers were always cache-aligned. In 425 * library 1.0, reducer cache alignment is optional. By default, reducers 426 * are unaligned (i.e., just naturally aligned), but legacy wrappers 427 * inherit from cache-aligned reducers for binary compatibility. 428 * 429 * This means that a wrapper will automatically be upcast to its aligned 430 * reducer base class. The following conversion operators provide 431 * pseudo-upcasts to the corresponding unaligned reducer class. 432 */ 433 //@{ 434 operator reducer< op_or<Type, false> >& () 435 { 436 return *reinterpret_cast< reducer< op_or<Type, false> >* >(this); 437 } 438 operator const reducer< op_or<Type, false> >& () const 439 { 440 return *reinterpret_cast< const reducer< op_or<Type, false> >* >(this); 441 } 442 //@} 443 444 }; 445 446 /// @cond internal 447 /** Metafunction specialization for reducer conversion. 448 * 449 * This specialization of the @ref legacy_reducer_downcast template class 450 * defined in reducer.h causes the `reducer< op_or<Type> >` class to have an 451 * `operator reducer_opor<Type>& ()` conversion operator that statically 452 * downcasts the `reducer<op_or>` to the corresponding `reducer_opor` type. 453 * (The reverse conversion, from `reducer_opor` to `reducer<op_or>`, is just 454 * an upcast, which is provided for free by the language.) 455 * 456 * @ingroup ReducersOr 457 */ 458 template <typename Type, bool Align> 459 struct legacy_reducer_downcast<reducer<op_or<Type, Align> > > 460 { 461 typedef reducer_opor<Type> type; 462 }; 463 /// @endcond 464 465 } // namespace cilk 466 467 #endif /* __cplusplus */ 468 469 470 /** @ingroup ReducersOr 471 */ 472 //@{ 473 474 /** @name C language reducer macros 475 * 476 * These macros are used to declare and work with op_or reducers in C code. 477 * 478 * @see @ref page_reducers_in_c 479 */ 480 //@{ 481 482 __CILKRTS_BEGIN_EXTERN_C 483 484 /** Opor reducer type name. 485 * 486 * This macro expands into the identifier which is the name of the op_or 487 * reducer type for a specified numeric type. 488 * 489 * @param tn The @ref reducers_c_type_names "numeric type name" specifying 490 * the type of the reducer. 491 * 492 * @see @ref reducers_c_predefined 493 * @see ReducersOr 494 */ 495 #define CILK_C_REDUCER_OPOR_TYPE(tn) \ 496 __CILKRTS_MKIDENT(cilk_c_reducer_opor_,tn) 497 498 /** Declare an op_or reducer object. 499 * 500 * This macro expands into a declaration of an op_or reducer object for a 501 * specified numeric type. For example: 502 * 503 * CILK_C_REDUCER_OPOR(my_reducer, ulong, 0); 504 * 505 * @param obj The variable name to be used for the declared reducer object. 506 * @param tn The @ref reducers_c_type_names "numeric type name" specifying 507 * the type of the reducer. 508 * @param v The initial value for the reducer. (A value which can be 509 * assigned to the numeric type represented by @a tn.) 510 * 511 * @see @ref reducers_c_predefined 512 * @see ReducersOr 513 */ 514 #define CILK_C_REDUCER_OPOR(obj,tn,v) \ 515 CILK_C_REDUCER_OPOR_TYPE(tn) obj = \ 516 CILK_C_INIT_REDUCER(_Typeof(obj.value), \ 517 __CILKRTS_MKIDENT(cilk_c_reducer_opor_reduce_,tn), \ 518 __CILKRTS_MKIDENT(cilk_c_reducer_opor_identity_,tn), \ 519 __cilkrts_hyperobject_noop_destroy, v) 520 521 /// @cond internal 522 523 /** Declare the op_or reducer functions for a numeric type. 524 * 525 * This macro expands into external function declarations for functions which 526 * implement the reducer functionality for the op_or reducer type for a 527 * specified numeric type. 528 * 529 * @param t The value type of the reducer. 530 * @param tn The value “type name” identifier, used to construct the reducer 531 * type name, function names, etc. 532 */ 533 #define CILK_C_REDUCER_OPOR_DECLARATION(t,tn) \ 534 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_OPOR_TYPE(tn); \ 535 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_opor,tn,l,r); \ 536 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_opor,tn); 537 538 /** Define the op_or reducer functions for a numeric type. 539 * 540 * This macro expands into function definitions for functions which implement 541 * the reducer functionality for the op_or reducer type for a specified 542 * numeric type. 543 * 544 * @param t The value type of the reducer. 545 * @param tn The value “type name” identifier, used to construct the reducer 546 * type name, function names, etc. 547 */ 548 #define CILK_C_REDUCER_OPOR_DEFINITION(t,tn) \ 549 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_OPOR_TYPE(tn); \ 550 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_opor,tn,l,r) \ 551 { *(t*)l |= *(t*)r; } \ 552 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_opor,tn) \ 553 { *(t*)v = 0; } 554 555 //@{ 556 /** @def CILK_C_REDUCER_OPOR_INSTANCE 557 * @brief Declare or define implementation functions for a reducer type. 558 * 559 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` 560 * will be defined, and this macro will generate reducer implementation 561 * functions. Everywhere else, `CILK_C_DEFINE_REDUCERS` will be undefined, and 562 * this macro will expand into external declarations for the functions. 563 */ 564 #ifdef CILK_C_DEFINE_REDUCERS 565 # define CILK_C_REDUCER_OPOR_INSTANCE(t,tn) \ 566 CILK_C_REDUCER_OPOR_DEFINITION(t,tn) 567 #else 568 # define CILK_C_REDUCER_OPOR_INSTANCE(t,tn) \ 569 CILK_C_REDUCER_OPOR_DECLARATION(t,tn) 570 #endif 571 //@} 572 573 /* Declare or define an instance of the reducer type and its functions for each 574 * numeric type. 575 */ 576 CILK_C_REDUCER_OPOR_INSTANCE(char, char) 577 CILK_C_REDUCER_OPOR_INSTANCE(unsigned char, uchar) 578 CILK_C_REDUCER_OPOR_INSTANCE(signed char, schar) 579 CILK_C_REDUCER_OPOR_INSTANCE(wchar_t, wchar_t) 580 CILK_C_REDUCER_OPOR_INSTANCE(short, short) 581 CILK_C_REDUCER_OPOR_INSTANCE(unsigned short, ushort) 582 CILK_C_REDUCER_OPOR_INSTANCE(int, int) 583 CILK_C_REDUCER_OPOR_INSTANCE(unsigned int, uint) 584 CILK_C_REDUCER_OPOR_INSTANCE(unsigned int, unsigned) /* alternate name */ 585 CILK_C_REDUCER_OPOR_INSTANCE(long, long) 586 CILK_C_REDUCER_OPOR_INSTANCE(unsigned long, ulong) 587 CILK_C_REDUCER_OPOR_INSTANCE(long long, longlong) 588 CILK_C_REDUCER_OPOR_INSTANCE(unsigned long long, ulonglong) 589 590 //@endcond 591 592 __CILKRTS_END_EXTERN_C 593 594 //@} 595 596 //@} 597 598 #endif /* REDUCER_OPOR_H_INCLUDED */ 599