1// Copyright 2015, 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_AARCH32_LABEL_AARCH32_H_
28#define VIXL_AARCH32_LABEL_AARCH32_H_
29
30extern "C" {
31#include <stdint.h>
32}
33
34#include <algorithm>
35#include <cstddef>
36#include <iomanip>
37#include <list>
38
39#include "utils-vixl.h"
40
41#include "constants-aarch32.h"
42
43namespace vixl {
44namespace aarch32 {
45
46class VeneerPoolManager;
47class MacroAssembler;
48
49class Label {
50 public:
51  typedef int32_t Offset;
52  static const Offset kMaxOffset = 0x7fffffff;
53
54  class LabelEmitOperator {
55    Label::Offset max_backward_;
56    Label::Offset max_forward_;
57
58   public:
59    LabelEmitOperator(Label::Offset max_backward, Label::Offset max_forward)
60        : max_backward_(max_backward), max_forward_(max_forward) {}
61    virtual ~LabelEmitOperator() {}
62    virtual uint32_t Encode(uint32_t /*instr*/,
63                            Label::Offset /*pc*/,
64                            const Label* /*label*/) const {
65      return 0;
66    }
67    Label::Offset GetMaxForwardDistance() const { return max_forward_; }
68    Label::Offset GetMaxBackwardDistance() const { return max_backward_; }
69  };
70
71  class ForwardReference {
72   public:
73    ForwardReference(int32_t location,
74                     const LabelEmitOperator& op,
75                     InstructionSet isa)
76        : location_(location), op_(op), isa_(isa), is_branch_(false) {
77#if defined(VIXL_INCLUDE_TARGET_A32_ONLY)
78      USE(isa_);
79      VIXL_ASSERT(isa_ == A32);
80#elif defined(VIXL_INCLUDE_TARGET_T32_ONLY)
81      USE(isa_);
82      VIXL_ASSERT(isa == T32);
83#endif
84    }
85    Offset GetMaxForwardDistance() const { return op_.GetMaxForwardDistance(); }
86    int32_t GetLocation() const { return location_; }
87    uint32_t GetStatePCOffset() const {
88      return IsUsingT32() ? kT32PcDelta : kA32PcDelta;
89    }
90
91#if defined(VIXL_INCLUDE_TARGET_A32_ONLY)
92    bool IsUsingT32() const { return false; }
93#elif defined(VIXL_INCLUDE_TARGET_T32_ONLY)
94    bool IsUsingT32() const { return true; }
95#else
96    bool IsUsingT32() const { return isa_ == T32; }
97#endif
98
99    bool IsBranch() const { return is_branch_; }
100    void SetIsBranch() { is_branch_ = true; }
101    const LabelEmitOperator& GetEmitOperator() const { return op_; }
102    Offset GetCheckpoint() const {
103      // The load instructions align down PC before adding the offset.
104      // The alignment is only needed for T32 as A32 instructions are always
105      // 4 byte aligned.
106      int32_t pc = GetLocation() + GetStatePCOffset();
107      return GetMaxForwardDistance() +
108             ((IsUsingT32() && !IsBranch()) ? AlignDown(pc, 4) : pc);
109    }
110
111   private:
112    int32_t location_;
113    const LabelEmitOperator& op_;
114    InstructionSet isa_;
115    bool is_branch_;
116  };
117
118  typedef std::list<ForwardReference> ForwardRefList;
119
120  enum UpdateCheckpointOption { kNoUpdateNecessary, kRecomputeCheckpoint };
121
122  static bool CompareCheckpoints(const ForwardReference& a,
123                                 const ForwardReference& b) {
124    return a.GetCheckpoint() < b.GetCheckpoint();
125  }
126
127  Offset GetNextCheckpoint() {
128    if (HasForwardReference()) {
129      ForwardRefList::iterator min_checkpoint =
130          std::min_element(forward_.begin(),
131                           forward_.end(),
132                           CompareCheckpoints);
133      return (*min_checkpoint).GetCheckpoint();
134    }
135    return kMaxOffset;
136  }
137
138 public:
139  Label()
140      : imm_offset_(kMaxOffset),
141        pc_offset_(0),
142        is_bound_(false),
143        minus_zero_(false),
144        isa_(kDefaultISA),
145        referenced_(false),
146        veneer_pool_manager_(NULL),
147        is_near_(false),
148        checkpoint_(kMaxOffset) {}
149  explicit Label(Offset offset, uint32_t pc_offset, bool minus_zero = false)
150      : imm_offset_(offset),
151        pc_offset_(pc_offset),
152        is_bound_(true),
153        minus_zero_(minus_zero),
154        isa_(kDefaultISA),
155        referenced_(false),
156        veneer_pool_manager_(NULL),
157        is_near_(false),
158        checkpoint_(kMaxOffset) {}
159  ~Label() VIXL_THROW_IN_NEGATIVE_TESTING_MODE(std::runtime_error) {
160#ifdef VIXL_DEBUG
161    if (referenced_ && !is_bound_) {
162      VIXL_ABORT_WITH_MSG("Label used but not bound.\n");
163    }
164#endif
165  }
166
167#undef DEFAULT_IS_T32
168
169  bool IsBound() const { return is_bound_; }
170  bool HasForwardReference() const { return !forward_.empty(); }
171  void Bind(Offset offset, InstructionSet isa) {
172    VIXL_ASSERT(!IsBound());
173    USE(isa);
174    USE(isa_);
175    imm_offset_ = offset;
176    is_bound_ = true;
177#if defined(VIXL_INCLUDE_TARGET_A32_ONLY)
178    VIXL_ASSERT(isa == A32);
179#elif defined(VIXL_INCLUDE_TARGET_T32_ONLY)
180    VIXL_ASSERT(isa == T32);
181#else
182    isa_ = isa;
183#endif
184  }
185  uint32_t GetPcOffset() const { return pc_offset_; }
186  Offset GetLocation() const {
187    VIXL_ASSERT(IsBound());
188    return imm_offset_ + static_cast<Offset>(pc_offset_);
189  }
190  bool IsUsingT32() const {
191    VIXL_ASSERT(IsBound());  // Must be bound to know its ISA.
192#if defined(VIXL_INCLUDE_TARGET_A32_ONLY)
193    return false;
194#elif defined(VIXL_INCLUDE_TARGET_T32_ONLY)
195    return true;
196#else
197    return isa_ == T32;
198#endif
199  }
200  bool IsMinusZero() const {
201    VIXL_ASSERT(IsBound());
202    return minus_zero_;
203  }
204  void SetReferenced() { referenced_ = true; }
205  bool IsReferenced() const { return referenced_; }
206  bool IsInVeneerPool() const { return veneer_pool_manager_ != NULL; }
207  VeneerPoolManager* GetVeneerPoolManager() const {
208    return veneer_pool_manager_;
209  }
210  void SetVeneerPoolManager(VeneerPoolManager* veneer_pool_manager,
211                            bool is_near) {
212    veneer_pool_manager_ = veneer_pool_manager;
213    is_near_ = is_near;
214  }
215  void ClearVeneerPoolManager() { veneer_pool_manager_ = NULL; }
216  bool IsNear() const { return is_near_; }
217  void SetCheckpoint(Offset checkpoint) { checkpoint_ = checkpoint; }
218  Offset GetCheckpoint() const { return checkpoint_; }
219  Offset GetAlignedCheckpoint(int byte_align) const {
220    return AlignDown(GetCheckpoint(), byte_align);
221  }
222  void AddForwardRef(int32_t instr_location,
223                     InstructionSet isa,
224                     const LabelEmitOperator& op) {
225    VIXL_ASSERT(referenced_);
226    forward_.push_back(ForwardReference(instr_location, op, isa));
227  }
228
229  ForwardRefList::iterator GetFirstForwardRef() { return forward_.begin(); }
230  ForwardRefList::iterator GetEndForwardRef() { return forward_.end(); }
231  const ForwardReference* GetForwardRefBack() const {
232    if (forward_.empty()) return NULL;
233    return &forward_.back();
234  }
235  // Erase an item in the list. We don't have to recompute the checkpoint as
236  // the caller does it.
237  ForwardRefList::iterator Erase(ForwardRefList::iterator ref) {
238    return forward_.erase(ref);
239  }
240  ForwardReference& GetBackForwardRef() { return forward_.back(); }
241
242  void ClearForwardRef() { forward_.clear(); }
243
244  // Only used by the literal pool.
245  // Removes the last forward reference, in particular because of a rewind.
246  // TODO(all): This is hard to test as the checkpoint could be affected only
247  //   if the literal has multiple forward references. So, the literal has to be
248  //   shared between multiple instructions and part of the literal pool which
249  //   is not yet supperted.
250  void InvalidateLastForwardReference(
251      UpdateCheckpointOption update_checkpoint = kRecomputeCheckpoint) {
252    if (!IsBound()) {
253      VIXL_ASSERT(HasForwardReference());
254      forward_.pop_back();
255    }
256    VIXL_ASSERT((update_checkpoint == kNoUpdateNecessary) &&
257                ((checkpoint_ == GetNextCheckpoint()) ||
258                 ((checkpoint_ == Label::kMaxOffset) && forward_.empty())));
259    if (update_checkpoint == kRecomputeCheckpoint) {
260      checkpoint_ = GetNextCheckpoint();
261    }
262  }
263
264  // Only used by the literal pool.
265  // Update the checkpoint as the shorter distance from the last
266  // literal in the pool's reference location to the point
267  // where the forward reference will fail.
268  // The last forward reference is assumed to be the one freshly
269  // added regarding this literal.
270  void UpdateCheckpoint() {
271    if (HasForwardReference()) {
272      const ForwardReference& ref = forward_.back();
273      checkpoint_ = std::min(checkpoint_, ref.GetCheckpoint());
274    }
275    VIXL_ASSERT(GetNextCheckpoint() == checkpoint_);
276  }
277
278  static bool CompareLabels(Label* a, Label* b) {
279    return a->GetCheckpoint() < b->GetCheckpoint();
280  }
281
282 private:
283  // Once bound, location of this label in the code buffer.
284  Offset imm_offset_;
285  uint32_t pc_offset_;
286  // Is the label bound.
287  bool is_bound_;
288  // Special flag for 'pc - 0'.
289  bool minus_zero_;
290  // Which ISA is the label in.
291  InstructionSet isa_;
292  // True if the label has been used at least once.
293  bool referenced_;
294  // Not null if the label is currently inserted in the veneer pool.
295  VeneerPoolManager* veneer_pool_manager_;
296  // True if the label is inserted in the near_labels_ list.
297  bool is_near_;
298  // Contains the references to the unbound label
299  ForwardRefList forward_;
300  // Max offset in the code buffer. Must be emitted before this checkpoint.
301  Offset checkpoint_;
302};
303
304class VeneerPoolManager {
305 public:
306  explicit VeneerPoolManager(MacroAssembler* masm)
307      : masm_(masm),
308        near_checkpoint_(Label::kMaxOffset),
309        far_checkpoint_(Label::kMaxOffset),
310        max_near_checkpoint_(0),
311        near_checkpoint_margin_(0),
312        last_label_reference_offset_(0),
313        monitor_(0) {}
314  bool IsEmpty() const {
315    return (near_labels_.size() + far_labels_.size()) == 0;
316  }
317  Label::Offset GetCheckpoint() const {
318    // For the far labels, we subtract the veneer size. This way avoids problems
319    // when two label have the same checkpoint. In the usual case, we lose some
320    // range but, as the minimum range for far labels is 1 mega byte, it's not
321    // very important.
322    size_t veneer_max_size = GetMaxSize();
323    VIXL_ASSERT(IsInt32(veneer_max_size));
324    Label::Offset tmp =
325        far_checkpoint_ - static_cast<Label::Offset>(veneer_max_size);
326    // Make room for a branch over the pools.
327    return std::min(near_checkpoint_, tmp) - kMaxInstructionSizeInBytes -
328           near_checkpoint_margin_;
329  }
330  size_t GetMaxSize() const {
331    return (near_labels_.size() + far_labels_.size()) *
332           kMaxInstructionSizeInBytes;
333  }
334  void AddLabel(Label* label);
335  void RemoveLabel(Label* label);
336  void EmitLabel(Label* label, Label::Offset emitted_target);
337  void Emit(Label::Offset target);
338
339  void Block() { monitor_++; }
340  void Release();
341  bool IsBlocked() const { return monitor_ != 0; }
342
343 private:
344  MacroAssembler* masm_;
345  // Lists of all unbound labels which are used by a branch instruction.
346  std::list<Label*> near_labels_;
347  std::list<Label*> far_labels_;
348  // Offset in the code buffer after which the veneer needs to be emitted.
349  // It's the lowest checkpoint value in the associated list.
350  // A default value of Label::kMaxOffset means that the checkpoint is
351  // invalid (no entry in the list).
352  Label::Offset near_checkpoint_;
353  Label::Offset far_checkpoint_;
354  // Highest checkpoint value for the near list.
355  Label::Offset max_near_checkpoint_;
356  // Margin we have to take to ensure that 16 bit branch instructions will be
357  // able to generate 32 bit veneers.
358  uint32_t near_checkpoint_margin_;
359  // Offset where the last reference to a label has been added to the pool.
360  Label::Offset last_label_reference_offset_;
361  // Indicates whether the emission of this pool is blocked.
362  int monitor_;
363};
364
365}  // namespace aarch32
366}  // namespace vixl
367
368#endif  // VIXL_AARCH32_LABEL_AARCH32_H_
369