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

1//===-- BoxAnalyzer.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// Coding style: https://mlir.llvm.org/getting_started/DeveloperGuide/
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef FORTRAN_LOWER_BOXANALYZER_H
14#define FORTRAN_LOWER_BOXANALYZER_H
15
16#include "flang/Evaluate/fold.h"
17#include "flang/Lower/Support/Utils.h"
18#include "flang/Optimizer/Dialect/FIRType.h"
19#include "flang/Optimizer/Support/Matcher.h"
20#include <optional>
21
22namespace Fortran::lower {
23
24//===----------------------------------------------------------------------===//
25// Classifications of a symbol.
26//
27// Each classification is a distinct class and can be used in pattern matching.
28//===----------------------------------------------------------------------===//
29
30namespace details {
31
32using FromBox = std::monostate;
33
34/// Base class for all box analysis results.
35struct ScalarSym {
36 ScalarSym(const Fortran::semantics::Symbol &sym) : sym{&sym} {}
37 ScalarSym &operator=(const ScalarSym &) = default;
38
39 const Fortran::semantics::Symbol &symbol() const { return *sym; }
40
41 static constexpr bool staticSize() { return true; }
42 static constexpr bool isChar() { return false; }
43 static constexpr bool isArray() { return false; }
44
45private:
46 const Fortran::semantics::Symbol *sym;
47};
48
49/// Scalar of dependent type CHARACTER, constant LEN.
50struct ScalarStaticChar : ScalarSym {
51 ScalarStaticChar(const Fortran::semantics::Symbol &sym, int64_t len)
52 : ScalarSym{sym}, len{len} {}
53
54 int64_t charLen() const { return len; }
55
56 static constexpr bool isChar() { return true; }
57
58private:
59 int64_t len;
60};
61
62/// Scalar of dependent type Derived, constant LEN(s).
63struct ScalarStaticDerived : ScalarSym {
64 ScalarStaticDerived(const Fortran::semantics::Symbol &sym,
65 llvm::SmallVectorImpl<int64_t> &&lens)
66 : ScalarSym{sym}, lens{std::move(lens)} {}
67
68private:
69 llvm::SmallVector<int64_t> lens;
70};
71
72/// Scalar of dependent type CHARACTER, dynamic LEN.
73struct ScalarDynamicChar : ScalarSym {
74 ScalarDynamicChar(const Fortran::semantics::Symbol &sym,
75 const Fortran::lower::SomeExpr &len)
76 : ScalarSym{sym}, len{len} {}
77 ScalarDynamicChar(const Fortran::semantics::Symbol &sym)
78 : ScalarSym{sym}, len{FromBox{}} {}
79
80 std::optional<Fortran::lower::SomeExpr> charLen() const {
81 if (auto *l = std::get_if<Fortran::lower::SomeExpr>(&len))
82 return {*l};
83 return std::nullopt;
84 }
85
86 static constexpr bool staticSize() { return false; }
87 static constexpr bool isChar() { return true; }
88
89private:
90 std::variant<FromBox, Fortran::lower::SomeExpr> len;
91};
92
93/// Scalar of dependent type Derived, dynamic LEN(s).
94struct ScalarDynamicDerived : ScalarSym {
95 ScalarDynamicDerived(const Fortran::semantics::Symbol &sym,
96 llvm::SmallVectorImpl<Fortran::lower::SomeExpr> &&lens)
97 : ScalarSym{sym}, lens{std::move(lens)} {}
98
99private:
100 llvm::SmallVector<Fortran::lower::SomeExpr> lens;
101};
102
103struct LBoundsAndShape {
104 LBoundsAndShape(llvm::SmallVectorImpl<int64_t> &&lbounds,
105 llvm::SmallVectorImpl<int64_t> &&shapes)
106 : lbounds{std::move(lbounds)}, shapes{std::move(shapes)} {}
107
108 static constexpr bool staticSize() { return true; }
109 static constexpr bool isArray() { return true; }
110 bool lboundAllOnes() const {
111 return llvm::all_of(lbounds, [](int64_t v) { return v == 1; });
112 }
113
114 llvm::SmallVector<int64_t> lbounds;
115 llvm::SmallVector<int64_t> shapes;
116};
117
118/// Array of T with statically known origin (lbounds) and shape.
119struct StaticArray : ScalarSym, LBoundsAndShape {
120 StaticArray(const Fortran::semantics::Symbol &sym,
121 llvm::SmallVectorImpl<int64_t> &&lbounds,
122 llvm::SmallVectorImpl<int64_t> &&shapes)
123 : ScalarSym{sym}, LBoundsAndShape{std::move(lbounds), std::move(shapes)} {
124 }
125
126 static constexpr bool staticSize() { return LBoundsAndShape::staticSize(); }
127};
128
129struct DynamicBound {
130 DynamicBound(
131 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
132 : bounds{std::move(bounds)} {}
133
134 static constexpr bool staticSize() { return false; }
135 static constexpr bool isArray() { return true; }
136 bool lboundAllOnes() const {
137 return llvm::all_of(bounds, [](const Fortran::semantics::ShapeSpec *p) {
138 if (auto low = p->lbound().GetExplicit())
139 if (auto lb = Fortran::evaluate::ToInt64(*low))
140 return *lb == 1;
141 return false;
142 });
143 }
144
145 llvm::SmallVector<const Fortran::semantics::ShapeSpec *> bounds;
146};
147
148/// Array of T with dynamic origin and/or shape.
149struct DynamicArray : ScalarSym, DynamicBound {
150 DynamicArray(
151 const Fortran::semantics::Symbol &sym,
152 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
153 : ScalarSym{sym}, DynamicBound{std::move(bounds)} {}
154
155 static constexpr bool staticSize() { return DynamicBound::staticSize(); }
156};
157
158/// Array of CHARACTER with statically known LEN, origin, and shape.
159struct StaticArrayStaticChar : ScalarStaticChar, LBoundsAndShape {
160 StaticArrayStaticChar(const Fortran::semantics::Symbol &sym, int64_t len,
161 llvm::SmallVectorImpl<int64_t> &&lbounds,
162 llvm::SmallVectorImpl<int64_t> &&shapes)
163 : ScalarStaticChar{sym, len}, LBoundsAndShape{std::move(lbounds),
164 std::move(shapes)} {}
165
166 static constexpr bool staticSize() {
167 return ScalarStaticChar::staticSize() && LBoundsAndShape::staticSize();
168 }
169};
170
171/// Array of CHARACTER with dynamic LEN but constant origin, shape.
172struct StaticArrayDynamicChar : ScalarDynamicChar, LBoundsAndShape {
173 StaticArrayDynamicChar(const Fortran::semantics::Symbol &sym,
174 const Fortran::lower::SomeExpr &len,
175 llvm::SmallVectorImpl<int64_t> &&lbounds,
176 llvm::SmallVectorImpl<int64_t> &&shapes)
177 : ScalarDynamicChar{sym, len}, LBoundsAndShape{std::move(lbounds),
178 std::move(shapes)} {}
179 StaticArrayDynamicChar(const Fortran::semantics::Symbol &sym,
180 llvm::SmallVectorImpl<int64_t> &&lbounds,
181 llvm::SmallVectorImpl<int64_t> &&shapes)
182 : ScalarDynamicChar{sym}, LBoundsAndShape{std::move(lbounds),
183 std::move(shapes)} {}
184
185 static constexpr bool staticSize() {
186 return ScalarDynamicChar::staticSize() && LBoundsAndShape::staticSize();
187 }
188};
189
190/// Array of CHARACTER with constant LEN but dynamic origin, shape.
191struct DynamicArrayStaticChar : ScalarStaticChar, DynamicBound {
192 DynamicArrayStaticChar(
193 const Fortran::semantics::Symbol &sym, int64_t len,
194 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
195 : ScalarStaticChar{sym, len}, DynamicBound{std::move(bounds)} {}
196
197 static constexpr bool staticSize() {
198 return ScalarStaticChar::staticSize() && DynamicBound::staticSize();
199 }
200};
201
202/// Array of CHARACTER with dynamic LEN, origin, and shape.
203struct DynamicArrayDynamicChar : ScalarDynamicChar, DynamicBound {
204 DynamicArrayDynamicChar(
205 const Fortran::semantics::Symbol &sym,
206 const Fortran::lower::SomeExpr &len,
207 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
208 : ScalarDynamicChar{sym, len}, DynamicBound{std::move(bounds)} {}
209 DynamicArrayDynamicChar(
210 const Fortran::semantics::Symbol &sym,
211 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
212 : ScalarDynamicChar{sym}, DynamicBound{std::move(bounds)} {}
213
214 static constexpr bool staticSize() {
215 return ScalarDynamicChar::staticSize() && DynamicBound::staticSize();
216 }
217};
218
219// TODO: Arrays of derived types with LEN(s)...
220
221} // namespace details
222
223inline bool symIsChar(const Fortran::semantics::Symbol &sym) {
224 return sym.GetType()->category() ==
225 Fortran::semantics::DeclTypeSpec::Character;
226}
227
228inline bool symIsArray(const Fortran::semantics::Symbol &sym) {
229 const auto *det =
230 sym.GetUltimate().detailsIf<Fortran::semantics::ObjectEntityDetails>();
231 return det && det->IsArray();
232}
233
234inline bool isExplicitShape(const Fortran::semantics::Symbol &sym) {
235 const auto *det =
236 sym.GetUltimate().detailsIf<Fortran::semantics::ObjectEntityDetails>();
237 return det && det->IsArray() && det->shape().IsExplicitShape();
238}
239
240inline bool isAssumedSize(const Fortran::semantics::Symbol &sym) {
241 return Fortran::semantics::IsAssumedSizeArray(sym.GetUltimate());
242}
243
244//===----------------------------------------------------------------------===//
245// Perform analysis to determine a box's parameter values
246//===----------------------------------------------------------------------===//
247
248/// Analyze a symbol, classify it as to whether it just a scalar, a CHARACTER
249/// scalar, an array entity, a combination thereof, and whether the LEN, shape,
250/// and lbounds are constant or not.
251class BoxAnalyzer : public fir::details::matcher<BoxAnalyzer> {
252public:
253 // Analysis default state
254 using None = std::monostate;
255
256 using ScalarSym = details::ScalarSym;
257 using ScalarStaticChar = details::ScalarStaticChar;
258 using ScalarDynamicChar = details::ScalarDynamicChar;
259 using StaticArray = details::StaticArray;
260 using DynamicArray = details::DynamicArray;
261 using StaticArrayStaticChar = details::StaticArrayStaticChar;
262 using StaticArrayDynamicChar = details::StaticArrayDynamicChar;
263 using DynamicArrayStaticChar = details::DynamicArrayStaticChar;
264 using DynamicArrayDynamicChar = details::DynamicArrayDynamicChar;
265 // TODO: derived types
266
267 using VT = std::variant<None, ScalarSym, ScalarStaticChar, ScalarDynamicChar,
268 StaticArray, DynamicArray, StaticArrayStaticChar,
269 StaticArrayDynamicChar, DynamicArrayStaticChar,
270 DynamicArrayDynamicChar>;
271
272 //===--------------------------------------------------------------------===//
273 // Constructor
274 //===--------------------------------------------------------------------===//
275
276 BoxAnalyzer() : box{None{}} {}
277
278 operator bool() const { return !std::holds_alternative<None>(box); }
279
280 bool isTrivial() const { return std::holds_alternative<ScalarSym>(box); }
281
282 /// Returns true for any sort of CHARACTER.
283 bool isChar() const {
284 return match([](const ScalarStaticChar &) { return true; },
285 [](const ScalarDynamicChar &) { return true; },
286 [](const StaticArrayStaticChar &) { return true; },
287 [](const StaticArrayDynamicChar &) { return true; },
288 [](const DynamicArrayStaticChar &) { return true; },
289 [](const DynamicArrayDynamicChar &) { return true; },
290 [](const auto &) { return false; });
291 }
292
293 /// Returns true for any sort of array.
294 bool isArray() const {
295 return match([](const StaticArray &) { return true; },
296 [](const DynamicArray &) { return true; },
297 [](const StaticArrayStaticChar &) { return true; },
298 [](const StaticArrayDynamicChar &) { return true; },
299 [](const DynamicArrayStaticChar &) { return true; },
300 [](const DynamicArrayDynamicChar &) { return true; },
301 [](const auto &) { return false; });
302 }
303
304 /// Returns true iff this is an array with constant extents and lbounds. This
305 /// returns true for arrays of CHARACTER, even if the LEN is not a constant.
306 bool isStaticArray() const {
307 return match([](const StaticArray &) { return true; },
308 [](const StaticArrayStaticChar &) { return true; },
309 [](const StaticArrayDynamicChar &) { return true; },
310 [](const auto &) { return false; });
311 }
312
313 bool isConstant() const {
314 return match(
315 [](const None &) -> bool {
316 llvm::report_fatal_error("internal: analysis failed");
317 },
318 [](const auto &x) { return x.staticSize(); });
319 }
320
321 std::optional<int64_t> getCharLenConst() const {
322 using A = std::optional<int64_t>;
323 return match(
324 [](const ScalarStaticChar &x) -> A { return {x.charLen()}; },
325 [](const StaticArrayStaticChar &x) -> A { return {x.charLen()}; },
326 [](const DynamicArrayStaticChar &x) -> A { return {x.charLen()}; },
327 [](const auto &) -> A { return std::nullopt; });
328 }
329
330 std::optional<Fortran::lower::SomeExpr> getCharLenExpr() const {
331 using A = std::optional<Fortran::lower::SomeExpr>;
332 return match([](const ScalarDynamicChar &x) { return x.charLen(); },
333 [](const StaticArrayDynamicChar &x) { return x.charLen(); },
334 [](const DynamicArrayDynamicChar &x) { return x.charLen(); },
335 [](const auto &) -> A { return std::nullopt; });
336 }
337
338 /// Is the origin of this array the default of vector of `1`?
339 bool lboundIsAllOnes() const {
340 return match(
341 [&](const StaticArray &x) { return x.lboundAllOnes(); },
342 [&](const DynamicArray &x) { return x.lboundAllOnes(); },
343 [&](const StaticArrayStaticChar &x) { return x.lboundAllOnes(); },
344 [&](const StaticArrayDynamicChar &x) { return x.lboundAllOnes(); },
345 [&](const DynamicArrayStaticChar &x) { return x.lboundAllOnes(); },
346 [&](const DynamicArrayDynamicChar &x) { return x.lboundAllOnes(); },
347 [](const auto &) -> bool { llvm::report_fatal_error("not an array"); });
348 }
349
350 /// Get the static lbound values (the origin of the array).
351 llvm::ArrayRef<int64_t> staticLBound() const {
352 using A = llvm::ArrayRef<int64_t>;
353 return match([](const StaticArray &x) -> A { return x.lbounds; },
354 [](const StaticArrayStaticChar &x) -> A { return x.lbounds; },
355 [](const StaticArrayDynamicChar &x) -> A { return x.lbounds; },
356 [](const auto &) -> A {
357 llvm::report_fatal_error("does not have static lbounds");
358 });
359 }
360
361 /// Get the static extents of the array.
362 llvm::ArrayRef<int64_t> staticShape() const {
363 using A = llvm::ArrayRef<int64_t>;
364 return match([](const StaticArray &x) -> A { return x.shapes; },
365 [](const StaticArrayStaticChar &x) -> A { return x.shapes; },
366 [](const StaticArrayDynamicChar &x) -> A { return x.shapes; },
367 [](const auto &) -> A {
368 llvm::report_fatal_error("does not have static shape");
369 });
370 }
371
372 /// Get the dynamic bounds information of the array (both origin, shape).
373 llvm::ArrayRef<const Fortran::semantics::ShapeSpec *> dynamicBound() const {
374 using A = llvm::ArrayRef<const Fortran::semantics::ShapeSpec *>;
375 return match([](const DynamicArray &x) -> A { return x.bounds; },
376 [](const DynamicArrayStaticChar &x) -> A { return x.bounds; },
377 [](const DynamicArrayDynamicChar &x) -> A { return x.bounds; },
378 [](const auto &) -> A {
379 llvm::report_fatal_error("does not have bounds");
380 });
381 }
382
383 /// Run the analysis on `sym`.
384 void analyze(const Fortran::semantics::Symbol &sym) {
385 if (Fortran::semantics::IsProcedurePointer(sym))
386 return;
387 if (symIsArray(sym)) {
388 bool isConstant = !isAssumedSize(sym);
389 llvm::SmallVector<int64_t> lbounds;
390 llvm::SmallVector<int64_t> shapes;
391 llvm::SmallVector<const Fortran::semantics::ShapeSpec *> bounds;
392 for (const Fortran::semantics::ShapeSpec &subs : getSymShape(sym)) {
393 bounds.push_back(&subs);
394 if (!isConstant)
395 continue;
396 if (auto low = subs.lbound().GetExplicit()) {
397 if (auto lb = Fortran::evaluate::ToInt64(*low)) {
398 lbounds.push_back(*lb); // origin for this dim
399 if (auto high = subs.ubound().GetExplicit()) {
400 if (auto ub = Fortran::evaluate::ToInt64(*high)) {
401 int64_t extent = *ub - *lb + 1;
402 shapes.push_back(extent < 0 ? 0 : extent);
403 continue;
404 }
405 } else if (subs.ubound().isStar()) {
406 assert(Fortran::semantics::IsNamedConstant(sym) &&
407 "expect implied shape constant");
408 shapes.push_back(fir::SequenceType::getUnknownExtent());
409 continue;
410 }
411 }
412 }
413 isConstant = false;
414 }
415
416 // sym : array<CHARACTER>
417 if (symIsChar(sym)) {
418 if (auto len = charLenConstant(sym)) {
419 if (isConstant)
420 box = StaticArrayStaticChar(sym, *len, std::move(lbounds),
421 std::move(shapes));
422 else
423 box = DynamicArrayStaticChar(sym, *len, std::move(bounds));
424 return;
425 }
426 if (auto var = charLenVariable(sym)) {
427 if (isConstant)
428 box = StaticArrayDynamicChar(sym, *var, std::move(lbounds),
429 std::move(shapes));
430 else
431 box = DynamicArrayDynamicChar(sym, *var, std::move(bounds));
432 return;
433 }
434 if (isConstant)
435 box = StaticArrayDynamicChar(sym, std::move(lbounds),
436 std::move(shapes));
437 else
438 box = DynamicArrayDynamicChar(sym, std::move(bounds));
439 return;
440 }
441
442 // sym : array<other>
443 if (isConstant)
444 box = StaticArray(sym, std::move(lbounds), std::move(shapes));
445 else
446 box = DynamicArray(sym, std::move(bounds));
447 return;
448 }
449
450 // sym : CHARACTER
451 if (symIsChar(sym)) {
452 if (auto len = charLenConstant(sym))
453 box = ScalarStaticChar(sym, *len);
454 else if (auto var = charLenVariable(sym))
455 box = ScalarDynamicChar(sym, *var);
456 else
457 box = ScalarDynamicChar(sym);
458 return;
459 }
460
461 // sym : other
462 box = ScalarSym(sym);
463 }
464
465 const VT &matchee() const { return box; }
466
467private:
468 // Get the shape of a symbol.
469 const Fortran::semantics::ArraySpec &
470 getSymShape(const Fortran::semantics::Symbol &sym) {
471 return sym.GetUltimate()
472 .get<Fortran::semantics::ObjectEntityDetails>()
473 .shape();
474 }
475
476 // Get the constant LEN of a CHARACTER, if it exists.
477 std::optional<int64_t>
478 charLenConstant(const Fortran::semantics::Symbol &sym) {
479 if (std::optional<Fortran::lower::SomeExpr> expr = charLenVariable(sym))
480 if (std::optional<int64_t> asInt = Fortran::evaluate::ToInt64(*expr)) {
481 // Length is max(0, *asInt) (F2018 7.4.4.2 point 5.).
482 if (*asInt < 0)
483 return 0;
484 return *asInt;
485 }
486 return std::nullopt;
487 }
488
489 // Get the `SomeExpr` that describes the CHARACTER's LEN.
490 std::optional<Fortran::lower::SomeExpr>
491 charLenVariable(const Fortran::semantics::Symbol &sym) {
492 const Fortran::semantics::ParamValue &lenParam =
493 sym.GetType()->characterTypeSpec().length();
494 if (Fortran::semantics::MaybeIntExpr expr = lenParam.GetExplicit())
495 return {Fortran::evaluate::AsGenericExpr(std::move(*expr))};
496 // For assumed LEN parameters, the length comes from the initialization
497 // expression.
498 if (sym.attrs().test(Fortran::semantics::Attr::PARAMETER))
499 if (const auto *objectDetails =
500 sym.GetUltimate()
501 .detailsIf<Fortran::semantics::ObjectEntityDetails>())
502 if (objectDetails->init())
503 if (const auto *charExpr = std::get_if<
504 Fortran::evaluate::Expr<Fortran::evaluate::SomeCharacter>>(
505 &objectDetails->init()->u))
506 if (Fortran::semantics::MaybeSubscriptIntExpr expr =
507 charExpr->LEN())
508 return {Fortran::evaluate::AsGenericExpr(std::move(*expr))};
509 return std::nullopt;
510 }
511
512 VT box;
513}; // namespace Fortran::lower
514
515} // namespace Fortran::lower
516
517#endif // FORTRAN_LOWER_BOXANALYZER_H
518

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

source code of flang/include/flang/Lower/BoxAnalyzer.h