1// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_RELOCATION_H_
6#define RUNTIME_VM_COMPILER_RELOCATION_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include "vm/allocation.h"
13#include "vm/image_snapshot.h"
14#include "vm/intrusive_dlist.h"
15#include "vm/object.h"
16#include "vm/type_testing_stubs.h"
17#include "vm/visitor.h"
18
19namespace dart {
20
21#if defined(DART_PRECOMPILER) && !defined(TARGET_ARCH_IA32)
22
23// Represents a pc-relative call which has not been patched up with the final
24// destination.
25class UnresolvedCall : public IntrusiveDListEntry<UnresolvedCall>,
26 public IntrusiveDListEntry<UnresolvedCall, 2> {
27 public:
28 UnresolvedCall(CodePtr caller,
29 intptr_t call_offset,
30 intptr_t text_offset,
31 CodePtr callee,
32 intptr_t offset_into_target,
33 bool is_tail_call)
34 : caller(caller),
35 call_offset(call_offset),
36 text_offset(text_offset),
37 callee(callee),
38 offset_into_target(offset_into_target),
39 is_tail_call(is_tail_call) {}
40
41 UnresolvedCall(const UnresolvedCall& other)
42 : IntrusiveDListEntry<UnresolvedCall>(),
43 IntrusiveDListEntry<UnresolvedCall, 2>(),
44 caller(other.caller),
45 call_offset(other.call_offset),
46 text_offset(other.text_offset),
47 callee(other.callee),
48 offset_into_target(other.offset_into_target),
49 is_tail_call(other.is_tail_call) {}
50
51 // The caller which has an unresolved call (will be null'ed out when
52 // resolved).
53 CodePtr caller;
54 // The offset from the payload of the calling code which performs the call.
55 const intptr_t call_offset;
56 // The offset in the .text segment where the call happens.
57 const intptr_t text_offset;
58 // The target of the forward call (will be null'ed out when resolved).
59 CodePtr callee;
60 // The extra offset into the target.
61 const intptr_t offset_into_target;
62 // Whether this is a tail call.
63 const bool is_tail_call;
64};
65
66// A list of all unresolved calls.
67using AllUnresolvedCallsList = IntrusiveDList<UnresolvedCall>;
68
69// A list of all unresolved calls which call the same destination.
70using SameDestinationUnresolvedCallsList = IntrusiveDList<UnresolvedCall, 2>;
71
72// Represents a trampoline which has not been patched up with the final
73// destination.
74//
75// The [CodeRelocator] will insert trampolines into the ".text" segment which
76// increase the range of PC-relative calls. If a pc-relative call in normal
77// code is too far away from it's destination, it will call a trampoline
78// instead (which will tail-call the destination).
79class UnresolvedTrampoline : public IntrusiveDListEntry<UnresolvedTrampoline> {
80 public:
81 UnresolvedTrampoline(CodePtr callee,
82 intptr_t offset_into_target,
83 uint8_t* trampoline_bytes,
84 intptr_t text_offset)
85 : callee(callee),
86 offset_into_target(offset_into_target),
87 trampoline_bytes(trampoline_bytes),
88 text_offset(text_offset) {}
89
90 // The target of the forward call.
91 CodePtr callee;
92 // The extra offset into the target.
93 intptr_t offset_into_target;
94
95 // The trampoline buffer.
96 uint8_t* trampoline_bytes;
97 // The offset in the .text segment where the trampoline starts.
98 intptr_t text_offset;
99};
100
101using UnresolvedTrampolineList = IntrusiveDList<UnresolvedTrampoline>;
102
103template <typename ValueType, ValueType kNoValue>
104class InstructionsMapTraits {
105 public:
106 struct Pair {
107 InstructionsPtr instructions;
108 ValueType value;
109
110 Pair() : instructions(nullptr), value(kNoValue) {}
111 Pair(InstructionsPtr i, const ValueType& value)
112 : instructions(i), value(value) {}
113 };
114
115 typedef const InstructionsPtr Key;
116 typedef const ValueType Value;
117
118 static Key KeyOf(Pair kv) { return kv.instructions; }
119 static ValueType ValueOf(Pair kv) { return kv.value; }
120 static inline intptr_t Hashcode(Key key) {
121 return static_cast<intptr_t>(key);
122 }
123 static inline bool IsKeyEqual(Pair pair, Key key) {
124 return pair.instructions == key;
125 }
126};
127
128using InstructionsPosition =
129 DirectChainedHashMap<InstructionsMapTraits<intptr_t, -1>>;
130
131using TrampolinesMap = DirectChainedHashMap<
132 InstructionsMapTraits<UnresolvedTrampolineList*, nullptr>>;
133
134using InstructionsUnresolvedCalls = DirectChainedHashMap<
135 InstructionsMapTraits<SameDestinationUnresolvedCallsList*, nullptr>>;
136
137// Relocates the given code objects by patching the instructions with the
138// correct pc offsets.
139//
140// Produces a set of [ImageWriterCommand]s which tell the image writer in which
141// order (and at which offset) to emit instructions.
142class CodeRelocator : public StackResource {
143 public:
144 // Relocates instructions of the code objects provided by patching any
145 // pc-relative calls/jumps.
146 //
147 // Populates the image writer command array which must be used later to write
148 // the ".text" segment.
149 static void Relocate(Thread* thread,
150 GrowableArray<CodePtr>* code_objects,
151 GrowableArray<ImageWriterCommand>* commands,
152 bool is_vm_isolate) {
153 CodeRelocator relocator(thread, code_objects, commands);
154 relocator.Relocate(is_vm_isolate);
155 }
156
157 private:
158 CodeRelocator(Thread* thread,
159 GrowableArray<CodePtr>* code_objects,
160 GrowableArray<ImageWriterCommand>* commands);
161
162 void Relocate(bool is_vm_isolate);
163
164 void FindInstructionAndCallLimits();
165
166 bool AddInstructionsToText(CodePtr code);
167 void ScanCallTargets(const Code& code,
168 const Array& call_targets,
169 intptr_t code_text_offset);
170
171 UnresolvedTrampoline* FindTrampolineFor(UnresolvedCall* unresolved_call);
172 void AddTrampolineToText(InstructionsPtr destination,
173 uint8_t* trampoline_bytes,
174 intptr_t trampoline_length);
175
176 void EnqueueUnresolvedCall(UnresolvedCall* unresolved_call);
177 void EnqueueUnresolvedTrampoline(UnresolvedTrampoline* unresolved_trampoline);
178
179 bool TryResolveBackwardsCall(UnresolvedCall* unresolved_call);
180 void ResolveUnresolvedCallsTargeting(const InstructionsPtr instructions);
181 void ResolveCall(UnresolvedCall* unresolved_call);
182 void ResolveCallToDestination(UnresolvedCall* unresolved_call,
183 intptr_t destination_text);
184 void ResolveTrampoline(UnresolvedTrampoline* unresolved_trampoline);
185
186 void BuildTrampolinesForAlmostOutOfRangeCalls();
187
188 intptr_t FindDestinationInText(const InstructionsPtr destination,
189 intptr_t offset_into_target);
190
191 static intptr_t AdjustPayloadOffset(intptr_t payload_offset);
192
193 bool IsTargetInRangeFor(UnresolvedCall* unresolved_call,
194 intptr_t target_text_offset);
195
196 CodePtr GetTarget(const StaticCallsTableEntry& entry);
197
198 // The code relocation happens during AOT snapshot writing and operates on raw
199 // objects. No allocations can be done.
200 NoSafepointScope no_savepoint_scope_;
201 Thread* thread_;
202
203 const GrowableArray<CodePtr>* code_objects_;
204 GrowableArray<ImageWriterCommand>* commands_;
205
206 // The size of largest instructions object in bytes.
207 intptr_t max_instructions_size_ = 0;
208 // The maximum number of pc-relative calls in an instructions object.
209 intptr_t max_calls_ = 0;
210 intptr_t max_offset_into_target_ = 0;
211
212 // Data structures used for relocation.
213 intptr_t next_text_offset_ = 0;
214 InstructionsPosition text_offsets_;
215 TrampolinesMap trampolines_by_destination_;
216 InstructionsUnresolvedCalls unresolved_calls_by_destination_;
217 AllUnresolvedCallsList all_unresolved_calls_;
218
219 // Reusable handles for [ScanCallTargets].
220 Smi& kind_type_and_offset_;
221 Object& target_;
222 Code& destination_;
223};
224
225#endif // defined(DART_PRECOMPILER) && !defined(TARGET_ARCH_IA32)
226
227} // namespace dart
228
229#endif // RUNTIME_VM_COMPILER_RELOCATION_H_
230