Xref: utzoo comp.arch:17038 comp.lang.misc:5134 Path: utzoo!utgpu!watserv1!watmath!att!rutgers!cs.utexas.edu!rice!sicilia.rice.edu!cliffc From: cliffc@sicilia.rice.edu (Cliff Click) Newsgroups: comp.arch,comp.lang.misc Subject: Re: Compiler Costs Message-ID: <9743@brazos.Rice.edu> Date: 10 Jul 90 18:22:51 GMT References: <23268@boulder.Colorado.EDU> <23285@boulder.Colorado.EDU> Sender: root@rice.edu Followup-To: comp.arch Organization: Rice University, Houston Lines: 24 In article meissner@osf.org (Michael Meissner) writes: >I also wonder about the computational complexity of global register >analysis. Global register allocation is NP-complete. >My experience has tended to be that register allocation is >one of the more memory intensive pieces of compilers, and the size of >the memory is needed scales with the number of basic blocks used and >number of distinct pseudo regs requested. I could easily imagine a >global register analysis phase thrashing on really large programs, Some folks at Rice here experimenting with a nameless commerical compiler discovered a simple 2000-line fortran program that took 90+ HOURS to compile on a 10+ Mips, 16 Meg workstation. The program spent roughly 98% of it's time thrashing the disk. The algorithm the compiler used required exponentional memory space. The same compile took ~15 minutes on a 48 Meg workstation. Cliff Click cliffc@rice.edu -- Cliff Click cliffc@owlnet.rice.edu