[HN Gopher] Compiling with Constraints
       ___________________________________________________________________
        
       Compiling with Constraints
        
       Author : philzook
       Score  : 35 points
       Date   : 2024-03-18 20:59 UTC (2 hours ago)
        
 (HTM) web link (www.philipzucker.com)
 (TXT) w3m dump (www.philipzucker.com)
        
       | anonymous_union wrote:
       | its fascinating how register allocation is not a solved problem.
       | thinking about it, it seems like optimal allocation would depend
       | on input/workload, so any ahead of time selection will always be
       | a compromise.
        
         | convolvatron wrote:
         | certainly optimal would be global, and I'm pretty sure its
         | isomorphic to bin packing..whether you use a fixed call
         | interface or not. so its solved, its just exponential
        
           | anonymous_union wrote:
           | im not sure. given a hypothetical arch with only 1 free
           | register, which local variable do you allocate to it?
           | 1 int       2 main(int argc, char *argv[])       3 {       4
           | int sum = 0;       5         int sum2 = 0;       6       7
           | if (argc >= 2)       8                 for (int i = 0; i <
           | argv[1]; i++)       9                         sum += i;
           | 10      11         if (argc >= 3)      12                 for
           | (int i = 0; i < argv[2]; i++)      13
           | sum2 += sum + i;      14      15         return 0;      16 }
        
             | anonymous_union wrote:
             | oops im dumb, convert argv[1] and argv[2] to integers
             | first.
        
         | philzook wrote:
         | I think one of the biggest problems is even stating what the
         | solution an optimal compiler would be. How does one model a
         | program or a CPU? There almost certainly isn't one perfect
         | model for all situations. CPU's are extremely complicated
         | despite the surface simplicity of assembly. Naive notions of
         | registers or instruction ordering don't really exist. But also
         | because of this, perfect compilation isn't that crucial. The
         | CPU kind of JITs for you. The only objective function that
         | seems pretty clear to me is code size.
        
           | anonymous_union wrote:
           | right yea, modern CPUs seem to have all sorts of abstract
           | optimizations. its kind of strange how we meet in the middle
           | with hardware ISA manufacturers. they do all sorts of tricks
           | on their side to make code go faster, and we try to generate
           | machine code that we think will go faster, but neither side
           | works with the other (compiler writers and ISA developers). i
           | bet there is easy low hanging fruit here.
        
             | LoganDark wrote:
             | There sort of is, but isn't that why stuff like VLIW
             | exists? So that the compiler can optimize the hell out of
             | the machine code, and the CPU doesn't have to do its own
             | OoO nonsense?
        
           | anonymous_union wrote:
           | interesting that code size is important to you. hey everyone,
           | write shorter programs :)
        
         | JonChesterfield wrote:
         | It's np hard. You can solve it perfectly for a given instance
         | using a constraint solver and adequate patience.
         | 
         | Unfortunately instruction selection is also NP, and so is
         | instruction scheduling, and all three are inter-related. An
         | optimal solution for one tends to be suboptimal for the other
         | two.
         | 
         | Ideally one would feed all three problems into a constraint
         | solver together. Thus far this is considered computationally
         | infeasible, though I don't think that belief would bear up to
         | scrutiny with a supercomputer.
        
           | LoganDark wrote:
           | > though I don't think that belief would bear up to scrutiny
           | with a supercomputer.
           | 
           | It's certainly computationally infeasible for home users,
           | that's for sure.
        
         | thechao wrote:
         | If you're willing to work in the SSA domain, and not do any
         | spill/fill, you can do optimal RA in polynomial time. (Usually
         | quoted as linear, but quadraticish IRL.)
        
       | mad0 wrote:
       | Huh I haven't thought that I will see minizinc outside of my
       | university. I keep being pleasantly surprised that constraint
       | programming and formal methods are being used somewhere out
       | there.
        
         | scholaronroad wrote:
         | Out of curiosity, which university is this? IMO the number of
         | universities that actually teach CP is small.
        
       ___________________________________________________________________
       (page generated 2024-03-18 23:00 UTC)