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 23 namespace Fortran::parser { 24 class ContextualMessages; 25 } 26 27 namespace Fortran::evaluate { 28 29 class FoldingContext; 30 31 using ExtentType = SubscriptInteger; 32 using ExtentExpr = Expr<ExtentType>; 33 using MaybeExtentExpr = std::optional<ExtentExpr>; 34 using Shape = std::vector<MaybeExtentExpr>; 35 36 bool IsImpliedShape(const Symbol &); 37 bool IsExplicitShape(const Symbol &); 38 39 // Conversions between various representations of shapes. 40 std::optional<ExtentExpr> AsExtentArrayExpr(const Shape &); 41 42 std::optional<Constant<ExtentType>> AsConstantShape( 43 FoldingContext &, const Shape &); 44 Constant<ExtentType> AsConstantShape(const ConstantSubscripts &); 45 46 // AsConstantExtents returns a constant shape. It may contain 47 // invalid negative extents; use HasNegativeExtent() to check. 48 ConstantSubscripts AsConstantExtents(const Constant<ExtentType> &); 49 std::optional<ConstantSubscripts> AsConstantExtents( 50 FoldingContext &, const Shape &); 51 inline 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 59 Shape AsShape(const ConstantSubscripts &); 60 std::optional<Shape> AsShape(const std::optional<ConstantSubscripts> &); 61 62 inline int GetRank(const Shape &s) { return static_cast<int>(s.size()); } 63 64 Shape Fold(FoldingContext &, Shape &&); 65 std::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. 70 template <typename A> 71 std::optional<Shape> GetShape( 72 FoldingContext &, const A &, bool invariantOnly = true); 73 template <typename A> 74 std::optional<Shape> GetShape( 75 FoldingContext *, const A &, bool invariantOnly = true); 76 template <typename A> 77 std::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. 89 ExtentExpr GetRawLowerBound( 90 const NamedEntity &, int dimension, bool invariantOnly = true); 91 ExtentExpr GetRawLowerBound(FoldingContext &, const NamedEntity &, 92 int dimension, bool invariantOnly = true); 93 MaybeExtentExpr GetLBOUND( 94 const NamedEntity &, int dimension, bool invariantOnly = true); 95 MaybeExtentExpr GetLBOUND(FoldingContext &, const NamedEntity &, int dimension, 96 bool invariantOnly = true); 97 MaybeExtentExpr GetRawUpperBound( 98 const NamedEntity &, int dimension, bool invariantOnly = true); 99 MaybeExtentExpr GetRawUpperBound(FoldingContext &, const NamedEntity &, 100 int dimension, bool invariantOnly = true); 101 MaybeExtentExpr GetUBOUND( 102 const NamedEntity &, int dimension, bool invariantOnly = true); 103 MaybeExtentExpr GetUBOUND(FoldingContext &, const NamedEntity &, int dimension, 104 bool invariantOnly = true); 105 MaybeExtentExpr ComputeUpperBound(ExtentExpr &&lower, MaybeExtentExpr &&extent); 106 MaybeExtentExpr ComputeUpperBound( 107 FoldingContext &, ExtentExpr &&lower, MaybeExtentExpr &&extent); 108 Shape GetRawLowerBounds(const NamedEntity &, bool invariantOnly = true); 109 Shape GetRawLowerBounds( 110 FoldingContext &, const NamedEntity &, bool invariantOnly = true); 111 Shape GetLBOUNDs(const NamedEntity &, bool invariantOnly = true); 112 Shape GetLBOUNDs( 113 FoldingContext &, const NamedEntity &, bool invariantOnly = true); 114 Shape GetUBOUNDs(const NamedEntity &, bool invariantOnly = true); 115 Shape GetUBOUNDs( 116 FoldingContext &, const NamedEntity &, bool invariantOnly = true); 117 MaybeExtentExpr GetExtent( 118 const NamedEntity &, int dimension, bool invariantOnly = true); 119 MaybeExtentExpr GetExtent(FoldingContext &, const NamedEntity &, int dimension, 120 bool invariantOnly = true); 121 MaybeExtentExpr GetExtent(const Subscript &, const NamedEntity &, int dimension, 122 bool invariantOnly = true); 123 MaybeExtentExpr GetExtent(FoldingContext &, const Subscript &, 124 const NamedEntity &, int dimension, bool invariantOnly = true); 125 126 // Similar analyses for coarrays 127 MaybeExtentExpr GetLCOBOUND( 128 const Symbol &, int dimension, bool invariantOnly = true); 129 MaybeExtentExpr GetUCOBOUND( 130 const Symbol &, int dimension, bool invariantOnly = true); 131 Shape GetLCOBOUNDs(const Symbol &, bool invariantOnly = true); 132 Shape GetUCOBOUNDs(const Symbol &, bool invariantOnly = true); 133 134 // Compute an element count for a triplet or trip count for a DO. 135 ExtentExpr CountTrips( 136 ExtentExpr &&lower, ExtentExpr &&upper, ExtentExpr &&stride); 137 ExtentExpr CountTrips( 138 const ExtentExpr &lower, const ExtentExpr &upper, const ExtentExpr &stride); 139 MaybeExtentExpr CountTrips( 140 MaybeExtentExpr &&lower, MaybeExtentExpr &&upper, MaybeExtentExpr &&stride); 141 142 // Computes SIZE() == PRODUCT(shape) 143 MaybeExtentExpr GetSize(Shape &&); 144 ConstantSubscript GetSize(const ConstantSubscripts &); 145 inline 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? 153 bool ContainsAnyImpliedDoIndex(const ExtentExpr &); 154 155 // GetShape() 156 157 class GetShapeHelper 158 : public AnyTraverse<GetShapeHelper, std::optional<Shape>> { 159 public: 160 using Result = std::optional<Shape>; 161 using Base = AnyTraverse<GetShapeHelper, Result>; 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 205 private: 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( 215 common::visitors{ 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 267 template <typename A> 268 std::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 281 template <typename A> 282 std::optional<Shape> GetShape( 283 FoldingContext &context, const A &x, bool invariantOnly) { 284 return GetShape(&context, x, invariantOnly); 285 } 286 287 template <typename A> 288 std::optional<Shape> GetShape(const A &x, bool invariantOnly) { 289 return GetShape(/*context=*/nullptr, x, invariantOnly); 290 } 291 292 template <typename A> 293 std::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. 303 template <typename A> 304 std::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). 320 template <typename A> 321 std::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. 334 struct CheckConformanceFlags { 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 }; 346 std::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). 355 bool IncrementSubscripts( 356 ConstantSubscripts &, const ConstantSubscripts &extents); 357 358 } // namespace Fortran::evaluate 359 #endif // FORTRAN_EVALUATE_SHAPE_H_ 360