1 // Copyright 2017, VIXL authors 2 // All rights reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are met: 6 // 7 // * Redistributions of source code must retain the above copyright notice, 8 // this list of conditions and the following disclaimer. 9 // * Redistributions in binary form must reproduce the above copyright notice, 10 // this list of conditions and the following disclaimer in the documentation 11 // and/or other materials provided with the distribution. 12 // * Neither the name of ARM Limited nor the names of its contributors may be 13 // used to endorse or promote products derived from this software without 14 // specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND 17 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 18 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 19 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE 20 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 22 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 23 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27 #ifndef VIXL_POOL_MANAGER_H_ 28 #define VIXL_POOL_MANAGER_H_ 29 30 #include <stdint.h> 31 32 #include <cstddef> 33 #include <limits> 34 #include <map> 35 #include <vector> 36 37 #include "globals-vixl.h" 38 #include "macro-assembler-interface.h" 39 #include "utils-vixl.h" 40 41 namespace vixl { 42 43 class TestPoolManager; 44 45 // There are four classes declared in this header file: 46 // PoolManager, PoolObject, ForwardReference and LocationBase. 47 48 // The PoolManager manages both literal and veneer pools, and is designed to be 49 // shared between AArch32 and AArch64. A pool is represented as an abstract 50 // collection of references to objects. The manager does not need to know 51 // architecture-specific details about literals and veneers; the actual 52 // emission of the pool objects is delegated. 53 // 54 // Literal and Label will derive from LocationBase. The MacroAssembler will 55 // create these objects as instructions that reference pool objects are 56 // encountered, and ask the PoolManager to track them. The PoolManager will 57 // create an internal PoolObject object for each object derived from 58 // LocationBase. Some of these PoolObject objects will be deleted when placed 59 // (e.g. the ones corresponding to Literals), whereas others will be updated 60 // with a new range when placed (e.g. Veneers) and deleted when Bind() is 61 // called on the PoolManager with their corresponding object as a parameter. 62 // 63 // A ForwardReference represents a reference to a PoolObject that will be 64 // placed later in the instruction stream. Each ForwardReference may only refer 65 // to one PoolObject, but many ForwardReferences may refer to the same 66 // object. 67 // 68 // A PoolObject represents an object that has not yet been placed. The final 69 // location of a PoolObject (and hence the LocationBase object to which it 70 // corresponds) is constrained mostly by the instructions that refer to it, but 71 // PoolObjects can also have inherent constraints, such as alignment. 72 // 73 // LocationBase objects, unlike PoolObject objects, can be used outside of the 74 // pool manager (e.g. as manually placed literals, which may still have 75 // forward references that need to be resolved). 76 // 77 // At the moment, each LocationBase will have at most one PoolObject that keeps 78 // the relevant information for placing this object in the pool. When that 79 // object is placed, all forward references of the object are resolved. For 80 // that reason, we do not need to keep track of the ForwardReference objects in 81 // the PoolObject. 82 83 // T is an integral type used for representing locations. For a 32-bit 84 // architecture it will typically be int32_t, whereas for a 64-bit 85 // architecture it will be int64_t. 86 template <typename T> 87 class ForwardReference; 88 template <typename T> 89 class PoolObject; 90 template <typename T> 91 class PoolManager; 92 93 // Represents an object that has a size and alignment, and either has a known 94 // location or has not been placed yet. An object of a subclass of LocationBase 95 // will typically keep track of a number of ForwardReferences when it has not 96 // yet been placed, but LocationBase does not assume or implement that 97 // functionality. LocationBase provides virtual methods for emitting the 98 // object, updating all the forward references, and giving the PoolManager 99 // information on the lifetime of this object and the corresponding PoolObject. 100 template <typename T> 101 class LocationBase { 102 public: 103 // The size of a LocationBase object is restricted to 4KB, in order to avoid 104 // situations where the size of the pool becomes larger than the range of 105 // an unconditional branch. This cannot happen without having large objects, 106 // as typically the range of an unconditional branch is the larger range 107 // an instruction supports. 108 // TODO: This would ideally be an architecture-specific value, perhaps 109 // another template parameter. 110 static const int kMaxObjectSize = 4 * KBytes; 111 112 // By default, LocationBase objects are aligned naturally to their size. LocationBase(uint32_t type,int size)113 LocationBase(uint32_t type, int size) 114 : pool_object_size_(size), 115 pool_object_alignment_(size), 116 pool_object_type_(type), 117 is_bound_(false), 118 location_(0) { 119 VIXL_ASSERT(size > 0); 120 VIXL_ASSERT(size <= kMaxObjectSize); 121 VIXL_ASSERT(IsPowerOf2(size)); 122 } 123 124 // Allow alignment to be specified, as long as it is smaller than the size. LocationBase(uint32_t type,int size,int alignment)125 LocationBase(uint32_t type, int size, int alignment) 126 : pool_object_size_(size), 127 pool_object_alignment_(alignment), 128 pool_object_type_(type), 129 is_bound_(false), 130 location_(0) { 131 VIXL_ASSERT(size > 0); 132 VIXL_ASSERT(size <= kMaxObjectSize); 133 VIXL_ASSERT(IsPowerOf2(alignment)); 134 VIXL_ASSERT(alignment <= size); 135 } 136 137 // Constructor for locations that are already bound. LocationBase(T location)138 explicit LocationBase(T location) 139 : pool_object_size_(-1), 140 pool_object_alignment_(-1), 141 pool_object_type_(0), 142 is_bound_(true), 143 location_(location) {} 144 ~LocationBase()145 virtual ~LocationBase() 146 VIXL_THROW_IN_NEGATIVE_TESTING_MODE(std::runtime_error) {} 147 148 // The PoolManager should assume ownership of some objects, and delete them 149 // after they have been placed. This can happen for example for literals that 150 // are created internally to the MacroAssembler and the user doesn't get a 151 // handle to. By default, the PoolManager will not do this. ShouldBeDeletedOnPlacementByPoolManager()152 virtual bool ShouldBeDeletedOnPlacementByPoolManager() const { return false; } 153 // The PoolManager should assume ownership of some objects, and delete them 154 // when it is destroyed. By default, the PoolManager will not do this. ShouldBeDeletedOnPoolManagerDestruction()155 virtual bool ShouldBeDeletedOnPoolManagerDestruction() const { return false; } 156 157 // Emit the PoolObject. Derived classes will implement this method to emit 158 // the necessary data and/or code (for example, to emit a literal or a 159 // veneer). This should not add padding, as it is added explicitly by the pool 160 // manager. 161 virtual void EmitPoolObject(MacroAssemblerInterface* masm) = 0; 162 163 // Resolve the references to this object. Will encode the necessary offset 164 // in the instruction corresponding to each reference and then delete it. 165 // TODO: An alternative here would be to provide a ResolveReference() 166 // method that only asks the LocationBase to resolve a specific reference 167 // (thus allowing the pool manager to resolve some of the references only). 168 // This would mean we need to have some kind of API to get all the references 169 // to a LabelObject. 170 virtual void ResolveReferences(internal::AssemblerBase* assembler) = 0; 171 172 // Returns true when the PoolObject corresponding to this LocationBase object 173 // needs to be removed from the pool once placed, and false if it needs to 174 // be updated instead (in which case UpdatePoolObject will be called). ShouldDeletePoolObjectOnPlacement()175 virtual bool ShouldDeletePoolObjectOnPlacement() const { return true; } 176 177 // Update the PoolObject after placing it, if necessary. This will happen for 178 // example in the case of a placed veneer, where we need to use a new updated 179 // range and a new reference (from the newly added branch instruction). 180 // By default, this does nothing, to avoid forcing objects that will not need 181 // this to have an empty implementation. UpdatePoolObject(PoolObject<T> *)182 virtual void UpdatePoolObject(PoolObject<T>*) {} 183 184 // Implement heuristics for emitting this object. If a margin is to be used 185 // as a hint during pool emission, we will try not to emit the object if we 186 // are further away from the maximum reachable location by more than the 187 // margin. UsePoolObjectEmissionMargin()188 virtual bool UsePoolObjectEmissionMargin() const { return false; } GetPoolObjectEmissionMargin()189 virtual T GetPoolObjectEmissionMargin() const { 190 VIXL_ASSERT(UsePoolObjectEmissionMargin() == false); 191 return 0; 192 } 193 GetPoolObjectSizeInBytes()194 int GetPoolObjectSizeInBytes() const { return pool_object_size_; } GetPoolObjectAlignment()195 int GetPoolObjectAlignment() const { return pool_object_alignment_; } GetPoolObjectType()196 uint32_t GetPoolObjectType() const { return pool_object_type_; } 197 IsBound()198 bool IsBound() const { return is_bound_; } GetLocation()199 T GetLocation() const { return location_; } 200 201 // This function can be called multiple times before the object is marked as 202 // bound with MarkBound() below. This is because some objects (e.g. the ones 203 // used to represent labels) can have veneers; every time we place a veneer 204 // we need to keep track of the location in order to resolve the references 205 // to the object. Reusing the location_ field for this is convenient. SetLocation(internal::AssemblerBase * assembler,T location)206 void SetLocation(internal::AssemblerBase* assembler, T location) { 207 VIXL_ASSERT(!is_bound_); 208 location_ = location; 209 ResolveReferences(assembler); 210 } 211 MarkBound()212 void MarkBound() { 213 VIXL_ASSERT(!is_bound_); 214 is_bound_ = true; 215 } 216 217 // The following two functions are used when an object is bound by a call to 218 // PoolManager<T>::Bind(). GetMaxAlignment()219 virtual int GetMaxAlignment() const { 220 VIXL_ASSERT(!ShouldDeletePoolObjectOnPlacement()); 221 return 1; 222 } GetMinLocation()223 virtual T GetMinLocation() const { 224 VIXL_ASSERT(!ShouldDeletePoolObjectOnPlacement()); 225 return 0; 226 } 227 228 private: 229 // The size of the corresponding PoolObject, in bytes. 230 int pool_object_size_; 231 // The alignment of the corresponding PoolObject; this must be a power of two. 232 int pool_object_alignment_; 233 234 // Different derived classes should have different type values. This can be 235 // used internally by the PoolManager for grouping of objects. 236 uint32_t pool_object_type_; 237 // Has the object been bound to a location yet? 238 bool is_bound_; 239 240 protected: 241 // See comment on SetLocation() for the use of this field. 242 T location_; 243 }; 244 245 template <typename T> 246 class PoolObject { 247 public: 248 // By default, PoolObjects have no inherent position constraints. PoolObject(LocationBase<T> * parent)249 explicit PoolObject(LocationBase<T>* parent) 250 : label_base_(parent), 251 min_location_(0), 252 max_location_(std::numeric_limits<T>::max()), 253 alignment_(parent->GetPoolObjectAlignment()), 254 skip_until_location_hint_(0), 255 type_(parent->GetPoolObjectType()) { 256 VIXL_ASSERT(IsPowerOf2(alignment_)); 257 UpdateLocationHint(); 258 } 259 260 // Reset the minimum and maximum location and the alignment of the object. 261 // This function is public in order to allow the LocationBase corresponding to 262 // this PoolObject to update the PoolObject when placed, e.g. in the case of 263 // veneers. The size and type of the object cannot be modified. Update(T min,T max,int alignment)264 void Update(T min, T max, int alignment) { 265 // We don't use RestrictRange here as the new range is independent of the 266 // old range (and the maximum location is typically larger). 267 min_location_ = min; 268 max_location_ = max; 269 RestrictAlignment(alignment); 270 UpdateLocationHint(); 271 } 272 273 private: RestrictRange(T min,T max)274 void RestrictRange(T min, T max) { 275 VIXL_ASSERT(min <= max_location_); 276 VIXL_ASSERT(max >= min_location_); 277 min_location_ = std::max(min_location_, min); 278 max_location_ = std::min(max_location_, max); 279 UpdateLocationHint(); 280 } 281 RestrictAlignment(int alignment)282 void RestrictAlignment(int alignment) { 283 VIXL_ASSERT(IsPowerOf2(alignment)); 284 VIXL_ASSERT(IsPowerOf2(alignment_)); 285 alignment_ = std::max(alignment_, alignment); 286 } 287 UpdateLocationHint()288 void UpdateLocationHint() { 289 if (label_base_->UsePoolObjectEmissionMargin()) { 290 skip_until_location_hint_ = 291 max_location_ - label_base_->GetPoolObjectEmissionMargin(); 292 } 293 } 294 295 // The LocationBase that this pool object represents. 296 LocationBase<T>* label_base_; 297 298 // Hard, precise location constraints for the start location of the object. 299 // They are both inclusive, that is the start location of the object can be 300 // at any location between min_location_ and max_location_, themselves 301 // included. 302 T min_location_; 303 T max_location_; 304 305 // The alignment must be a power of two. 306 int alignment_; 307 308 // Avoid generating this object until skip_until_location_hint_. This 309 // supports cases where placing the object in the pool has an inherent cost 310 // that could be avoided in some other way. Veneers are a typical example; we 311 // would prefer to branch directly (over a pool) rather than use veneers, so 312 // this value can be set using some heuristic to leave them in the pool. 313 // This value is only a hint, which will be ignored if it has to in order to 314 // meet the hard constraints we have. 315 T skip_until_location_hint_; 316 317 // Used only to group objects of similar type together. The PoolManager does 318 // not know what the types represent. 319 uint32_t type_; 320 321 friend class PoolManager<T>; 322 }; 323 324 // Class that represents a forward reference. It is the responsibility of 325 // LocationBase objects to keep track of forward references and patch them when 326 // an object is placed - this class is only used by the PoolManager in order to 327 // restrict the requirements on PoolObjects it is tracking. 328 template <typename T> 329 class ForwardReference { 330 public: 331 ForwardReference(T location, 332 int size, 333 T min_object_location, 334 T max_object_location, 335 int object_alignment = 1) location_(location)336 : location_(location), 337 size_(size), 338 object_alignment_(object_alignment), 339 min_object_location_(min_object_location), 340 max_object_location_(max_object_location) { 341 VIXL_ASSERT(AlignDown(max_object_location, object_alignment) >= 342 min_object_location); 343 } 344 LocationIsEncodable(T location)345 bool LocationIsEncodable(T location) const { 346 return location >= min_object_location_ && 347 location <= max_object_location_ && 348 IsAligned(location, object_alignment_); 349 } 350 GetLocation()351 T GetLocation() const { return location_; } GetMinLocation()352 T GetMinLocation() const { return min_object_location_; } GetMaxLocation()353 T GetMaxLocation() const { return max_object_location_; } GetAlignment()354 int GetAlignment() const { return object_alignment_; } 355 356 // Needed for InvalSet. SetLocationToInvalidateOnly(T location)357 void SetLocationToInvalidateOnly(T location) { location_ = location; } 358 359 private: 360 // The location of the thing that contains the reference. For example, this 361 // can be the location of the branch or load instruction. 362 T location_; 363 364 // The size of the instruction that makes the reference, in bytes. 365 int size_; 366 367 // The alignment that the object must satisfy for this reference - must be a 368 // power of two. 369 int object_alignment_; 370 371 // Specify the possible locations where the object could be stored. AArch32's 372 // PC offset, and T32's PC alignment calculations should be applied by the 373 // Assembler, not here. The PoolManager deals only with simple locationes. 374 // Including min_object_adddress_ is necessary to handle AArch32 some 375 // instructions which have a minimum offset of 0, but also have the implicit 376 // PC offset. 377 // Note that this structure cannot handle sparse ranges, such as A32's ADR, 378 // but doing so is costly and probably not useful in practice. The min and 379 // and max object location both refer to the beginning of the object, are 380 // inclusive and are not affected by the object size. E.g. if 381 // max_object_location_ is equal to X, we can place the object at location X 382 // regardless of its size. 383 T min_object_location_; 384 T max_object_location_; 385 386 friend class PoolManager<T>; 387 }; 388 389 390 template <typename T> 391 class PoolManager { 392 public: PoolManager(int header_size,int alignment,int buffer_alignment)393 PoolManager(int header_size, int alignment, int buffer_alignment) 394 : header_size_(header_size), 395 alignment_(alignment), 396 buffer_alignment_(buffer_alignment), 397 checkpoint_(std::numeric_limits<T>::max()), 398 max_pool_size_(0), 399 monitor_(0) {} 400 401 ~PoolManager(); 402 403 // Check if we will need to emit the pool at location 'pc', when planning to 404 // generate a certain number of bytes. This optionally takes a 405 // ForwardReference we are about to generate, in which case the size of the 406 // reference must be included in 'num_bytes'. 407 bool MustEmit(T pc, 408 int num_bytes = 0, 409 ForwardReference<T>* reference = NULL, 410 LocationBase<T>* object = NULL) const; 411 412 enum EmitOption { kBranchRequired, kNoBranchRequired }; 413 414 // Emit the pool at location 'pc', using 'masm' as the macroassembler. 415 // The branch over the header can be optionally omitted using 'option'. 416 // Returns the new PC after pool emission. 417 // This expects a number of bytes that are about to be emitted, to be taken 418 // into account in heuristics for pool object emission. 419 // This also optionally takes a forward reference and an object as 420 // parameters, to be used in the case where emission of the pool is triggered 421 // by adding a new reference to the pool that does not fit. The pool manager 422 // will need this information in order to apply its heuristics correctly. 423 T Emit(MacroAssemblerInterface* masm, 424 T pc, 425 int num_bytes = 0, 426 ForwardReference<T>* new_reference = NULL, 427 LocationBase<T>* new_object = NULL, 428 EmitOption option = kBranchRequired); 429 430 // Add 'reference' to 'object'. Should not be preceded by a call to MustEmit() 431 // that returned true, unless Emit() has been successfully afterwards. 432 void AddObjectReference(const ForwardReference<T>* reference, 433 LocationBase<T>* object); 434 435 // This is to notify the pool that a LocationBase has been bound to a location 436 // and does not need to be tracked anymore. 437 // This will happen, for example, for Labels, which are manually bound by the 438 // user. 439 // This can potentially add some padding bytes in order to meet the object 440 // requirements, and will return the new location. 441 T Bind(MacroAssemblerInterface* masm, LocationBase<T>* object, T location); 442 443 // Functions for blocking and releasing the pools. Block()444 void Block() { monitor_++; } 445 void Release(T pc); IsBlocked()446 bool IsBlocked() const { return monitor_ != 0; } 447 448 private: 449 typedef typename std::vector<PoolObject<T> >::iterator objects_iter; 450 typedef 451 typename std::vector<PoolObject<T> >::const_iterator const_objects_iter; 452 GetObjectIfTracked(LocationBase<T> * label)453 PoolObject<T>* GetObjectIfTracked(LocationBase<T>* label) { 454 return const_cast<PoolObject<T>*>( 455 static_cast<const PoolManager<T>*>(this)->GetObjectIfTracked(label)); 456 } 457 GetObjectIfTracked(LocationBase<T> * label)458 const PoolObject<T>* GetObjectIfTracked(LocationBase<T>* label) const { 459 for (const_objects_iter iter = objects_.begin(); iter != objects_.end(); 460 ++iter) { 461 const PoolObject<T>& current = *iter; 462 if (current.label_base_ == label) return ¤t; 463 } 464 return NULL; 465 } 466 467 // Helper function for calculating the checkpoint. 468 enum SortOption { kSortRequired, kNoSortRequired }; 469 void RecalculateCheckpoint(SortOption sort_option = kSortRequired); 470 471 // Comparison function for using std::sort() on objects_. PoolObject A is 472 // ordered before PoolObject B when A should be emitted before B. The 473 // comparison depends on the max_location_, size_, alignment_ and 474 // min_location_. 475 static bool PoolObjectLessThan(const PoolObject<T>& a, 476 const PoolObject<T>& b); 477 478 // Helper function used in the checkpoint calculation. 'checkpoint' is the 479 // current checkpoint, which is modified to take 'object' into account. The 480 // new checkpoint is returned. 481 static T UpdateCheckpointForObject(T checkpoint, const PoolObject<T>* object); 482 483 // Helper function to add a new object into a sorted objects_ array. 484 void Insert(const PoolObject<T>& new_object); 485 486 // Helper functions to remove an object from objects_ and delete the 487 // corresponding LocationBase object, if necessary. This will be called 488 // either after placing the object, or when Bind() is called. 489 void RemoveAndDelete(PoolObject<T>* object); 490 objects_iter RemoveAndDelete(objects_iter iter); 491 492 // Helper function to check if we should skip emitting an object. 493 bool ShouldSkipObject(PoolObject<T>* pool_object, 494 T pc, 495 int num_bytes, 496 ForwardReference<T>* new_reference, 497 LocationBase<T>* new_object, 498 PoolObject<T>* existing_object) const; 499 500 // Used only for debugging. 501 void DumpCurrentState(T pc) const; 502 503 // Methods used for testing only, via the test friend classes. PoolIsEmptyForTest()504 bool PoolIsEmptyForTest() const { return objects_.empty(); } GetCheckpointForTest()505 T GetCheckpointForTest() const { return checkpoint_; } 506 int GetPoolSizeForTest() const; 507 508 // The objects we are tracking references to. The objects_ vector is sorted 509 // at all times between calls to the public members of the PoolManager. It 510 // is sorted every time we add, delete or update a PoolObject. 511 // TODO: Consider a more efficient data structure here, to allow us to delete 512 // elements as we emit them. 513 std::vector<PoolObject<T> > objects_; 514 515 // Objects to be deleted on pool destruction. 516 std::vector<LocationBase<T>*> delete_on_destruction_; 517 518 // The header_size_ and alignment_ values are hardcoded for each instance of 519 // PoolManager. The PoolManager does not know how to emit the header, and 520 // relies on the EmitPoolHeader and EndPool methods of the 521 // MacroAssemblerInterface for that. It will also emit padding if necessary, 522 // both for the header and at the end of the pool, according to alignment_, 523 // and using the EmitNopBytes and EmitPaddingBytes method of the 524 // MacroAssemblerInterface. 525 526 // The size of the header, in bytes. 527 int header_size_; 528 // The alignment of the header - must be a power of two. 529 int alignment_; 530 // The alignment of the buffer - we cannot guarantee any object alignment 531 // larger than this alignment. When a buffer is grown, this alignment has 532 // to be guaranteed. 533 // TODO: Consider extending this to describe the guaranteed alignment as the 534 // modulo of a known number. 535 int buffer_alignment_; 536 537 // The current checkpoint. This is the latest location at which the pool 538 // *must* be emitted. This should not be visible outside the pool manager 539 // and should only be updated in RecalculateCheckpoint. 540 T checkpoint_; 541 542 // Maximum size of the pool, assuming we need the maximum possible padding 543 // for each object and for the header. It is only updated in 544 // RecalculateCheckpoint. 545 T max_pool_size_; 546 547 // Indicates whether the emission of this pool is blocked. 548 int monitor_; 549 550 friend class vixl::TestPoolManager; 551 }; 552 553 554 } // namespace vixl 555 556 #endif // VIXL_POOL_MANAGER_H_ 557