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