Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(143)

Side by Side Diff: src/jump-target-arm.cc

Issue 40169: Change the way we handle backward jumps in the code generator. Keep... (Closed) Base URL: http://v8.googlecode.com/svn/branches/bleeding_edge/
Patch Set: '' Created 11 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 // Copyright 2008 the V8 project authors. All rights reserved. 1 // Copyright 2008 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without 2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are 3 // modification, are permitted provided that the following conditions are
4 // met: 4 // met:
5 // 5 //
6 // * Redistributions of source code must retain the above copyright 6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer. 7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above 8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following 9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided 10 // disclaimer in the documentation and/or other materials provided
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after
63 63
64 is_linked_ = !is_bound_; 64 is_linked_ = !is_bound_;
65 } 65 }
66 66
67 67
68 void JumpTarget::Branch(Condition cc, Hint ignored) { 68 void JumpTarget::Branch(Condition cc, Hint ignored) {
69 ASSERT(cgen_ != NULL); 69 ASSERT(cgen_ != NULL);
70 ASSERT(cgen_->has_valid_frame()); 70 ASSERT(cgen_->has_valid_frame());
71 71
72 if (is_bound()) { 72 if (is_bound()) {
73 ASSERT(direction_ == BIDIRECTIONAL);
73 // Backward branch. We have an expected frame to merge to on the 74 // Backward branch. We have an expected frame to merge to on the
74 // backward edge. We negate the condition and emit the merge code 75 // backward edge.
75 // here. 76
76 // 77 // Swap the current frame for a copy (we do the swapping to get
77 // TODO(210): we should try to avoid negating the condition in the 78 // the off-frame registers off the fall through) to use for the
78 // case where there is no merge code to emit. Otherwise, we emit 79 // branch.
79 // a branch around an unconditional jump. 80 VirtualFrame* fall_through_frame = cgen_->frame();
80 ASSERT(direction_ == BIDIRECTIONAL); 81 VirtualFrame* branch_frame = new VirtualFrame(fall_through_frame);
82 RegisterFile non_frame_registers = RegisterAllocator::Reserved();
83 cgen_->SetFrame(branch_frame, &non_frame_registers);
84
85 // Check if we can avoid merge code.
86 cgen_->frame()->PrepareMergeTo(entry_frame_);
87 if (cgen_->frame()->Equals(entry_frame_)) {
88 // Branch right in to the block.
89 cgen_->DeleteFrame();
90 __ b(cc, &entry_label_);
91 cgen_->SetFrame(fall_through_frame, &non_frame_registers);
92 return;
93 }
94
95 // Check if we can reuse existing merge code.
96 for (int i = 0; i < reaching_frames_.length(); i++) {
97 if (reaching_frames_[i] != NULL &&
98 cgen_->frame()->Equals(reaching_frames_[i])) {
99 // Branch to the merge code.
100 cgen_->DeleteFrame();
101 __ b(cc, &merge_labels_[i]);
102 cgen_->SetFrame(fall_through_frame, &non_frame_registers);
103 return;
104 }
105 }
106
107 // To emit the merge code here, we negate the condition and branch
108 // around the merge code on the fall through path.
81 Label original_fall_through; 109 Label original_fall_through;
82 __ b(NegateCondition(cc), &original_fall_through); 110 __ b(NegateCondition(cc), &original_fall_through);
83 // Swap the current frame for a copy of it, saving non-frame 111 cgen_->frame()->MergeTo(entry_frame_);
84 // register reference counts and invalidating all non-frame register 112 cgen_->DeleteFrame();
85 // references except the reserved ones on the backward edge. 113 __ b(&entry_label_);
86 VirtualFrame* original_frame = cgen_->frame(); 114 cgen_->SetFrame(fall_through_frame, &non_frame_registers);
87 VirtualFrame* working_frame = new VirtualFrame(original_frame); 115 __ bind(&original_fall_through);
88 RegisterFile non_frame_registers = RegisterAllocator::Reserved();
89 cgen_->SetFrame(working_frame, &non_frame_registers);
90 116
91 working_frame->MergeTo(entry_frame_);
92 cgen_->DeleteFrame();
93 __ jmp(&entry_label_);
94
95 // Restore the frame and its associated non-frame registers.
96 cgen_->SetFrame(original_frame, &non_frame_registers);
97 __ bind(&original_fall_through);
98 } else { 117 } else {
99 // Forward branch. A copy of the current frame is added to the end 118 // Forward branch. A copy of the current frame is added to the end
100 // of the list of frames reaching the target block and a branch to 119 // of the list of frames reaching the target block and a branch to
101 // the merge code is emitted. 120 // the merge code is emitted.
102 AddReachingFrame(new VirtualFrame(cgen_->frame())); 121 AddReachingFrame(new VirtualFrame(cgen_->frame()));
103 __ b(cc, &merge_labels_.last()); 122 __ b(cc, &merge_labels_.last());
123 is_linked_ = true;
104 } 124 }
105
106 is_linked_ = !is_bound_;
107 } 125 }
108 126
109 127
110 void JumpTarget::Call() { 128 void JumpTarget::Call() {
111 // Call is used to push the address of the catch block on the stack as 129 // Call is used to push the address of the catch block on the stack as
112 // a return address when compiling try/catch and try/finally. We 130 // a return address when compiling try/catch and try/finally. We
113 // fully spill the frame before making the call. The expected frame 131 // fully spill the frame before making the call. The expected frame
114 // at the label (which should be the only one) is the spilled current 132 // at the label (which should be the only one) is the spilled current
115 // frame plus an in-memory return address. The "fall-through" frame 133 // frame plus an in-memory return address. The "fall-through" frame
116 // at the return site is the spilled current frame. 134 // at the return site is the spilled current frame.
(...skipping 14 matching lines...) Expand all
131 149
132 150
133 void JumpTarget::Bind(int mergable_elements) { 151 void JumpTarget::Bind(int mergable_elements) {
134 ASSERT(cgen_ != NULL); 152 ASSERT(cgen_ != NULL);
135 ASSERT(!is_bound()); 153 ASSERT(!is_bound());
136 154
137 // Live non-frame registers are not allowed at the start of a basic 155 // Live non-frame registers are not allowed at the start of a basic
138 // block. 156 // block.
139 ASSERT(!cgen_->has_valid_frame() || cgen_->HasValidEntryRegisters()); 157 ASSERT(!cgen_->has_valid_frame() || cgen_->HasValidEntryRegisters());
140 158
159 if (direction_ == FORWARD_ONLY) {
160 // A simple case: no forward jumps and no possible backward jumps.
161 if (!is_linked()) {
162 // The stack pointer can be floating above the top of the
163 // virtual frame before the bind. Afterward, it should not.
164 ASSERT(cgen_->has_valid_frame());
165 VirtualFrame* frame = cgen_->frame();
166 int difference =
167 frame->stack_pointer_ - (frame->elements_.length() - 1);
168 if (difference > 0) {
169 frame->stack_pointer_ -= difference;
170 __ add(sp, sp, Operand(difference * kPointerSize));
171 }
172
173 is_bound_ = true;
174 return;
175 }
176
177 // Another simple case: no fall through, a single forward jump,
178 // and no possible backward jumps.
179 if (!cgen_->has_valid_frame() && reaching_frames_.length() == 1) {
180 // Pick up the only reaching frame, take ownership of it, and
181 // use it for the block about to be emitted.
182 VirtualFrame* frame = reaching_frames_[0];
183 RegisterFile reserved = RegisterAllocator::Reserved();
184 cgen_->SetFrame(frame, &reserved);
185 reaching_frames_[0] = NULL;
186 __ bind(&merge_labels_[0]);
187
188 // The stack pointer can be floating above the top of the
189 // virtual frame before the bind. Afterward, it should not.
190 int difference =
191 frame->stack_pointer_ - (frame->elements_.length() - 1);
192 if (difference > 0) {
193 frame->stack_pointer_ -= difference;
194 __ add(sp, sp, Operand(difference * kPointerSize));
195 }
196
197 is_linked_ = false;
198 is_bound_ = true;
199 return;
200 }
201 }
202
203 // If there is a current frame, record it as the fall-through. It
204 // is owned by the reaching frames for now.
205 bool had_fall_through = false;
206 if (cgen_->has_valid_frame()) {
207 had_fall_through = true;
208 AddReachingFrame(cgen_->frame());
209 RegisterFile empty;
210 cgen_->SetFrame(NULL, &empty);
211 }
212
141 // Compute the frame to use for entry to the block. 213 // Compute the frame to use for entry to the block.
142 ComputeEntryFrame(mergable_elements); 214 ComputeEntryFrame(mergable_elements);
143 215
216 // Some moves required to merge to an expected frame require purely
217 // frame state changes, and do not require any code generation.
218 // Perform those first to increase the possibility of finding equal
219 // frames below.
220 for (int i = 0; i < reaching_frames_.length(); i++) {
221 if (reaching_frames_[i] != NULL) {
222 reaching_frames_[i]->PrepareMergeTo(entry_frame_);
223 }
224 }
225
144 if (is_linked()) { 226 if (is_linked()) {
145 // There were forward jumps. Handle merging the reaching frames 227 // There were forward jumps. Handle merging the reaching frames
146 // and possible fall through to the entry frame. 228 // and possible fall through to the entry frame.
147 229
148 // Some moves required to merge to an expected frame require 230 // Loop over the (non-null) reaching frames and process any that
149 // purely frame state changes, and do not require any code 231 // need merge code. Iterate backwards through the list to handle
150 // generation. Perform those first to increase the possibility of 232 // the fall-through frame first. Set frames that will be
151 // finding equal frames below. 233 // processed after 'i' to NULL if we want to avoid processing
152 if (cgen_->has_valid_frame()) { 234 // them.
153 cgen_->frame()->PrepareMergeTo(entry_frame_); 235 for (int i = reaching_frames_.length() - 1; i >= 0; i--) {
154 } 236 VirtualFrame* frame = reaching_frames_[i];
155 for (int i = 0; i < reaching_frames_.length(); i++) {
156 reaching_frames_[i]->PrepareMergeTo(entry_frame_);
157 }
158 237
159 // If there is a fall through to the jump target and it needs 238 if (frame != NULL) {
160 // merge code, process it first. 239 // Does the frame (probably) need merge code?
161 if (cgen_->has_valid_frame() && !cgen_->frame()->Equals(entry_frame_)) { 240 if (!frame->Equals(entry_frame_)) {
162 // Loop over all the reaching frames, looking for any that can 241 // We could have a valid frame as the fall through to the
163 // share merge code with this one. 242 // binding site or as the fall through from a previous merge
164 for (int i = 0; i < reaching_frames_.length(); i++) { 243 // code block. Jump around the code we are about to
165 if (cgen_->frame()->Equals(reaching_frames_[i])) { 244 // generate.
166 // Set the reaching frames element to null to avoid 245 if (cgen_->has_valid_frame()) {
167 // processing it later, and then bind its entry label. 246 cgen_->DeleteFrame();
168 delete reaching_frames_[i]; 247 __ b(&entry_label_);
248 }
249 // Pick up the frame for this block. Assume ownership if
250 // there cannot be backward jumps.
251 RegisterFile reserved = RegisterAllocator::Reserved();
252 if (direction_ == BIDIRECTIONAL) {
253 cgen_->SetFrame(new VirtualFrame(frame), &reserved);
254 } else {
255 cgen_->SetFrame(frame, &reserved);
256 reaching_frames_[i] = NULL;
257 }
258 __ bind(&merge_labels_[i]);
259
260 // Loop over the remaining (non-null) reaching frames,
261 // looking for any that can share merge code with this one.
262 for (int j = 0; j < i; j++) {
263 VirtualFrame* other = reaching_frames_[j];
264 if (other != NULL && other->Equals(cgen_->frame())) {
265 // Set the reaching frame element to null to avoid
266 // processing it later, and then bind its entry label.
267 delete other;
268 reaching_frames_[j] = NULL;
269 __ bind(&merge_labels_[j]);
270 }
271 }
272
273 // Emit the merge code.
274 cgen_->frame()->MergeTo(entry_frame_);
275 } else if (i == reaching_frames_.length() - 1 && had_fall_through) {
276 // If this is the fall through, and it didn't need merge
277 // code, we need to pick up the frame so we can jump around
278 // subsequent merge blocks if necessary.
279 RegisterFile reserved = RegisterAllocator::Reserved();
280 cgen_->SetFrame(frame, &reserved);
169 reaching_frames_[i] = NULL; 281 reaching_frames_[i] = NULL;
170 __ bind(&merge_labels_[i]);
171 } 282 }
172 } 283 }
173
174 // Emit the merge code.
175 cgen_->frame()->MergeTo(entry_frame_);
176 }
177
178 // Loop over the (non-null) reaching frames and process any that
179 // need merge code.
180 for (int i = 0; i < reaching_frames_.length(); i++) {
181 VirtualFrame* frame = reaching_frames_[i];
182 if (frame != NULL && !frame->Equals(entry_frame_)) {
183 // Set the reaching frames element to null to avoid processing
184 // it later. Do not delete it as it is needed for merging.
185 reaching_frames_[i] = NULL;
186
187 // If the code generator has a current frame (a fall-through
188 // or a previously merged frame), insert a jump around the
189 // merge code we are about to generate.
190 if (cgen_->has_valid_frame()) {
191 cgen_->DeleteFrame();
192 __ jmp(&entry_label_);
193 }
194
195 // Set the frame to merge as the code generator's current
196 // frame and bind its merge label.
197 RegisterFile reserved_registers = RegisterAllocator::Reserved();
198 cgen_->SetFrame(frame, &reserved_registers);
199 __ bind(&merge_labels_[i]);
200
201 // Loop over the remaining (non-null) reaching frames, looking
202 // for any that can share merge code with this one.
203 for (int j = i + 1; j < reaching_frames_.length(); j++) {
204 VirtualFrame* other = reaching_frames_[j];
205 if (other != NULL && frame->Equals(other)) {
206 delete other;
207 reaching_frames_[j] = NULL;
208 __ bind(&merge_labels_[j]);
209 }
210 }
211
212 // Emit the merge code.
213 cgen_->frame()->MergeTo(entry_frame_);
214 }
215 } 284 }
216 285
217 // The code generator may not have a current frame if there was no 286 // The code generator may not have a current frame if there was no
218 // fall through and none of the reaching frames needed merging. 287 // fall through and none of the reaching frames needed merging.
219 // In that case, clone the entry frame as the current frame. 288 // In that case, clone the entry frame as the current frame.
220 if (!cgen_->has_valid_frame()) { 289 if (!cgen_->has_valid_frame()) {
221 RegisterFile reserved_registers = RegisterAllocator::Reserved(); 290 RegisterFile reserved_registers = RegisterAllocator::Reserved();
222 cgen_->SetFrame(new VirtualFrame(entry_frame_), &reserved_registers); 291 cgen_->SetFrame(new VirtualFrame(entry_frame_), &reserved_registers);
223 } 292 }
224 293
225 // There is certainly a current frame equal to the entry frame. 294 // There is certainly a current frame equal to the entry frame.
226 // Bind the entry frame label. 295 // Bind the entry frame label.
227 __ bind(&entry_label_); 296 __ bind(&entry_label_);
228 297
229 // There may be unprocessed reaching frames that did not need 298 // There may be unprocessed reaching frames that did not need
230 // merge code. Bind their merge labels to be the same as the 299 // merge code. They will have unbound merge labels. Bind their
231 // entry label. 300 // merge labels to be the same as the entry label and deallocate
301 // them.
232 for (int i = 0; i < reaching_frames_.length(); i++) { 302 for (int i = 0; i < reaching_frames_.length(); i++) {
233 if (reaching_frames_[i] != NULL) { 303 if (!merge_labels_[i].is_bound()) {
234 delete reaching_frames_[i]; 304 delete reaching_frames_[i];
305 reaching_frames_[i] = NULL;
235 __ bind(&merge_labels_[i]); 306 __ bind(&merge_labels_[i]);
236 } 307 }
237 } 308 }
238 309
239 // All the reaching frames except the one that is the current 310 // There are non-NULL reaching frames with bound labels for each
240 // frame (if it is one of the reaching frames) have been deleted. 311 // merge block, but only on backward targets.
241 reaching_frames_.Clear(); 312 } else {
242 merge_labels_.Clear(); 313 // There were no forward jumps. There must be a current frame and
314 // this must be a bidirectional target.
315 ASSERT(reaching_frames_.length() == 1);
316 ASSERT(reaching_frames_[0] != NULL);
317 ASSERT(direction_ == BIDIRECTIONAL);
243 318
244 } else { 319 // Use a copy of the reaching frame so the original can be saved
245 // There were no forward jumps. The current frame is merged to 320 // for possible reuse as a backward merge block.
246 // the entry frame. 321 RegisterFile reserved = RegisterAllocator::Reserved();
322 cgen_->SetFrame(new VirtualFrame(reaching_frames_[0]), &reserved);
323 __ bind(&merge_labels_[0]);
247 cgen_->frame()->MergeTo(entry_frame_); 324 cgen_->frame()->MergeTo(entry_frame_);
248 __ bind(&entry_label_); 325 __ bind(&entry_label_);
249 } 326 }
250 327
251 is_linked_ = false; 328 is_linked_ = false;
252 is_bound_ = true; 329 is_bound_ = true;
253 } 330 }
254 331
255 #undef __ 332 #undef __
256 333
257 334
258 } } // namespace v8::internal 335 } } // namespace v8::internal
OLDNEW
« src/jump-target.cc ('K') | « src/jump-target.cc ('k') | src/jump-target-ia32.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698