413 lines · cpp
1//===-- lib/Evaluate/constant.cpp -----------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "flang/Evaluate/constant.h"10#include "flang/Evaluate/expression.h"11#include "flang/Evaluate/shape.h"12#include "flang/Evaluate/tools.h"13#include "flang/Evaluate/type.h"14#include <string>15 16namespace Fortran::evaluate {17 18ConstantBounds::ConstantBounds(const ConstantSubscripts &shape)19 : shape_(shape), lbounds_(shape_.size(), 1) {}20 21ConstantBounds::ConstantBounds(ConstantSubscripts &&shape)22 : shape_(std::move(shape)), lbounds_(shape_.size(), 1) {}23 24ConstantBounds::~ConstantBounds() = default;25 26void ConstantBounds::set_lbounds(ConstantSubscripts &&lb) {27 CHECK(lb.size() == shape_.size());28 lbounds_ = std::move(lb);29 for (std::size_t j{0}; j < shape_.size(); ++j) {30 if (shape_[j] == 0) {31 lbounds_[j] = 1;32 }33 }34}35 36ConstantSubscripts ConstantBounds::ComputeUbounds(37 std::optional<int> dim) const {38 if (dim) {39 CHECK(*dim < Rank());40 return {lbounds_[*dim] + (shape_[*dim] - 1)};41 } else {42 ConstantSubscripts ubounds(Rank());43 for (int i{0}; i < Rank(); ++i) {44 ubounds[i] = lbounds_[i] + (shape_[i] - 1);45 }46 return ubounds;47 }48}49 50void ConstantBounds::SetLowerBoundsToOne() {51 for (auto &n : lbounds_) {52 n = 1;53 }54}55 56Constant<SubscriptInteger> ConstantBounds::SHAPE() const {57 return AsConstantShape(shape_);58}59 60bool ConstantBounds::HasNonDefaultLowerBound() const {61 for (auto n : lbounds_) {62 if (n != 1) {63 return true;64 }65 }66 return false;67}68 69ConstantSubscript ConstantBounds::SubscriptsToOffset(70 const ConstantSubscripts &index) const {71 CHECK(GetRank(index) == GetRank(shape_));72 ConstantSubscript stride{1}, offset{0};73 int dim{0};74 for (auto j : index) {75 auto lb{lbounds_[dim]};76 auto extent{shape_[dim++]};77 CHECK(j >= lb && j - lb < extent);78 offset += stride * (j - lb);79 stride *= extent;80 }81 return offset;82}83 84std::optional<uint64_t> TotalElementCount(const ConstantSubscripts &shape) {85 uint64_t size{1};86 for (auto dim : shape) {87 CHECK(dim >= 0);88 uint64_t osize{size};89 size = osize * dim;90 if (size > std::numeric_limits<decltype(dim)>::max() ||91 (dim != 0 && size / dim != osize)) {92 return std::nullopt;93 }94 }95 return static_cast<uint64_t>(GetSize(shape));96}97 98bool ConstantBounds::IncrementSubscripts(99 ConstantSubscripts &indices, const std::vector<int> *dimOrder) const {100 int rank{GetRank(shape_)};101 CHECK(GetRank(indices) == rank);102 CHECK(!dimOrder || static_cast<int>(dimOrder->size()) == rank);103 for (int j{0}; j < rank; ++j) {104 ConstantSubscript k{dimOrder ? (*dimOrder)[j] : j};105 auto lb{lbounds_[k]};106 CHECK(indices[k] >= lb);107 if (++indices[k] - lb < shape_[k]) {108 return true;109 } else {110 CHECK(indices[k] - lb == std::max<ConstantSubscript>(shape_[k], 1));111 indices[k] = lb;112 }113 }114 return false; // all done115}116 117std::optional<std::vector<int>> ValidateDimensionOrder(118 int rank, const std::vector<int> &order) {119 std::vector<int> dimOrder(rank);120 if (static_cast<int>(order.size()) == rank) {121 std::bitset<common::maxRank> seenDimensions;122 for (int j{0}; j < rank; ++j) {123 int dim{order[j]};124 if (dim < 1 || dim > rank || seenDimensions.test(dim - 1)) {125 return std::nullopt;126 }127 dimOrder[j] = dim - 1;128 seenDimensions.set(dim - 1);129 }130 return dimOrder;131 } else {132 return std::nullopt;133 }134}135 136bool HasNegativeExtent(const ConstantSubscripts &shape) {137 for (ConstantSubscript extent : shape) {138 if (extent < 0) {139 return true;140 }141 }142 return false;143}144 145template <typename RESULT, typename ELEMENT>146ConstantBase<RESULT, ELEMENT>::ConstantBase(147 std::vector<Element> &&x, ConstantSubscripts &&sh, Result res)148 : ConstantBounds(std::move(sh)), result_{res}, values_(std::move(x)) {149 CHECK(TotalElementCount(shape()) && size() == *TotalElementCount(shape()));150}151 152template <typename RESULT, typename ELEMENT>153ConstantBase<RESULT, ELEMENT>::~ConstantBase() {}154 155template <typename RESULT, typename ELEMENT>156bool ConstantBase<RESULT, ELEMENT>::operator==(const ConstantBase &that) const {157 return shape() == that.shape() && values_ == that.values_;158}159 160template <typename RESULT, typename ELEMENT>161auto ConstantBase<RESULT, ELEMENT>::Reshape(162 const ConstantSubscripts &dims) const -> std::vector<Element> {163 std::optional<uint64_t> optN{TotalElementCount(dims)};164 CHECK_MSG(optN, "Overflow in TotalElementCount");165 uint64_t n{*optN};166 CHECK(!empty() || n == 0);167 std::vector<Element> elements;168 auto iter{values().cbegin()};169 while (n-- > 0) {170 elements.push_back(*iter);171 if (++iter == values().cend()) {172 iter = values().cbegin();173 }174 }175 return elements;176}177 178template <typename RESULT, typename ELEMENT>179std::size_t ConstantBase<RESULT, ELEMENT>::CopyFrom(180 const ConstantBase<RESULT, ELEMENT> &source, std::size_t count,181 ConstantSubscripts &resultSubscripts, const std::vector<int> *dimOrder) {182 std::size_t copied{0};183 ConstantSubscripts sourceSubscripts{source.lbounds()};184 while (copied < count) {185 values_.at(SubscriptsToOffset(resultSubscripts)) =186 source.values_.at(source.SubscriptsToOffset(sourceSubscripts));187 copied++;188 source.IncrementSubscripts(sourceSubscripts);189 IncrementSubscripts(resultSubscripts, dimOrder);190 }191 return copied;192}193 194template <typename T>195auto Constant<T>::At(const ConstantSubscripts &index) const -> Element {196 return Base::values_.at(Base::SubscriptsToOffset(index));197}198 199template <typename T>200auto Constant<T>::Reshape(ConstantSubscripts &&dims) const -> Constant {201 return {Base::Reshape(dims), std::move(dims)};202}203 204template <typename T>205std::size_t Constant<T>::CopyFrom(const Constant<T> &source, std::size_t count,206 ConstantSubscripts &resultSubscripts, const std::vector<int> *dimOrder) {207 return Base::CopyFrom(source, count, resultSubscripts, dimOrder);208}209 210// Constant<Type<TypeCategory::Character, KIND> specializations211template <int KIND>212Constant<Type<TypeCategory::Character, KIND>>::Constant(213 const Scalar<Result> &str)214 : values_{str}, length_{static_cast<ConstantSubscript>(values_.size())} {}215 216template <int KIND>217Constant<Type<TypeCategory::Character, KIND>>::Constant(Scalar<Result> &&str)218 : values_{std::move(str)}, length_{static_cast<ConstantSubscript>(219 values_.size())} {}220 221template <int KIND>222Constant<Type<TypeCategory::Character, KIND>>::Constant(ConstantSubscript len,223 std::vector<Scalar<Result>> &&strings, ConstantSubscripts &&sh)224 : ConstantBounds(std::move(sh)), length_{len} {225 CHECK(TotalElementCount(shape()) &&226 strings.size() == *TotalElementCount(shape()));227 values_.assign(strings.size() * length_,228 static_cast<typename Scalar<Result>::value_type>(' '));229 ConstantSubscript at{0};230 for (const auto &str : strings) {231 auto strLen{static_cast<ConstantSubscript>(str.size())};232 if (strLen > length_) {233 values_.replace(at, length_, str.substr(0, length_));234 } else {235 values_.replace(at, strLen, str);236 }237 at += length_;238 }239 CHECK(at == static_cast<ConstantSubscript>(values_.size()));240}241 242template <int KIND>243Constant<Type<TypeCategory::Character, KIND>>::~Constant() {}244 245template <int KIND>246bool Constant<Type<TypeCategory::Character, KIND>>::empty() const {247 return size() == 0;248}249 250template <int KIND>251std::size_t Constant<Type<TypeCategory::Character, KIND>>::size() const {252 if (length_ == 0) {253 std::optional<uint64_t> n{TotalElementCount(shape())};254 CHECK(n);255 return *n;256 } else {257 return static_cast<ConstantSubscript>(values_.size()) / length_;258 }259}260 261template <int KIND>262auto Constant<Type<TypeCategory::Character, KIND>>::At(263 const ConstantSubscripts &index) const -> Scalar<Result> {264 auto offset{SubscriptsToOffset(index)};265 return values_.substr(offset * length_, length_);266}267 268template <int KIND>269auto Constant<Type<TypeCategory::Character, KIND>>::Substring(270 ConstantSubscript lo, ConstantSubscript hi) const271 -> std::optional<Constant> {272 std::vector<Element> elements;273 ConstantSubscript n{GetSize(shape())};274 ConstantSubscript newLength{0};275 if (lo > hi) { // zero-length results276 while (n-- > 0) {277 elements.emplace_back(); // ""278 }279 } else if (lo < 1 || hi > length_) {280 return std::nullopt;281 } else {282 newLength = hi - lo + 1;283 for (ConstantSubscripts at{lbounds()}; n-- > 0; IncrementSubscripts(at)) {284 elements.emplace_back(At(at).substr(lo - 1, newLength));285 }286 }287 return Constant{newLength, std::move(elements), ConstantSubscripts{shape()}};288}289 290template <int KIND>291auto Constant<Type<TypeCategory::Character, KIND>>::Reshape(292 ConstantSubscripts &&dims) const -> Constant<Result> {293 std::optional<uint64_t> optN{TotalElementCount(dims)};294 CHECK(optN);295 uint64_t n{*optN};296 CHECK(!empty() || n == 0);297 std::vector<Element> elements;298 ConstantSubscript at{0},299 limit{static_cast<ConstantSubscript>(values_.size())};300 while (n-- > 0) {301 elements.push_back(values_.substr(at, length_));302 at += length_;303 if (at == limit) { // subtle: at > limit somehow? substr() will catch it304 at = 0;305 }306 }307 return {length_, std::move(elements), std::move(dims)};308}309 310template <int KIND>311std::size_t Constant<Type<TypeCategory::Character, KIND>>::CopyFrom(312 const Constant<Type<TypeCategory::Character, KIND>> &source,313 std::size_t count, ConstantSubscripts &resultSubscripts,314 const std::vector<int> *dimOrder) {315 CHECK(length_ == source.length_);316 if (length_ == 0) {317 // It's possible that the array of strings consists of all empty strings.318 // If so, constant folding will result in a string that's completely empty319 // and the length_ will be zero, and there's nothing to do.320 return count;321 } else {322 std::size_t copied{0};323 std::size_t elementBytes{length_ * sizeof(decltype(values_[0]))};324 ConstantSubscripts sourceSubscripts{source.lbounds()};325 while (copied < count) {326 auto *dest{&values_.at(SubscriptsToOffset(resultSubscripts) * length_)};327 const auto *src{&source.values_.at(328 source.SubscriptsToOffset(sourceSubscripts) * length_)};329 std::memcpy(dest, src, elementBytes);330 copied++;331 source.IncrementSubscripts(sourceSubscripts);332 IncrementSubscripts(resultSubscripts, dimOrder);333 }334 return copied;335 }336}337 338// Constant<SomeDerived> specialization339Constant<SomeDerived>::Constant(const StructureConstructor &x)340 : Base{x.values(), Result{x.derivedTypeSpec()}} {}341 342Constant<SomeDerived>::Constant(StructureConstructor &&x)343 : Base{std::move(x.values()), Result{x.derivedTypeSpec()}} {}344 345Constant<SomeDerived>::Constant(const semantics::DerivedTypeSpec &spec,346 std::vector<StructureConstructorValues> &&x, ConstantSubscripts &&s)347 : Base{std::move(x), std::move(s), Result{spec}} {}348 349static std::vector<StructureConstructorValues> AcquireValues(350 std::vector<StructureConstructor> &&x) {351 std::vector<StructureConstructorValues> result;352 for (auto &&structure : std::move(x)) {353 result.emplace_back(std::move(structure.values()));354 }355 return result;356}357 358Constant<SomeDerived>::Constant(const semantics::DerivedTypeSpec &spec,359 std::vector<StructureConstructor> &&x, ConstantSubscripts &&shape)360 : Base{AcquireValues(std::move(x)), std::move(shape), Result{spec}} {}361 362std::optional<StructureConstructor>363Constant<SomeDerived>::GetScalarValue() const {364 if (Rank() == 0) {365 return StructureConstructor{result().derivedTypeSpec(), values_.at(0)};366 } else {367 return std::nullopt;368 }369}370 371StructureConstructor Constant<SomeDerived>::At(372 const ConstantSubscripts &index) const {373 return {result().derivedTypeSpec(), values_.at(SubscriptsToOffset(index))};374}375 376bool Constant<SomeDerived>::operator==(377 const Constant<SomeDerived> &that) const {378 return result().derivedTypeSpec() == that.result().derivedTypeSpec() &&379 shape() == that.shape() && values_ == that.values_;380}381 382auto Constant<SomeDerived>::Reshape(ConstantSubscripts &&dims) const383 -> Constant {384 return {result().derivedTypeSpec(), Base::Reshape(dims), std::move(dims)};385}386 387std::size_t Constant<SomeDerived>::CopyFrom(const Constant<SomeDerived> &source,388 std::size_t count, ConstantSubscripts &resultSubscripts,389 const std::vector<int> *dimOrder) {390 return Base::CopyFrom(source, count, resultSubscripts, dimOrder);391}392 393bool ComponentCompare::operator()(SymbolRef x, SymbolRef y) const {394 if (&x->owner() != &y->owner()) {395 // Not components of the same derived type; put ancestors' components first.396 if (auto xDepth{CountDerivedTypeAncestors(x->owner())}) {397 if (auto yDepth{CountDerivedTypeAncestors(y->owner())}) {398 if (*xDepth != *yDepth) {399 return *xDepth < *yDepth;400 }401 }402 }403 }404 // Same derived type, distinct instantiations, or error recovery.405 return semantics::SymbolSourcePositionCompare{}(x, y);406}407 408#ifdef _MSC_VER // disable bogus warning about missing definitions409#pragma warning(disable : 4661)410#endif411INSTANTIATE_CONSTANT_TEMPLATES412} // namespace Fortran::evaluate413