Path: utzoo!mnetor!uunet!husc6!uwvax!umn-d-ub!umn-cs!hall!rig
From: rig@hall.cray.com (Richard Gisselquist)
Newsgroups: comp.lang.c
Subject: noalias and vectors
Message-ID: <2942@hall.cray.com>
Date: 12 Jan 88 16:19:49 GMT
Organization: Cray Research, Inc., Mendota Heights, MN
Lines: 75
Keywords: noalias, auto-vectorizing


After following the discussion about the "noalias" for several weeks,
some of the implications of this keyword became clear to me. Of 
course, after I figured it out, I discovered that Fred Gwyn had also stated
it to the network. Let me try to summarize the situation with vector
instruction sets (read Cray Research) and the C language.

First statement. An automatic vectorizing compiler is a marketing requirement
at Cray.

First example. (roughly translated from the Fortran vectorization handbook)

void
sub1( a, b, c, i )
int *a, *b, *c;
int i;
{
	int j;
	for( j=0; j<i; j++) *a++ = *b++ + *c++;
}

A Fortran compiler is permitted to generate vector code for a program like
this. Why? Because the Fortran standard states that hidden equivalences are
not permitted. Thus, if a,b and c appear to refer to different locations in
memory, in Fortran they do. However, a C compiler is not permitted to assume
that pointers reference disjoint areas; indeed, sub1( a+1, a+1, a, N) will
sum a vector into its last element.

There are several different ways to get around this difficulty. They include:

	A) Compiler directives, for example "pragma(SAFE_VECTORIZING)".
	The difficulty here is that the code that comprises the program
	is in two different places: in the program itself and in the
	side-band information that instructs the compiler how to generate
	instructions. Of course, a compiler that depends on compiler
	directives is not quite automatic in its vectorization.

	B) Vectorize only the safe constructions. We have a compiler like
	this. It generates exactly three vectorized loops every time we
	rebuild all the system software. An average C program just does
	not contain a lot of arrays that are completely seen by the
	compiler in the module where they are processed. This is an
	automatic vectorizing compiler, but it has limited utility.

	C) Change the language to include the "vector" concept. This has
	the advantage of directness. It has been tried [SIGPLAN Notices,
	Kuo-Cheng Li in the January, 86 issue and myself in one of the
	late autumn issues]. However, this is not automatic vectorization.

	D) Generate both code paths and determine at run-time if the
	array references are disjoint enough to permit using the path
	with the vector instructions. Don't worry about the size, we've
	got real memory bigger than most computers have virtual. This is
	certainly automatic vectorization, but complicated.

	E) Generate vector code, but decide at run-time on a maximum
	value of the vector length such that vector references are
	sufficiently disjoint. This is automatic vectorization and it
	has been attempted, but the inner scalar loops that have been
	executed using vector registers with a vector length of one
	have left a bad taste.

"But there was a third possibility" (Arlo Guthrie, Alice's Restaurant). That
being to use the new "noalias" keyword to mean that loops involving this
variable may be safely vectorized if it looks like they may be vectorized.
The change to the standard still will not permit "dusty deck" C programs
to be vectorized without changes, but it will permit vectorized code after
only "standard" changes.

The "noalias" keyword has meaning for scalar optimization and for other
non-vector parallel constructs. I write because the "aha" experience
made clear to me the relationship between "noalias" and automatic
vectorization.

Solely the personal opinions of Richard Gisselquist.