1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #if V8_TARGET_ARCH_IA32 6 7 #include "src/regexp/ia32/regexp-macro-assembler-ia32.h" 8 9 #include "src/log.h" 10 #include "src/macro-assembler.h" 11 #include "src/profiler/cpu-profiler.h" 12 #include "src/regexp/regexp-macro-assembler.h" 13 #include "src/regexp/regexp-stack.h" 14 #include "src/unicode.h" 15 16 namespace v8 { 17 namespace internal { 18 19 #ifndef V8_INTERPRETED_REGEXP 20 /* 21 * This assembler uses the following register assignment convention 22 * - edx : Current character. Must be loaded using LoadCurrentCharacter 23 * before using any of the dispatch methods. Temporarily stores the 24 * index of capture start after a matching pass for a global regexp. 25 * - edi : Current position in input, as negative offset from end of string. 26 * Please notice that this is the byte offset, not the character offset! 27 * - esi : end of input (points to byte after last character in input). 28 * - ebp : Frame pointer. Used to access arguments, local variables and 29 * RegExp registers. 30 * - esp : Points to tip of C stack. 31 * - ecx : Points to tip of backtrack stack 32 * 33 * The registers eax and ebx are free to use for computations. 34 * 35 * Each call to a public method should retain this convention. 36 * The stack will have the following structure: 37 * - Isolate* isolate (address of the current isolate) 38 * - direct_call (if 1, direct call from JavaScript code, if 0 39 * call through the runtime system) 40 * - stack_area_base (high end of the memory area to use as 41 * backtracking stack) 42 * - capture array size (may fit multiple sets of matches) 43 * - int* capture_array (int[num_saved_registers_], for output). 44 * - end of input (address of end of string) 45 * - start of input (address of first character in string) 46 * - start index (character index of start) 47 * - String* input_string (location of a handle containing the string) 48 * --- frame alignment (if applicable) --- 49 * - return address 50 * ebp-> - old ebp 51 * - backup of caller esi 52 * - backup of caller edi 53 * - backup of caller ebx 54 * - success counter (only for global regexps to count matches). 55 * - Offset of location before start of input (effectively character 56 * string start - 1). Used to initialize capture registers to a 57 * non-position. 58 * - register 0 ebp[-4] (only positions must be stored in the first 59 * - register 1 ebp[-8] num_saved_registers_ registers) 60 * - ... 61 * 62 * The first num_saved_registers_ registers are initialized to point to 63 * "character -1" in the string (i.e., char_size() bytes before the first 64 * character of the string). The remaining registers starts out as garbage. 65 * 66 * The data up to the return address must be placed there by the calling 67 * code, by calling the code entry as cast to a function with the signature: 68 * int (*match)(String* input_string, 69 * int start_index, 70 * Address start, 71 * Address end, 72 * int* capture_output_array, 73 * bool at_start, 74 * byte* stack_area_base, 75 * bool direct_call) 76 */ 77 78 #define __ ACCESS_MASM(masm_) 79 80 RegExpMacroAssemblerIA32::RegExpMacroAssemblerIA32(Isolate* isolate, Zone* zone, 81 Mode mode, 82 int registers_to_save) 83 : NativeRegExpMacroAssembler(isolate, zone), 84 masm_(new MacroAssembler(isolate, NULL, kRegExpCodeSize, 85 CodeObjectRequired::kYes)), 86 mode_(mode), 87 num_registers_(registers_to_save), 88 num_saved_registers_(registers_to_save), 89 entry_label_(), 90 start_label_(), 91 success_label_(), 92 backtrack_label_(), 93 exit_label_() { 94 DCHECK_EQ(0, registers_to_save % 2); 95 __ jmp(&entry_label_); // We'll write the entry code later. 96 __ bind(&start_label_); // And then continue from here. 97 } 98 99 100 RegExpMacroAssemblerIA32::~RegExpMacroAssemblerIA32() { 101 delete masm_; 102 // Unuse labels in case we throw away the assembler without calling GetCode. 103 entry_label_.Unuse(); 104 start_label_.Unuse(); 105 success_label_.Unuse(); 106 backtrack_label_.Unuse(); 107 exit_label_.Unuse(); 108 check_preempt_label_.Unuse(); 109 stack_overflow_label_.Unuse(); 110 } 111 112 113 int RegExpMacroAssemblerIA32::stack_limit_slack() { 114 return RegExpStack::kStackLimitSlack; 115 } 116 117 118 void RegExpMacroAssemblerIA32::AdvanceCurrentPosition(int by) { 119 if (by != 0) { 120 __ add(edi, Immediate(by * char_size())); 121 } 122 } 123 124 125 void RegExpMacroAssemblerIA32::AdvanceRegister(int reg, int by) { 126 DCHECK(reg >= 0); 127 DCHECK(reg < num_registers_); 128 if (by != 0) { 129 __ add(register_location(reg), Immediate(by)); 130 } 131 } 132 133 134 void RegExpMacroAssemblerIA32::Backtrack() { 135 CheckPreemption(); 136 // Pop Code* offset from backtrack stack, add Code* and jump to location. 137 Pop(ebx); 138 __ add(ebx, Immediate(masm_->CodeObject())); 139 __ jmp(ebx); 140 } 141 142 143 void RegExpMacroAssemblerIA32::Bind(Label* label) { 144 __ bind(label); 145 } 146 147 148 void RegExpMacroAssemblerIA32::CheckCharacter(uint32_t c, Label* on_equal) { 149 __ cmp(current_character(), c); 150 BranchOrBacktrack(equal, on_equal); 151 } 152 153 154 void RegExpMacroAssemblerIA32::CheckCharacterGT(uc16 limit, Label* on_greater) { 155 __ cmp(current_character(), limit); 156 BranchOrBacktrack(greater, on_greater); 157 } 158 159 160 void RegExpMacroAssemblerIA32::CheckAtStart(Label* on_at_start) { 161 __ lea(eax, Operand(edi, -char_size())); 162 __ cmp(eax, Operand(ebp, kStringStartMinusOne)); 163 BranchOrBacktrack(equal, on_at_start); 164 } 165 166 167 void RegExpMacroAssemblerIA32::CheckNotAtStart(int cp_offset, 168 Label* on_not_at_start) { 169 __ lea(eax, Operand(edi, -char_size() + cp_offset * char_size())); 170 __ cmp(eax, Operand(ebp, kStringStartMinusOne)); 171 BranchOrBacktrack(not_equal, on_not_at_start); 172 } 173 174 175 void RegExpMacroAssemblerIA32::CheckCharacterLT(uc16 limit, Label* on_less) { 176 __ cmp(current_character(), limit); 177 BranchOrBacktrack(less, on_less); 178 } 179 180 181 void RegExpMacroAssemblerIA32::CheckGreedyLoop(Label* on_equal) { 182 Label fallthrough; 183 __ cmp(edi, Operand(backtrack_stackpointer(), 0)); 184 __ j(not_equal, &fallthrough); 185 __ add(backtrack_stackpointer(), Immediate(kPointerSize)); // Pop. 186 BranchOrBacktrack(no_condition, on_equal); 187 __ bind(&fallthrough); 188 } 189 190 191 void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase( 192 int start_reg, bool read_backward, Label* on_no_match) { 193 Label fallthrough; 194 __ mov(edx, register_location(start_reg)); // Index of start of capture 195 __ mov(ebx, register_location(start_reg + 1)); // Index of end of capture 196 __ sub(ebx, edx); // Length of capture. 197 198 // At this point, the capture registers are either both set or both cleared. 199 // If the capture length is zero, then the capture is either empty or cleared. 200 // Fall through in both cases. 201 __ j(equal, &fallthrough); 202 203 // Check that there are sufficient characters left in the input. 204 if (read_backward) { 205 __ mov(eax, Operand(ebp, kStringStartMinusOne)); 206 __ add(eax, ebx); 207 __ cmp(edi, eax); 208 BranchOrBacktrack(less_equal, on_no_match); 209 } else { 210 __ mov(eax, edi); 211 __ add(eax, ebx); 212 BranchOrBacktrack(greater, on_no_match); 213 } 214 215 if (mode_ == LATIN1) { 216 Label success; 217 Label fail; 218 Label loop_increment; 219 // Save register contents to make the registers available below. 220 __ push(edi); 221 __ push(backtrack_stackpointer()); 222 // After this, the eax, ecx, and edi registers are available. 223 224 __ add(edx, esi); // Start of capture 225 __ add(edi, esi); // Start of text to match against capture. 226 if (read_backward) { 227 __ sub(edi, ebx); // Offset by length when matching backwards. 228 } 229 __ add(ebx, edi); // End of text to match against capture. 230 231 Label loop; 232 __ bind(&loop); 233 __ movzx_b(eax, Operand(edi, 0)); 234 __ cmpb_al(Operand(edx, 0)); 235 __ j(equal, &loop_increment); 236 237 // Mismatch, try case-insensitive match (converting letters to lower-case). 238 __ or_(eax, 0x20); // Convert match character to lower-case. 239 __ lea(ecx, Operand(eax, -'a')); 240 __ cmp(ecx, static_cast<int32_t>('z' - 'a')); // Is eax a lowercase letter? 241 Label convert_capture; 242 __ j(below_equal, &convert_capture); // In range 'a'-'z'. 243 // Latin-1: Check for values in range [224,254] but not 247. 244 __ sub(ecx, Immediate(224 - 'a')); 245 __ cmp(ecx, Immediate(254 - 224)); 246 __ j(above, &fail); // Weren't Latin-1 letters. 247 __ cmp(ecx, Immediate(247 - 224)); // Check for 247. 248 __ j(equal, &fail); 249 __ bind(&convert_capture); 250 // Also convert capture character. 251 __ movzx_b(ecx, Operand(edx, 0)); 252 __ or_(ecx, 0x20); 253 254 __ cmp(eax, ecx); 255 __ j(not_equal, &fail); 256 257 __ bind(&loop_increment); 258 // Increment pointers into match and capture strings. 259 __ add(edx, Immediate(1)); 260 __ add(edi, Immediate(1)); 261 // Compare to end of match, and loop if not done. 262 __ cmp(edi, ebx); 263 __ j(below, &loop); 264 __ jmp(&success); 265 266 __ bind(&fail); 267 // Restore original values before failing. 268 __ pop(backtrack_stackpointer()); 269 __ pop(edi); 270 BranchOrBacktrack(no_condition, on_no_match); 271 272 __ bind(&success); 273 // Restore original value before continuing. 274 __ pop(backtrack_stackpointer()); 275 // Drop original value of character position. 276 __ add(esp, Immediate(kPointerSize)); 277 // Compute new value of character position after the matched part. 278 __ sub(edi, esi); 279 if (read_backward) { 280 // Subtract match length if we matched backward. 281 __ add(edi, register_location(start_reg)); 282 __ sub(edi, register_location(start_reg + 1)); 283 } 284 } else { 285 DCHECK(mode_ == UC16); 286 // Save registers before calling C function. 287 __ push(esi); 288 __ push(edi); 289 __ push(backtrack_stackpointer()); 290 __ push(ebx); 291 292 static const int argument_count = 4; 293 __ PrepareCallCFunction(argument_count, ecx); 294 // Put arguments into allocated stack area, last argument highest on stack. 295 // Parameters are 296 // Address byte_offset1 - Address captured substring's start. 297 // Address byte_offset2 - Address of current character position. 298 // size_t byte_length - length of capture in bytes(!) 299 // Isolate* isolate 300 301 // Set isolate. 302 __ mov(Operand(esp, 3 * kPointerSize), 303 Immediate(ExternalReference::isolate_address(isolate()))); 304 // Set byte_length. 305 __ mov(Operand(esp, 2 * kPointerSize), ebx); 306 // Set byte_offset2. 307 // Found by adding negative string-end offset of current position (edi) 308 // to end of string. 309 __ add(edi, esi); 310 if (read_backward) { 311 __ sub(edi, ebx); // Offset by length when matching backwards. 312 } 313 __ mov(Operand(esp, 1 * kPointerSize), edi); 314 // Set byte_offset1. 315 // Start of capture, where edx already holds string-end negative offset. 316 __ add(edx, esi); 317 __ mov(Operand(esp, 0 * kPointerSize), edx); 318 319 { 320 AllowExternalCallThatCantCauseGC scope(masm_); 321 ExternalReference compare = 322 ExternalReference::re_case_insensitive_compare_uc16(isolate()); 323 __ CallCFunction(compare, argument_count); 324 } 325 // Pop original values before reacting on result value. 326 __ pop(ebx); 327 __ pop(backtrack_stackpointer()); 328 __ pop(edi); 329 __ pop(esi); 330 331 // Check if function returned non-zero for success or zero for failure. 332 __ or_(eax, eax); 333 BranchOrBacktrack(zero, on_no_match); 334 // On success, advance position by length of capture. 335 if (read_backward) { 336 __ sub(edi, ebx); 337 } else { 338 __ add(edi, ebx); 339 } 340 } 341 __ bind(&fallthrough); 342 } 343 344 345 void RegExpMacroAssemblerIA32::CheckNotBackReference(int start_reg, 346 bool read_backward, 347 Label* on_no_match) { 348 Label fallthrough; 349 Label success; 350 Label fail; 351 352 // Find length of back-referenced capture. 353 __ mov(edx, register_location(start_reg)); 354 __ mov(eax, register_location(start_reg + 1)); 355 __ sub(eax, edx); // Length to check. 356 357 // At this point, the capture registers are either both set or both cleared. 358 // If the capture length is zero, then the capture is either empty or cleared. 359 // Fall through in both cases. 360 __ j(equal, &fallthrough); 361 362 // Check that there are sufficient characters left in the input. 363 if (read_backward) { 364 __ mov(ebx, Operand(ebp, kStringStartMinusOne)); 365 __ add(ebx, eax); 366 __ cmp(edi, ebx); 367 BranchOrBacktrack(less_equal, on_no_match); 368 } else { 369 __ mov(ebx, edi); 370 __ add(ebx, eax); 371 BranchOrBacktrack(greater, on_no_match); 372 } 373 374 // Save register to make it available below. 375 __ push(backtrack_stackpointer()); 376 377 // Compute pointers to match string and capture string 378 __ add(edx, esi); // Start of capture. 379 __ lea(ebx, Operand(esi, edi, times_1, 0)); // Start of match. 380 if (read_backward) { 381 __ sub(ebx, eax); // Offset by length when matching backwards. 382 } 383 __ lea(ecx, Operand(eax, ebx, times_1, 0)); // End of match 384 385 Label loop; 386 __ bind(&loop); 387 if (mode_ == LATIN1) { 388 __ movzx_b(eax, Operand(edx, 0)); 389 __ cmpb_al(Operand(ebx, 0)); 390 } else { 391 DCHECK(mode_ == UC16); 392 __ movzx_w(eax, Operand(edx, 0)); 393 __ cmpw_ax(Operand(ebx, 0)); 394 } 395 __ j(not_equal, &fail); 396 // Increment pointers into capture and match string. 397 __ add(edx, Immediate(char_size())); 398 __ add(ebx, Immediate(char_size())); 399 // Check if we have reached end of match area. 400 __ cmp(ebx, ecx); 401 __ j(below, &loop); 402 __ jmp(&success); 403 404 __ bind(&fail); 405 // Restore backtrack stackpointer. 406 __ pop(backtrack_stackpointer()); 407 BranchOrBacktrack(no_condition, on_no_match); 408 409 __ bind(&success); 410 // Move current character position to position after match. 411 __ mov(edi, ecx); 412 __ sub(edi, esi); 413 if (read_backward) { 414 // Subtract match length if we matched backward. 415 __ add(edi, register_location(start_reg)); 416 __ sub(edi, register_location(start_reg + 1)); 417 } 418 // Restore backtrack stackpointer. 419 __ pop(backtrack_stackpointer()); 420 421 __ bind(&fallthrough); 422 } 423 424 425 void RegExpMacroAssemblerIA32::CheckNotCharacter(uint32_t c, 426 Label* on_not_equal) { 427 __ cmp(current_character(), c); 428 BranchOrBacktrack(not_equal, on_not_equal); 429 } 430 431 432 void RegExpMacroAssemblerIA32::CheckCharacterAfterAnd(uint32_t c, 433 uint32_t mask, 434 Label* on_equal) { 435 if (c == 0) { 436 __ test(current_character(), Immediate(mask)); 437 } else { 438 __ mov(eax, mask); 439 __ and_(eax, current_character()); 440 __ cmp(eax, c); 441 } 442 BranchOrBacktrack(equal, on_equal); 443 } 444 445 446 void RegExpMacroAssemblerIA32::CheckNotCharacterAfterAnd(uint32_t c, 447 uint32_t mask, 448 Label* on_not_equal) { 449 if (c == 0) { 450 __ test(current_character(), Immediate(mask)); 451 } else { 452 __ mov(eax, mask); 453 __ and_(eax, current_character()); 454 __ cmp(eax, c); 455 } 456 BranchOrBacktrack(not_equal, on_not_equal); 457 } 458 459 460 void RegExpMacroAssemblerIA32::CheckNotCharacterAfterMinusAnd( 461 uc16 c, 462 uc16 minus, 463 uc16 mask, 464 Label* on_not_equal) { 465 DCHECK(minus < String::kMaxUtf16CodeUnit); 466 __ lea(eax, Operand(current_character(), -minus)); 467 if (c == 0) { 468 __ test(eax, Immediate(mask)); 469 } else { 470 __ and_(eax, mask); 471 __ cmp(eax, c); 472 } 473 BranchOrBacktrack(not_equal, on_not_equal); 474 } 475 476 477 void RegExpMacroAssemblerIA32::CheckCharacterInRange( 478 uc16 from, 479 uc16 to, 480 Label* on_in_range) { 481 __ lea(eax, Operand(current_character(), -from)); 482 __ cmp(eax, to - from); 483 BranchOrBacktrack(below_equal, on_in_range); 484 } 485 486 487 void RegExpMacroAssemblerIA32::CheckCharacterNotInRange( 488 uc16 from, 489 uc16 to, 490 Label* on_not_in_range) { 491 __ lea(eax, Operand(current_character(), -from)); 492 __ cmp(eax, to - from); 493 BranchOrBacktrack(above, on_not_in_range); 494 } 495 496 497 void RegExpMacroAssemblerIA32::CheckBitInTable( 498 Handle<ByteArray> table, 499 Label* on_bit_set) { 500 __ mov(eax, Immediate(table)); 501 Register index = current_character(); 502 if (mode_ != LATIN1 || kTableMask != String::kMaxOneByteCharCode) { 503 __ mov(ebx, kTableSize - 1); 504 __ and_(ebx, current_character()); 505 index = ebx; 506 } 507 __ cmpb(FieldOperand(eax, index, times_1, ByteArray::kHeaderSize), 0); 508 BranchOrBacktrack(not_equal, on_bit_set); 509 } 510 511 512 bool RegExpMacroAssemblerIA32::CheckSpecialCharacterClass(uc16 type, 513 Label* on_no_match) { 514 // Range checks (c in min..max) are generally implemented by an unsigned 515 // (c - min) <= (max - min) check 516 switch (type) { 517 case 's': 518 // Match space-characters 519 if (mode_ == LATIN1) { 520 // One byte space characters are '\t'..'\r', ' ' and \u00a0. 521 Label success; 522 __ cmp(current_character(), ' '); 523 __ j(equal, &success, Label::kNear); 524 // Check range 0x09..0x0d 525 __ lea(eax, Operand(current_character(), -'\t')); 526 __ cmp(eax, '\r' - '\t'); 527 __ j(below_equal, &success, Label::kNear); 528 // \u00a0 (NBSP). 529 __ cmp(eax, 0x00a0 - '\t'); 530 BranchOrBacktrack(not_equal, on_no_match); 531 __ bind(&success); 532 return true; 533 } 534 return false; 535 case 'S': 536 // The emitted code for generic character classes is good enough. 537 return false; 538 case 'd': 539 // Match ASCII digits ('0'..'9') 540 __ lea(eax, Operand(current_character(), -'0')); 541 __ cmp(eax, '9' - '0'); 542 BranchOrBacktrack(above, on_no_match); 543 return true; 544 case 'D': 545 // Match non ASCII-digits 546 __ lea(eax, Operand(current_character(), -'0')); 547 __ cmp(eax, '9' - '0'); 548 BranchOrBacktrack(below_equal, on_no_match); 549 return true; 550 case '.': { 551 // Match non-newlines (not 0x0a('\n'), 0x0d('\r'), 0x2028 and 0x2029) 552 __ mov(eax, current_character()); 553 __ xor_(eax, Immediate(0x01)); 554 // See if current character is '\n'^1 or '\r'^1, i.e., 0x0b or 0x0c 555 __ sub(eax, Immediate(0x0b)); 556 __ cmp(eax, 0x0c - 0x0b); 557 BranchOrBacktrack(below_equal, on_no_match); 558 if (mode_ == UC16) { 559 // Compare original value to 0x2028 and 0x2029, using the already 560 // computed (current_char ^ 0x01 - 0x0b). I.e., check for 561 // 0x201d (0x2028 - 0x0b) or 0x201e. 562 __ sub(eax, Immediate(0x2028 - 0x0b)); 563 __ cmp(eax, 0x2029 - 0x2028); 564 BranchOrBacktrack(below_equal, on_no_match); 565 } 566 return true; 567 } 568 case 'w': { 569 if (mode_ != LATIN1) { 570 // Table is 256 entries, so all Latin1 characters can be tested. 571 __ cmp(current_character(), Immediate('z')); 572 BranchOrBacktrack(above, on_no_match); 573 } 574 DCHECK_EQ(0, word_character_map[0]); // Character '\0' is not a word char. 575 ExternalReference word_map = ExternalReference::re_word_character_map(); 576 __ test_b(current_character(), 577 Operand::StaticArray(current_character(), times_1, word_map)); 578 BranchOrBacktrack(zero, on_no_match); 579 return true; 580 } 581 case 'W': { 582 Label done; 583 if (mode_ != LATIN1) { 584 // Table is 256 entries, so all Latin1 characters can be tested. 585 __ cmp(current_character(), Immediate('z')); 586 __ j(above, &done); 587 } 588 DCHECK_EQ(0, word_character_map[0]); // Character '\0' is not a word char. 589 ExternalReference word_map = ExternalReference::re_word_character_map(); 590 __ test_b(current_character(), 591 Operand::StaticArray(current_character(), times_1, word_map)); 592 BranchOrBacktrack(not_zero, on_no_match); 593 if (mode_ != LATIN1) { 594 __ bind(&done); 595 } 596 return true; 597 } 598 // Non-standard classes (with no syntactic shorthand) used internally. 599 case '*': 600 // Match any character. 601 return true; 602 case 'n': { 603 // Match newlines (0x0a('\n'), 0x0d('\r'), 0x2028 or 0x2029). 604 // The opposite of '.'. 605 __ mov(eax, current_character()); 606 __ xor_(eax, Immediate(0x01)); 607 // See if current character is '\n'^1 or '\r'^1, i.e., 0x0b or 0x0c 608 __ sub(eax, Immediate(0x0b)); 609 __ cmp(eax, 0x0c - 0x0b); 610 if (mode_ == LATIN1) { 611 BranchOrBacktrack(above, on_no_match); 612 } else { 613 Label done; 614 BranchOrBacktrack(below_equal, &done); 615 DCHECK_EQ(UC16, mode_); 616 // Compare original value to 0x2028 and 0x2029, using the already 617 // computed (current_char ^ 0x01 - 0x0b). I.e., check for 618 // 0x201d (0x2028 - 0x0b) or 0x201e. 619 __ sub(eax, Immediate(0x2028 - 0x0b)); 620 __ cmp(eax, 1); 621 BranchOrBacktrack(above, on_no_match); 622 __ bind(&done); 623 } 624 return true; 625 } 626 // No custom implementation (yet): s(UC16), S(UC16). 627 default: 628 return false; 629 } 630 } 631 632 633 void RegExpMacroAssemblerIA32::Fail() { 634 STATIC_ASSERT(FAILURE == 0); // Return value for failure is zero. 635 if (!global()) { 636 __ Move(eax, Immediate(FAILURE)); 637 } 638 __ jmp(&exit_label_); 639 } 640 641 642 Handle<HeapObject> RegExpMacroAssemblerIA32::GetCode(Handle<String> source) { 643 Label return_eax; 644 // Finalize code - write the entry point code now we know how many 645 // registers we need. 646 647 // Entry code: 648 __ bind(&entry_label_); 649 650 // Tell the system that we have a stack frame. Because the type is MANUAL, no 651 // code is generated. 652 FrameScope scope(masm_, StackFrame::MANUAL); 653 654 // Actually emit code to start a new stack frame. 655 __ push(ebp); 656 __ mov(ebp, esp); 657 // Save callee-save registers. Order here should correspond to order of 658 // kBackup_ebx etc. 659 __ push(esi); 660 __ push(edi); 661 __ push(ebx); // Callee-save on MacOS. 662 __ push(Immediate(0)); // Number of successful matches in a global regexp. 663 __ push(Immediate(0)); // Make room for "string start - 1" constant. 664 665 // Check if we have space on the stack for registers. 666 Label stack_limit_hit; 667 Label stack_ok; 668 669 ExternalReference stack_limit = 670 ExternalReference::address_of_stack_limit(isolate()); 671 __ mov(ecx, esp); 672 __ sub(ecx, Operand::StaticVariable(stack_limit)); 673 // Handle it if the stack pointer is already below the stack limit. 674 __ j(below_equal, &stack_limit_hit); 675 // Check if there is room for the variable number of registers above 676 // the stack limit. 677 __ cmp(ecx, num_registers_ * kPointerSize); 678 __ j(above_equal, &stack_ok); 679 // Exit with OutOfMemory exception. There is not enough space on the stack 680 // for our working registers. 681 __ mov(eax, EXCEPTION); 682 __ jmp(&return_eax); 683 684 __ bind(&stack_limit_hit); 685 CallCheckStackGuardState(ebx); 686 __ or_(eax, eax); 687 // If returned value is non-zero, we exit with the returned value as result. 688 __ j(not_zero, &return_eax); 689 690 __ bind(&stack_ok); 691 // Load start index for later use. 692 __ mov(ebx, Operand(ebp, kStartIndex)); 693 694 // Allocate space on stack for registers. 695 __ sub(esp, Immediate(num_registers_ * kPointerSize)); 696 // Load string length. 697 __ mov(esi, Operand(ebp, kInputEnd)); 698 // Load input position. 699 __ mov(edi, Operand(ebp, kInputStart)); 700 // Set up edi to be negative offset from string end. 701 __ sub(edi, esi); 702 703 // Set eax to address of char before start of the string. 704 // (effectively string position -1). 705 __ neg(ebx); 706 if (mode_ == UC16) { 707 __ lea(eax, Operand(edi, ebx, times_2, -char_size())); 708 } else { 709 __ lea(eax, Operand(edi, ebx, times_1, -char_size())); 710 } 711 // Store this value in a local variable, for use when clearing 712 // position registers. 713 __ mov(Operand(ebp, kStringStartMinusOne), eax); 714 715 #if V8_OS_WIN 716 // Ensure that we write to each stack page, in order. Skipping a page 717 // on Windows can cause segmentation faults. Assuming page size is 4k. 718 const int kPageSize = 4096; 719 const int kRegistersPerPage = kPageSize / kPointerSize; 720 for (int i = num_saved_registers_ + kRegistersPerPage - 1; 721 i < num_registers_; 722 i += kRegistersPerPage) { 723 __ mov(register_location(i), eax); // One write every page. 724 } 725 #endif // V8_OS_WIN 726 727 Label load_char_start_regexp, start_regexp; 728 // Load newline if index is at start, previous character otherwise. 729 __ cmp(Operand(ebp, kStartIndex), Immediate(0)); 730 __ j(not_equal, &load_char_start_regexp, Label::kNear); 731 __ mov(current_character(), '\n'); 732 __ jmp(&start_regexp, Label::kNear); 733 734 // Global regexp restarts matching here. 735 __ bind(&load_char_start_regexp); 736 // Load previous char as initial value of current character register. 737 LoadCurrentCharacterUnchecked(-1, 1); 738 __ bind(&start_regexp); 739 740 // Initialize on-stack registers. 741 if (num_saved_registers_ > 0) { // Always is, if generated from a regexp. 742 // Fill saved registers with initial value = start offset - 1 743 // Fill in stack push order, to avoid accessing across an unwritten 744 // page (a problem on Windows). 745 if (num_saved_registers_ > 8) { 746 __ mov(ecx, kRegisterZero); 747 Label init_loop; 748 __ bind(&init_loop); 749 __ mov(Operand(ebp, ecx, times_1, 0), eax); 750 __ sub(ecx, Immediate(kPointerSize)); 751 __ cmp(ecx, kRegisterZero - num_saved_registers_ * kPointerSize); 752 __ j(greater, &init_loop); 753 } else { // Unroll the loop. 754 for (int i = 0; i < num_saved_registers_; i++) { 755 __ mov(register_location(i), eax); 756 } 757 } 758 } 759 760 // Initialize backtrack stack pointer. 761 __ mov(backtrack_stackpointer(), Operand(ebp, kStackHighEnd)); 762 763 __ jmp(&start_label_); 764 765 // Exit code: 766 if (success_label_.is_linked()) { 767 // Save captures when successful. 768 __ bind(&success_label_); 769 if (num_saved_registers_ > 0) { 770 // copy captures to output 771 __ mov(ebx, Operand(ebp, kRegisterOutput)); 772 __ mov(ecx, Operand(ebp, kInputEnd)); 773 __ mov(edx, Operand(ebp, kStartIndex)); 774 __ sub(ecx, Operand(ebp, kInputStart)); 775 if (mode_ == UC16) { 776 __ lea(ecx, Operand(ecx, edx, times_2, 0)); 777 } else { 778 __ add(ecx, edx); 779 } 780 for (int i = 0; i < num_saved_registers_; i++) { 781 __ mov(eax, register_location(i)); 782 if (i == 0 && global_with_zero_length_check()) { 783 // Keep capture start in edx for the zero-length check later. 784 __ mov(edx, eax); 785 } 786 // Convert to index from start of string, not end. 787 __ add(eax, ecx); 788 if (mode_ == UC16) { 789 __ sar(eax, 1); // Convert byte index to character index. 790 } 791 __ mov(Operand(ebx, i * kPointerSize), eax); 792 } 793 } 794 795 if (global()) { 796 // Restart matching if the regular expression is flagged as global. 797 // Increment success counter. 798 __ inc(Operand(ebp, kSuccessfulCaptures)); 799 // Capture results have been stored, so the number of remaining global 800 // output registers is reduced by the number of stored captures. 801 __ mov(ecx, Operand(ebp, kNumOutputRegisters)); 802 __ sub(ecx, Immediate(num_saved_registers_)); 803 // Check whether we have enough room for another set of capture results. 804 __ cmp(ecx, Immediate(num_saved_registers_)); 805 __ j(less, &exit_label_); 806 807 __ mov(Operand(ebp, kNumOutputRegisters), ecx); 808 // Advance the location for output. 809 __ add(Operand(ebp, kRegisterOutput), 810 Immediate(num_saved_registers_ * kPointerSize)); 811 812 // Prepare eax to initialize registers with its value in the next run. 813 __ mov(eax, Operand(ebp, kStringStartMinusOne)); 814 815 if (global_with_zero_length_check()) { 816 // Special case for zero-length matches. 817 // edx: capture start index 818 __ cmp(edi, edx); 819 // Not a zero-length match, restart. 820 __ j(not_equal, &load_char_start_regexp); 821 // edi (offset from the end) is zero if we already reached the end. 822 __ test(edi, edi); 823 __ j(zero, &exit_label_, Label::kNear); 824 // Advance current position after a zero-length match. 825 if (mode_ == UC16) { 826 __ add(edi, Immediate(2)); 827 } else { 828 __ inc(edi); 829 } 830 } 831 832 __ jmp(&load_char_start_regexp); 833 } else { 834 __ mov(eax, Immediate(SUCCESS)); 835 } 836 } 837 838 __ bind(&exit_label_); 839 if (global()) { 840 // Return the number of successful captures. 841 __ mov(eax, Operand(ebp, kSuccessfulCaptures)); 842 } 843 844 __ bind(&return_eax); 845 // Skip esp past regexp registers. 846 __ lea(esp, Operand(ebp, kBackup_ebx)); 847 // Restore callee-save registers. 848 __ pop(ebx); 849 __ pop(edi); 850 __ pop(esi); 851 // Exit function frame, restore previous one. 852 __ pop(ebp); 853 __ ret(0); 854 855 // Backtrack code (branch target for conditional backtracks). 856 if (backtrack_label_.is_linked()) { 857 __ bind(&backtrack_label_); 858 Backtrack(); 859 } 860 861 Label exit_with_exception; 862 863 // Preempt-code 864 if (check_preempt_label_.is_linked()) { 865 SafeCallTarget(&check_preempt_label_); 866 867 __ push(backtrack_stackpointer()); 868 __ push(edi); 869 870 CallCheckStackGuardState(ebx); 871 __ or_(eax, eax); 872 // If returning non-zero, we should end execution with the given 873 // result as return value. 874 __ j(not_zero, &return_eax); 875 876 __ pop(edi); 877 __ pop(backtrack_stackpointer()); 878 // String might have moved: Reload esi from frame. 879 __ mov(esi, Operand(ebp, kInputEnd)); 880 SafeReturn(); 881 } 882 883 // Backtrack stack overflow code. 884 if (stack_overflow_label_.is_linked()) { 885 SafeCallTarget(&stack_overflow_label_); 886 // Reached if the backtrack-stack limit has been hit. 887 888 Label grow_failed; 889 // Save registers before calling C function 890 __ push(esi); 891 __ push(edi); 892 893 // Call GrowStack(backtrack_stackpointer()) 894 static const int num_arguments = 3; 895 __ PrepareCallCFunction(num_arguments, ebx); 896 __ mov(Operand(esp, 2 * kPointerSize), 897 Immediate(ExternalReference::isolate_address(isolate()))); 898 __ lea(eax, Operand(ebp, kStackHighEnd)); 899 __ mov(Operand(esp, 1 * kPointerSize), eax); 900 __ mov(Operand(esp, 0 * kPointerSize), backtrack_stackpointer()); 901 ExternalReference grow_stack = 902 ExternalReference::re_grow_stack(isolate()); 903 __ CallCFunction(grow_stack, num_arguments); 904 // If return NULL, we have failed to grow the stack, and 905 // must exit with a stack-overflow exception. 906 __ or_(eax, eax); 907 __ j(equal, &exit_with_exception); 908 // Otherwise use return value as new stack pointer. 909 __ mov(backtrack_stackpointer(), eax); 910 // Restore saved registers and continue. 911 __ pop(edi); 912 __ pop(esi); 913 SafeReturn(); 914 } 915 916 if (exit_with_exception.is_linked()) { 917 // If any of the code above needed to exit with an exception. 918 __ bind(&exit_with_exception); 919 // Exit with Result EXCEPTION(-1) to signal thrown exception. 920 __ mov(eax, EXCEPTION); 921 __ jmp(&return_eax); 922 } 923 924 CodeDesc code_desc; 925 masm_->GetCode(&code_desc); 926 Handle<Code> code = 927 isolate()->factory()->NewCode(code_desc, 928 Code::ComputeFlags(Code::REGEXP), 929 masm_->CodeObject()); 930 PROFILE(isolate(), RegExpCodeCreateEvent(*code, *source)); 931 return Handle<HeapObject>::cast(code); 932 } 933 934 935 void RegExpMacroAssemblerIA32::GoTo(Label* to) { 936 BranchOrBacktrack(no_condition, to); 937 } 938 939 940 void RegExpMacroAssemblerIA32::IfRegisterGE(int reg, 941 int comparand, 942 Label* if_ge) { 943 __ cmp(register_location(reg), Immediate(comparand)); 944 BranchOrBacktrack(greater_equal, if_ge); 945 } 946 947 948 void RegExpMacroAssemblerIA32::IfRegisterLT(int reg, 949 int comparand, 950 Label* if_lt) { 951 __ cmp(register_location(reg), Immediate(comparand)); 952 BranchOrBacktrack(less, if_lt); 953 } 954 955 956 void RegExpMacroAssemblerIA32::IfRegisterEqPos(int reg, 957 Label* if_eq) { 958 __ cmp(edi, register_location(reg)); 959 BranchOrBacktrack(equal, if_eq); 960 } 961 962 963 RegExpMacroAssembler::IrregexpImplementation 964 RegExpMacroAssemblerIA32::Implementation() { 965 return kIA32Implementation; 966 } 967 968 969 void RegExpMacroAssemblerIA32::LoadCurrentCharacter(int cp_offset, 970 Label* on_end_of_input, 971 bool check_bounds, 972 int characters) { 973 DCHECK(cp_offset < (1<<30)); // Be sane! (And ensure negation works) 974 if (check_bounds) { 975 if (cp_offset >= 0) { 976 CheckPosition(cp_offset + characters - 1, on_end_of_input); 977 } else { 978 CheckPosition(cp_offset, on_end_of_input); 979 } 980 } 981 LoadCurrentCharacterUnchecked(cp_offset, characters); 982 } 983 984 985 void RegExpMacroAssemblerIA32::PopCurrentPosition() { 986 Pop(edi); 987 } 988 989 990 void RegExpMacroAssemblerIA32::PopRegister(int register_index) { 991 Pop(eax); 992 __ mov(register_location(register_index), eax); 993 } 994 995 996 void RegExpMacroAssemblerIA32::PushBacktrack(Label* label) { 997 Push(Immediate::CodeRelativeOffset(label)); 998 CheckStackLimit(); 999 } 1000 1001 1002 void RegExpMacroAssemblerIA32::PushCurrentPosition() { 1003 Push(edi); 1004 } 1005 1006 1007 void RegExpMacroAssemblerIA32::PushRegister(int register_index, 1008 StackCheckFlag check_stack_limit) { 1009 __ mov(eax, register_location(register_index)); 1010 Push(eax); 1011 if (check_stack_limit) CheckStackLimit(); 1012 } 1013 1014 1015 void RegExpMacroAssemblerIA32::ReadCurrentPositionFromRegister(int reg) { 1016 __ mov(edi, register_location(reg)); 1017 } 1018 1019 1020 void RegExpMacroAssemblerIA32::ReadStackPointerFromRegister(int reg) { 1021 __ mov(backtrack_stackpointer(), register_location(reg)); 1022 __ add(backtrack_stackpointer(), Operand(ebp, kStackHighEnd)); 1023 } 1024 1025 void RegExpMacroAssemblerIA32::SetCurrentPositionFromEnd(int by) { 1026 Label after_position; 1027 __ cmp(edi, -by * char_size()); 1028 __ j(greater_equal, &after_position, Label::kNear); 1029 __ mov(edi, -by * char_size()); 1030 // On RegExp code entry (where this operation is used), the character before 1031 // the current position is expected to be already loaded. 1032 // We have advanced the position, so it's safe to read backwards. 1033 LoadCurrentCharacterUnchecked(-1, 1); 1034 __ bind(&after_position); 1035 } 1036 1037 1038 void RegExpMacroAssemblerIA32::SetRegister(int register_index, int to) { 1039 DCHECK(register_index >= num_saved_registers_); // Reserved for positions! 1040 __ mov(register_location(register_index), Immediate(to)); 1041 } 1042 1043 1044 bool RegExpMacroAssemblerIA32::Succeed() { 1045 __ jmp(&success_label_); 1046 return global(); 1047 } 1048 1049 1050 void RegExpMacroAssemblerIA32::WriteCurrentPositionToRegister(int reg, 1051 int cp_offset) { 1052 if (cp_offset == 0) { 1053 __ mov(register_location(reg), edi); 1054 } else { 1055 __ lea(eax, Operand(edi, cp_offset * char_size())); 1056 __ mov(register_location(reg), eax); 1057 } 1058 } 1059 1060 1061 void RegExpMacroAssemblerIA32::ClearRegisters(int reg_from, int reg_to) { 1062 DCHECK(reg_from <= reg_to); 1063 __ mov(eax, Operand(ebp, kStringStartMinusOne)); 1064 for (int reg = reg_from; reg <= reg_to; reg++) { 1065 __ mov(register_location(reg), eax); 1066 } 1067 } 1068 1069 1070 void RegExpMacroAssemblerIA32::WriteStackPointerToRegister(int reg) { 1071 __ mov(eax, backtrack_stackpointer()); 1072 __ sub(eax, Operand(ebp, kStackHighEnd)); 1073 __ mov(register_location(reg), eax); 1074 } 1075 1076 1077 // Private methods: 1078 1079 void RegExpMacroAssemblerIA32::CallCheckStackGuardState(Register scratch) { 1080 static const int num_arguments = 3; 1081 __ PrepareCallCFunction(num_arguments, scratch); 1082 // RegExp code frame pointer. 1083 __ mov(Operand(esp, 2 * kPointerSize), ebp); 1084 // Code* of self. 1085 __ mov(Operand(esp, 1 * kPointerSize), Immediate(masm_->CodeObject())); 1086 // Next address on the stack (will be address of return address). 1087 __ lea(eax, Operand(esp, -kPointerSize)); 1088 __ mov(Operand(esp, 0 * kPointerSize), eax); 1089 ExternalReference check_stack_guard = 1090 ExternalReference::re_check_stack_guard_state(isolate()); 1091 __ CallCFunction(check_stack_guard, num_arguments); 1092 } 1093 1094 1095 // Helper function for reading a value out of a stack frame. 1096 template <typename T> 1097 static T& frame_entry(Address re_frame, int frame_offset) { 1098 return reinterpret_cast<T&>(Memory::int32_at(re_frame + frame_offset)); 1099 } 1100 1101 1102 template <typename T> 1103 static T* frame_entry_address(Address re_frame, int frame_offset) { 1104 return reinterpret_cast<T*>(re_frame + frame_offset); 1105 } 1106 1107 1108 int RegExpMacroAssemblerIA32::CheckStackGuardState(Address* return_address, 1109 Code* re_code, 1110 Address re_frame) { 1111 return NativeRegExpMacroAssembler::CheckStackGuardState( 1112 frame_entry<Isolate*>(re_frame, kIsolate), 1113 frame_entry<int>(re_frame, kStartIndex), 1114 frame_entry<int>(re_frame, kDirectCall) == 1, return_address, re_code, 1115 frame_entry_address<String*>(re_frame, kInputString), 1116 frame_entry_address<const byte*>(re_frame, kInputStart), 1117 frame_entry_address<const byte*>(re_frame, kInputEnd)); 1118 } 1119 1120 1121 Operand RegExpMacroAssemblerIA32::register_location(int register_index) { 1122 DCHECK(register_index < (1<<30)); 1123 if (num_registers_ <= register_index) { 1124 num_registers_ = register_index + 1; 1125 } 1126 return Operand(ebp, kRegisterZero - register_index * kPointerSize); 1127 } 1128 1129 1130 void RegExpMacroAssemblerIA32::CheckPosition(int cp_offset, 1131 Label* on_outside_input) { 1132 if (cp_offset >= 0) { 1133 __ cmp(edi, -cp_offset * char_size()); 1134 BranchOrBacktrack(greater_equal, on_outside_input); 1135 } else { 1136 __ lea(eax, Operand(edi, cp_offset * char_size())); 1137 __ cmp(eax, Operand(ebp, kStringStartMinusOne)); 1138 BranchOrBacktrack(less_equal, on_outside_input); 1139 } 1140 } 1141 1142 1143 void RegExpMacroAssemblerIA32::BranchOrBacktrack(Condition condition, 1144 Label* to) { 1145 if (condition < 0) { // No condition 1146 if (to == NULL) { 1147 Backtrack(); 1148 return; 1149 } 1150 __ jmp(to); 1151 return; 1152 } 1153 if (to == NULL) { 1154 __ j(condition, &backtrack_label_); 1155 return; 1156 } 1157 __ j(condition, to); 1158 } 1159 1160 1161 void RegExpMacroAssemblerIA32::SafeCall(Label* to) { 1162 Label return_to; 1163 __ push(Immediate::CodeRelativeOffset(&return_to)); 1164 __ jmp(to); 1165 __ bind(&return_to); 1166 } 1167 1168 1169 void RegExpMacroAssemblerIA32::SafeReturn() { 1170 __ pop(ebx); 1171 __ add(ebx, Immediate(masm_->CodeObject())); 1172 __ jmp(ebx); 1173 } 1174 1175 1176 void RegExpMacroAssemblerIA32::SafeCallTarget(Label* name) { 1177 __ bind(name); 1178 } 1179 1180 1181 void RegExpMacroAssemblerIA32::Push(Register source) { 1182 DCHECK(!source.is(backtrack_stackpointer())); 1183 // Notice: This updates flags, unlike normal Push. 1184 __ sub(backtrack_stackpointer(), Immediate(kPointerSize)); 1185 __ mov(Operand(backtrack_stackpointer(), 0), source); 1186 } 1187 1188 1189 void RegExpMacroAssemblerIA32::Push(Immediate value) { 1190 // Notice: This updates flags, unlike normal Push. 1191 __ sub(backtrack_stackpointer(), Immediate(kPointerSize)); 1192 __ mov(Operand(backtrack_stackpointer(), 0), value); 1193 } 1194 1195 1196 void RegExpMacroAssemblerIA32::Pop(Register target) { 1197 DCHECK(!target.is(backtrack_stackpointer())); 1198 __ mov(target, Operand(backtrack_stackpointer(), 0)); 1199 // Notice: This updates flags, unlike normal Pop. 1200 __ add(backtrack_stackpointer(), Immediate(kPointerSize)); 1201 } 1202 1203 1204 void RegExpMacroAssemblerIA32::CheckPreemption() { 1205 // Check for preemption. 1206 Label no_preempt; 1207 ExternalReference stack_limit = 1208 ExternalReference::address_of_stack_limit(isolate()); 1209 __ cmp(esp, Operand::StaticVariable(stack_limit)); 1210 __ j(above, &no_preempt); 1211 1212 SafeCall(&check_preempt_label_); 1213 1214 __ bind(&no_preempt); 1215 } 1216 1217 1218 void RegExpMacroAssemblerIA32::CheckStackLimit() { 1219 Label no_stack_overflow; 1220 ExternalReference stack_limit = 1221 ExternalReference::address_of_regexp_stack_limit(isolate()); 1222 __ cmp(backtrack_stackpointer(), Operand::StaticVariable(stack_limit)); 1223 __ j(above, &no_stack_overflow); 1224 1225 SafeCall(&stack_overflow_label_); 1226 1227 __ bind(&no_stack_overflow); 1228 } 1229 1230 1231 void RegExpMacroAssemblerIA32::LoadCurrentCharacterUnchecked(int cp_offset, 1232 int characters) { 1233 if (mode_ == LATIN1) { 1234 if (characters == 4) { 1235 __ mov(current_character(), Operand(esi, edi, times_1, cp_offset)); 1236 } else if (characters == 2) { 1237 __ movzx_w(current_character(), Operand(esi, edi, times_1, cp_offset)); 1238 } else { 1239 DCHECK(characters == 1); 1240 __ movzx_b(current_character(), Operand(esi, edi, times_1, cp_offset)); 1241 } 1242 } else { 1243 DCHECK(mode_ == UC16); 1244 if (characters == 2) { 1245 __ mov(current_character(), 1246 Operand(esi, edi, times_1, cp_offset * sizeof(uc16))); 1247 } else { 1248 DCHECK(characters == 1); 1249 __ movzx_w(current_character(), 1250 Operand(esi, edi, times_1, cp_offset * sizeof(uc16))); 1251 } 1252 } 1253 } 1254 1255 1256 #undef __ 1257 1258 #endif // V8_INTERPRETED_REGEXP 1259 1260 } // namespace internal 1261 } // namespace v8 1262 1263 #endif // V8_TARGET_ARCH_IA32 1264