Warning: This file is not a C or C++ file. It does not have highlighting.

1//===-- include/flang/Evaluate/shape.h --------------------------*- C++ -*-===//
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// GetShape() analyzes an expression and determines its shape, if possible,
10// representing the result as a vector of scalar integer expressions.
11
12#ifndef FORTRAN_EVALUATE_SHAPE_H_
13#define FORTRAN_EVALUATE_SHAPE_H_
14
15#include "expression.h"
16#include "traverse.h"
17#include "variable.h"
18#include "flang/Common/indirection.h"
19#include "flang/Evaluate/type.h"
20#include <optional>
21#include <variant>
22
23namespace Fortran::parser {
24class ContextualMessages;
25}
26
27namespace Fortran::evaluate {
28
29class FoldingContext;
30
31using ExtentType = SubscriptInteger;
32using ExtentExpr = Expr<ExtentType>;
33using MaybeExtentExpr = std::optional<ExtentExpr>;
34using Shape = std::vector<MaybeExtentExpr>;
35
36bool IsImpliedShape(const Symbol &);
37bool IsExplicitShape(const Symbol &);
38
39// Conversions between various representations of shapes.
40std::optional<ExtentExpr> AsExtentArrayExpr(const Shape &);
41
42std::optional<Constant<ExtentType>> AsConstantShape(
43 FoldingContext &, const Shape &);
44Constant<ExtentType> AsConstantShape(const ConstantSubscripts &);
45
46ConstantSubscripts AsConstantExtents(const Constant<ExtentType> &);
47std::optional<ConstantSubscripts> AsConstantExtents(
48 FoldingContext &, const Shape &);
49Shape AsShape(const ConstantSubscripts &);
50std::optional<Shape> AsShape(const std::optional<ConstantSubscripts> &);
51
52inline int GetRank(const Shape &s) { return static_cast<int>(s.size()); }
53
54Shape Fold(FoldingContext &, Shape &&);
55std::optional<Shape> Fold(FoldingContext &, std::optional<Shape> &&);
56
57// Computes shapes in terms of expressions that are scope-invariant, by
58// default, which is nearly always what one wants outside of procedure
59// characterization.
60template <typename A>
61std::optional<Shape> GetShape(
62 FoldingContext &, const A &, bool invariantOnly = true);
63template <typename A>
64std::optional<Shape> GetShape(const A &, bool invariantOnly = true);
65
66// The dimension argument to these inquiries is zero-based,
67// unlike the DIM= arguments to many intrinsics.
68//
69// GetRawLowerBound() returns a lower bound expression, which may
70// not be suitable for all purposes; specifically, it might not be invariant
71// in its scope, and it will not have been forced to 1 on an empty dimension.
72// GetLBOUND()'s result is safer, but it is optional because it does fail
73// in those circumstances.
74// Similarly, GetUBOUND result will be forced to 0 on an empty dimension,
75// but will fail if the extent is not a compile time constant.
76ExtentExpr GetRawLowerBound(
77 const NamedEntity &, int dimension, bool invariantOnly = true);
78ExtentExpr GetRawLowerBound(FoldingContext &, const NamedEntity &,
79 int dimension, bool invariantOnly = true);
80MaybeExtentExpr GetLBOUND(
81 const NamedEntity &, int dimension, bool invariantOnly = true);
82MaybeExtentExpr GetLBOUND(FoldingContext &, const NamedEntity &, int dimension,
83 bool invariantOnly = true);
84MaybeExtentExpr GetRawUpperBound(
85 const NamedEntity &, int dimension, bool invariantOnly = true);
86MaybeExtentExpr GetRawUpperBound(FoldingContext &, const NamedEntity &,
87 int dimension, bool invariantOnly = true);
88MaybeExtentExpr GetUBOUND(
89 const NamedEntity &, int dimension, bool invariantOnly = true);
90MaybeExtentExpr GetUBOUND(FoldingContext &, const NamedEntity &, int dimension,
91 bool invariantOnly = true);
92MaybeExtentExpr ComputeUpperBound(ExtentExpr &&lower, MaybeExtentExpr &&extent);
93MaybeExtentExpr ComputeUpperBound(
94 FoldingContext &, ExtentExpr &&lower, MaybeExtentExpr &&extent);
95Shape GetRawLowerBounds(const NamedEntity &, bool invariantOnly = true);
96Shape GetRawLowerBounds(
97 FoldingContext &, const NamedEntity &, bool invariantOnly = true);
98Shape GetLBOUNDs(const NamedEntity &, bool invariantOnly = true);
99Shape GetLBOUNDs(
100 FoldingContext &, const NamedEntity &, bool invariantOnly = true);
101Shape GetUBOUNDs(const NamedEntity &, bool invariantOnly = true);
102Shape GetUBOUNDs(
103 FoldingContext &, const NamedEntity &, bool invariantOnly = true);
104MaybeExtentExpr GetExtent(
105 const NamedEntity &, int dimension, bool invariantOnly = true);
106MaybeExtentExpr GetExtent(FoldingContext &, const NamedEntity &, int dimension,
107 bool invariantOnly = true);
108MaybeExtentExpr GetExtent(const Subscript &, const NamedEntity &, int dimension,
109 bool invariantOnly = true);
110MaybeExtentExpr GetExtent(FoldingContext &, const Subscript &,
111 const NamedEntity &, int dimension, bool invariantOnly = true);
112
113// Compute an element count for a triplet or trip count for a DO.
114ExtentExpr CountTrips(
115 ExtentExpr &&lower, ExtentExpr &&upper, ExtentExpr &&stride);
116ExtentExpr CountTrips(
117 const ExtentExpr &lower, const ExtentExpr &upper, const ExtentExpr &stride);
118MaybeExtentExpr CountTrips(
119 MaybeExtentExpr &&lower, MaybeExtentExpr &&upper, MaybeExtentExpr &&stride);
120
121// Computes SIZE() == PRODUCT(shape)
122MaybeExtentExpr GetSize(Shape &&);
123ConstantSubscript GetSize(const ConstantSubscripts &);
124
125// Utility predicate: does an expression reference any implied DO index?
126bool ContainsAnyImpliedDoIndex(const ExtentExpr &);
127
128class GetShapeHelper
129 : public AnyTraverse<GetShapeHelper, std::optional<Shape>> {
130public:
131 using Result = std::optional<Shape>;
132 using Base = AnyTraverse<GetShapeHelper, Result>;
133 using Base::operator();
134 GetShapeHelper(FoldingContext *context, bool invariantOnly)
135 : Base{*this}, context_{context}, invariantOnly_{invariantOnly} {}
136
137 Result operator()(const ImpliedDoIndex &) const { return ScalarShape(); }
138 Result operator()(const DescriptorInquiry &) const { return ScalarShape(); }
139 Result operator()(const TypeParamInquiry &) const { return ScalarShape(); }
140 Result operator()(const BOZLiteralConstant &) const { return ScalarShape(); }
141 Result operator()(const StaticDataObject::Pointer &) const {
142 return ScalarShape();
143 }
144 Result operator()(const StructureConstructor &) const {
145 return ScalarShape();
146 }
147
148 template <typename T> Result operator()(const Constant<T> &c) const {
149 return ConstantShape(c.SHAPE());
150 }
151
152 Result operator()(const Symbol &) const;
153 Result operator()(const Component &) const;
154 Result operator()(const ArrayRef &) const;
155 Result operator()(const CoarrayRef &) const;
156 Result operator()(const Substring &) const;
157 Result operator()(const ProcedureRef &) const;
158
159 template <typename T>
160 Result operator()(const ArrayConstructor<T> &aconst) const {
161 return Shape{GetArrayConstructorExtent(aconst)};
162 }
163 template <typename D, typename R, typename LO, typename RO>
164 Result operator()(const Operation<D, R, LO, RO> &operation) const {
165 if (operation.right().Rank() > 0) {
166 return (*this)(operation.right());
167 } else {
168 return (*this)(operation.left());
169 }
170 }
171
172private:
173 static Result ScalarShape() { return Shape{}; }
174 static Shape ConstantShape(const Constant<ExtentType> &);
175 Result AsShapeResult(ExtentExpr &&) const;
176 Shape CreateShape(int rank, NamedEntity &) const;
177
178 template <typename T>
179 MaybeExtentExpr GetArrayConstructorValueExtent(
180 const ArrayConstructorValue<T> &value) const {
181 return common::visit(
182 common::visitors{
183 [&](const Expr<T> &x) -> MaybeExtentExpr {
184 if (auto xShape{(*this)(x)}) {
185 // Array values in array constructors get linearized.
186 return GetSize(std::move(*xShape));
187 } else {
188 return std::nullopt;
189 }
190 },
191 [&](const ImpliedDo<T> &ido) -> MaybeExtentExpr {
192 // Don't be heroic and try to figure out triangular implied DO
193 // nests.
194 if (!ContainsAnyImpliedDoIndex(ido.lower()) &&
195 !ContainsAnyImpliedDoIndex(ido.upper()) &&
196 !ContainsAnyImpliedDoIndex(ido.stride())) {
197 if (auto nValues{GetArrayConstructorExtent(ido.values())}) {
198 if (!ContainsAnyImpliedDoIndex(*nValues)) {
199 return std::move(*nValues) *
200 CountTrips(ido.lower(), ido.upper(), ido.stride());
201 }
202 }
203 }
204 return std::nullopt;
205 },
206 },
207 value.u);
208 }
209
210 template <typename T>
211 MaybeExtentExpr GetArrayConstructorExtent(
212 const ArrayConstructorValues<T> &values) const {
213 ExtentExpr result{0};
214 for (const auto &value : values) {
215 if (MaybeExtentExpr n{GetArrayConstructorValueExtent(value)}) {
216 AccumulateExtent(result, std::move(*n));
217 } else {
218 return std::nullopt;
219 }
220 }
221 return result;
222 }
223
224 // Add an extent to another, with folding
225 void AccumulateExtent(ExtentExpr &, ExtentExpr &&) const;
226
227 FoldingContext *context_{nullptr};
228 mutable bool useResultSymbolShape_{true};
229 // When invariantOnly=false, the returned shape need not be invariant
230 // in its scope; in particular, it may contain references to dummy arguments.
231 bool invariantOnly_{true};
232};
233
234template <typename A>
235std::optional<Shape> GetShape(
236 FoldingContext &context, const A &x, bool invariantOnly) {
237 if (auto shape{GetShapeHelper{&context, invariantOnly}(x)}) {
238 return Fold(context, std::move(shape));
239 } else {
240 return std::nullopt;
241 }
242}
243
244template <typename A>
245std::optional<Shape> GetShape(const A &x, bool invariantOnly) {
246 return GetShapeHelper{/*context=*/nullptr, invariantOnly}(x);
247}
248
249template <typename A>
250std::optional<Shape> GetShape(
251 FoldingContext *context, const A &x, bool invariantOnly = true) {
252 return GetShapeHelper{context, invariantOnly}(x);
253}
254
255template <typename A>
256std::optional<Constant<ExtentType>> GetConstantShape(
257 FoldingContext &context, const A &x) {
258 if (auto shape{GetShape(context, x, /*invariantonly=*/true)}) {
259 return AsConstantShape(context, *shape);
260 } else {
261 return std::nullopt;
262 }
263}
264
265template <typename A>
266std::optional<ConstantSubscripts> GetConstantExtents(
267 FoldingContext &context, const A &x) {
268 if (auto shape{GetShape(context, x, /*invariantOnly=*/true)}) {
269 return AsConstantExtents(context, *shape);
270 } else {
271 return std::nullopt;
272 }
273}
274
275// Get shape that does not depends on callee scope symbols if the expression
276// contains calls. Return std::nullopt if it is not possible to build such shape
277// (e.g. for calls to array-valued functions whose result shape depends on the
278// arguments).
279template <typename A>
280std::optional<Shape> GetContextFreeShape(FoldingContext &context, const A &x) {
281 return GetShapeHelper{&context, /*invariantOnly=*/true}(x);
282}
283
284// Compilation-time shape conformance checking, when corresponding extents
285// are or should be known. The result is an optional Boolean:
286// - nullopt: no error found or reported, but conformance cannot
287// be guaranteed during compilation; this result is possible only
288// when one or both arrays are allowed to have deferred shape
289// - true: no error found or reported, arrays conform
290// - false: errors found and reported
291// Use "CheckConformance(...).value_or()" to specify a default result
292// when you don't care whether messages have been emitted.
293struct CheckConformanceFlags {
294 enum Flags {
295 None = 0,
296 LeftScalarExpandable = 1,
297 RightScalarExpandable = 2,
298 LeftIsDeferredShape = 4,
299 RightIsDeferredShape = 8,
300 EitherScalarExpandable = LeftScalarExpandable | RightScalarExpandable,
301 BothDeferredShape = LeftIsDeferredShape | RightIsDeferredShape,
302 RightIsExpandableDeferred = RightScalarExpandable | RightIsDeferredShape,
303 };
304};
305std::optional<bool> CheckConformance(parser::ContextualMessages &,
306 const Shape &left, const Shape &right,
307 CheckConformanceFlags::Flags flags = CheckConformanceFlags::None,
308 const char *leftIs = "left operand", const char *rightIs = "right operand");
309
310// Increments one-based subscripts in element order (first varies fastest)
311// and returns true when they remain in range; resets them all to one and
312// return false otherwise (including the case where one or more of the
313// extents are zero).
314bool IncrementSubscripts(
315 ConstantSubscripts &, const ConstantSubscripts &extents);
316
317} // namespace Fortran::evaluate
318#endif // FORTRAN_EVALUATE_SHAPE_H_
319

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of flang/include/flang/Evaluate/shape.h