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