Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!wuarchive!ukma!seismo!dimacs.rutgers.edu!rutgers!cmcl2!lanl!cochiti.lanl.gov!jlg
From: jlg@cochiti.lanl.gov (Jim Giles)
Newsgroups: comp.lang.fortran
Subject: Re: why does optimization take so long ?
Message-ID: <24204@lanl.gov>
Date: 22 May 91 14:19:49 GMT
References: <1236@nikhefh.nikhef.nl> <24940@well.sf.ca.us>
Sender: news@lanl.gov
Organization: Los Alamos National Laboratory
Lines: 15

In article <24940@well.sf.ca.us>, rchrd@well.sf.ca.us (Richard Friedman) writes:
|> t19@nikhefh.nikhef.nl (Geert J v Oldenborgh) writes:
|> [...]                         Compilers also have to be smart enough
|> to detect that   pnpb*pept*pbpt*qk  is the same as pept*qk*pnpb*pnbt.
                              ^^^^                                 ^^^^
I assume you meant that _part_ of these expressions are the same.  If 
they were completely identical, the compiler could detect the fact with
a simple cannonical ordering on the operands (say, alphabetical on the
identifiers).  However, _partial_ commonality is an interesting exercise.
Consider (A*B*C + A*D*C + B*C*D): common expressions are A*C, B*C, A*D,
and C*D.  However, no _two_ of these are simultaneously useful as common
expressions!  Fortunately, stuff like this comes out automatically in 
the DAG construction.

J. Giles