1 //===- ConstantInitBuilder.h - Builder for LLVM IR constants ----*- 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 // This class provides a convenient interface for building complex 10 // global initializers of the sort that are frequently required for 11 // language ABIs. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_CODEGEN_CONSTANTINITBUILDER_H 16 #define LLVM_CLANG_CODEGEN_CONSTANTINITBUILDER_H 17 18 #include "llvm/ADT/ArrayRef.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/IR/Constants.h" 21 #include "llvm/IR/GlobalValue.h" 22 #include "clang/AST/CharUnits.h" 23 #include "clang/CodeGen/ConstantInitFuture.h" 24 25 #include <vector> 26 27 namespace clang { 28 namespace CodeGen { 29 30 class CodeGenModule; 31 32 /// A convenience builder class for complex constant initializers, 33 /// especially for anonymous global structures used by various language 34 /// runtimes. 35 /// 36 /// The basic usage pattern is expected to be something like: 37 /// ConstantInitBuilder builder(CGM); 38 /// auto toplevel = builder.beginStruct(); 39 /// toplevel.addInt(CGM.SizeTy, widgets.size()); 40 /// auto widgetArray = builder.beginArray(); 41 /// for (auto &widget : widgets) { 42 /// auto widgetDesc = widgetArray.beginStruct(); 43 /// widgetDesc.addInt(CGM.SizeTy, widget.getPower()); 44 /// widgetDesc.add(CGM.GetAddrOfConstantString(widget.getName())); 45 /// widgetDesc.add(CGM.GetAddrOfGlobal(widget.getInitializerDecl())); 46 /// widgetDesc.finishAndAddTo(widgetArray); 47 /// } 48 /// widgetArray.finishAndAddTo(toplevel); 49 /// auto global = toplevel.finishAndCreateGlobal("WIDGET_LIST", Align, 50 /// /*constant*/ true); 51 class ConstantInitBuilderBase { 52 struct SelfReference { 53 llvm::GlobalVariable *Dummy; 54 llvm::SmallVector<llvm::Constant*, 4> Indices; 55 56 SelfReference(llvm::GlobalVariable *dummy) : Dummy(dummy) {} 57 }; 58 CodeGenModule &CGM; 59 llvm::SmallVector<llvm::Constant*, 16> Buffer; 60 std::vector<SelfReference> SelfReferences; 61 bool Frozen = false; 62 63 friend class ConstantInitFuture; 64 friend class ConstantAggregateBuilderBase; 65 template <class, class> 66 friend class ConstantAggregateBuilderTemplateBase; 67 68 protected: 69 explicit ConstantInitBuilderBase(CodeGenModule &CGM) : CGM(CGM) {} 70 71 ~ConstantInitBuilderBase() { 72 assert(Buffer.empty() && "didn't claim all values out of buffer"); 73 assert(SelfReferences.empty() && "didn't apply all self-references"); 74 } 75 76 private: 77 llvm::GlobalVariable *createGlobal(llvm::Constant *initializer, 78 const llvm::Twine &name, 79 CharUnits alignment, 80 bool constant = false, 81 llvm::GlobalValue::LinkageTypes linkage 82 = llvm::GlobalValue::InternalLinkage, 83 unsigned addressSpace = 0); 84 85 ConstantInitFuture createFuture(llvm::Constant *initializer); 86 87 void setGlobalInitializer(llvm::GlobalVariable *GV, 88 llvm::Constant *initializer); 89 90 void resolveSelfReferences(llvm::GlobalVariable *GV); 91 92 void abandon(size_t newEnd); 93 }; 94 95 /// A concrete base class for struct and array aggregate 96 /// initializer builders. 97 class ConstantAggregateBuilderBase { 98 protected: 99 ConstantInitBuilderBase &Builder; 100 ConstantAggregateBuilderBase *Parent; 101 size_t Begin; 102 mutable size_t CachedOffsetEnd = 0; 103 bool Finished = false; 104 bool Frozen = false; 105 bool Packed = false; 106 mutable CharUnits CachedOffsetFromGlobal; 107 108 llvm::SmallVectorImpl<llvm::Constant*> &getBuffer() { 109 return Builder.Buffer; 110 } 111 112 const llvm::SmallVectorImpl<llvm::Constant*> &getBuffer() const { 113 return Builder.Buffer; 114 } 115 116 ConstantAggregateBuilderBase(ConstantInitBuilderBase &builder, 117 ConstantAggregateBuilderBase *parent) 118 : Builder(builder), Parent(parent), Begin(builder.Buffer.size()) { 119 if (parent) { 120 assert(!parent->Frozen && "parent already has child builder active"); 121 parent->Frozen = true; 122 } else { 123 assert(!builder.Frozen && "builder already has child builder active"); 124 builder.Frozen = true; 125 } 126 } 127 128 ~ConstantAggregateBuilderBase() { 129 assert(Finished && "didn't finish aggregate builder"); 130 } 131 132 void markFinished() { 133 assert(!Frozen && "child builder still active"); 134 assert(!Finished && "builder already finished"); 135 Finished = true; 136 if (Parent) { 137 assert(Parent->Frozen && 138 "parent not frozen while child builder active"); 139 Parent->Frozen = false; 140 } else { 141 assert(Builder.Frozen && 142 "builder not frozen while child builder active"); 143 Builder.Frozen = false; 144 } 145 } 146 147 public: 148 // Not copyable. 149 ConstantAggregateBuilderBase(const ConstantAggregateBuilderBase &) = delete; 150 ConstantAggregateBuilderBase &operator=(const ConstantAggregateBuilderBase &) 151 = delete; 152 153 // Movable, mostly to allow returning. But we have to write this out 154 // properly to satisfy the assert in the destructor. 155 ConstantAggregateBuilderBase(ConstantAggregateBuilderBase &&other) 156 : Builder(other.Builder), Parent(other.Parent), Begin(other.Begin), 157 CachedOffsetEnd(other.CachedOffsetEnd), 158 Finished(other.Finished), Frozen(other.Frozen), Packed(other.Packed), 159 CachedOffsetFromGlobal(other.CachedOffsetFromGlobal) { 160 other.Finished = true; 161 } 162 ConstantAggregateBuilderBase &operator=(ConstantAggregateBuilderBase &&other) 163 = delete; 164 165 /// Return the number of elements that have been added to 166 /// this struct or array. 167 size_t size() const { 168 assert(!this->Finished && "cannot query after finishing builder"); 169 assert(!this->Frozen && "cannot query while sub-builder is active"); 170 assert(this->Begin <= this->getBuffer().size()); 171 return this->getBuffer().size() - this->Begin; 172 } 173 174 /// Return true if no elements have yet been added to this struct or array. 175 bool empty() const { 176 return size() == 0; 177 } 178 179 /// Abandon this builder completely. 180 void abandon() { 181 markFinished(); 182 Builder.abandon(Begin); 183 } 184 185 /// Add a new value to this initializer. 186 void add(llvm::Constant *value) { 187 assert(value && "adding null value to constant initializer"); 188 assert(!Finished && "cannot add more values after finishing builder"); 189 assert(!Frozen && "cannot add values while subbuilder is active"); 190 Builder.Buffer.push_back(value); 191 } 192 193 /// Add an integer value of type size_t. 194 void addSize(CharUnits size); 195 196 /// Add an integer value of a specific type. 197 void addInt(llvm::IntegerType *intTy, uint64_t value, 198 bool isSigned = false) { 199 add(llvm::ConstantInt::get(intTy, value, isSigned)); 200 } 201 202 /// Add a null pointer of a specific type. 203 void addNullPointer(llvm::PointerType *ptrTy) { 204 add(llvm::ConstantPointerNull::get(ptrTy)); 205 } 206 207 /// Add a bitcast of a value to a specific type. 208 void addBitCast(llvm::Constant *value, llvm::Type *type) { 209 add(llvm::ConstantExpr::getBitCast(value, type)); 210 } 211 212 /// Add a bunch of new values to this initializer. 213 void addAll(llvm::ArrayRef<llvm::Constant *> values) { 214 assert(!Finished && "cannot add more values after finishing builder"); 215 assert(!Frozen && "cannot add values while subbuilder is active"); 216 Builder.Buffer.append(values.begin(), values.end()); 217 } 218 219 /// Add a relative offset to the given target address, i.e. the 220 /// static difference between the target address and the address 221 /// of the relative offset. The target must be known to be defined 222 /// in the current linkage unit. The offset will have the given 223 /// integer type, which must be no wider than intptr_t. Some 224 /// targets may not fully support this operation. 225 void addRelativeOffset(llvm::IntegerType *type, llvm::Constant *target) { 226 add(getRelativeOffset(type, target)); 227 } 228 229 /// Add a relative offset to the target address, plus a small 230 /// constant offset. This is primarily useful when the relative 231 /// offset is known to be a multiple of (say) four and therefore 232 /// the tag can be used to express an extra two bits of information. 233 void addTaggedRelativeOffset(llvm::IntegerType *type, 234 llvm::Constant *address, 235 unsigned tag) { 236 llvm::Constant *offset = getRelativeOffset(type, address); 237 if (tag) { 238 offset = llvm::ConstantExpr::getAdd(offset, 239 llvm::ConstantInt::get(type, tag)); 240 } 241 add(offset); 242 } 243 244 /// Return the offset from the start of the initializer to the 245 /// next position, assuming no padding is required prior to it. 246 /// 247 /// This operation will not succeed if any unsized placeholders are 248 /// currently in place in the initializer. 249 CharUnits getNextOffsetFromGlobal() const { 250 assert(!Finished && "cannot add more values after finishing builder"); 251 assert(!Frozen && "cannot add values while subbuilder is active"); 252 return getOffsetFromGlobalTo(Builder.Buffer.size()); 253 } 254 255 /// An opaque class to hold the abstract position of a placeholder. 256 class PlaceholderPosition { 257 size_t Index; 258 friend class ConstantAggregateBuilderBase; 259 PlaceholderPosition(size_t index) : Index(index) {} 260 }; 261 262 /// Add a placeholder value to the structure. The returned position 263 /// can be used to set the value later; it will not be invalidated by 264 /// any intermediate operations except (1) filling the same position or 265 /// (2) finishing the entire builder. 266 /// 267 /// This is useful for emitting certain kinds of structure which 268 /// contain some sort of summary field, generally a count, before any 269 /// of the data. By emitting a placeholder first, the structure can 270 /// be emitted eagerly. 271 PlaceholderPosition addPlaceholder() { 272 assert(!Finished && "cannot add more values after finishing builder"); 273 assert(!Frozen && "cannot add values while subbuilder is active"); 274 Builder.Buffer.push_back(nullptr); 275 return Builder.Buffer.size() - 1; 276 } 277 278 /// Add a placeholder, giving the expected type that will be filled in. 279 PlaceholderPosition addPlaceholderWithSize(llvm::Type *expectedType); 280 281 /// Fill a previously-added placeholder. 282 void fillPlaceholderWithInt(PlaceholderPosition position, 283 llvm::IntegerType *type, uint64_t value, 284 bool isSigned = false) { 285 fillPlaceholder(position, llvm::ConstantInt::get(type, value, isSigned)); 286 } 287 288 /// Fill a previously-added placeholder. 289 void fillPlaceholder(PlaceholderPosition position, llvm::Constant *value) { 290 assert(!Finished && "cannot change values after finishing builder"); 291 assert(!Frozen && "cannot add values while subbuilder is active"); 292 llvm::Constant *&slot = Builder.Buffer[position.Index]; 293 assert(slot == nullptr && "placeholder already filled"); 294 slot = value; 295 } 296 297 /// Produce an address which will eventually point to the next 298 /// position to be filled. This is computed with an indexed 299 /// getelementptr rather than by computing offsets. 300 /// 301 /// The returned pointer will have type T*, where T is the given 302 /// position. 303 llvm::Constant *getAddrOfCurrentPosition(llvm::Type *type); 304 305 llvm::ArrayRef<llvm::Constant*> getGEPIndicesToCurrentPosition( 306 llvm::SmallVectorImpl<llvm::Constant*> &indices) { 307 getGEPIndicesTo(indices, Builder.Buffer.size()); 308 return indices; 309 } 310 311 protected: 312 llvm::Constant *finishArray(llvm::Type *eltTy); 313 llvm::Constant *finishStruct(llvm::StructType *structTy); 314 315 private: 316 void getGEPIndicesTo(llvm::SmallVectorImpl<llvm::Constant*> &indices, 317 size_t position) const; 318 319 llvm::Constant *getRelativeOffset(llvm::IntegerType *offsetType, 320 llvm::Constant *target); 321 322 CharUnits getOffsetFromGlobalTo(size_t index) const; 323 }; 324 325 template <class Impl, class Traits> 326 class ConstantAggregateBuilderTemplateBase 327 : public Traits::AggregateBuilderBase { 328 using super = typename Traits::AggregateBuilderBase; 329 public: 330 using InitBuilder = typename Traits::InitBuilder; 331 using ArrayBuilder = typename Traits::ArrayBuilder; 332 using StructBuilder = typename Traits::StructBuilder; 333 using AggregateBuilderBase = typename Traits::AggregateBuilderBase; 334 335 protected: 336 ConstantAggregateBuilderTemplateBase(InitBuilder &builder, 337 AggregateBuilderBase *parent) 338 : super(builder, parent) {} 339 340 Impl &asImpl() { return *static_cast<Impl*>(this); } 341 342 public: 343 ArrayBuilder beginArray(llvm::Type *eltTy = nullptr) { 344 return ArrayBuilder(static_cast<InitBuilder&>(this->Builder), this, eltTy); 345 } 346 347 StructBuilder beginStruct(llvm::StructType *ty = nullptr) { 348 return StructBuilder(static_cast<InitBuilder&>(this->Builder), this, ty); 349 } 350 351 /// Given that this builder was created by beginning an array or struct 352 /// component on the given parent builder, finish the array/struct 353 /// component and add it to the parent. 354 /// 355 /// It is an intentional choice that the parent is passed in explicitly 356 /// despite it being redundant with information already kept in the 357 /// builder. This aids in readability by making it easier to find the 358 /// places that add components to a builder, as well as "bookending" 359 /// the sub-builder more explicitly. 360 void finishAndAddTo(AggregateBuilderBase &parent) { 361 assert(this->Parent == &parent && "adding to non-parent builder"); 362 parent.add(asImpl().finishImpl()); 363 } 364 365 /// Given that this builder was created by beginning an array or struct 366 /// directly on a ConstantInitBuilder, finish the array/struct and 367 /// create a global variable with it as the initializer. 368 template <class... As> 369 llvm::GlobalVariable *finishAndCreateGlobal(As &&...args) { 370 assert(!this->Parent && "finishing non-root builder"); 371 return this->Builder.createGlobal(asImpl().finishImpl(), 372 std::forward<As>(args)...); 373 } 374 375 /// Given that this builder was created by beginning an array or struct 376 /// directly on a ConstantInitBuilder, finish the array/struct and 377 /// set it as the initializer of the given global variable. 378 void finishAndSetAsInitializer(llvm::GlobalVariable *global) { 379 assert(!this->Parent && "finishing non-root builder"); 380 return this->Builder.setGlobalInitializer(global, asImpl().finishImpl()); 381 } 382 383 /// Given that this builder was created by beginning an array or struct 384 /// directly on a ConstantInitBuilder, finish the array/struct and 385 /// return a future which can be used to install the initializer in 386 /// a global later. 387 /// 388 /// This is useful for allowing a finished initializer to passed to 389 /// an API which will build the global. However, the "future" preserves 390 /// a dependency on the original builder; it is an error to pass it aside. 391 ConstantInitFuture finishAndCreateFuture() { 392 assert(!this->Parent && "finishing non-root builder"); 393 return this->Builder.createFuture(asImpl().finishImpl()); 394 } 395 }; 396 397 template <class Traits> 398 class ConstantArrayBuilderTemplateBase 399 : public ConstantAggregateBuilderTemplateBase<typename Traits::ArrayBuilder, 400 Traits> { 401 using super = 402 ConstantAggregateBuilderTemplateBase<typename Traits::ArrayBuilder, Traits>; 403 404 public: 405 using InitBuilder = typename Traits::InitBuilder; 406 using AggregateBuilderBase = typename Traits::AggregateBuilderBase; 407 408 private: 409 llvm::Type *EltTy; 410 411 template <class, class> 412 friend class ConstantAggregateBuilderTemplateBase; 413 414 protected: 415 ConstantArrayBuilderTemplateBase(InitBuilder &builder, 416 AggregateBuilderBase *parent, 417 llvm::Type *eltTy) 418 : super(builder, parent), EltTy(eltTy) {} 419 420 private: 421 /// Form an array constant from the values that have been added to this 422 /// builder. 423 llvm::Constant *finishImpl() { 424 return AggregateBuilderBase::finishArray(EltTy); 425 } 426 }; 427 428 /// A template class designed to allow other frontends to 429 /// easily customize the builder classes used by ConstantInitBuilder, 430 /// and thus to extend the API to work with the abstractions they 431 /// prefer. This would probably not be necessary if C++ just 432 /// supported extension methods. 433 template <class Traits> 434 class ConstantStructBuilderTemplateBase 435 : public ConstantAggregateBuilderTemplateBase<typename Traits::StructBuilder, 436 Traits> { 437 using super = 438 ConstantAggregateBuilderTemplateBase<typename Traits::StructBuilder,Traits>; 439 440 public: 441 using InitBuilder = typename Traits::InitBuilder; 442 using AggregateBuilderBase = typename Traits::AggregateBuilderBase; 443 444 private: 445 llvm::StructType *StructTy; 446 447 template <class, class> 448 friend class ConstantAggregateBuilderTemplateBase; 449 450 protected: 451 ConstantStructBuilderTemplateBase(InitBuilder &builder, 452 AggregateBuilderBase *parent, 453 llvm::StructType *structTy) 454 : super(builder, parent), StructTy(structTy) { 455 if (structTy) this->Packed = structTy->isPacked(); 456 } 457 458 public: 459 void setPacked(bool packed) { 460 this->Packed = packed; 461 } 462 463 /// Use the given type for the struct if its element count is correct. 464 /// Don't add more elements after calling this. 465 void suggestType(llvm::StructType *structTy) { 466 if (this->size() == structTy->getNumElements()) { 467 StructTy = structTy; 468 } 469 } 470 471 private: 472 /// Form an array constant from the values that have been added to this 473 /// builder. 474 llvm::Constant *finishImpl() { 475 return AggregateBuilderBase::finishStruct(StructTy); 476 } 477 }; 478 479 /// A template class designed to allow other frontends to 480 /// easily customize the builder classes used by ConstantInitBuilder, 481 /// and thus to extend the API to work with the abstractions they 482 /// prefer. This would probably not be necessary if C++ just 483 /// supported extension methods. 484 template <class Traits> 485 class ConstantInitBuilderTemplateBase : public ConstantInitBuilderBase { 486 protected: 487 ConstantInitBuilderTemplateBase(CodeGenModule &CGM) 488 : ConstantInitBuilderBase(CGM) {} 489 490 public: 491 using InitBuilder = typename Traits::InitBuilder; 492 using ArrayBuilder = typename Traits::ArrayBuilder; 493 using StructBuilder = typename Traits::StructBuilder; 494 495 ArrayBuilder beginArray(llvm::Type *eltTy = nullptr) { 496 return ArrayBuilder(static_cast<InitBuilder&>(*this), nullptr, eltTy); 497 } 498 499 StructBuilder beginStruct(llvm::StructType *structTy = nullptr) { 500 return StructBuilder(static_cast<InitBuilder&>(*this), nullptr, structTy); 501 } 502 }; 503 504 class ConstantInitBuilder; 505 class ConstantStructBuilder; 506 class ConstantArrayBuilder; 507 508 struct ConstantInitBuilderTraits { 509 using InitBuilder = ConstantInitBuilder; 510 using AggregateBuilderBase = ConstantAggregateBuilderBase; 511 using ArrayBuilder = ConstantArrayBuilder; 512 using StructBuilder = ConstantStructBuilder; 513 }; 514 515 /// The standard implementation of ConstantInitBuilder used in Clang. 516 class ConstantInitBuilder 517 : public ConstantInitBuilderTemplateBase<ConstantInitBuilderTraits> { 518 public: 519 explicit ConstantInitBuilder(CodeGenModule &CGM) : 520 ConstantInitBuilderTemplateBase(CGM) {} 521 }; 522 523 /// A helper class of ConstantInitBuilder, used for building constant 524 /// array initializers. 525 class ConstantArrayBuilder 526 : public ConstantArrayBuilderTemplateBase<ConstantInitBuilderTraits> { 527 template <class Traits> 528 friend class ConstantInitBuilderTemplateBase; 529 530 // The use of explicit qualification is a GCC workaround. 531 template <class Impl, class Traits> 532 friend class CodeGen::ConstantAggregateBuilderTemplateBase; 533 534 ConstantArrayBuilder(ConstantInitBuilder &builder, 535 ConstantAggregateBuilderBase *parent, 536 llvm::Type *eltTy) 537 : ConstantArrayBuilderTemplateBase(builder, parent, eltTy) {} 538 }; 539 540 /// A helper class of ConstantInitBuilder, used for building constant 541 /// struct initializers. 542 class ConstantStructBuilder 543 : public ConstantStructBuilderTemplateBase<ConstantInitBuilderTraits> { 544 template <class Traits> 545 friend class ConstantInitBuilderTemplateBase; 546 547 // The use of explicit qualification is a GCC workaround. 548 template <class Impl, class Traits> 549 friend class CodeGen::ConstantAggregateBuilderTemplateBase; 550 551 ConstantStructBuilder(ConstantInitBuilder &builder, 552 ConstantAggregateBuilderBase *parent, 553 llvm::StructType *structTy) 554 : ConstantStructBuilderTemplateBase(builder, parent, structTy) {} 555 }; 556 557 } // end namespace CodeGen 558 } // end namespace clang 559 560 #endif 561