1 //===-- lib/Semantics/compute-offsets.cpp -----------------------*- 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 #include "compute-offsets.h" 10 #include "../../runtime/descriptor.h" 11 #include "flang/Evaluate/fold-designator.h" 12 #include "flang/Evaluate/fold.h" 13 #include "flang/Evaluate/shape.h" 14 #include "flang/Evaluate/type.h" 15 #include "flang/Semantics/scope.h" 16 #include "flang/Semantics/semantics.h" 17 #include "flang/Semantics/symbol.h" 18 #include "flang/Semantics/tools.h" 19 #include "flang/Semantics/type.h" 20 #include <algorithm> 21 #include <vector> 22 23 namespace Fortran::semantics { 24 25 class ComputeOffsetsHelper { 26 public: 27 // TODO: configure based on target 28 static constexpr std::size_t maxAlignment{8}; 29 30 ComputeOffsetsHelper(SemanticsContext &context) : context_{context} {} 31 void Compute() { Compute(context_.globalScope()); } 32 33 private: 34 struct SizeAndAlignment { 35 SizeAndAlignment() {} 36 SizeAndAlignment(std::size_t bytes) : size{bytes}, alignment{bytes} {} 37 SizeAndAlignment(std::size_t bytes, std::size_t align) 38 : size{bytes}, alignment{align} {} 39 std::size_t size{0}; 40 std::size_t alignment{0}; 41 }; 42 struct SymbolAndOffset { 43 SymbolAndOffset(Symbol &s, std::size_t off, const EquivalenceObject &obj) 44 : symbol{&s}, offset{off}, object{&obj} {} 45 SymbolAndOffset(const SymbolAndOffset &) = default; 46 Symbol *symbol; 47 std::size_t offset; 48 const EquivalenceObject *object; 49 }; 50 51 void Compute(Scope &); 52 void DoScope(Scope &); 53 void DoCommonBlock(Symbol &); 54 void DoEquivalenceBlockBase(Symbol &, SizeAndAlignment &); 55 void DoEquivalenceSet(const EquivalenceSet &); 56 SymbolAndOffset Resolve(const SymbolAndOffset &); 57 std::size_t ComputeOffset(const EquivalenceObject &); 58 void DoSymbol(Symbol &); 59 SizeAndAlignment GetSizeAndAlignment(const Symbol &); 60 SizeAndAlignment GetElementSize(const Symbol &); 61 std::size_t CountElements(const Symbol &); 62 static std::size_t Align(std::size_t, std::size_t); 63 static SizeAndAlignment GetIntrinsicSizeAndAlignment(TypeCategory, int); 64 65 SemanticsContext &context_; 66 evaluate::FoldingContext &foldingContext_{context_.foldingContext()}; 67 std::size_t offset_{0}; 68 std::size_t alignment_{0}; 69 // symbol -> symbol+offset that determines its location, from EQUIVALENCE 70 std::map<MutableSymbolRef, SymbolAndOffset> dependents_; 71 // base symbol -> SizeAndAlignment for each distinct EQUIVALENCE block 72 std::map<MutableSymbolRef, SizeAndAlignment> equivalenceBlock_; 73 }; 74 75 void ComputeOffsetsHelper::Compute(Scope &scope) { 76 for (Scope &child : scope.children()) { 77 Compute(child); 78 } 79 DoScope(scope); 80 dependents_.clear(); 81 equivalenceBlock_.clear(); 82 } 83 84 void ComputeOffsetsHelper::DoScope(Scope &scope) { 85 if (scope.symbol() && scope.IsParameterizedDerivedType()) { 86 return; // only process instantiations of parameterized derived types 87 } 88 // Build dependents_ from equivalences: symbol -> symbol+offset 89 for (const EquivalenceSet &set : scope.equivalenceSets()) { 90 DoEquivalenceSet(set); 91 } 92 offset_ = 0; 93 alignment_ = 0; 94 // Compute a base symbol and overall block size for each 95 // disjoint EQUIVALENCE storage sequence. 96 for (auto &[symbol, dep] : dependents_) { 97 dep = Resolve(dep); 98 CHECK(symbol->size() == 0); 99 auto symInfo{GetSizeAndAlignment(*symbol)}; 100 symbol->set_size(symInfo.size); 101 Symbol &base{*dep.symbol}; 102 auto iter{equivalenceBlock_.find(base)}; 103 std::size_t minBlockSize{dep.offset + symInfo.size}; 104 if (iter == equivalenceBlock_.end()) { 105 equivalenceBlock_.emplace( 106 base, SizeAndAlignment{minBlockSize, symInfo.alignment}); 107 } else { 108 SizeAndAlignment &blockInfo{iter->second}; 109 blockInfo.size = std::max(blockInfo.size, minBlockSize); 110 blockInfo.alignment = std::max(blockInfo.alignment, symInfo.alignment); 111 } 112 } 113 // Assign offsets for non-COMMON EQUIVALENCE blocks 114 for (auto &[symbol, blockInfo] : equivalenceBlock_) { 115 if (!InCommonBlock(*symbol)) { 116 DoSymbol(*symbol); 117 DoEquivalenceBlockBase(*symbol, blockInfo); 118 offset_ = std::max(offset_, symbol->offset() + blockInfo.size); 119 } 120 } 121 // Process remaining non-COMMON symbols; this is all of them if there 122 // was no use of EQUIVALENCE in the scope. 123 for (auto &symbol : scope.GetSymbols()) { 124 if (!InCommonBlock(*symbol) && 125 dependents_.find(symbol) == dependents_.end() && 126 equivalenceBlock_.find(symbol) == equivalenceBlock_.end()) { 127 DoSymbol(*symbol); 128 } 129 } 130 scope.set_size(offset_); 131 scope.set_alignment(alignment_); 132 // Assign offsets in COMMON blocks. 133 for (auto &pair : scope.commonBlocks()) { 134 DoCommonBlock(*pair.second); 135 } 136 for (auto &[symbol, dep] : dependents_) { 137 symbol->set_offset(dep.symbol->offset() + dep.offset); 138 if (const auto *block{FindCommonBlockContaining(*dep.symbol)}) { 139 symbol->get<ObjectEntityDetails>().set_commonBlock(*block); 140 } 141 } 142 } 143 144 auto ComputeOffsetsHelper::Resolve(const SymbolAndOffset &dep) 145 -> SymbolAndOffset { 146 auto it{dependents_.find(*dep.symbol)}; 147 if (it == dependents_.end()) { 148 return dep; 149 } else { 150 SymbolAndOffset result{Resolve(it->second)}; 151 result.offset += dep.offset; 152 result.object = dep.object; 153 return result; 154 } 155 } 156 157 void ComputeOffsetsHelper::DoCommonBlock(Symbol &commonBlock) { 158 auto &details{commonBlock.get<CommonBlockDetails>()}; 159 offset_ = 0; 160 alignment_ = 0; 161 std::size_t minSize{0}; 162 std::size_t minAlignment{0}; 163 for (auto &object : details.objects()) { 164 Symbol &symbol{*object}; 165 DoSymbol(symbol); 166 auto iter{dependents_.find(symbol)}; 167 if (iter == dependents_.end()) { 168 // Get full extent of any EQUIVALENCE block into size of COMMON 169 auto eqIter{equivalenceBlock_.find(symbol)}; 170 if (eqIter != equivalenceBlock_.end()) { 171 SizeAndAlignment &blockInfo{eqIter->second}; 172 DoEquivalenceBlockBase(symbol, blockInfo); 173 minSize = std::max( 174 minSize, std::max(offset_, symbol.offset() + blockInfo.size)); 175 minAlignment = std::max(minAlignment, blockInfo.alignment); 176 } 177 } else { 178 SymbolAndOffset &dep{iter->second}; 179 Symbol &base{*dep.symbol}; 180 auto errorSite{ 181 commonBlock.name().empty() ? symbol.name() : commonBlock.name()}; 182 if (const auto *baseBlock{FindCommonBlockContaining(base)}) { 183 if (baseBlock == &commonBlock) { 184 context_.Say(errorSite, 185 "'%s' is storage associated with '%s' by EQUIVALENCE elsewhere in COMMON block /%s/"_err_en_US, 186 symbol.name(), base.name(), commonBlock.name()); 187 } else { // 8.10.3(1) 188 context_.Say(errorSite, 189 "'%s' in COMMON block /%s/ must not be storage associated with '%s' in COMMON block /%s/ by EQUIVALENCE"_err_en_US, 190 symbol.name(), commonBlock.name(), base.name(), 191 baseBlock->name()); 192 } 193 } else if (dep.offset > symbol.offset()) { // 8.10.3(3) 194 context_.Say(errorSite, 195 "'%s' cannot backward-extend COMMON block /%s/ via EQUIVALENCE with '%s'"_err_en_US, 196 symbol.name(), commonBlock.name(), base.name()); 197 } else { 198 base.get<ObjectEntityDetails>().set_commonBlock(commonBlock); 199 base.set_offset(symbol.offset() - dep.offset); 200 } 201 } 202 } 203 commonBlock.set_size(std::max(minSize, offset_)); 204 details.set_alignment(std::max(minAlignment, alignment_)); 205 } 206 207 void ComputeOffsetsHelper::DoEquivalenceBlockBase( 208 Symbol &symbol, SizeAndAlignment &blockInfo) { 209 if (symbol.size() > blockInfo.size) { 210 blockInfo.size = symbol.size(); 211 } 212 } 213 214 void ComputeOffsetsHelper::DoEquivalenceSet(const EquivalenceSet &set) { 215 std::vector<SymbolAndOffset> symbolOffsets; 216 std::optional<std::size_t> representative; 217 for (const EquivalenceObject &object : set) { 218 std::size_t offset{ComputeOffset(object)}; 219 SymbolAndOffset resolved{ 220 Resolve(SymbolAndOffset{object.symbol, offset, object})}; 221 symbolOffsets.push_back(resolved); 222 if (!representative || 223 resolved.offset >= symbolOffsets[*representative].offset) { 224 // The equivalenced object with the largest offset from its resolved 225 // symbol will be the representative of this set, since the offsets 226 // of the other objects will be positive relative to it. 227 representative = symbolOffsets.size() - 1; 228 } 229 } 230 CHECK(representative); 231 const SymbolAndOffset &base{symbolOffsets[*representative]}; 232 for (const auto &[symbol, offset, object] : symbolOffsets) { 233 if (symbol == base.symbol) { 234 if (offset != base.offset) { 235 auto x{evaluate::OffsetToDesignator( 236 context_.foldingContext(), *symbol, base.offset, 1)}; 237 auto y{evaluate::OffsetToDesignator( 238 context_.foldingContext(), *symbol, offset, 1)}; 239 if (x && y) { 240 context_ 241 .Say(base.object->source, 242 "'%s' and '%s' cannot have the same first storage unit"_err_en_US, 243 x->AsFortran(), y->AsFortran()) 244 .Attach(object->source, "Incompatible reference to '%s'"_en_US, 245 y->AsFortran()); 246 } else { // error recovery 247 context_ 248 .Say(base.object->source, 249 "'%s' (offset %zd bytes and %zd bytes) cannot have the same first storage unit"_err_en_US, 250 symbol->name(), base.offset, offset) 251 .Attach(object->source, 252 "Incompatible reference to '%s' offset %zd bytes"_en_US, 253 symbol->name(), offset); 254 } 255 } 256 } else { 257 dependents_.emplace(*symbol, 258 SymbolAndOffset{*base.symbol, base.offset - offset, *object}); 259 } 260 } 261 } 262 263 // Offset of this equivalence object from the start of its variable. 264 std::size_t ComputeOffsetsHelper::ComputeOffset( 265 const EquivalenceObject &object) { 266 std::size_t offset{0}; 267 if (!object.subscripts.empty()) { 268 const ArraySpec &shape{object.symbol.get<ObjectEntityDetails>().shape()}; 269 auto lbound{[&](std::size_t i) { 270 return *ToInt64(shape[i].lbound().GetExplicit()); 271 }}; 272 auto ubound{[&](std::size_t i) { 273 return *ToInt64(shape[i].ubound().GetExplicit()); 274 }}; 275 for (std::size_t i{object.subscripts.size() - 1};;) { 276 offset += object.subscripts[i] - lbound(i); 277 if (i == 0) { 278 break; 279 } 280 --i; 281 offset *= ubound(i) - lbound(i) + 1; 282 } 283 } 284 auto result{offset * GetElementSize(object.symbol).size}; 285 if (object.substringStart) { 286 int kind{context_.defaultKinds().GetDefaultKind(TypeCategory::Character)}; 287 if (const DeclTypeSpec * type{object.symbol.GetType()}) { 288 if (const IntrinsicTypeSpec * intrinsic{type->AsIntrinsic()}) { 289 kind = ToInt64(intrinsic->kind()).value_or(kind); 290 } 291 } 292 result += kind * (*object.substringStart - 1); 293 } 294 return result; 295 } 296 297 void ComputeOffsetsHelper::DoSymbol(Symbol &symbol) { 298 if (symbol.has<TypeParamDetails>() || symbol.has<SubprogramDetails>() || 299 symbol.has<UseDetails>() || symbol.has<ProcBindingDetails>()) { 300 return; // these have type but no size 301 } 302 SizeAndAlignment s{GetSizeAndAlignment(symbol)}; 303 if (s.size == 0) { 304 return; 305 } 306 offset_ = Align(offset_, s.alignment); 307 symbol.set_size(s.size); 308 symbol.set_offset(offset_); 309 offset_ += s.size; 310 alignment_ = std::max(alignment_, s.alignment); 311 } 312 313 auto ComputeOffsetsHelper::GetSizeAndAlignment(const Symbol &symbol) 314 -> SizeAndAlignment { 315 SizeAndAlignment result{GetElementSize(symbol)}; 316 std::size_t elements{CountElements(symbol)}; 317 if (elements > 1) { 318 result.size = Align(result.size, result.alignment); 319 } 320 result.size *= elements; 321 return result; 322 } 323 324 auto ComputeOffsetsHelper::GetElementSize(const Symbol &symbol) 325 -> SizeAndAlignment { 326 const DeclTypeSpec *type{symbol.GetType()}; 327 if (!type) { 328 return {}; 329 } 330 // TODO: The size of procedure pointers is not yet known 331 // and is independent of rank (and probably also the number 332 // of length type parameters). 333 if (IsDescriptor(symbol) || IsProcedurePointer(symbol)) { 334 int lenParams{0}; 335 if (const DerivedTypeSpec * derived{type->AsDerived()}) { 336 lenParams = CountLenParameters(*derived); 337 } 338 std::size_t size{ 339 runtime::Descriptor::SizeInBytes(symbol.Rank(), false, lenParams)}; 340 return {size, maxAlignment}; 341 } 342 if (IsProcedure(symbol)) { 343 return {}; 344 } 345 SizeAndAlignment result; 346 if (const IntrinsicTypeSpec * intrinsic{type->AsIntrinsic()}) { 347 if (auto kind{ToInt64(intrinsic->kind())}) { 348 result = GetIntrinsicSizeAndAlignment(intrinsic->category(), *kind); 349 } 350 if (type->category() == DeclTypeSpec::Character) { 351 ParamValue length{type->characterTypeSpec().length()}; 352 CHECK(length.isExplicit()); // else should be descriptor 353 if (MaybeIntExpr lengthExpr{length.GetExplicit()}) { 354 if (auto lengthInt{ToInt64(*lengthExpr)}) { 355 result.size *= *lengthInt; 356 } 357 } 358 } 359 } else if (const DerivedTypeSpec * derived{type->AsDerived()}) { 360 if (derived->scope()) { 361 result.size = derived->scope()->size(); 362 result.alignment = derived->scope()->alignment(); 363 } 364 } else { 365 DIE("not intrinsic or derived"); 366 } 367 return result; 368 } 369 370 std::size_t ComputeOffsetsHelper::CountElements(const Symbol &symbol) { 371 if (auto shape{GetShape(foldingContext_, symbol)}) { 372 if (auto sizeExpr{evaluate::GetSize(std::move(*shape))}) { 373 if (auto size{ToInt64(Fold(foldingContext_, std::move(*sizeExpr)))}) { 374 return *size; 375 } 376 } 377 } 378 return 1; 379 } 380 381 // Align a size to its natural alignment, up to maxAlignment. 382 std::size_t ComputeOffsetsHelper::Align(std::size_t x, std::size_t alignment) { 383 if (alignment > maxAlignment) { 384 alignment = maxAlignment; 385 } 386 return (x + alignment - 1) & -alignment; 387 } 388 389 auto ComputeOffsetsHelper::GetIntrinsicSizeAndAlignment( 390 TypeCategory category, int kind) -> SizeAndAlignment { 391 if (category == TypeCategory::Character) { 392 return {static_cast<std::size_t>(kind)}; 393 } 394 auto bytes{evaluate::ToInt64( 395 evaluate::DynamicType{category, kind}.MeasureSizeInBytes())}; 396 CHECK(bytes && *bytes > 0); 397 std::size_t size{static_cast<std::size_t>(*bytes)}; 398 if (category == TypeCategory::Complex) { 399 return {size, size >> 1}; 400 } else { 401 return {size}; 402 } 403 } 404 405 void ComputeOffsets(SemanticsContext &context) { 406 ComputeOffsetsHelper{context}.Compute(); 407 } 408 409 } // namespace Fortran::semantics 410