From: Chris Wilson <cwilson@CS.Stanford.EDU>
Date: Wed, 26 Jun 96 20:31:19 PDT
Subject: Re: cookbook: prog3
Message-Id: <CMM.0.90.4.835846279.cwilson@Xenon.Stanford.EDU>
Sorry for the delay in replying to this message. I was on vacation.
> Hi,
> I have installed the suifcookbook package. 'prog3' runs succesfully
> on the input program 'input3.c' provided by the package, but I face a
> problem with the following simple program:
>
> ********************
> #define N 1024
>
> int i, j, k;
> int x[N][N], y[N][N], z[N][N];
>
> main()
> {
>
>
> for (i=0; i<N; i++)
> for (k=0; k<N; k++)
> for (j=0; j<N; j++)
> z[i][j] += x[i][k] * y[k][j];
>
>
> }
> ****************
>
> The output I get ::
>
> Dependency test statistics
> one_var_succ = 0
> one_var_fail = 0
> cycle_ok = 0
> cycle_not_ok = 0
> lr_ok = 0
> lr_not_ok = 0
> fourier_ok = 0
> fourier_not_ok = 0
> const_test = 0
> num_indep = 0
> num_dep = 0
>
> num_check_bounds = 0
> num_first_call_fourier = 0
> num_call_fourier = 0
> max_bb_lev = 0
> num_in_ineqs = 0
> max_in_ineqs = 0
> reply_true = 0
>
> =======main=======
> For loop i (Outermost)
> For loop k
> For loop j
>
> **** Program: prog3
> **** Assertion failure in file "arrayinfo.cc" at line 257 (module
> libuseful.a)
> **** False expression: i->dst_op().is_instr()
> IOT trap (core dumped)
> *******************************
>
> Is this expected ? or am I doing something wrong ?
>
> Thanks,
> Somnath
This problem is caused by a bug in useful/arrayinfo.cc. Here's a
patch to fix the problem:
--cut-here----cut-here----cut-here----cut-here----cut-here----cut-here--
*** basesuif-1.1.2/src/basesuif/useful/arrayinfo.cc Sun Apr 7 23:54:31 1996
--- arrayinfo.cc Wed Jun 26 20:06:04 1996
***************
*** 254,260 ****
if(!array_ok)
if(i->opcode() == io_array) return FALSE; // B[A[]]
! assert(i->dst_op().is_instr());
instruction * ins = i->dst_op().instr();
if(ins->opcode() == io_memcpy) {
--- 254,261 ----
if(!array_ok)
if(i->opcode() == io_array) return FALSE; // B[A[]]
! if (!i->dst_op().is_instr())
! return FALSE;
instruction * ins = i->dst_op().instr();
if(ins->opcode() == io_memcpy) {
--cut-here----cut-here----cut-here----cut-here----cut-here----cut-here--
Thanks for the bug report. This fix will be included in the next
release of SUIF.
This bug is only triggered when an array reference calculation is
written into a temporary variable. That is the case in your example
because you used the C ``+='' and then didn't run all the usual passes
to set up for good parallelization, such as forward propagation
passes. It's legal to do what you did, but most people don't because
it's more effective to run all set-up passes for parallelization
before doing dependence analysis, which is why nobody noticed the bug
before.
--Chris
From: Vineeth Kumar <vineeth@csa.iisc.ernet.in>
Date: Wed, 26 Jun 1996 16:13:38 +0500 (GMT+0500)
Subject: Scalar Dependence
Message-Id: <199606261113.QAA02982@veda.csa.iisc.ernet.in>
Dear Chris Wilson,
Please recall our earlier discussion regarding the issue of whether there exist
routines for scalar dependence analysis. The text of the discussion is ecnlosed
here for reference.
Let me clearly mention what I am looking for:
GIven a statement S1 I would like to have have all other statements which are
dependent on it; true, anti, and output dependences.
Prog4 in Cookbook finds the same for array references in loops calling routine
"DependenceTest".
In your earlier answer you have mentioned about the routine "overlaps()" which
will check the dependence, whether there exist a memory overlap, for two scalar
variables. But this won't serve my purpose because it will JUST CHECK the
dependence given the two variables. This means that I have to write the my own
program to get the solution I want; that is getting all dependent statements
(and finally the corresponding variables) for a given statement. Is that right?
I was thinking that since scalars can be considered as arrays of dimension zero,
as you have mentioned, I could use "DependenceTest()" for scalars. But it seems
that I am not right in my guess.
Will you please suggest what I can do to get my problem solved?
Thank you,
Vineeth.
********************************************************************************
Text of our earlier discussion.
********************************************************************************
> Someone there for help?
>
> >From the SUIF documents I understand that routines for dependence analysis is
> available only for array references. Am I right?
Yes, that is correct.
> If yes, is there anyone who had written dependence analysis routines for scalars?
>
> Vineeth.
The answer depends on what you mean by dependence analysis for
scalars.
If by ``dependence analysis for scalars'' you mean the exact analog
for scalars of what the SUIF dependence library gives for arrays, the
answer is that the solution turns out to be so trivial there's no need
for a separate routine to compute it. Let me explain.
The SUIF library's dependence library takes two expression trees that
compute addresses and computes some information about when they can
refer to the same memory location. It assumes they are both array
reference instructions. The dependence library first looks at the
base addresses of the arrays. If the addresses are both the addresses
of the same array variable, then it looks at the index expressions for
more information. If the array variables are different, the
dependence library knows they cannot depend on one another. If the
dependence library can't tell if they point to the same array (for
example, if one or both base addresses are pointer variables), the
dependence library gives up and says it can't tell anything about the
dependence between the two addresses.
Scalars are just a special case of arrays in which the number of
dimensions is zero. Think about the above description of the SUIF
array dependence library in those terms. You are given two different
expressions for scalar addresses. In this case, there is no dimension
information at all, the whole address in each case is the base
address. So the same algorithm that is used for array dependence
would first check to see if both addresses are simple addresses of
known variables. If so, it's trivial to see if the scalar variables
overlap (the var_sym::overlaps() method tells you that). If either
expression is not a simple variable address, the algorithm would give
up and assume there might be a dependence.
So you see that the analog of the array dependence algorithm for
scalars would just check two expressions to see if they are simple
addresses of scalar variables, and if so check the scalars to see if
they are the same or occupy overlapping memory locations. And any
memory operations that use a simple address of a variable would likely
be replaced by a simple use of the variable (which is done
automatically by ``porky -fold'' or the folding routines in
libuseful); or, more likely, such memory operations with simple
addresses of variables would never have been created in the first
place. So the direct analog of the array dependence analysis done by
the SUIF dependence library is trivial, and is, in effect, taken care
of automatically by local folding such as ``porky -fold''. When
source and destination operands are simple scalar variables, a call to
var_sym::overlaps() determines precisely whether or not there is a
scalar dependence.
Of course there are many cases when memory operations on scalars go
through pointer variables, and it would be useful to try to figure out
whether there is a dependence between such memory operations. You
might think of that as scalar dependence analysis. But it's just an
example of the pointer alias analysis problem, which can give
information for both scalar and array dependence analysis. The
pointer alias analysis problem is a difficult one. Research work on
such analysis has been done using SUIF, but there is no released
system for doing that analysis.
--Chris