cps soup

27 July 2015 2:43 PM (guile | cps | ssa | compilers | contification | cse | closure optimization | clojure | bagwell | persistent data structures)

Hello internets! This blog goes out to my long-time readers who have followed my saga hacking on Guile's compiler. For the rest of you, a little history, then the new thing.

In the olden days, Guile had no compiler, just an interpreter written in C. Around 8 years ago now, we ported Guile to compile to bytecode. That bytecode is what is currently deployed as Guile 2.0. For many reasons we wanted to upgrade our compiler and virtual machine for Guile 2.2, and the result of that was a new continuation-passing-style compiler for Guile. Check that link for all the backstory.

So, I was going to finish documenting this intermediate language about 5 months ago, in preparation for making the first Guile 2.2 prereleases. But something about it made me really unhappy. You can catch some foreshadowing of this in my article from last August on common subexpression elimination; I'll just quote a paragraph here:

In essence, the scope tree doesn't necessarily reflect the dominator tree, so not all transformations you might like to make are syntactically valid. In Guile 2.2's CSE pass, we work around the issue by concurrently rewriting the scope tree to reflect the dominator tree. It's something I am seeing more and more and it gives me some pause as to the suitability of CPS as an intermediate language.

This is exactly the same concern that Matthew Fluet and Stephen Weeks had back in 2003:

Thinking of it another way, both CPS and SSA require that variable definitions dominate uses. The difference is that using CPS as an IL requires that all transformations provide a proof of dominance in the form of the nesting, while SSA doesn't. Now, if a CPS transformation doesn't do too much rewriting, then the partial dominance information that it had from the input tree is sufficient for the output tree. Hence tree splicing works fine. However, sometimes it is not sufficient.

As a concrete example, consider common-subexpression elimination. Suppose we have a common subexpression x = e that dominates an expression y = e in a function. In CPS, if y = e happens to be within the scope of x = e, then we are fine and can rewrite it to y = x. If however, y = e is not within the scope of x, then either we have to do massive tree rewriting (essentially making the syntax tree closer to the dominator tree) or skip the optimization. Another way out is to simply use the syntax tree as an approximation to the dominator tree for common-subexpression elimination, but then you miss some optimization opportunities. On the other hand, with SSA, you simply compute the dominator tree, and can always replace y = e with y = x, without having to worry about providing a proof in the output that x dominates y (i.e. without putting y in the scope of x)

[MLton-devel] CPS vs SSA

To be honest I think all this talk about dominators is distracting. Dominators are but a lightweight flow analysis, and I usually find myself using full-on flow analysis to compute the set of optimizations that I can do on a piece of code. In fact the only use I had for dominators in the nested CPS language was to rewrite scope trees! The salient part of Weeks' observation is that nested scope trees are the problem, not that dominators are the solution.

So, after literally years of hemming and hawing about this, I finally decided to remove nested scope trees from Guile's CPS intermediate language. Instead, a function is now a collection of labelled continuations, with one distinguished entry continuation. There is no more $letk term to nest continuations in each other. A program is now represented as a "soup" -- basically a map from labels to continuation bodies, again with a distinguished entry. As an example, consider this expression:

  return add(x, 1)

If we rewrote it in continuation-passing style, we'd give the function a name for its "tail continuation", ktail, and annotate each expression with its continuation:

function(ktail, x):
  add(x, 1) -> ktail

Here the -> ktail means that the add expression passes its values to the continuation ktail.

With nested CPS, it could look like:

function(ktail, x):
  letk have_one(one): add(x, one) -> ktail
    load_constant(1) -> have_one

Here the label have_one is in a scope, as is the value one. With "CPS soup", though, it looks more like this:

function(ktail, x):
  label have_one(one): add(x, one) -> ktail
  label main(x): load_constant(1) -> have_one

It's a subtle change, but it took a few months to make so it's worth pointing out what's going on. The difference is that there is no scope tree for labels or variables any more. A variable can be used at a label if it flows to the label, in a flow analysis sense. Indeed, determining the set of variables that can be used at a label requires flow analysis; that's what Weeks was getting at in his 2003 mail about the advantages of SSA, which are really the advantages of an intermediate language without nested scope trees.

The question arises, though, now that we've decided on CPS soup, how should we represent a program as a value? We've gone from a nested term to a graph term, and we need to find a way to represent it somehow that facilitates looking up labels by name, and facilitates tree rewrites.

In Guile's IR, labels and variables are both integers, so happily enough, we have such a data structure: Clojure-style maps specialized for integer keys.

Friends, if there has been one realization or revolution for me in the last year, it has been Clojure-style data structures. Here's why. In compilers, I often have to build up some kind of analysis, then use that analysis to transform data. Often I need to keep the old term around while I build a new one, but it would be nice to share state between old and new terms. With a nested tree, if a leaf changed you'd have to rebuild all surrounding terms, which is gnarly. But with Clojure-style data structures, more and more I find myself computing in terms of values: build up this value, transform this map to that set, fold over this map -- and yes, you can fold over Guile's intmaps -- and so on. By providing an expressive data structure for which I can control performance characteristics by using transients if needed, these data structures make my programs more about data and less about gnarly machinery.

As a concrete example, the old contification pass in Guile, I didn't have the mental capacity to understand all the moving parts in such a way that I could compute an optimal contification from the beginning; instead I had to iterate to a fixed point, as Kennedy did in his "Compiling with Continuations, Continued" paper. With the new CPS soup language and with Clojure-style data structures, I could actually fit more of the algorithm into my head, with the result that Guile now contifies optimally while avoiding the fixed-point transformation. Also, the old pass used hash tables to represent the analysis, which I found incredibly confusing to reason about -- I totally buy Rich Hickey's argument that place-oriented programming is the source of many evils in programs, and hash tables are nothing if not a place party. Using functional maps let me solve harder problems because they are easier for me to reason about.

Contification isn't an isolated case, either. For example, we are able to do the complete set of optimizations from the "Optimizing closures in O(0) time" paper, including closure sharing, which I think makes Guile unique besides Chez Scheme. I wasn't capable of doing it on the old representation because it was just too hard for me to think about, because my data structures weren't right.

This new "CPS soup" language is still a first-order CPS language in that each term specifies its continuation, and that variable names appear in the continuation of a definition, not the definition itself. This effectively makes every variable a phi variable, in the sense of SSA, and you have to do some work to get to a variable's definition. It could be that still this isn't the right number of names; consider this function:

function foo(k, x):
  label have_y(y) bar(y) -> k
  label y_is_two() load_constant(2) -> have_y
  label y_is_one() load_constant(1) -> have_y
  label main(x) if x -> y_is_one else -> y_is_two

Here there is no distinguished name for the value load_constant(1) versus load_constant(2): both are possible values for y. If we ended up giving them names, we'd have to reintroduce actual phi variables for the joins, which would basically complete the transformation to SSA. Until now though I haven't wanted those names, so perhaps I can put this off. On the other hand, every term has a label, which simplifies many things compared to having to contain terms in basic blocks, as is usually done in SSA. Yet another chapter in CPS is SSA is CPS is SSA, it seems.

Welp, that's all the nerdery for right now. Talk at yall later!

75 responses

  1. Colin Fleming says:

    Indeed, persistent data structures are wonderful things. They make many aspects of the language analysis that I do in Cursive much, much easier. Want to keep the state of your indexing at any point in the file? No problem, you already did. Maintaining state in backtracking PEG parsers? No problem, it comes for free.


  2. Jaromil says:

    Way to go! Guile is extremely important to the GNU project and you are making the right choices. Clojure is an amazing language, very empowering: is wise to learn from it.

  3. Anonymous says:

    It sounds like a big relief to get that deeper understanding of SSA vs CPS and how encouraging that changing the IL led to those dramatic improvements in code clarity! Thank you for sharing this lesson learned and all this work going into improving guile.

  4. ApkCage says:

    Nowadays apps are every android mobile user need to download

  5. clases de manejo en monterrey economicas says:

    You know if you break my heart I'll go But I'll be back again Cos I told you once before goodbye But I came back again

  6. escuela de manejo monterrey centro says:

    You could find better things to do Than to break my heart again This time I will try to show that I'm Not trying to pretend

  7. todo para tu fiesta says:

    I'll pray and pray more each day Cos we love you, Mr. Moonlight And the night you don't come my way

  8. James says:

    Agree with your post! Bytecode makes programming easier and it's safe.

  9. Academic Writing -DoneDissertation says:

    There is no more $letk term to home continuations in each other. A program is currently spoken to as a "soup" - fundamentally a guide from marks to continuation bodies, again with a recognized passage. For instance, consider this expression:

  10. Thompson Harry says:

    Bytecode makes programming easier and it's safe. Agree with your post!

  11. 192.168.l.2 says:

    Way to go! Guile is extremely important to the GNU project and you are making the right choices. Clojure is an amazing language, very empowering: is wise to learn from it.

  12. says:

    Despite the fact that the reception of the EMV activity which includes changing out your present POS gadgets to those that bolster EMV empowered charge cards (those with a chip rather than an attractive stripe) is deliberate and misrepresentation is not your real concern, I would even now investigate doing the switch over.

  13. Essay Mall says:

    which extend from a spotless format based site to a modern channel supervisor that handles the online conveyance of convenience suppliers.

  14. says:

    Extraordinary information! I as of late went over your blog and have been perusing along. I thought I would leave my first remark. I don't comprehend what to state with the exception of that I have

  15. says:

    As a solid illustration, the old contification go in Guile, I didn't have the mental ability to see all the moving parts such that I could figure an ideal contification from the earliest starting point; rather I needed to emphasize to a settled point, as Kennedy did in his "Ordering with Continuations, Continued" paper.

  16. Coursework Writing Service  says:

    Along these lines, after truly years of faltering about this, I at last chose to expel settled extension trees from Guile's CPS moderate dialect. Rather, a capacity is currently an accumulation of named continuations, with one recognized passage continuation. There is no more $letk term to settle continuations in each other.

  17. paypal cash says:

    This is the biggest achievement of this website.

  18. Thesis writing service says:

    I thought that Guile had the compiler initially. But now I realized that it has only interpreter written in C. Now it has the compiler which process byte code. Thanks for this information and I am very happy for that.

  19. says:

    Thanks for this one.

  20. colour switch says:

    Oh! This article has suggested to me many new ideas. I will embark on doing it. Hope you can continue to contribute your talents in this area. Thank you.

  21. hermes says:

    the more nervous the child is at a loss and loses self-confidence. He will repeat mistakes like obsessive-compulsive disorder.

  22. Homepage says:

    If she mobilizes relatives again, you will say to relatives: I also owe a butt debt. The enemy is blocking the door

  23. dior says:

    No one will love you more than you. Please believe that science believes in humanity. Didn't sleep well last night and made an anxious dream

  24. replica versace sunglasses says:

    Do not know what she was afraid of, I was afraid when I cried, anxious to cry, cry to interrupt my cry

  25. javad says:

  26. medical billing services in Texas says:

    Great Blog.Expressed in a variety way.Keep it up

  27. waitrose voucher codes says:

    Amazing post.Well explained things.keep it up

  28. business listing in kerala says:

    I congratulate your effort to do this.I think you have to add more details about the topic.

  29. business listing in kerala says:

    I congratulate your effort to do this.I think you have to add more details about the topic.

  30. Walatra Propolis Brazil Original says:

    Modern online tradition of banking, running a blog, social networking and shopping makes it much easier than in the past for all those with nefarious intentions to steal your individual info.

  31. Matt W says:

    I found this link on clojure transient data-structures

  32. Matt W says:

    Oh, and very interesting article. I'm having fun diving into this.

  33. Buy Dissertation Online says:

    I was going to finish documenting this intermediate language about 5 months ago, in preparation for making the first Guile 2.2 prereleases. But something about it made me really unhappy.

  34. Topdissertations says:

    Great blog. And the really nice style of writing. I've dived into this topic.

  35. High School Diploma says:

    I feel very lucky to find your site. Your sharing is meaningful. Wish you have a good day.

  36. muebles monterrey says:

    thats ok!

  37. reja acero says:

    On a dark desert highway, cool wind in my hair

  38. Udem toefl says:

    Warm smell of colitas, rising up through the air

  39. examen toefl en monterrey says:

    Up ahead in the distance, I saw a shimmering light

  40. sistema tress de recursos humanos says:

    My head grew heavy and my sight grew dim I had to stop for the night

  41. software de nomina says:

    go go!

  42. proveedores de erp kit consultores en mexico says:

    There she stood in the doorway I heard the mission bell

  43. software contable says:

    And I was thinking to myself "This could be Heaven or this could be Hell"

  44. kumar says:

    playing games is right or not.

  45. Exclusive-paper says:

    Lab Report Writing Service:
    Achieve Success Easily!

  46. run 3 says:

    Great article. I would love to read your post. Hope you have more posts.

  47. Küçükçekmece İkinci El Eşya Alanlar says:

    Thank you. Nice Blog

  48. Istanbul Property says:

    Thank you. Istanbul Property

  49. Kral Park Oyun Makineleri says:

    Thank you nice wingolog. Oyun Makineleri

  50. istanbul property says:

    It's a good blog post. A nice site thanks. We thank you as istanbul property. Istanbul Property offers real estate sales services in Istanbul. istanbul property consists of expert teams.

  51. samedayessay says:

    wonderful tips you've written. I'm going to apply
    these in my regural life. Hopefully, it should increase quality of the life

  52. website says:

    However, after the founding of the People's Republic

  53. mysite says:

    but in civil compensation, the bus company should bear the main responsibility

  54. bathroom remodel says:

    Really informative article.Really looking forward to read more. Really Cool.

  55. buy articles online says:

    Searching for someone who can help you with article writing. Consider a reliable writing service. Expert writers will help you with articles of any complexity.

  56. modem arayüzü says:
  57. modem arayüzü says:
  58. buy discussion post says:

    A discussion board post written on your own should demonstrate that you have properly understood the course material and can provide a well-developed response to one of the course topics.

  59. finance dissertation says:

    Our fully hardworking team with 3000+ experts will provide impeccable contracts law assignment online services around the world. We also charge reasonable prices for this.

  60. assignment help says:

    What crystal clear and noteworthy points you have put forward? If your students can not complete your assignment on time and wait for assignment help service cheap the place your order at SourceESsay.

  61. Subway Surfers says:

    Thanks for sharing your idea with regards to the topic. I learned something today about CPS.

  62. Alpha Assignment Help says:

    We are the most professional quality-oriented assignment writing help Service providers. Alpha academic assignment help are 100% original and free from plagiarism at very affordable rates. We are available 24*7 to help the students in their academic work. We provide academic help in subjects like Management assignment writing services, accounting assignment writing service, Operations Assignment, Marketing Assignment writing services, Economics Assignment and IT. Our main aim is to provide the best help in academic assignment help to students, which helps them to get good grades in their academic performances.

  63. Organizational behavior case study says:

    Due to numerous assignment that comes up within a tight deadline, It becomes very difficult for the student to finish up their organizational behavior case study within due time. Best assignment experts are here to help you to get your work delivered within the tight deadline along with the plagiarism-free report.

  64. Perdisco Help Australia says:

    We at My Perdisco Help company is very popular in the world for MYOB Perdisco assignment help and MYOB practice set solutions.

  65. E Liquid Shop in UK says:

    I was reading some of your content on this website and I conceive this internet site is really informative ! Keep on putting up.

  66. A Perfect Review says:

    I this way post, And I figure they creating a a lot of extra fun to peruse this post, they could take a decent site to create an information, thank you for sharing it to me.

  67. wiseessays review says:

    I found wiseessays review to be helpful. Timely response from my writer and overall great papers, this service literally saved my life. i highly recommend them.

  68. trustmypaper coupon says:

    Some services even offer huge discounts. You just need to know when exactly they ptovide them. Not so long ago, I saw a tremendous trustmypaper coupon with a price reduction up to 20%.

  69. PhD assistance HIGS says:

    HIGS we are a global PhD research assistance and we are the ultimate choice of every PhD research scholars. Here, you will get A to Z PhD assistance for all your research needs. As we serve as the best PhD research consultants, we are here to clarify you all your doubts regards to your research work. We can proudly say that HIGS rewarded as one of the most reliable and well-established research consultancies. If you approach HIGS we people guide you in-person or via an online method to guide you in terms of PhD admissions. We know that ‘knowledge is power’, thus we work based on the motive of giving 100%gratification for our clients. Our professionals are highly qualified and trained in various fields so that they can offer you the best PhD guidance. Since we started up HIGS, we are maintaining such great growth in PhD guidance and also in the journal paper publishing process. We have many satisfied clients in and out of India. We bring world-class services to our clients in terms of PhD admissions, University selection, Topic selection, Thesis paper writing, thesis paper editing, research paper writing, Viva process and more and more. We are bestowed with our reputed name as India’s best PhD assistance, which makes us to serve even better for our aspirants. You may think that PhD will take 5 to 6 years to complete, and finishing PhD in 3 years may be a nightmare. But at HIGS we make a unique and easy way for your research, we assure you that finishing PhD in 3 years it is possible. HIGS have the sole purpose of doing our services with 100% gratification of our clients. So we never lose our professionalism for anything. We offer entire PhD assistance and journal paper publication help, thesis writing help and more.

  70. History Essay Writing Service says:

    When you work on any type of essay, you should do your best to demonstrate creativity, originality, as well as critical thinking of yours by presenting what the question asks, and why it is of great significance rather than simply repeating or restating it.

  71. Best Assignment Experts in Australia says:

    Best Assignment Experts work 24*7 round the clock instantly to help you and to support you promptly as we know time counts a lot in your assignment submissions. The most affordable website for your all assignment help is surely the best assignment

  72. academic writers online says:

    Whenever I’m too busy to do my homework, I can rely on AcademHelpers. So good to know that.

  73. Web Sitesi SEO says:

    Thank you nice website.

  74. says:

    These cards are taking over New York smart carts
    whats your take?

  75. MYOB assignment help says:

    MYOB assignment is one of the best study for student's career. MYOB assignment appears very interesting and awesome but MYOB assignment wants a lot of concentration and dedication from the students. It is full of perceptions and theory. At times after putting hard efforts many students failed to gain good scores and face disappointment. If you are one of them and face the same problems then you are in the right place. You can simply progress knowledge in this subject. We have more professionals who have depth of knowledge in MYOB assignment, they guide you appropriately. We at homework help give online MYOB assignment helps under our with the goal that students can finish their assignment on schedule and secure good marks.

Leave a Reply