[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

127.0. "Overlapping Operands" by HARE::GILBERT () Thu Aug 16 1984 00:13

Most computer languages have arrays.  Some compilers generate different code
depending on whether operands do/don't/might overlap.  The range of addresses
occupied by element x(i1,...,im) and element y(j1,...,jn) in nonhomogenous
arrays are, in general, given by:

	x + i0 + s1*i1 + ... + sm*im	y + j0 + t1*j1 + ... + tm*jn

where (bounds on array indices):

	0 <= i0 <= k0			0 <= j0 <= l0
	0 <= i1 <= k1			0 <= j1 <= l1
	...				...
	0 <= im <= km			0 <= jm <= ln

and (subarrays are properly nested):

	k0 < s1				l0 < t1
	k0+s1*k1 < s2			l0+t1*l1 < t2
	...				...
	k0+...+s(m-1)*k(m-1) < sm	l0+...+t(n-1)*l(n-1) < tn

The problem is this:
Given the above, and values for x, y, m, n, k(*), l(*), s(*) and t(*), is there
a fairly simple test to determine whether there are i(*) and j(*) such that:

	x + i0 + s1*i1 + ... + sm*im =	y + j0 + t1*j1 + ... + tm*jn

In other words, to determine whether two array reference might overlap.

If not, can a fairly simple test be supplied for the cases m,n < 3?  m,n < 2?
T.RTitleUserPersonal
Name		DateLines
127.1AURORA::HALLYBThu Aug 16 1984 11:3210
Unless I'm mistaken (which is often the case) this is the same kind of
problem that faces FORTRAN compiler writers.  It is necessary in FORTRAN
to make sure that fancy use of EQUIVALENCE is legal and how data must be
assigned memory locations in order to accomplish the desired overlaps.
Furthermore if some of the variables are in COMMON you need to be extra
careful not to rearrange things.

So my suggestion is to ask our language folks what FORTRAN does in such cases.

						John
127.2TURTLE::GILBERTSun Aug 19 1984 22:584
Although the source of some interesting algorithms in its own right,
the Fortran Equivalence problem doesn't seem applicable.  There, each
equivalence determines (or verifies) the offset between base addresses
of the two structures.
127.3AURORA::HALLYBTue Aug 28 1984 16:3312
It still looks like the same problem to me.  E.g.,

	INTEGER ALPHA(10,23),BETA(100),GAMMA(5,5,5)
	EQUIVALENCE(ALPHA(2,3),BETA(1))
	EQUIVALENCE(BETA(96),GAMMA(1,2,3))

Does ALPHA overlap GAMMA?  If so, where?  FORTRAN has
to be able to determine if this is legal.  At least, I
thought this was the same kind of problem you were trying
to solve in .0

						John
127.4TURTLE::GILBERTTue Aug 28 1984 19:2323
Oops.  I failed to make response 2 clear.

In Fortran, each array is "dense"; it occupies ALL locations from array(1,...,1)
through array(1,...,1) + <size-of-array>.  This means the test for overlap is
fairly simple -- is (hi-addr-1 >= lo-addr-2) and (hi-addr-2 >= lo-addr-1) ?

Consider the following (in pseudo-Pascal).  Can A[i].C ever overlap D[j].E[k] ?

    var	v: record
	   z: integer;
	   case z of
	    [0]: a: array[0..9] of
		    record
		    b: array [0..4] of real;
		    c: char;
		    end;
	    [1]: d: array[0..12] of
		    record
		    e: array [0..3] of real;
		    f: array [0..5] of real;
		    end;
	   end;
	   end;