[Pcre-svn] [990] code/trunk: Improved JIT compiler optimizat…

Etusivu
Poista viesti
Lähettäjä: Subversion repository
Päiväys:  
Vastaanottaja: pcre-svn
Aihe: [Pcre-svn] [990] code/trunk: Improved JIT compiler optimizations for character ranges.
Revision: 990
          http://vcs.pcre.org/viewvc?view=rev&revision=990
Author:   zherczeg
Date:     2012-07-08 17:32:22 +0100 (Sun, 08 Jul 2012)


Log Message:
-----------
Improved JIT compiler optimizations for character ranges.

Modified Paths:
--------------
    code/trunk/ChangeLog
    code/trunk/pcre_jit_compile.c


Modified: code/trunk/ChangeLog
===================================================================
--- code/trunk/ChangeLog    2012-07-07 11:11:02 UTC (rev 989)
+++ code/trunk/ChangeLog    2012-07-08 16:32:22 UTC (rev 990)
@@ -12,7 +12,9 @@


3. Single character iterator optimizations in the JIT compiler.

+4. Improved JIT compiler optimizations for character ranges.

+
Version 8.31 06-July-2012
-------------------------


Modified: code/trunk/pcre_jit_compile.c
===================================================================
--- code/trunk/pcre_jit_compile.c    2012-07-07 11:11:02 UTC (rev 989)
+++ code/trunk/pcre_jit_compile.c    2012-07-08 16:32:22 UTC (rev 990)
@@ -268,6 +268,8 @@
   backtrack_common common;
 } recurse_backtrack;


+#define MAX_RANGE_SIZE 6
+
typedef struct compiler_common {
struct sljit_compiler *compiler;
pcre_uchar *start;
@@ -290,16 +292,22 @@
/* Points to the marked string. */
int mark_ptr;

- /* Other */
+ /* Flipped and lower case tables. */
const pcre_uint8 *fcc;
sljit_w lcc;
+ /* Mode can be PCRE_STUDY_JIT_COMPILE and others. */
int mode;
+ /* Newline control. */
int nltype;
int newline;
int bsr_nltype;
+ /* Dollar endonly. */
int endonly;
BOOL has_set_som;
+ /* Tables. */
sljit_w ctypes;
+ int digits[2 + MAX_RANGE_SIZE];
+ /* Named capturing brackets. */
sljit_uw name_table;
sljit_w name_count;
sljit_w name_entry_size;
@@ -3124,6 +3132,141 @@
sljit_emit_fast_return(compiler, SLJIT_MEM1(SLJIT_LOCALS_REG), LOCALS0);
}

+/*
+  range format:
+
+  ranges[0] = length of the range (max MAX_RANGE_SIZE, -1 means invalid range).
+  ranges[1] = first bit (0 or 1)
+  ranges[2-length] = position of the bit change (when the current bit is not equal to the previous)
+*/
+
+static BOOL check_ranges(compiler_common *common, int *ranges, jump_list **backtracks, BOOL readch)
+{
+DEFINE_COMPILER;
+struct sljit_jump *jump;
+
+if (ranges[0] < 0)
+  return FALSE;
+
+switch(ranges[0])
+  {
+  case 1:
+  if (readch)
+    read_char(common);
+  add_jump(compiler, backtracks, CMP(ranges[1] == 0 ? SLJIT_C_LESS : SLJIT_C_GREATER_EQUAL, TMP1, 0, SLJIT_IMM, ranges[2]));
+  return TRUE;
+
+  case 2:
+  if (readch)
+    read_char(common);
+  OP2(SLJIT_SUB, TMP1, 0, TMP1, 0, SLJIT_IMM, ranges[2]);
+  add_jump(compiler, backtracks, CMP(ranges[1] != 0 ? SLJIT_C_LESS : SLJIT_C_GREATER_EQUAL, TMP1, 0, SLJIT_IMM, ranges[3] - ranges[2]));
+  return TRUE;
+
+  case 4:
+  if (ranges[2] + 1 == ranges[3] && ranges[4] + 1 == ranges[5])
+    {
+    if (readch)
+      read_char(common);
+    if (ranges[1] != 0)
+      {
+      add_jump(compiler, backtracks, CMP(SLJIT_C_EQUAL, TMP1, 0, SLJIT_IMM, ranges[2]));
+      add_jump(compiler, backtracks, CMP(SLJIT_C_EQUAL, TMP1, 0, SLJIT_IMM, ranges[4]));
+      }
+    else
+      {
+      jump = CMP(SLJIT_C_EQUAL, TMP1, 0, SLJIT_IMM, ranges[2]);
+      add_jump(compiler, backtracks, CMP(SLJIT_C_NOT_EQUAL, TMP1, 0, SLJIT_IMM, ranges[4]));
+      JUMPHERE(jump);
+      }
+    return TRUE;
+    }
+  return FALSE;
+
+  default:
+  return FALSE;
+  }
+}
+
+static void get_ctype_ranges(compiler_common *common, int flag, int *ranges)
+{
+int i, bit, length;
+const pcre_uint8 *ctypes = (const pcre_uint8*)common->ctypes;
+
+bit = ctypes[0] & flag;
+ranges[1] = bit != 0 ? 1 : 0;
+length = 0;
+
+for (i = 1; i < 256; i++)
+  if ((ctypes[i] & flag) != bit)
+    {
+    if (length >= MAX_RANGE_SIZE)
+      {
+      ranges[0] = -1;
+      return;
+      }
+    ranges[2 + length] = i;
+    length++;
+    bit ^= flag;
+    }
+
+if (bit != 0)
+  {
+  if (length >= MAX_RANGE_SIZE)
+    {
+    ranges[0] = -1;
+    return;
+    }
+  ranges[2 + length] = 256;
+  length++;
+  }
+ranges[0] = length;
+}
+
+static BOOL check_class_ranges(compiler_common *common, const pcre_uint8 *bits, BOOL nclass, jump_list **backtracks)
+{
+int ranges[2 + MAX_RANGE_SIZE];
+pcre_uint8 bit, cbit, all;
+int i, byte, length = 0;
+
+bit = bits[0] & 0x1;
+ranges[1] = bit;
+/* Can be 0 or 255. */
+all = -bit;
+
+for (i = 0; i < 256; )
+  {
+  byte = i >> 3;
+  if ((i & 0x7) == 0 && bits[byte] == all)
+    i += 8;
+  else
+    {
+    cbit = (bits[byte] >> (i & 0x7)) & 0x1;
+    if (cbit != bit)
+      {
+      if (length >= MAX_RANGE_SIZE)
+        return FALSE;
+      ranges[2 + length] = i;
+      length++;
+      bit = cbit;
+      all = -cbit;
+      }
+    i++;
+    }
+  }
+
+if (((bit == 0) && nclass) || ((bit == 1) && !nclass))
+  {
+  if (length >= MAX_RANGE_SIZE)
+    return FALSE;
+  ranges[2 + length] = 256;
+  length++;
+  }
+ranges[0] = length;
+
+return check_ranges(common, ranges, backtracks, FALSE);
+}
+
 static void check_anynewline(compiler_common *common)
 {
 /* Check whether TMP1 contains a newline character. TMP2 destroyed. */
@@ -3517,7 +3660,8 @@
 int invertcmp, numberofcmps;
 unsigned int charoffset;


-/* Although SUPPORT_UTF must be defined, we are not necessary in utf mode. */
+/* Although SUPPORT_UTF must be defined, we are
+ not necessary in utf mode even in 8 bit mode. */
detect_partial_match(common, backtracks);
read_char(common);

@@ -3531,12 +3675,15 @@
     jump = CMP(SLJIT_C_GREATER, TMP1, 0, SLJIT_IMM, 255);
 #endif


-  OP2(SLJIT_AND, TMP2, 0, TMP1, 0, SLJIT_IMM, 0x7);
-  OP2(SLJIT_LSHR, TMP1, 0, TMP1, 0, SLJIT_IMM, 3);
-  OP1(SLJIT_MOV_UB, TMP1, 0, SLJIT_MEM1(TMP1), (sljit_w)cc);
-  OP2(SLJIT_SHL, TMP2, 0, SLJIT_IMM, 1, TMP2, 0);
-  OP2(SLJIT_AND | SLJIT_SET_E, SLJIT_UNUSED, 0, TMP1, 0, TMP2, 0);
-  add_jump(compiler, list, JUMP(SLJIT_C_NOT_ZERO));
+  if (!check_class_ranges(common, (const pcre_uint8 *)cc, TRUE, list))
+    {
+    OP2(SLJIT_AND, TMP2, 0, TMP1, 0, SLJIT_IMM, 0x7);
+    OP2(SLJIT_LSHR, TMP1, 0, TMP1, 0, SLJIT_IMM, 3);
+    OP1(SLJIT_MOV_UB, TMP1, 0, SLJIT_MEM1(TMP1), (sljit_w)cc);
+    OP2(SLJIT_SHL, TMP2, 0, SLJIT_IMM, 1, TMP2, 0);
+    OP2(SLJIT_AND | SLJIT_SET_E, SLJIT_UNUSED, 0, TMP1, 0, TMP2, 0);
+    add_jump(compiler, list, JUMP(SLJIT_C_NOT_ZERO));
+    }


#ifndef COMPILE_PCRE8
JUMPHERE(jump);
@@ -3872,10 +4019,21 @@

   case OP_NOT_DIGIT:
   case OP_DIGIT:
+  /* Digits are usually 0-9, so it is worth to optimize them. */
+  if (common->digits[0] == -2)
+    get_ctype_ranges(common, ctype_digit, common->digits);
   detect_partial_match(common, backtracks);
-  read_char8_type(common);
-  OP2(SLJIT_AND | SLJIT_SET_E, SLJIT_UNUSED, 0, TMP1, 0, SLJIT_IMM, ctype_digit);
-  add_jump(compiler, backtracks, JUMP(type == OP_DIGIT ? SLJIT_C_ZERO : SLJIT_C_NOT_ZERO));
+  /* Flip the starting bit in the negative case. */
+  if (type == OP_NOT_DIGIT)
+    common->digits[1] ^= 1;
+  if (!check_ranges(common, common->digits, backtracks, TRUE))
+    {
+    read_char8_type(common);
+    OP2(SLJIT_AND | SLJIT_SET_E, SLJIT_UNUSED, 0, TMP1, 0, SLJIT_IMM, ctype_digit);
+    add_jump(compiler, backtracks, JUMP(type == OP_DIGIT ? SLJIT_C_ZERO : SLJIT_C_NOT_ZERO));
+    }
+  if (type == OP_NOT_DIGIT)
+    common->digits[1] ^= 1;
   return cc;


   case OP_NOT_WHITESPACE:
@@ -4299,6 +4457,9 @@
   case OP_NCLASS:
   detect_partial_match(common, backtracks);
   read_char(common);
+  if (check_class_ranges(common, (const pcre_uint8 *)cc, type == OP_NCLASS, backtracks))
+    return cc + 32 / sizeof(pcre_uchar);
+
 #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
   jump[0] = NULL;
 #ifdef COMPILE_PCRE8
@@ -7538,6 +7699,7 @@
   }
 common->endonly = (re->options & PCRE_DOLLAR_ENDONLY) != 0;
 common->ctypes = (sljit_w)(tables + ctypes_offset);
+common->digits[0] = -2;
 common->name_table = (sljit_w)((pcre_uchar *)re + re->name_table_offset);
 common->name_count = re->name_count;
 common->name_entry_size = re->name_entry_size;