[PATCH] check alias sets in add_inter_loop_mem_dep (ddg.c)

Bingfeng Mei bmei@broadcom.com
Mon Jan 19 13:13:00 GMT 2009


Correction: -fstrict-alias instead of -fno-strict-aliasing. With the patch, both loops in foo1 and foo2 can be pipelined. 

/* { dg-do run } */
/* { dg-options "-O2 -fmodulo-sched -w" } */
void foo( int * __restrict__ a, int * __restrict__ b, int * __restrict__ c) <--- 'a', 'b' and 'c' belong to different alias sets.
{
   int i;
   for(i = 0; i < 100; i+=4)
     {
       a[i] = b[i] * c[i];
       a[i+1] = b[i+1] * c[i+1];
       a[i+2] = b[i+2] * c[i+2];
       a[i+3] = b[i+3] * c[i+3];
     }
}   


void foo2( int *  a, short *  b, short *  c) <--- 'b' and 'c' belong to different alias set than 'a' here 
{
   int i;
   for(i = 0; i < 100; i+=4)
     {
       a[i] = b[i] * c[i];
       a[i+1] = b[i+1] * c[i+1];
       a[i+2] = b[i+2] * c[i+2];
       a[i+3] = b[i+3] * c[i+3];
     }
}   

int a[100], b[100], c[100];
int main()
{
  int i, res;
  for(i = 0; i < 100; i++)
    {
      b[i] = c[i] = i;
    }  
  foo(a, b, c);
  
  res = 0;  
  for(i = 0; i < 100; i++)
    {
      res += a[i];
    }
  if(res != 328350)
    abort();
  
  return 0;        
}

 

> -----Original Message-----
> From: Revital1 Eres [mailto:ERES@il.ibm.com] 
> Sent: 19 January 2009 09:59
> To: Bingfeng Mei
> Cc: Andrey Belevantsev; Ayal Zaks; gcc-patches@gcc.gnu.org
> Subject: RE: [PATCH] check alias sets in 
> add_inter_loop_mem_dep (ddg.c)
> 
> Hello,
> 
> > I asked on the GCC mailing list about the DDG export patch 
> a few months
> ago. I
> > tried to merged it recently into the mainline, without much 
> success. A
> > immediate issue I have with modulo scheduling is that it 
> doesn't handle
> > restrict keyword. I just adapt these the walker functions 
> in the above
> patch,
> > which I think is generic and simple.
> 
> OK, thanks.
> I am a little confused regarding how alias_sets_conflict_p will handle
> cross-iteration dependencies when constructing DDG for SMS.
> 
> From previous talks with Andrey I understood that data dependency
> graph construction for SMS can not use rtl alias analysis 
> because of the
> following explanation:
> When adding cross-iteration dependencies, because rtl AA includes
> base+offset disambiguation, which allows to disambiguate a[i] 
> and a[i+1]
> on targets with base+offset memory addressing; while a[i] and a[i+1]
> are independent within one iteration, cross-iteration dependency still
> must be added; thus, DDG construction adds dependency edges for all
> pairs of memory references.
> 
> Revital
> 
> >
> > Cheers,
> > Bingfeng
> >
> > > -----Original Message-----
> > > From: Revital1 Eres [mailto:ERES@il.ibm.com]
> > > Sent: 19 January 2009 06:27
> > > To: Bingfeng Mei
> > > Cc: Andrey Belevantsev; Ayal Zaks; gcc-patches@gcc.gnu.org
> > > Subject: Re: [PATCH] check alias sets in
> > > add_inter_loop_mem_dep (ddg.c)
> > >
> > > Hello,
> > >
> > > It seems that a similar function can be found in the export
> > > DDG patch: http://gcc.gnu.org/ml/gcc/2007-08/msg00342.html
> > > (please see independent_by_exported_info () in
> > > http://gcc.gnu.org/ml/gcc/2007-08/txt00017.txt)
> > > However, alias_sets_conflict_p is not used there.
> > >
> > > Andrey, I appreciate it if you could explain the 
> difference between
> > > those two functions.
> > >
> > > Thanks,
> > > Revital
> > >
> > > > I have a following patch to detect if memory references of two
> > > instructions
> > > > belong to non-conflicting alias sets. It is used in
> > > inter-loop dependence
> > >
> > > > analysis (ddg.c) by modulo scheduler. For the following
> > > testcase, GCC
> > > will
> > > > produce better code due to better memory dependency 
> info. In fact,
> > > powperpc-
> > > > gcc cannot software pipeline this loop without the patch. OK for
> > > mainline?
> > > > Should I also include this test in the patch?
> > > >
> > > > /* {dg-do run} */
> > > > /* {dg-options "-O2 -fmodulo-sched -w"} */
> > > > void foo( int * __restrict__ a, int * __restrict__ b, int *
> > > __restrict__
> > > c)
> > > > {
> > > >    int i;
> > > >    for(i = 0; i < 100; i+=4)
> > > >      {
> > > >        a[i] = b[i] * c[i];
> > > >        a[i+1] = b[i+1] * c[i+1];
> > > >        a[i+2] = b[i+2] * c[i+2];
> > > >        a[i+3] = b[i+3] * c[i+3];
> > > >      }
> > > > }
> > > >
> > > >
> > > > int a[100], b[100], c[100];
> > > > int main()
> > > > {
> > > >   int i, res;
> > > >   for(i = 0; i < 100; i++)
> > > >     {
> > > >       b[i] = c[i] = i;
> > > >     }
> > > >   foo(a, b, c);
> > > >
> > > >   res = 0;
> > > >   for(i = 0; i < 100; i++)
> > > >     {
> > > >       res += a[i];
> > > >     }
> > > >   if(res != 328350)
> > > >     abort();
> > > >
> > > >   return 0;
> > > > }
> > > >
> > > > This is the first time I try to submit a patch. Hope it
> > > conforms to the
> > > coding
> > > > style, patch format, etc. Additionally, my company
> > > (Broadcom) has already
> > >
> > > > signed coporate copyright form with FSF.
> > > >
> > > > Bingfeng Mei
> > > > Broadcom UK
> > > >
> > > >
> > > > 2009-01-15 Bingfeng Mei <bmei@broadcom.com>
> > > >
> > > >    *alias.c (walk_mems_1, walk_mems_2,
> > > insn_alias_sets_conflict_p): Check
> > > >    whether two instructions have memory references that 
> belong to
> > > conflicting
> > > > alias sets.
> > > >    walk_mems_1 and walk_mems_2 are helper functions for 
> traversing
> > > >    *alias.h (insn_alias_sets_confilict_p): new prototypes
> > > >    *ddg.c (add_inter_loop_mem_dep): call
> > > insn_alias_sets_conflict_p not
> > > to
> > > > draw dependency edge
> > > >    for instructions with non-conflicting alias sets.
> > > >
> > > > Index: gcc/ddg.c
> > > > 
> ===================================================================
> > > > --- gcc/ddg.c   (revision 143391)
> > > > +++ gcc/ddg.c   (working copy)
> > > > @@ -345,6 +345,10 @@
> > > >  static void
> > > >  add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from,
> > > ddg_node_ptr to)
> > > >  {
> > > > +  if (!insn_alias_sets_conflict_p (from->insn, to->insn))
> > > > +    /* Do not create edge if memory references have
> > > disjoint alias sets.
> > > */
> > > > +    return;
> > > > +
> > > >    if (mem_write_insn_p (from->insn))
> > > >      {
> > > >        if (mem_read_insn_p (to->insn))
> > > > Index: gcc/alias.c
> > > > 
> ===================================================================
> > > > --- gcc/alias.c   (revision 143391)
> > > > +++ gcc/alias.c   (working copy)
> > > > @@ -344,6 +344,43 @@
> > > >    return 0;
> > > >  }
> > > >
> > > > +static int
> > > > +walk_mems_2 (rtx *x, rtx mem)
> > > > +{
> > > > +  if (MEM_P (*x))
> > > > +    {
> > > > +      if (alias_sets_conflict_p (MEM_ALIAS_SET(*x),
> > > MEM_ALIAS_SET(mem)))
> > > > +        return 1;
> > > > +
> > > > +      return -1;
> > > > +    }
> > > > +  return 0;
> > > > +}
> > > > +
> > > > +static int
> > > > +walk_mems_1 (rtx *x, rtx *pat)
> > > > +{
> > > > +  if (MEM_P (*x))
> > > > +    {
> > > > +      /* Visit all MEMs in *PAT and check indepedence.  */
> > > > +      if (for_each_rtx (pat, (rtx_function) walk_mems_2, *x))
> > > > +        /* Indicate that dependence was determined and
> > > stop traversal.
> > > */
> > > > +        return 1;
> > > > +
> > > > +      return -1;
> > > > +    }
> > > > +  return 0;
> > > > +}
> > > > +
> > > > +/* Return 1 if two specified instructions have mem expr
> > > with conflict
> > > alias sets*/
> > > > +bool
> > > > +insn_alias_sets_conflict_p (rtx insn1, rtx insn2)
> > > > +{
> > > > +  /* For each pair of MEMs in INSN1 and INSN2 check their
> > > independence.
> > > */
> > > > +  return  for_each_rtx (&PATTERN (insn1), (rtx_function)
> > > walk_mems_1,
> > > > +          &PATTERN (insn2));
> > > > +}
> > > > +
> > > >  /* Return 1 if the two specified alias sets will always
> > > conflict.  */
> > > >
> > > >  int
> > > > Index: gcc/alias.h
> > > > 
> ===================================================================
> > > > --- gcc/alias.h   (revision 143391)
> > > > +++ gcc/alias.h   (working copy)
> > > > @@ -41,6 +41,7 @@
> > > >  extern int alias_sets_must_conflict_p (alias_set_type,
> > > alias_set_type);
> > > >  extern int objects_must_conflict_p (tree, tree);
> > > >  extern int nonoverlapping_memrefs_p (const_rtx, const_rtx);
> > > > +extern bool insn_alias_sets_conflict_p (rtx, rtx);
> > > >
> > > >  /* This alias set can be used to force a memory to
> > > conflict with all
> > > >     other memories, creating a barrier across which no
> > > memory reference
> > >
> > >
> > >
> 
> 
> 



More information about the Gcc-patches mailing list