xref: /llvm-project/flang/runtime/reduction.cpp (revision fc97d2e68b03bc2979395e84b645e5b3ba35aecd) 
1 //===-- runtime/reduction.cpp ---------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // Implements ALL, ANY, COUNT, IALL, IANY, IPARITY, & PARITY for all required
10 // operand types and shapes.
11 //
12 // DOT_PRODUCT, FINDLOC, MATMUL, SUM, and PRODUCT are in their own eponymous
13 // source files.
14 // NORM2, MAXLOC, MINLOC, MAXVAL, and MINVAL are in extrema.cpp.
15 
16 #include "flang/Runtime/reduction.h"
17 #include "reduction-templates.h"
18 #include "flang/Runtime/descriptor.h"
19 #include <cinttypes>
20 
21 namespace Fortran::runtime {
22 
23 // IALL, IANY, IPARITY
24 
25 template <typename INTERMEDIATE> class IntegerAndAccumulator {
26 public:
27   explicit RT_API_ATTRS IntegerAndAccumulator(const Descriptor &array)
28       : array_{array} {}
29   RT_API_ATTRS void Reinitialize() { and_ = ~INTERMEDIATE{0}; }
30   template <typename A>
31   RT_API_ATTRS void GetResult(A *p, int /*zeroBasedDim*/ = -1) const {
32     *p = static_cast<A>(and_);
33   }
34   template <typename A>
35   RT_API_ATTRS bool AccumulateAt(const SubscriptValue at[]) {
36     and_ &= *array_.Element<A>(at);
37     return true;
38   }
39 
40 private:
41   const Descriptor &array_;
42   INTERMEDIATE and_{~INTERMEDIATE{0}};
43 };
44 
45 template <typename INTERMEDIATE> class IntegerOrAccumulator {
46 public:
47   explicit RT_API_ATTRS IntegerOrAccumulator(const Descriptor &array)
48       : array_{array} {}
49   RT_API_ATTRS void Reinitialize() { or_ = 0; }
50   template <typename A>
51   RT_API_ATTRS void GetResult(A *p, int /*zeroBasedDim*/ = -1) const {
52     *p = static_cast<A>(or_);
53   }
54   template <typename A>
55   RT_API_ATTRS bool AccumulateAt(const SubscriptValue at[]) {
56     or_ |= *array_.Element<A>(at);
57     return true;
58   }
59 
60 private:
61   const Descriptor &array_;
62   INTERMEDIATE or_{0};
63 };
64 
65 template <typename INTERMEDIATE> class IntegerXorAccumulator {
66 public:
67   explicit RT_API_ATTRS IntegerXorAccumulator(const Descriptor &array)
68       : array_{array} {}
69   RT_API_ATTRS void Reinitialize() { xor_ = 0; }
70   template <typename A>
71   RT_API_ATTRS void GetResult(A *p, int /*zeroBasedDim*/ = -1) const {
72     *p = static_cast<A>(xor_);
73   }
74   template <typename A>
75   RT_API_ATTRS bool AccumulateAt(const SubscriptValue at[]) {
76     xor_ ^= *array_.Element<A>(at);
77     return true;
78   }
79 
80 private:
81   const Descriptor &array_;
82   INTERMEDIATE xor_{0};
83 };
84 
85 extern "C" {
86 CppTypeFor<TypeCategory::Integer, 1> RTDEF(IAll1)(const Descriptor &x,
87     const char *source, int line, int dim, const Descriptor *mask) {
88   return GetTotalReduction<TypeCategory::Integer, 1>(x, source, line, dim, mask,
89       IntegerAndAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IALL",
90       /*allowUnsignedForInteger=*/true);
91 }
92 CppTypeFor<TypeCategory::Integer, 2> RTDEF(IAll2)(const Descriptor &x,
93     const char *source, int line, int dim, const Descriptor *mask) {
94   return GetTotalReduction<TypeCategory::Integer, 2>(x, source, line, dim, mask,
95       IntegerAndAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IALL",
96       /*allowUnsignedForInteger=*/true);
97 }
98 CppTypeFor<TypeCategory::Integer, 4> RTDEF(IAll4)(const Descriptor &x,
99     const char *source, int line, int dim, const Descriptor *mask) {
100   return GetTotalReduction<TypeCategory::Integer, 4>(x, source, line, dim, mask,
101       IntegerAndAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IALL",
102       /*allowUnsignedForInteger=*/true);
103 }
104 CppTypeFor<TypeCategory::Integer, 8> RTDEF(IAll8)(const Descriptor &x,
105     const char *source, int line, int dim, const Descriptor *mask) {
106   return GetTotalReduction<TypeCategory::Integer, 8>(x, source, line, dim, mask,
107       IntegerAndAccumulator<CppTypeFor<TypeCategory::Integer, 8>>{x}, "IALL",
108       /*allowUnsignedForInteger=*/true);
109 }
110 #ifdef __SIZEOF_INT128__
111 CppTypeFor<TypeCategory::Integer, 16> RTDEF(IAll16)(const Descriptor &x,
112     const char *source, int line, int dim, const Descriptor *mask) {
113   return GetTotalReduction<TypeCategory::Integer, 16>(x, source, line, dim,
114       mask, IntegerAndAccumulator<CppTypeFor<TypeCategory::Integer, 16>>{x},
115       "IALL", /*allowUnsignedForInteger=*/true);
116 }
117 #endif
118 void RTDEF(IAllDim)(Descriptor &result, const Descriptor &x, int dim,
119     const char *source, int line, const Descriptor *mask) {
120   Terminator terminator{source, line};
121   auto catKind{x.type().GetCategoryAndKind()};
122   RUNTIME_CHECK(terminator,
123       catKind.has_value() &&
124           (catKind->first == TypeCategory::Integer ||
125               catKind->first == TypeCategory::Unsigned));
126   PartialIntegerReduction<IntegerAndAccumulator>(
127       result, x, dim, catKind->second, mask, "IALL", terminator);
128 }
129 
130 CppTypeFor<TypeCategory::Integer, 1> RTDEF(IAny1)(const Descriptor &x,
131     const char *source, int line, int dim, const Descriptor *mask) {
132   return GetTotalReduction<TypeCategory::Integer, 1>(x, source, line, dim, mask,
133       IntegerOrAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IANY",
134       /*allowUnsignedForInteger=*/true);
135 }
136 CppTypeFor<TypeCategory::Integer, 2> RTDEF(IAny2)(const Descriptor &x,
137     const char *source, int line, int dim, const Descriptor *mask) {
138   return GetTotalReduction<TypeCategory::Integer, 2>(x, source, line, dim, mask,
139       IntegerOrAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IANY",
140       /*allowUnsignedForInteger=*/true);
141 }
142 CppTypeFor<TypeCategory::Integer, 4> RTDEF(IAny4)(const Descriptor &x,
143     const char *source, int line, int dim, const Descriptor *mask) {
144   return GetTotalReduction<TypeCategory::Integer, 4>(x, source, line, dim, mask,
145       IntegerOrAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IANY",
146       /*allowUnsignedForInteger=*/true);
147 }
148 CppTypeFor<TypeCategory::Integer, 8> RTDEF(IAny8)(const Descriptor &x,
149     const char *source, int line, int dim, const Descriptor *mask) {
150   return GetTotalReduction<TypeCategory::Integer, 8>(x, source, line, dim, mask,
151       IntegerOrAccumulator<CppTypeFor<TypeCategory::Integer, 8>>{x}, "IANY",
152       /*allowUnsignedForInteger=*/true);
153 }
154 #ifdef __SIZEOF_INT128__
155 CppTypeFor<TypeCategory::Integer, 16> RTDEF(IAny16)(const Descriptor &x,
156     const char *source, int line, int dim, const Descriptor *mask) {
157   return GetTotalReduction<TypeCategory::Integer, 16>(x, source, line, dim,
158       mask, IntegerOrAccumulator<CppTypeFor<TypeCategory::Integer, 16>>{x},
159       "IANY", /*allowUnsignedForInteger=*/true);
160 }
161 #endif
162 void RTDEF(IAnyDim)(Descriptor &result, const Descriptor &x, int dim,
163     const char *source, int line, const Descriptor *mask) {
164   Terminator terminator{source, line};
165   auto catKind{x.type().GetCategoryAndKind()};
166   RUNTIME_CHECK(terminator,
167       catKind.has_value() &&
168           (catKind->first == TypeCategory::Integer ||
169               catKind->first == TypeCategory::Unsigned));
170   PartialIntegerReduction<IntegerOrAccumulator>(
171       result, x, dim, catKind->second, mask, "IANY", terminator);
172 }
173 
174 CppTypeFor<TypeCategory::Integer, 1> RTDEF(IParity1)(const Descriptor &x,
175     const char *source, int line, int dim, const Descriptor *mask) {
176   return GetTotalReduction<TypeCategory::Integer, 1>(x, source, line, dim, mask,
177       IntegerXorAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IPARITY",
178       /*allowUnsignedForInteger=*/true);
179 }
180 CppTypeFor<TypeCategory::Integer, 2> RTDEF(IParity2)(const Descriptor &x,
181     const char *source, int line, int dim, const Descriptor *mask) {
182   return GetTotalReduction<TypeCategory::Integer, 2>(x, source, line, dim, mask,
183       IntegerXorAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IPARITY",
184       /*allowUnsignedForInteger=*/true);
185 }
186 CppTypeFor<TypeCategory::Integer, 4> RTDEF(IParity4)(const Descriptor &x,
187     const char *source, int line, int dim, const Descriptor *mask) {
188   return GetTotalReduction<TypeCategory::Integer, 4>(x, source, line, dim, mask,
189       IntegerXorAccumulator<CppTypeFor<TypeCategory::Integer, 4>>{x}, "IPARITY",
190       /*allowUnsignedForInteger=*/true);
191 }
192 CppTypeFor<TypeCategory::Integer, 8> RTDEF(IParity8)(const Descriptor &x,
193     const char *source, int line, int dim, const Descriptor *mask) {
194   return GetTotalReduction<TypeCategory::Integer, 8>(x, source, line, dim, mask,
195       IntegerXorAccumulator<CppTypeFor<TypeCategory::Integer, 8>>{x}, "IPARITY",
196       /*allowUnsignedForInteger=*/true);
197 }
198 #ifdef __SIZEOF_INT128__
199 CppTypeFor<TypeCategory::Integer, 16> RTDEF(IParity16)(const Descriptor &x,
200     const char *source, int line, int dim, const Descriptor *mask) {
201   return GetTotalReduction<TypeCategory::Integer, 16>(x, source, line, dim,
202       mask, IntegerXorAccumulator<CppTypeFor<TypeCategory::Integer, 16>>{x},
203       "IPARITY", /*allowUnsignedForInteger=*/true);
204 }
205 #endif
206 void RTDEF(IParityDim)(Descriptor &result, const Descriptor &x, int dim,
207     const char *source, int line, const Descriptor *mask) {
208   Terminator terminator{source, line};
209   auto catKind{x.type().GetCategoryAndKind()};
210   RUNTIME_CHECK(terminator,
211       catKind.has_value() &&
212           (catKind->first == TypeCategory::Integer ||
213               catKind->first == TypeCategory::Unsigned));
214   PartialIntegerReduction<IntegerXorAccumulator>(
215       result, x, dim, catKind->second, mask, "IPARITY", terminator);
216 }
217 }
218 
219 // ALL, ANY, COUNT, & PARITY
220 
221 enum class LogicalReduction { All, Any, Parity };
222 
223 template <LogicalReduction REDUCTION> class LogicalAccumulator {
224 public:
225   using Type = bool;
226   explicit LogicalAccumulator(const Descriptor &array) : array_{array} {}
227   void Reinitialize() { result_ = REDUCTION == LogicalReduction::All; }
228   bool Result() const { return result_; }
229   bool Accumulate(bool x) {
230     if constexpr (REDUCTION == LogicalReduction::Parity) {
231       result_ = result_ != x;
232     } else if (x != (REDUCTION == LogicalReduction::All)) {
233       result_ = x;
234       return false;
235     }
236     return true;
237   }
238   template <typename IGNORED = void>
239   bool AccumulateAt(const SubscriptValue at[]) {
240     return Accumulate(IsLogicalElementTrue(array_, at));
241   }
242 
243 private:
244   const Descriptor &array_;
245   bool result_{REDUCTION == LogicalReduction::All};
246 };
247 
248 template <typename ACCUMULATOR>
249 inline auto GetTotalLogicalReduction(const Descriptor &x, const char *source,
250     int line, int dim, ACCUMULATOR &&accumulator, const char *intrinsic) ->
251     typename ACCUMULATOR::Type {
252   Terminator terminator{source, line};
253   if (dim < 0 || dim > 1) {
254     terminator.Crash("%s: bad DIM=%d for ARRAY with rank=1", intrinsic, dim);
255   }
256   SubscriptValue xAt[maxRank];
257   x.GetLowerBounds(xAt);
258   for (auto elements{x.Elements()}; elements--; x.IncrementSubscripts(xAt)) {
259     if (!accumulator.AccumulateAt(xAt)) {
260       break; // cut short, result is known
261     }
262   }
263   return accumulator.Result();
264 }
265 
266 template <typename ACCUMULATOR>
267 inline auto ReduceLogicalDimToScalar(const Descriptor &x, int zeroBasedDim,
268     SubscriptValue subscripts[]) -> typename ACCUMULATOR::Type {
269   ACCUMULATOR accumulator{x};
270   SubscriptValue xAt[maxRank];
271   GetExpandedSubscripts(xAt, x, zeroBasedDim, subscripts);
272   const auto &dim{x.GetDimension(zeroBasedDim)};
273   SubscriptValue at{dim.LowerBound()};
274   for (auto n{dim.Extent()}; n-- > 0; ++at) {
275     xAt[zeroBasedDim] = at;
276     if (!accumulator.AccumulateAt(xAt)) {
277       break;
278     }
279   }
280   return accumulator.Result();
281 }
282 
283 template <LogicalReduction REDUCTION> struct LogicalReduceHelper {
284   template <int KIND> struct Functor {
285     void operator()(Descriptor &result, const Descriptor &x, int dim,
286         Terminator &terminator, const char *intrinsic) const {
287       // Standard requires result to have same LOGICAL kind as argument.
288       CreatePartialReductionResult(
289           result, x, x.ElementBytes(), dim, terminator, intrinsic, x.type());
290       SubscriptValue at[maxRank];
291       result.GetLowerBounds(at);
292       INTERNAL_CHECK(result.rank() == 0 || at[0] == 1);
293       using CppType = CppTypeFor<TypeCategory::Logical, KIND>;
294       for (auto n{result.Elements()}; n-- > 0; result.IncrementSubscripts(at)) {
295         *result.Element<CppType>(at) =
296             ReduceLogicalDimToScalar<LogicalAccumulator<REDUCTION>>(
297                 x, dim - 1, at);
298       }
299     }
300   };
301 };
302 
303 template <LogicalReduction REDUCTION>
304 inline void DoReduceLogicalDimension(Descriptor &result, const Descriptor &x,
305     int dim, Terminator &terminator, const char *intrinsic) {
306   auto catKind{x.type().GetCategoryAndKind()};
307   RUNTIME_CHECK(terminator, catKind && catKind->first == TypeCategory::Logical);
308   ApplyLogicalKind<LogicalReduceHelper<REDUCTION>::template Functor, void>(
309       catKind->second, terminator, result, x, dim, terminator, intrinsic);
310 }
311 
312 // COUNT
313 
314 class CountAccumulator {
315 public:
316   using Type = std::int64_t;
317   explicit CountAccumulator(const Descriptor &array) : array_{array} {}
318   void Reinitialize() { result_ = 0; }
319   Type Result() const { return result_; }
320   template <typename IGNORED = void>
321   bool AccumulateAt(const SubscriptValue at[]) {
322     if (IsLogicalElementTrue(array_, at)) {
323       ++result_;
324     }
325     return true;
326   }
327 
328 private:
329   const Descriptor &array_;
330   Type result_{0};
331 };
332 
333 template <int KIND> struct CountDimension {
334   void operator()(Descriptor &result, const Descriptor &x, int dim,
335       Terminator &terminator) const {
336     // Element size of the descriptor descriptor is the size
337     // of {TypeCategory::Integer, KIND}.
338     CreatePartialReductionResult(result, x,
339         Descriptor::BytesFor(TypeCategory::Integer, KIND), dim, terminator,
340         "COUNT", TypeCode{TypeCategory::Integer, KIND});
341     SubscriptValue at[maxRank];
342     result.GetLowerBounds(at);
343     INTERNAL_CHECK(result.rank() == 0 || at[0] == 1);
344     using CppType = CppTypeFor<TypeCategory::Integer, KIND>;
345     for (auto n{result.Elements()}; n-- > 0; result.IncrementSubscripts(at)) {
346       *result.Element<CppType>(at) =
347           ReduceLogicalDimToScalar<CountAccumulator>(x, dim - 1, at);
348     }
349   }
350 };
351 
352 extern "C" {
353 RT_EXT_API_GROUP_BEGIN
354 
355 bool RTDEF(All)(const Descriptor &x, const char *source, int line, int dim) {
356   return GetTotalLogicalReduction(x, source, line, dim,
357       LogicalAccumulator<LogicalReduction::All>{x}, "ALL");
358 }
359 void RTDEF(AllDim)(Descriptor &result, const Descriptor &x, int dim,
360     const char *source, int line) {
361   Terminator terminator{source, line};
362   DoReduceLogicalDimension<LogicalReduction::All>(
363       result, x, dim, terminator, "ALL");
364 }
365 
366 bool RTDEF(Any)(const Descriptor &x, const char *source, int line, int dim) {
367   return GetTotalLogicalReduction(x, source, line, dim,
368       LogicalAccumulator<LogicalReduction::Any>{x}, "ANY");
369 }
370 void RTDEF(AnyDim)(Descriptor &result, const Descriptor &x, int dim,
371     const char *source, int line) {
372   Terminator terminator{source, line};
373   DoReduceLogicalDimension<LogicalReduction::Any>(
374       result, x, dim, terminator, "ANY");
375 }
376 
377 std::int64_t RTDEF(Count)(
378     const Descriptor &x, const char *source, int line, int dim) {
379   return GetTotalLogicalReduction(
380       x, source, line, dim, CountAccumulator{x}, "COUNT");
381 }
382 
383 void RTDEF(CountDim)(Descriptor &result, const Descriptor &x, int dim, int kind,
384     const char *source, int line) {
385   Terminator terminator{source, line};
386   ApplyIntegerKind<CountDimension, void>(
387       kind, terminator, result, x, dim, terminator);
388 }
389 
390 bool RTDEF(Parity)(const Descriptor &x, const char *source, int line, int dim) {
391   return GetTotalLogicalReduction(x, source, line, dim,
392       LogicalAccumulator<LogicalReduction::Parity>{x}, "PARITY");
393 }
394 void RTDEF(ParityDim)(Descriptor &result, const Descriptor &x, int dim,
395     const char *source, int line) {
396   Terminator terminator{source, line};
397   DoReduceLogicalDimension<LogicalReduction::Parity>(
398       result, x, dim, terminator, "PARITY");
399 }
400 
401 RT_EXT_API_GROUP_END
402 } // extern "C"
403 } // namespace Fortran::runtime
404