wingolog

effects analysis in guile

18 May 2014 7:19 PM (guile | compilers | optimization | cps | ssa | anf | cse | v8 | igalia)

OK kids, so I had a bit of time recently. I've been hacking on Guile's new CPS-based compiler, which should appear in a stable release in a few months. I have a few things to write about, but today's article is on effects analysis.

what it is, yo

The job of the optimization phase of a compiler is to remove, replace and reorder the sub-expressions of a program. The optimizer recognizes ways in which the program can be better, and then needs to check if those transformations are valid. A transformation is valid if a program exhibits the same behavior both before and after the transformation.

Effects analysis is a proof technique that builds a conservative model of how expressions can affect each other. It can be used to prove the validity of some transformations. For example, if we determine that an expression A reads the first field in a vector, and expression B sets the second field in a vector, then we can use effects analysis to show that the expressions don't affect each others' value and can be freely reordered, for example to hoist either one out of a loop.

In effects analysis, we model the program state coarsely and conservatively with a limited set of categories. The precise set of categories depends on the domain. In graphics, for example, you might have a state bit for the current coordinate system, the current color, the current fill mode, etc. In general-purpose compilation, the effects are mostly about memory and (sometimes) exceptions.

In Guile we model four kinds of effects: type checks (T), allocations (A), reads (R), and writes (W). Each of these effects is allocated to a bit. An expression can have any or none of these effects.

For the purposes of Guile, a "type check" is the possibility that this expression will throw an exception if its arguments are somehow out of range. For example, cons will never throw an exception, except in out-of-memory situations, but + may throw an exception if its arguments aren't numbers. However if an expression is dominated by a copy of itself -- that is, if we see that (+ a b) (which may throw an exception) is dominated by (+ a b), perhaps after CSE -- then we can determine that only the first will exhibit the type-check effects, and that the second will not.

Allocation indicates that an expression allocates a fresh object. In Scheme (and many other languages), each allocated object has its own identity: (eq? (cons 1 2) (cons 1 2)) must be false. Note that this restriction does not apply to constant literals, in Scheme; (eq? '(1 . 2) '(1 . 2)) may or may not be true. In Guile both results are possible. They are the same object when compiled (and thus deduplicated), but different when interpreted; the objects are just the ones returned from `read' and this are different. Anyway we use this allocation bit to indicate that an expression allocates a fresh object with a fresh identity.

The remaining effect kinds are "read" and "write", which indicate reads or writes to memory. So there are just 4 kinds of effects.

Allocation, read, and write effects are associated at run-time with particular memory locations. At compile-time we cannot in general know which of these locations are distinct, and which are actually the same. To simplify the problem, we simply record the type of the object, knowing that (say) a pair and a vector will never be at the same location. We also record the field in the object in the case of objects with multiple fields. There are special catch-all values to indicate "all memory kinds", when we really don't know what an expression will do (which is the case for all expression kinds without specific support in the effect analyzer), and for "all fields" when we don't know which field we are accessing.

One example of the use of this analysis is in common subexpression elimination (CSE). If at a program point P we have a set of available expressions A, then to determine which members of A are still available after the expression at P, you subtract members of A that are clobbered by P. Computation of A at each P plus value numbering is most of CSE; but more on that in some later dispatch. Anyway here's the definition of effects-clobber?.

(define (effect-clobbers? a b)
  "Return true if A clobbers B.  This is the case
if A might be a write, and B might be a read or a
write to the same location as A."
  (define (locations-same?)
    (let ((a (ash a (- &effect-kind-bits)))
          (b (ash b (- &effect-kind-bits))))
      (or (eqv? &unknown-memory-kinds
                (logand a &memory-kind-mask))
          (eqv? &unknown-memory-kinds
               (logand b &memory-kind-mask))
          (and (eqv? (logand a &memory-kind-mask)
                     (logand b &memory-kind-mask))
               ;; A negative field indicates "the
               ;; whole object".  Non-negative fields
               ;; indicate only part of the object.
               (or (< a 0) (< b 0) (= a b))))))
  (and (not (zero? (logand a &write)))
       (not (zero? (logand b (logior &read &write))))
       (locations-same?)))

This analysis is simple, small, and fast. It's also coarse and imprecise -- if you are reading from and writing to two vectors at once, you're almost sure to miss some optimization opportunities as accesses to all vectors are conflated into one bit. Oh well. If you get into this situation, you'll know it, and be able to invest a bit more time into alias analysis; there's lots of literature out there. A simple extension would be to have alias analysis create another mapping from expression to equivalence class, and to use those equivalence classes in the same-location? check above.

Of course this assumes that expressions just access one object. This is the case for Guile's CPS intermediate language, because in CPS, as in SSA or ANF, expressions don't have subexpressions.

This contrasts with direct-style intermediate languages, in which expressions may have nested subexpressions. If you are doing effects analysis on such a language, it's probably more appropriate to allocate a bit to each kind of effect on each kind of object, so that you can usefully union effects for a tree of expressions. Since you don't have to do this for CPS, we can allocate a fixed bit-budget towards more precision as to which field of an object is being accessed. The inability to be precise as to which field was being accessed due to the direct-style IL was one of the problems in Guile's old CSE pass.

Finally, a note about type checks. Guile includes type checks as part of the effects analysis for two reasons. The first is the obvious case of asking whether an expression is effect-free or not, which can lead to some optimizations in other parts of the compiler. The other is to express the potential for elision of duplicate expressions, if one dominates the other. But it's also possible to remove type checks in more cases than that: one can run a type inference pass to remove type-check effects if we can prove that the arguments to an expression are in range. Obviously this is more profitable for dynamically-typed languages, but the same considerations apply to any language with sum types.

Guile's effects analysis pass is here. V8 seems to have two effects analysis passes; one is in effects.h and typing.cc, and operates over the direct-style AST, and the other is in the value numbering pass (hydrogen-instructions.h and hydrogen-gvn.h; search for GVNFlag).

More on how effects analysis is used in Guile in a future missive. Until then, happy hacking.

24 responses

  1. John Cowan says:

    This, of course, is exactly how effects were treated in the primordial CPS compiler Rabbit. The more it changes, the samer it gets.

  2. tomás zerolo says:

    Hi, Andy

    again an unspecific comment, but I've got to let you know that I enjoy thoroughly those Guile articles. Not only are you doing an awesome job, but you are making it awesomely accessible with your write-ups.

    Thanks!

  3. Nala Ginrut says:

    It's a nice introduction for effects analysis in Guile. I've learned much from it. I didn't know the type checks in Guile is part of the effects analysis.
    Thanks!

  4. ASP Project Help says:

    This may be the best web I've ever discovered today. Awesome works without a doubt!

  5. zara says:

    Enjoyable article ! i should be follow your instructions...

  6. pay someone to do my homework for me says:

    Are you making an amazing showing with regards to, as well as you are production it fantastically available with your examination.

  7. matlab programming help says:

    Great Information,it has lot for stuff which is informative.I will share the post with my friends.

  8. Harvard Business Review HBR Cases Solutions and Analysis says:

    The leading assignment help UK firm offers state of the art services to its clients with a promise of delivering all the required work well within the deadline.

  9. aadhar card satus says:

    Get all information related to aadhar card.

  10. slimmest phone says:

    Great! I really liked your blog. Very informative, have bookmarked it.

  11. msqrd app for android says:

    Record video selfie animations, change the way you look and send it to friends via your favorite messengers and social networks.

  12. WiFi Kill App work says:

    Best wifi kill app review is on check it out to know more about this app.

  13. aol.com mail login says:
  14. YO YO says:
  15. YO YO says:
  16. Maria says:
  17. Academic Dissertation Help says:

    After effects of compiler at any software of student’s personal computer to do practice for reorder to confirm effects.

  18. Indian flag says:

    The Indian Flag which is known as the Tricolor or the Tiranga is the pride of the Indian Nationals.

  19. Andre says:

    Where is the post where you show further analysis of the Guile? I'm interested in this subject. Thanks!

    Andre (Projeto Importador Profissional 2.0

  20. Report Writing Help says:

    thanks for sharing helpful information, Most important thing is transformation should be valid and exhibits right way.

  21. Hire Write My Assignment Service says:

    Nice explanation about effect of analysis in guile, i learned more about guile but never read this informaton so this is new thing to improve my knowledge, again thanks for sharing such kind of information.

  22. oneplus 5 price says:

    One plus 4 is having a price and specifications which will even make the most successful mobiles jealous.

  23. ADIL says:

    best printable 2017 Calendarbest printable 2017 Calendarbest printable 2017 Calendarbest printable 2017 Calendarbest printable Calendar 2017best printable Calendar 2007best printable Calendar 2017best printable Calendar 2017best printable Calendar 2007best printable Calendar 2017best printable Calendar 2017best printable Calendar 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2007USA River map 2007USA River map 2007USA River map 2007USA River map 2007USA River map 2007USA River map 2007Map of united statesMap of united statesMap of united states

    In Rome, where winters were not as harsh as those in the far north, Saturnalia—a holiday in honor of Saturn, the god of agriculture—was celebrated.
    Beginning in the week leading up to the winter solstice and continuing for a full month, Saturnalia was a hedonistic time,
    when food and drink were plentiful and the normal Roman social order was turned upside down. For a month, slaves would become masters.
    Peasants were in command of the city. Business and schools were closed so that everyone could join in the fun.

  24. Gabriel says:

    Interesting analisys.
    Nice! Visit my blog too.como comprar da china

Leave a Reply