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/tools.h"
20 #include "flang/Evaluate/type.h"
21 #include <optional>
22 #include <variant>
23
24 namespace Fortran::parser {
25 class ContextualMessages;
26 }
27
28 namespace Fortran::evaluate {
29
30 class FoldingContext;
31
32 using ExtentType = SubscriptInteger;
33 using ExtentExpr = Expr<ExtentType>;
34 using MaybeExtentExpr = std::optional<ExtentExpr>;
35 using Shape = std::vector<MaybeExtentExpr>;
36
37 bool IsImpliedShape(const Symbol &);
38 bool IsExplicitShape(const Symbol &);
39
40 // Conversions between various representations of shapes.
41 Shape AsShape(const Constant<ExtentType> &);
42 std::optional<Shape> AsShape(FoldingContext &, ExtentExpr &&);
43
44 std::optional<ExtentExpr> AsExtentArrayExpr(const Shape &);
45
46 std::optional<Constant<ExtentType>> AsConstantShape(
47 FoldingContext &, const Shape &);
48 Constant<ExtentType> AsConstantShape(const ConstantSubscripts &);
49
50 ConstantSubscripts AsConstantExtents(const Constant<ExtentType> &);
51 std::optional<ConstantSubscripts> AsConstantExtents(
52 FoldingContext &, const Shape &);
53
GetRank(const Shape & s)54 inline int GetRank(const Shape &s) { return static_cast<int>(s.size()); }
55
56 template <typename A>
57 std::optional<Shape> GetShape(FoldingContext &, const A &);
58
59 // The dimension argument to these inquiries is zero-based,
60 // unlike the DIM= arguments to many intrinsics.
61 ExtentExpr GetLowerBound(FoldingContext &, const NamedEntity &, int dimension);
62 MaybeExtentExpr GetUpperBound(
63 FoldingContext &, const NamedEntity &, int dimension);
64 MaybeExtentExpr ComputeUpperBound(
65 FoldingContext &, ExtentExpr &&lower, MaybeExtentExpr &&extent);
66 Shape GetLowerBounds(FoldingContext &, const NamedEntity &);
67 Shape GetUpperBounds(FoldingContext &, const NamedEntity &);
68 MaybeExtentExpr GetExtent(FoldingContext &, const NamedEntity &, int dimension);
69 MaybeExtentExpr GetExtent(
70 FoldingContext &, const Subscript &, const NamedEntity &, int dimension);
71
72 // Compute an element count for a triplet or trip count for a DO.
73 ExtentExpr CountTrips(FoldingContext &, ExtentExpr &&lower, ExtentExpr &&upper,
74 ExtentExpr &&stride);
75 ExtentExpr CountTrips(FoldingContext &, const ExtentExpr &lower,
76 const ExtentExpr &upper, const ExtentExpr &stride);
77 MaybeExtentExpr CountTrips(FoldingContext &, MaybeExtentExpr &&lower,
78 MaybeExtentExpr &&upper, MaybeExtentExpr &&stride);
79
80 // Computes SIZE() == PRODUCT(shape)
81 MaybeExtentExpr GetSize(Shape &&);
82
83 // Utility predicate: does an expression reference any implied DO index?
84 bool ContainsAnyImpliedDoIndex(const ExtentExpr &);
85
86 class GetShapeHelper
87 : public AnyTraverse<GetShapeHelper, std::optional<Shape>> {
88 public:
89 using Result = std::optional<Shape>;
90 using Base = AnyTraverse<GetShapeHelper, Result>;
91 using Base::operator();
GetShapeHelper(FoldingContext & c)92 explicit GetShapeHelper(FoldingContext &c) : Base{*this}, context_{c} {}
93
operator()94 Result operator()(const ImpliedDoIndex &) const { return Scalar(); }
operator()95 Result operator()(const DescriptorInquiry &) const { return Scalar(); }
operator()96 Result operator()(const TypeParamInquiry &) const { return Scalar(); }
operator()97 Result operator()(const BOZLiteralConstant &) const { return Scalar(); }
operator()98 Result operator()(const StaticDataObject::Pointer &) const {
99 return Scalar();
100 }
operator()101 Result operator()(const StructureConstructor &) const { return Scalar(); }
102
operator()103 template <typename T> Result operator()(const Constant<T> &c) const {
104 return AsShape(c.SHAPE());
105 }
106
107 Result operator()(const Symbol &) const;
108 Result operator()(const Component &) const;
109 Result operator()(const ArrayRef &) const;
110 Result operator()(const CoarrayRef &) const;
111 Result operator()(const Substring &) const;
112 Result operator()(const ProcedureRef &) const;
113
114 template <typename T>
operator()115 Result operator()(const ArrayConstructor<T> &aconst) const {
116 return Shape{GetArrayConstructorExtent(aconst)};
117 }
118 template <typename D, typename R, typename LO, typename RO>
operator()119 Result operator()(const Operation<D, R, LO, RO> &operation) const {
120 if (operation.right().Rank() > 0) {
121 return (*this)(operation.right());
122 } else {
123 return (*this)(operation.left());
124 }
125 }
126
127 private:
Scalar()128 static Result Scalar() { return Shape{}; }
CreateShape(int rank,NamedEntity & base)129 Shape CreateShape(int rank, NamedEntity &base) const {
130 Shape shape;
131 for (int dimension{0}; dimension < rank; ++dimension) {
132 shape.emplace_back(GetExtent(context_, base, dimension));
133 }
134 return shape;
135 }
136 template <typename T>
GetArrayConstructorValueExtent(const ArrayConstructorValue<T> & value)137 MaybeExtentExpr GetArrayConstructorValueExtent(
138 const ArrayConstructorValue<T> &value) const {
139 return std::visit(
140 common::visitors{
141 [&](const Expr<T> &x) -> MaybeExtentExpr {
142 if (std::optional<Shape> xShape{GetShape(context_, x)}) {
143 // Array values in array constructors get linearized.
144 return GetSize(std::move(*xShape));
145 } else {
146 return std::nullopt;
147 }
148 },
149 [&](const ImpliedDo<T> &ido) -> MaybeExtentExpr {
150 // Don't be heroic and try to figure out triangular implied DO
151 // nests.
152 if (!ContainsAnyImpliedDoIndex(ido.lower()) &&
153 !ContainsAnyImpliedDoIndex(ido.upper()) &&
154 !ContainsAnyImpliedDoIndex(ido.stride())) {
155 if (auto nValues{GetArrayConstructorExtent(ido.values())}) {
156 return std::move(*nValues) *
157 CountTrips(
158 context_, ido.lower(), ido.upper(), ido.stride());
159 }
160 }
161 return std::nullopt;
162 },
163 },
164 value.u);
165 }
166
167 template <typename T>
GetArrayConstructorExtent(const ArrayConstructorValues<T> & values)168 MaybeExtentExpr GetArrayConstructorExtent(
169 const ArrayConstructorValues<T> &values) const {
170 ExtentExpr result{0};
171 for (const auto &value : values) {
172 if (MaybeExtentExpr n{GetArrayConstructorValueExtent(value)}) {
173 result = std::move(result) + std::move(*n);
174 } else {
175 return std::nullopt;
176 }
177 }
178 return result;
179 }
180
181 FoldingContext &context_;
182 };
183
184 template <typename A>
GetShape(FoldingContext & context,const A & x)185 std::optional<Shape> GetShape(FoldingContext &context, const A &x) {
186 return GetShapeHelper{context}(x);
187 }
188
189 template <typename A>
GetConstantShape(FoldingContext & context,const A & x)190 std::optional<Constant<ExtentType>> GetConstantShape(
191 FoldingContext &context, const A &x) {
192 if (auto shape{GetShape(context, x)}) {
193 return AsConstantShape(context, *shape);
194 } else {
195 return std::nullopt;
196 }
197 }
198
199 template <typename A>
GetConstantExtents(FoldingContext & context,const A & x)200 std::optional<ConstantSubscripts> GetConstantExtents(
201 FoldingContext &context, const A &x) {
202 if (auto shape{GetShape(context, x)}) {
203 return AsConstantExtents(context, *shape);
204 } else {
205 return std::nullopt;
206 }
207 }
208
209 // Compilation-time shape conformance checking, when corresponding extents
210 // are known.
211 bool CheckConformance(parser::ContextualMessages &, const Shape &left,
212 const Shape &right, const char *leftIs = "left operand",
213 const char *rightIs = "right operand", bool leftScalarExpandable = true,
214 bool rightScalarExpandable = true);
215
216 // Increments one-based subscripts in element order (first varies fastest)
217 // and returns true when they remain in range; resets them all to one and
218 // return false otherwise (including the case where one or more of the
219 // extents are zero).
220 bool IncrementSubscripts(
221 ConstantSubscripts &, const ConstantSubscripts &extents);
222
223 } // namespace Fortran::evaluate
224 #endif // FORTRAN_EVALUATE_SHAPE_H_
225