Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!hc!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.arch
Subject: Re: complexity
Message-ID: <12854@lanl.gov>
Date: 28 Apr 89 19:16:19 GMT
References: <4844@pt.cs.cmu.edu>
Organization: Los Alamos National Laboratory
Lines: 28

schow@bnr-public.uucp (Stanley Chow) says:
>"Compilers can do optimizations", I hear the yelling. This is another
>interesting phenomenon - reduce the complexity in the CPU so that the 
>compiler must do all these other optimizations. I have also now seem any
>indications that a compiler can to anywhere close to an optimal job on
>scheduling code or pipelining. Even discounting the NP-completeness of
>just about everything, theoratical indications point the other way,
>especially when the compiler has to juggle so many conflicting constraints.
>
>It would be interesting to speculate on total system complexity, is it
>higher for CISC or for RISC (with its attendent memory and compiler
>requirements).

Actually, increasing the complexity of instructions also _increases_ the
complexity of the compiler.  This happens because the compiler now has an
additional degree of freedom in its optimization search-space: instruction
selection!  The triad of scheduling, register allocation, and instruction
selection all feed back on one another.  If the first two are already 
NP complete, the problem is obviously made much worse by the introduction
of alternate instructions.
.
.
.
.
.
.
.
.