Path: utzoo!attcan!uunet!cs.utexas.edu!usc!orion.oac.uci.edu!uci-ics!rfg From: rfg@ics.uci.edu (Ron Guilmette) Newsgroups: comp.sys.m88k Subject: Re: Information wanted on m88000 Risc workstations Message-ID: <25AFDC1A.11327@paris.ics.uci.edu> Date: 14 Jan 90 01:55:38 GMT References: <641@s5.Morgan.COM> <25A64468.11498@paris.ics.uci.edu> <648@s5.Morgan.COM> <1879@xyzzy.UUCP> <2811@yogi.oakhill.UUCP> Reply-To: rfg@ics.uci.edu (Ron Guilmette) Organization: UC Irvine Department of ICS Lines: 55 In article tom@ssd.csd.harris.com (Tom Horsley) writes: > >However, there is a real problem with loop unrolling that depends on language >semantics. In FORTRAN compilers it may well be possible to profitably unroll >many loops, due to some of the aliasing restrictions that the FORTRAN standard >imposes on arguments. In the long term in Ada, it is also possible because >Ada requires a global program database which could someday be used to do the >sorts of interprocedural analysis required to determine that no aliasing >occurs. But on U**x systems, most code is written in C, increasingly even >numerical code is written in C. But C pointers can point pretty much anywhere. >Compilers generally have to make worst case assumptions... NOT true! I have been arguing over this very issue with a professor here recently. He is particularly interested in issues of instruction scheduling for VLIW machines and I have been telling him (repeatedly) that you will never achieve enough parallelism to make it worth your while on machines like that (or even on the lowly 88k) if you are compiling from C source code and if you do not do some heafty (but plausible) alias analysis based on as much information as can be gleaned from the source code. For instance, although pointers can in in theory point almost anywhere, there are in fact many cases where it is obvious that the set of things that could in fact be pointed to is some identifiable subset of the entire address space. For example: { char array[100]; char *end = &array[99]; char *p = array; while (p <= end) *p = ' '; } Guess where p always points to! Now guess where end always points to. You can work your way up to significantly more complex examples from here. Some particularly good work was done on alias analysis for C at Hewlett Packard (for the PA) and was written up a "Retargetable High Level Alias Analysis" in the 1986 ACM POPL Proceedings. Even though that's the best paper I have seen on the subject yet, I think that they may have missed a few possible additional tricks which might allow them to infer additional limitations on the set of things that a pointer can point to, but it is hard to tell. They did do a pretty detailed analysis, but I guess that my own ego makes me want to believe that (if given enough time) I could do better. With a really robust alias analysis mechanism, you start to get into some interesting questions regarding storing aliasing information for "library" modules as well as for the code your are currently compiling. How much do you store? How do you represent it? If anybody has ideas about such things, I (for one) am all ears. // rfg