3 ms·

This kind of thing is quite useful for people implementing block-level compilers; in particular spending time on optimizations for “small” tensors that are bein

This kind of thing is quite useful for people implementing block-level compilers; in particular spending time on optimizations for “small” tensors that are being operated on in a block are very worthwhile because the generated code is then reused across all blocks and multiple invocations of the kernel. For this case, you can actually calculate a closed form for many recurrences, in the same way that SCEV works. You don’t need to interpret the loop to do this. If you mark your induction variables and put the loop in the right form then it’s possible to do recurrence analysis in constant time. This isn’t particularly complex or novel (and, to be fair, the paper doesn’t do much other than go “hmm what if we did this for tensors”) so I suggest you look up how it’s done in traditional compilers.

almostgotcaught 2y ago
> closed form for many recurrences, in the same way that SCEV works ... so I suggest you look up how it’s done in traditional compilers. SCEV does not compute closed forms ... because that's impossible. if you don't understand why it's impossible you can consult this same team's slides on SCEV in LLVM, a "traditional compiler": https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution.pdf#page=18.00 https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution... specifically pages 16-18
- saagarjha 2y ago
  I feel like we must be talking about different things, because I don't see how any of this follows, and the slides just seem to explain how LLVM does its SCEV? Consider the following program (in C and not LLVM IR because I am very lazy): int foo = 0; for (int i = 0; i < n; ++i) { foo += 1; } Both foo and i have an addrec of {0, +, 1}. Given the loop iteration count n it is pretty clear that you can calculate the value at exit to be n without actually running the loop n times. In fact you don't even know n and can still convert it to a closed form at compile time. So what's the point of disagreement here?
  - almostgotcaught 2y ago
    > In fact you don't even know n and can still convert it to a closed form at compile time. 1. you have to prove monotonicity to make the inference you're implying is "pretty clear". recall that "prove" really does mean prove in compilers 2. even if you did prove motonicity, it's the simplest category of loop body behavior. recall control flow. > without actually running the loop n times this is not possible without an oracle because PSPACE \subseteq EXPTIME https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_classes https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_cl...
    - saagarjha 2y ago
      Put the theory aside and look at the loop I showed you. Surely you can see that its CFG is trivial? You can track all the variables across the basic block and it's really easy to prove (yes, prove) what I claimed. And compilers can of course do more advanced forms of this, here are some more examples: https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo.... I'm confused why you think this is hard because major compilers have been doing it for decades now. I assure you they can do this efficiently.
      - almostgotcaught 2y ago
        I feel like you have poor reading comprehension. I literally said yes for simple cases it works. > https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo... Literally not a single loop on that page has a conditional in it. They're all the same stupid "polynomial" example. Hint: how often do you think people are trying to optimize loops that compute polynomials.... > I assure you they can do this efficiently. It's amazing you think your assurances mean anything. So let me assure you: I know exactly what I'm talking about. In the last month I landed basically SCEV in a production compiler. Except since our programs are real and not just goofy polynomial examples, my SCEV is actually an abstract interpreter.
        2y ago

almostgotcaught 2y ago

> closed form for many recurrences, in the same way that SCEV works ... so I suggest you look up how it’s done in traditional compilers. SCEV does not compute closed forms ... because that's impossible. if you don't understand why it's impossible you can consult this same team's slides on SCEV in LLVM, a "traditional compiler": https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution.pdf#page=18.00 https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution... specifically pages 16-18

saagarjha 2y ago
I feel like we must be talking about different things, because I don't see how any of this follows, and the slides just seem to explain how LLVM does its SCEV? Consider the following program (in C and not LLVM IR because I am very lazy): int foo = 0; for (int i = 0; i < n; ++i) { foo += 1; } Both foo and i have an addrec of {0, +, 1}. Given the loop iteration count n it is pretty clear that you can calculate the value at exit to be n without actually running the loop n times. In fact you don't even know n and can still convert it to a closed form at compile time. So what's the point of disagreement here?
- almostgotcaught 2y ago
  > In fact you don't even know n and can still convert it to a closed form at compile time. 1. you have to prove monotonicity to make the inference you're implying is "pretty clear". recall that "prove" really does mean prove in compilers 2. even if you did prove motonicity, it's the simplest category of loop body behavior. recall control flow. > without actually running the loop n times this is not possible without an oracle because PSPACE \subseteq EXPTIME https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_classes https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_cl...
  - saagarjha 2y ago
    Put the theory aside and look at the loop I showed you. Surely you can see that its CFG is trivial? You can track all the variables across the basic block and it's really easy to prove (yes, prove) what I claimed. And compilers can of course do more advanced forms of this, here are some more examples: https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo.... I'm confused why you think this is hard because major compilers have been doing it for decades now. I assure you they can do this efficiently.
    - almostgotcaught 2y ago
      I feel like you have poor reading comprehension. I literally said yes for simple cases it works. > https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo... Literally not a single loop on that page has a conditional in it. They're all the same stupid "polynomial" example. Hint: how often do you think people are trying to optimize loops that compute polynomials.... > I assure you they can do this efficiently. It's amazing you think your assurances mean anything. So let me assure you: I know exactly what I'm talking about. In the last month I landed basically SCEV in a production compiler. Except since our programs are real and not just goofy polynomial examples, my SCEV is actually an abstract interpreter.
      - 2y ago