This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Fix PR58464


This re-instantiates a generic recursion prevention for PHI translation,
removing the simple one added for PR51042.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2013-09-23  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/58464
	* tree-ssa-pre.c (phi_trans_lookup): Remove.
	(phi_trans_add): Change to add conditionally on being not
	present.
	(phi_translate_1): Remove recursion detection here.
	(phi_translate): Pre-seed the cache with NULL to catch
	recursion here in a more generic way.
	(bitmap_find_leader): Adjust comment.
	(get_representative_for): Dump value-numbers.
	(create_expression_by_pieces): Likewise.
	(insert_into_preds_of_block): Likewise.

	* g++.dg/torture/pr58464.C: New testcase.

Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c	(revision 202823)
--- gcc/tree-ssa-pre.c	(working copy)
*************** expr_pred_trans_d::equal (const value_ty
*** 525,570 ****
     expression and predecessor.  */
  static hash_table <expr_pred_trans_d> phi_translate_table;
  
- /* Search in the phi translation table for the translation of
-    expression E in basic block PRED.
-    Return the translated value, if found, NULL otherwise.  */
- 
- static inline pre_expr
- phi_trans_lookup (pre_expr e, basic_block pred)
- {
-   expr_pred_trans_t *slot;
-   struct expr_pred_trans_d ept;
- 
-   ept.e = e;
-   ept.pred = pred;
-   ept.hashcode = iterative_hash_hashval_t (pre_expr_d::hash (e), pred->index);
-   slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode,
- 				   NO_INSERT);
-   if (!slot)
-     return NULL;
-   else
-     return (*slot)->v;
- }
- 
- 
  /* Add the tuple mapping from {expression E, basic block PRED} to
!    value V, to the phi translation table.  */
  
! static inline void
! phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
  {
    expr_pred_trans_t *slot;
!   expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
!   new_pair->e = e;
!   new_pair->pred = pred;
!   new_pair->v = v;
!   new_pair->hashcode = iterative_hash_hashval_t (pre_expr_d::hash (e),
! 						 pred->index);
! 
!   slot = phi_translate_table.find_slot_with_hash (new_pair,
! 				   new_pair->hashcode, INSERT);
!   free (*slot);
!   *slot = new_pair;
  }
  
  
--- 525,555 ----
     expression and predecessor.  */
  static hash_table <expr_pred_trans_d> phi_translate_table;
  
  /* Add the tuple mapping from {expression E, basic block PRED} to
!    the phi translation table and return whether it pre-existed.  */
  
! static inline bool
! phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
  {
    expr_pred_trans_t *slot;
!   expr_pred_trans_d tem;
!   hashval_t hash = iterative_hash_hashval_t (pre_expr_d::hash (e),
! 					     pred->index);
!   tem.e = e;
!   tem.pred = pred;
!   tem.hashcode = hash;
!   slot = phi_translate_table.find_slot_with_hash (&tem, hash, INSERT);
!   if (*slot)
!     {
!       *entry = *slot;
!       return true;
!     }
! 
!   *entry = *slot = XNEW (struct expr_pred_trans_d);
!   (*entry)->e = e;
!   (*entry)->pred = pred;
!   (*entry)->hashcode = hash;
!   return false;
  }
  
  
*************** get_representative_for (const pre_expr e
*** 1420,1426 ****
        print_generic_expr (dump_file, name, 0);
        fprintf (dump_file, " for expression:");
        print_pre_expr (dump_file, e);
!       fprintf (dump_file, "\n");
      }
  
    return name;
--- 1405,1411 ----
        print_generic_expr (dump_file, name, 0);
        fprintf (dump_file, " for expression:");
        print_pre_expr (dump_file, e);
!       fprintf (dump_file, " (%04d)\n", value_id);
      }
  
    return name;
*************** phi_translate_1 (pre_expr expr, bitmap_s
*** 1561,1583 ****
  		leader = find_leader_in_sets (op_val_id, set1, set2);
  		if (!leader)
  		  break;
! 		/* Make sure we do not recursively translate ourselves
! 		   like for translating a[n_1] with the leader for
! 		   n_1 being a[n_1].  */
! 		if (get_expression_id (leader) != get_expression_id (expr))
  		  {
! 		    opresult = phi_translate (leader, set1, set2,
! 					      pred, phiblock);
! 		    if (!opresult)
  		      break;
! 		    if (opresult != leader)
! 		      {
! 			tree name = get_representative_for (opresult);
! 			if (!name)
! 			  break;
! 			changed |= name != op[n];
! 			op[n] = name;
! 		      }
  		  }
  	      }
  	    if (n != 3)
--- 1546,1561 ----
  		leader = find_leader_in_sets (op_val_id, set1, set2);
  		if (!leader)
  		  break;
! 		opresult = phi_translate (leader, set1, set2, pred, phiblock);
! 		if (!opresult)
! 		  break;
! 		if (opresult != leader)
  		  {
! 		    tree name = get_representative_for (opresult);
! 		    if (!name)
  		      break;
! 		    changed |= name != op[n];
! 		    op[n] = name;
  		  }
  	      }
  	    if (n != 3)
*************** static pre_expr
*** 1751,1756 ****
--- 1729,1735 ----
  phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
  	       basic_block pred, basic_block phiblock)
  {
+   expr_pred_trans_t slot = NULL;
    pre_expr phitrans;
  
    if (!expr)
*************** phi_translate (pre_expr expr, bitmap_set
*** 1763,1783 ****
    if (value_id_constant_p (get_expr_value_id (expr)))
      return expr;
  
    if (expr->kind != NAME)
      {
!       phitrans = phi_trans_lookup (expr, pred);
!       if (phitrans)
! 	return phitrans;
      }
  
    /* Translate.  */
    phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
  
!   /* Don't add empty translations to the cache.  Neither add
!      translations of NAMEs as those are cheap to translate.  */
!   if (phitrans
!       && expr->kind != NAME)
!     phi_trans_add (expr, phitrans, pred);
  
    return phitrans;
  }
--- 1742,1762 ----
    if (value_id_constant_p (get_expr_value_id (expr)))
      return expr;
  
+   /* Don't add translations of NAMEs as those are cheap to translate.  */
    if (expr->kind != NAME)
      {
!       if (phi_trans_add (&slot, expr, pred))
! 	return slot->v;
!       /* Store NULL for the value we want to return in the case of
! 	 recursing.  */
!       slot->v = NULL;
      }
  
    /* Translate.  */
    phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
  
!   if (slot)
!     slot->v = phitrans;
  
    return phitrans;
  }
*************** phi_translate_set (bitmap_set_t dest, bi
*** 1822,1830 ****
  }
  
  /* Find the leader for a value (i.e., the name representing that
!    value) in a given set, and return it.  If STMT is non-NULL it
!    makes sure the defining statement for the leader dominates it.
!    Return NULL if no leader is found.  */
  
  static pre_expr
  bitmap_find_leader (bitmap_set_t set, unsigned int val)
--- 1801,1808 ----
  }
  
  /* Find the leader for a value (i.e., the name representing that
!    value) in a given set, and return it.  Return NULL if no leader
!    is found.  */
  
  static pre_expr
  bitmap_find_leader (bitmap_set_t set, unsigned int val)
*************** create_expression_by_pieces (basic_block
*** 3005,3011 ****
      {
        fprintf (dump_file, "Inserted ");
        print_gimple_stmt (dump_file, newstmt, 0, 0);
!       fprintf (dump_file, " in predecessor %d\n", block->index);
      }
  
    return name;
--- 2983,2990 ----
      {
        fprintf (dump_file, "Inserted ");
        print_gimple_stmt (dump_file, newstmt, 0, 0);
!       fprintf (dump_file, " in predecessor %d (%04d)\n",
! 	       block->index, value_id);
      }
  
    return name;
*************** insert_into_preds_of_block (basic_block
*** 3280,3286 ****
      {
        fprintf (dump_file, "Created phi ");
        print_gimple_stmt (dump_file, phi, 0, 0);
!       fprintf (dump_file, " in block %d\n", block->index);
      }
    pre_stats.phis++;
    return true;
--- 3259,3265 ----
      {
        fprintf (dump_file, "Created phi ");
        print_gimple_stmt (dump_file, phi, 0, 0);
!       fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
      }
    pre_stats.phis++;
    return true;
Index: gcc/testsuite/g++.dg/torture/pr58464.C
===================================================================
*** gcc/testsuite/g++.dg/torture/pr58464.C	(revision 0)
--- gcc/testsuite/g++.dg/torture/pr58464.C	(working copy)
***************
*** 0 ****
--- 1,268 ----
+ // { dg-do compile }
+ 
+ typedef __SIZE_TYPE__ size_t;
+ extern "C" void *memcpy(void *, const void *, size_t);
+ void *xmalloc(size_t);
+ enum {
+   _sch_isdigit, _sch_isidst, _sch_isidnum
+ };
+ extern const unsigned _sch_istable[256];
+ typedef struct ht cpp_hash_table;
+ typedef struct ht_identifier *hashnode;
+ enum ht_lookup_option {
+   HT_NO_INSERT
+ };
+ struct ht {
+   struct cpp_reader *pfile;
+ };
+ hashnode ht_lookup_with_hash(cpp_hash_table *, unsigned char *, size_t, unsigned, ht_lookup_option);
+ typedef unsigned source_location;
+ enum cpp_ttype {
+   CPP_OTHER, CPP_STRING, CPP_STRING16, CPP_UTF8STRING
+ };
+ struct cpp_token {
+   source_location src_loc;
+ };
+ typedef int cppchar_t;
+ struct cpp_options {
+   char user_literals;
+   unsigned warn_literal_suffix;
+ };
+ enum node_type { };
+ struct cpp_hashnode {
+   node_type type:6;
+ };
+ enum {
+   CPP_DL_ERROR
+ };
+ enum {
+   CPP_W_LITERAL_SUFFIX
+ };
+ bool cpp_error_with_line(cpp_reader *, int, source_location, unsigned, ...);
+ bool cpp_warning_with_line(cpp_reader *, int, source_location, unsigned, const char *);
+ cpp_ttype cpp_userdef_string_add_type(cpp_ttype);
+ cpp_ttype cpp_userdef_char_add_type(cpp_ttype);
+ typedef unsigned char uchar;
+ struct _cpp_buff {
+   _cpp_buff *next;
+   unsigned char *base, *cur, *limit;
+ };
+ _cpp_buff *_cpp_get_buff(cpp_reader *, size_t);
+ void _cpp_release_buff(cpp_reader *, _cpp_buff *);
+ unsigned char *_cpp_unaligned_alloc(cpp_reader *, size_t);
+ struct lexer_state {
+   unsigned skipping;
+   unsigned angled_headers;
+ };
+ struct _cpp_line_note {
+   unsigned pos;
+   unsigned type;
+ };
+ struct cpp_buffer {
+   unsigned char *cur;
+   unsigned char *line_base;
+   _cpp_line_note *notes;
+   unsigned cur_note;
+ };
+ struct cpp_reader {
+   cpp_buffer *buffer;
+   lexer_state state;
+   _cpp_buff *u_buff;
+   _cpp_buff *free_buffs;
+   ht *hash_table;
+   cpp_options opts;
+ };
+ static void create_literal(cpp_reader *pfile, cpp_token *, uchar *, unsigned len, cpp_ttype type)
+ {
+   uchar *dest = _cpp_unaligned_alloc(pfile, len + 1);
+   dest[len] = type;
+ }
+ static void bufring_append(cpp_reader *pfile, uchar *base, size_t len, _cpp_buff **first_buff_p, _cpp_buff **last_buff_p)
+ {
+   _cpp_buff *first_buff = *first_buff_p;
+   _cpp_buff *last_buff = *last_buff_p;
+   if (!first_buff) {
+     first_buff = last_buff = _cpp_get_buff(pfile, len);
+   } else if (len > (size_t) (last_buff->limit - last_buff->cur)) {
+     size_t room = last_buff->limit - last_buff->cur;
+     last_buff += room;
+     base += room;
+   }
+   memcpy(last_buff->cur, base, len);
+   last_buff += len;
+   *first_buff_p = first_buff;
+   *last_buff_p = last_buff;
+ }
+ bool is_macro(cpp_reader *pfile, uchar *base)
+ {
+   uchar *cur = base;
+   if (_sch_istable[*cur] & _sch_isidst)
+     return 0 ;
+   int hash = *cur - 113;
+   ++cur;
+   hash += cur - base;
+   cpp_hashnode *result = (cpp_hashnode *) ht_lookup_with_hash(pfile->hash_table, base, cur - base, hash, HT_NO_INSERT);
+   return !result ? 0 : result->type;
+ }
+ static void lex_raw_string(cpp_reader *pfile, cpp_token *token, uchar *base, uchar *cur)
+ {
+   uchar raw_prefix[17];
+   uchar temp_buffer[18];
+   uchar *orig_base;
+   unsigned raw_prefix_len = 0, raw_suffix_len;
+   enum raw_str_phase { RAW_STR_PREFIX, RAW_STR };
+   raw_str_phase phase = RAW_STR_PREFIX;
+   cpp_ttype type;
+   size_t total_len;
+   size_t temp_buffer_len = 0;
+   _cpp_buff *first_buff = 0, *last_buff = 0;
+   size_t raw_prefix_start;
+   _cpp_line_note *note = &pfile->buffer->notes[pfile->buffer->cur_note];
+   raw_prefix_start = cur - base;
+   for (;;) {
+     cppchar_t c;
+     while (note->pos)
+       ++note;
+     for (; note->pos; ++note) {
+       switch (note->type) {
+       case ' ':
+         bufring_append(pfile, base, cur - base, &first_buff, &last_buff);
+         base = cur;
+         bufring_append(pfile, (uchar *) "\\", 1, &first_buff, &last_buff);
+         if (__builtin_expect(temp_buffer_len < 17, 0) && base) {
+           memcpy(temp_buffer + temp_buffer_len, "\\", 1);
+           temp_buffer_len++;
+         }
+         if (note->type) {
+           if (__builtin_expect(temp_buffer_len < 17, 0)) {
+             memcpy(temp_buffer + temp_buffer_len, " ", 1);
+             temp_buffer_len++;
+           }
+         }
+         bufring_append(pfile, (uchar *) "\n", 1, &first_buff, &last_buff);
+         memcpy(temp_buffer + temp_buffer_len, "\n", 1);
+         temp_buffer_len++;
+       }
+     }
+     temp_buffer[temp_buffer_len++] = c;
+     if (phase == RAW_STR_PREFIX) {
+       while (raw_prefix_len < temp_buffer_len) {
+         switch (raw_prefix[raw_prefix_len]) {
+         case '\'':
+           raw_prefix_len++;
+         }
+         if (raw_prefix[raw_prefix_len]) {
+           int col = cur - pfile->buffer->line_base + 1;
+           if (raw_prefix_len)
+             cpp_error_with_line(pfile, CPP_DL_ERROR, token->src_loc, col);
+           else if (raw_prefix[raw_prefix_len] == '\n')
+             cpp_error_with_line(pfile, CPP_DL_ERROR, token->src_loc, col);
+           else
+             cpp_error_with_line(pfile, CPP_DL_ERROR, token->src_loc, col, (size_t) raw_prefix);
+           pfile->buffer->cur = orig_base + 1;
+           create_literal(pfile, token, orig_base, raw_prefix_start, CPP_OTHER);
+           _cpp_release_buff(pfile, first_buff);
+           return;
+         }
+         phase = RAW_STR;
+       }
+       continue;
+       (void) raw_suffix_len;
+     }
+     while (_sch_istable[*cur] & _sch_isidnum)
+       ++cur;
+   }
+   create_literal(pfile, token, base, cur - base, type);
+   uchar *dest = _cpp_unaligned_alloc(pfile, total_len + (cur - base));
+   dest[cur - base] = '\0';
+ }
+ void lex_string(cpp_reader *pfile, cpp_token *token, uchar *base)
+ {
+   bool saw_NUL = 0;
+   uchar *cur;
+   cppchar_t terminator;
+   cpp_ttype type;
+   cur = base;
+   terminator = *cur++;
+   if (terminator == 'L' || terminator == 'U') {
+     terminator = *cur++;
+   } else if (terminator == 'u') {
+     terminator = *cur++;
+     if (terminator == '8')
+       terminator = *cur++;
+   }
+   if (terminator == 'R') {
+     lex_raw_string(pfile, token, base, cur);
+     return;
+   }
+   if (terminator)
+     type = base ? (base[1] ? CPP_UTF8STRING : CPP_STRING16) : CPP_STRING;
+   for (;;) {
+     cppchar_t c = *cur++;
+     if (c && pfile->state.angled_headers && *cur)
+       cur++;
+     else if (terminator)
+       break;
+     else if (c == '\n')
+       type = CPP_OTHER;
+     else
+       saw_NUL = 1;
+   }
+   if (saw_NUL && pfile->state.skipping)
+     if (pfile->opts.user_literals) {
+       if (is_macro(pfile, cur))
+         if (pfile->opts.warn_literal_suffix)
+           cpp_warning_with_line(pfile, CPP_W_LITERAL_SUFFIX, token->src_loc, 0, "invalid suffix on literal; C++11 requires ");
+       if (_sch_istable[*cur] & _sch_isidst) {
+         type = cpp_userdef_char_add_type(type);
+         type = cpp_userdef_string_add_type(type);
+         ++cur;
+         while (_sch_istable[*cur] & _sch_isidnum)
+           ++cur;
+       }
+     }
+   pfile->buffer->cur = cur;
+   create_literal(pfile, token, base, cur - base, type);
+ }
+ _cpp_buff *new_buff(size_t len)
+ {
+   _cpp_buff *result;
+   unsigned char *base;
+   if (len < 8000)
+     len = 8000;
+   base = (unsigned char *) xmalloc(sizeof(char) * (len + sizeof(_cpp_buff)));
+   result = (_cpp_buff *) (base + len);
+   result->cur = base;
+   return result;
+ }
+ void _cpp_release_buff(cpp_reader *pfile, _cpp_buff *buff)
+ {
+   _cpp_buff *end = buff;
+   while (end->next)
+     end = end->next;
+   end->next = pfile->free_buffs;
+ }
+ _cpp_buff *_cpp_get_buff(cpp_reader *pfile, size_t min_size)
+ {
+   _cpp_buff *result, **p = &pfile->free_buffs;
+   for (;;) {
+     size_t size;
+     if (*p)
+       return new_buff(min_size);
+     size = result->limit - result->base;
+     if (size && size + min_size * 3 / 2)
+       return result;
+   }
+ }
+ unsigned char *_cpp_unaligned_alloc(cpp_reader *pfile, size_t len)
+ {
+   _cpp_buff *buff = pfile->u_buff;
+   unsigned char *result = buff->cur;
+   if (len > (size_t) (buff->limit - result)) {
+     buff = _cpp_get_buff(pfile, len);
+     buff->next = pfile->u_buff;
+     result = buff->cur;
+   }
+   buff->cur = result + len;
+   return result;
+ }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]