Re: Fix PR 33870

["Richard Guenther" <richard.guenther@gmail.com>]

On 11/8/07, Diego Novillo <dnovillo@google.com> wrote:
> This patch fixes PR 33870.  There were a couple of things at play here
> related to the way we compute sub-variables for structures and arrays.
>  Particularly in the presence of nesting.
>
> When alias analysis computes points-to information for a structure for
> which we have sub-variables, it never adds all the variables to the
> set.  It only adds the first SFT reachable by the pointer.
>
> So, if we have a pointer p_1 pointing into some structure and we
> dereference a field with p_1->fld, we can find out what offset to use
> by calling get_base_ref_and_extent.  However, if that field is inside
> a nested structure, the offset computed by get_ref_base_and_extent is
> the offset from the start of the immediately containing structure.
> However, to find out what other SFTs are affected by this reference,
> we need to know the offsets starting at the root structure in the
> nesting hierarchy.
>
> For instance, given the following structure:
>
>        struct X {
>          int a;
>          struct Y {
>            int b;
>            struct Z {
>              int c[3];
>            } d;
>          } e;
>        } m;
>
> and the following address expression:
>
>        p_1 = &m.e.d;
>
> This structure will receive 5 SFTs, namely 2 for fields 'a' and 'b'
> and 3 for the array 'c' in struct Z.  So, the reference p_1->c[2] and
> m.e.d.c[2] access the exact same memory location (ie, SFT.5).
>
> Now, alias analysis computed the points-to set for pointer p_1 as  {
> SFT.3 } because that is the first field that p_1 actually points to.
> When the expression p_1->c[2] is analyzed, get_ref_base_and_extent
> will return an offset of 96 because we are accessing the third element
> of the array.  But the SFT we are looking for is actually at offset
> 160, counting from the top of struct X.
>
> Therefore, we need to adjust the offset given by
> get_base_ref_and_extent by the offset of VAR so that we can get at all
> the fields starting at VAR.
>
> Notice that this adjustment is ONLY necessary if the pointer is
> pointing inside a nested structure.  If p_1 is pointing at the base
> structure of the nesting hierarchy, then no adjustment is necessary.
>
> Since this adjustment was being applied with every field reference, we
> were failing to add SFTs when some of the SFTs in the structure had
> been partitioned away into an MPT.
>
> In the specific case of PR 33870, there was a single field 'pDirty'
> inside a large structure that was being referenced with a pointer and
> with a regular variable.  The field had the subvariable SFT.12
> associated with it, with an offset of X bytes.
>
> Since SFT.12 was the only field that had not been partitioned away,
> when we were adding SFTs in the operand scanner, we would blindly
> adjust the offset of SFT.12 by X bytes and then trying to see if there
> was any SFT at offset X + X.
>
> There wasn't any, of course, and so no VOP was added to the memory
> load expression, which was then taken out of the loop because it was
> thought to be loop independent.  Leading to the runtime failure.
>
> The only reason this didn't occur if partitioning was disabled was
> that the same blind offset adjustment was adding SFT.12 because it had
> ajdusted the offset of an SFT that was X bytes earlier in the
> structure.  So, it was working by chance.
>
> By recognizing that this offset adjustment is only required for nested
> structures, we do not need to blindly adjust every offset and so we
> don't end up adding SFTs by accident.
>
> Tested on x86_64.  Committed.

You are only working around the problem and do not address the fundamental
issue.  The following still fails:

extern void abort (void);

typedef struct PgHdr PgHdr;
typedef unsigned char u8;
struct PgHdr {
int y;
struct {
  unsigned int pgno;
  PgHdr *pNextHash, *pPrevHash;
  PgHdr *pNextFree, *pPrevFree;
  PgHdr *pNextAll;
  u8 inJournal;
  short int nRef;
  PgHdr *pDirty, *pPrevDirty;
  unsigned int notUsed;
} x;
};
volatile PgHdr **xx;
static inline PgHdr *merge_pagelist(PgHdr *pA, PgHdr *pB)
{
  PgHdr result;
  PgHdr *pTail;
  xx = &result.x.pDirty;
  pTail = &result;
  while( pA && pB ){
    if( pA->x.pgno<pB->x.pgno ){
      pTail->x.pDirty = pA;
      pTail = pA;
      pA = pA->x.pDirty;
    }else{
      pTail->x.pDirty = pB;
      pTail = pB;
      pB = pB->x.pDirty;
    }
  }
  if( pA ){
    pTail->x.pDirty = pA;
  }else if( pB ){
    pTail->x.pDirty = pB;
  }else{
    pTail->x.pDirty = 0;
  }
  return result.x.pDirty;
}

PgHdr * __attribute__((noinline)) sort_pagelist(PgHdr *pIn)
{
  PgHdr *a[25], *p;
  int i;
  __builtin_memset (a, 0, sizeof (a));
  while( pIn ){
    p = pIn;
    pIn = p->x.pDirty;
    p->x.pDirty = 0;
    for(i=0; i<25 -1; i++){
      if( a[i]==0 ){
        a[i] = p;
        break;
      }else{
        p = merge_pagelist(a[i], p);
        a[i] = 0;
        a[i] = 0;
      }
    }
    if( i==25 -1 ){
      a[i] = merge_pagelist(a[i], p);
    }
  }
  p = a[0];
  for(i=1; i<25; i++){
    p = merge_pagelist (p, a[i]);
  }
  return p;
}

int main()
{
  PgHdr a[5];
  PgHdr *p;
  a[0].x.pgno = 5;
  a[0].x.pDirty = &a[1];
  a[1].x.pgno = 4;
  a[1].x.pDirty = &a[2];
  a[2].x.pgno = 1;
  a[2].x.pDirty = &a[3];
  a[3].x.pgno = 3;
  a[3].x.pDirty = 0;
  p = sort_pagelist (&a[0]);
  if (p->x.pDirty == p)
    abort ();
  return 0;
}

taking the address of result.x.pDirty causes the SFT to be marked as
in substructure
and the problem re-surfaces.

Richard.