[PATCH][3/n] tree LIM TLC

[Richard Biener]

This exploits symmetry in memory reference disambiguation.  That
should reduce the number of queries and space needed in the
cache bitmaps.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Richard.

2013-03-12  Richard Biener  <rguent...@suse.de>

        PR tree-optimization/39326
        * tree-ssa-loop-im.c (refs_independent_p): Exploit symmetry.

Index: trunk/gcc/tree-ssa-loop-im.c
===================================================================
*** trunk.orig/gcc/tree-ssa-loop-im.c   2013-03-12 11:41:58.000000000 +0100
--- trunk/gcc/tree-ssa-loop-im.c        2013-03-12 11:44:11.507745552 +0100
*************** ref_always_accessed_p (struct loop *loop
*** 2163,2177 ****
  static bool
  refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
  {
!   if (ref1 == ref2
!       || bitmap_bit_p (ref1->indep_ref, ref2->id))
      return true;
!   if (bitmap_bit_p (ref1->dep_ref, ref2->id))
!     return false;
    if (!MEM_ANALYZABLE (ref1)
        || !MEM_ANALYZABLE (ref2))
      return false;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "Querying dependency of refs %u and %u: ",
             ref1->id, ref2->id);
--- 2163,2188 ----
  static bool
  refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
  {
!   if (ref1 == ref2)
      return true;
! 
    if (!MEM_ANALYZABLE (ref1)
        || !MEM_ANALYZABLE (ref2))
      return false;
  
+   /* Reference dependence in a loop is symmetric.  */
+   if (ref1->id > ref2->id)
+     {
+       mem_ref_p tem = ref1;
+       ref1 = ref2;
+       ref2 = tem;
+     }
+ 
+   if (bitmap_bit_p (ref1->indep_ref, ref2->id))
+     return true;
+   if (bitmap_bit_p (ref1->dep_ref, ref2->id))
+     return false;
+ 
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "Querying dependency of refs %u and %u: ",
             ref1->id, ref2->id);
*************** refs_independent_p (mem_ref_p ref1, mem_
*** 2180,2186 ****
                            &memory_accesses.ttae_cache))
      {
        bitmap_set_bit (ref1->dep_ref, ref2->id);
-       bitmap_set_bit (ref2->dep_ref, ref1->id);
        if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "dependent.\n");
        return false;
--- 2191,2196 ----
*************** refs_independent_p (mem_ref_p ref1, mem_
*** 2188,2194 ****
    else
      {
        bitmap_set_bit (ref1->indep_ref, ref2->id);
-       bitmap_set_bit (ref2->indep_ref, ref1->id);
        if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "independent.\n");
        return true;
--- 2198,2203 ----