wingolog

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:

function(x):
  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!

41 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.

    Lovely.

  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. Help With Python says:

    Another incredible post, I value all the work you put into this site, assisting others with your fun and inventive works.

  5. no deposit bonus codes 2016 says:

    No Deposit Bonus for you to make the most of to play any of the games at our online casino for as long as you want..
    http://tinyurl.com/zvbas3e

  6. Ganong Bros, Limited Case Solution says:

    I truly esteem your carry out the occupation and tips determined by you is useful to me. I will impart this subtle elements to my relatives and companions.

  7. Labor Economics Homework Help says:

    Labor Economics is worried about a lot of the essential choices dealing with people at numerous different points in their lives, regardless of a few of these choices being made when the individual is not actively associated with the labor market.

  8. VBA Excel Programming Assignment Help says:

    VBA Excel Assignment Help Introduction When you setup Microsoft Excel, Microsoft Visual Basic is a programming environment that gets immediately…………

  9. plaque psoriasis says:

    Intriguing post. I Have Been pondering about this issue, so much obliged for posting. Thanks

  10. a10 says:

    Thanks for the best blog.it was very useful for me. keep sharing such ideas in the future as well. this was actually what i was looking for,and i am glad to came here!

  11. You tv player ios says:

    You tv player is one of the best softwares for android to watch TV

  12. music paradise pro app says:

    Nice one. download music paradise pro to enjoy streaming latest music

  13. Hostgator black friday 2016 says:

    Posts shared useful information and meaningful life, I'm glad to be reading this article and hope to soon learn the next article.I wanna inform you that black Friday sale is out now.You can get latest discount coupons here.Thank you.

  14. pof login says:

    Excellent read, Positive site, where did u come up with the information on this posting? I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work

  15. Ravish Sundriyal says:
  16. dhruva rating says:
  17. Leela says:

    Thanks for posting the information it was such a wonderful website Cps Soup

    Target Discount Codes

  18. asdf says:
  19. YO YO says:
  20. Mobdro APK Download says:

    awesome continue browsing by numerous individuals. Mobdro streaming application is feasible till now. We are right here to assist you with new upgrade Mobdro for PC is additionally readily available nice.

  21. Merry Christmas says:
  22. what is my ip says:

    I would like to thank you for the efforts you have made in writing this post. * google maps street view - google mail

  23. Cupshe coupon says:

    This is an informative post review. I am so pleased to get this post article and nice information. I was looking forward to getting such a post which is very helpful to us.Thanks for sharing.

  24. dipika mishra says:

    The middle of winter has long been a time of celebration around the world. Centuries before the arrival of the man called Jesus, early Europeans celebrated light and birth in the darkest days of winter. Many peoples rejoiced during the winter solstice, when the worst of the winter was behind them and they could look forward to longer days and extended hours of sunlight.

    In Scandinavia, the Norse celebrated Yule from December 21, the winter solstice, through January. In recognition of the return of the sun, fathers and sons would bring home large logs, which they would set on fire. The people would feast until the log burned out, which could take as many as 12 days. The Norse believed that each spark from the fire represented a new pig or calf that would be born during the coming year.

    The end of December was a perfect time for celebrationFeliz Navidad 2016 Navidad 2016Feliz año nuevo 2017

    Frohe weihnachten 2016Frohe weihnachten Status für FacebookCanciones de Navidad 2016 Villancicos de Feliz Navidad 2016 en inglesCanciones de Feliz Navidad 2016
      Frohes Neues Jahr2017 Frohe weihnachten 2016 weihnachtsgrüße 2016 Frohe weihnachten
      Frohe Weihnachten und Neues Jahr 2017 Neues Jahr 2017frohe Weihnachten 2016
     
     
     Frohe Weihnachtsgrüße 2016 Weihnachtsgrüße 2016Frohe Weihnachtsgrüße
     
     Sprüche zu Weihnachten 2016Frohe Weihnachten Sprüche, Wünsche, GedichteGedichte zu weihnachten 2016Weihnachten 2016 Wünsche

    analyze big data big data search data mining with big databig data database architecturehadoop big data database sql books hadoop big data analyticsdefine big databig data computing concept of big dataanalytics data database sql technology it big data big data examples big data miningsources of big datadata analytics companybig data volumemassive data big data storeopen source big data analytics analytics tools of big databig data structurebusiness data analytics applications for big databest big data databasemanaging big databig data analysis methods what's big data big data 3vexplain big data big data intelligence big data overviewanalytics on big datamassive data analysis big data featuresdatabase of big datause of big data big data productsbig data application developmentbig data and data mininghadoop analytics toolslarge data analytics big data data sourcesbig data researchbig data analytics startupadvanced data analyticsdata management big dataanalytics for big data features of big datadatabase sql books big data analytics methodology
     database sql books database sql pdfdatabase sqldatabase sql and nosqlwhat is data analyticsbig data in securitybig data articleshadoop articleshadoop software downloadhadoop trainingsdatabase sql tutorialsdata analytics booksbig data training in gaziabadbig data training in usbig data courses in goahadoop and big dataapplications of rhow to download big data pdfhow to learn big data and get jobbig data jobs and salary packagessalary packages of big data professionalbig data professionalsbig data professionals jobs
     spanish happinesshow to become spanish translatorspanish newbiespanish loveI love you more in spanish
     love and care in spanisbheat in spanishspanish loversspanish worldhow to speak and write spanishspanish language learn spanish very easily
     download the R tutorials for beginnersdownload SAS tutorials freelearn R and sasBig data engineer salary all over india
     I love you more than anyone in spanishhow to say bad in spanishhow to say you are good in spanishwhat are benfits of spanishspanish songs download sadlearn spanish from the websitespanish learning offline
     
     
    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.

  25. MERRY says:

    Here We have Good Collection of christmas background free free christmas background images December 25 is marked as the birth of Jesus Christ, who Christians believe is the son of God. People from all parts of the country celebrate Christmas with great zeal enthusiasm where they take part in several activities which makes them happy.christmas tree background Merry christmas Vector Images 2016 christmas background photography.christmas wishes messages

  26. merry christmas images says:

    Here We have Good Collection of christmas background free free christmas background images December 25 is marked as the birth of Jesus Christ, who Christians believe is the son of God. People from all parts of the country celebrate Christmas with great zeal enthusiasm where they take part in several activities which makes them happy.christmas tree background Merry christmas Vector Images 2016 christmas background photography.Merry christmas Images

  27. Allen says:

    Amazed to be here and want to read this amazing info. Thanks for this interesting article and I would really want to say thanks for this info. Tidebuy coupons

  28. Deep Web says:
  29. 9Apps APK says:

    Great This is one of the key and also helpful function of 9App as it helps to maintain you far from any kind of type of problem when it come to compatibility. Fine.

  30. best torrent client says:

    I would like to thank you for the efforts you have made in writing this post.

    - top websites in the world
    - famous people

  31. weer says:
  32. slither io says:

    Let’s keep are safe place to play the very best free games for kids! Please click: wingsio | slither io |

  33. 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.

  34. Bethann Wuebker says:

    ironsteelcenter.com ironsteelcenter.comHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga besi cnp Harga besi cnpHarga besi unp Harga besi unpHarga wiremesh Harga wiremeshHarga besi wf Harga besi wfHarga besi h beam Harga besi h beamHarga Plat besi Harga Plat besiHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga besi siku Harga besi sikuHarga Plat kapal besi baja bki krakatau steel Harga Plat kapal besi baja bki krakatau steelHarga bondek Harga bondekHarga baja ringan Harga baja ringanHarga Atap spandek Harga atap spandekHarga stainless steel Harga stainless steeljasa konstruksi jasa konstruksi besi baja jasa konstruksi gudang jasa konstruksi gedung jasa konstruksi undangan pernikahan undangan pernikahan simpleundangan pernikahan online udangan pernikahan pinkundangan pernikahan unik undangan pernikahan onlineundangan pernikahan murah undangan pernikahan islamiundangan pernikahan islami undangan pernikahan murahundangan pernikahan elegan undangan pernikahan artisundangan pernikahan unik dan murah contoh undangan pernikahan
    www.gudangbesibaja.com www.gudangbesibaja.comHarga besi cnp Harga besi cnpHarga besi h beam baja Harga besi h beam bajaHarga Plat besi plat kapal Harga Plat besi plat kapalHarga besi siku Harga besi sikuHarga besi unp Harga besi unpHarga besi wf baja Harga besi wf bajaHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga wiremesh Harga wiremeshHarga bondek Harga bondekHarga besi Wf Baja Harga besi Wf Bajajasa konstruksi baja wf jasa konstruksi jembatan jasa konstruksi bangunan jasa konstruksi undangan pernikahan elegan dan murah undangan pernikahan eleganundangan pernikahan simple undangan pernikahan elegan dan murahundangan pernikahan artis undangan pernikahan putihudangan pernikahan pink undangan pernikahan unik dan murahundangan pernikahan putih undangan pernikahan unikContoh undangan pernikahan undangan pernikahan

    harga besi beton sni toko besi baja harga besi bahan bangunanharga pipa stainless steel pipa galvanis medium a besi bjkujual baja wf tabel baja krakatau steel harga besi ulir 16 mmharga stainless steel harga baja profil per kg harga besi 12 sniharga besi ulir harga besi wire mesh harga besi 8 mmdaftar harga pipa galvanis harga besi hollow stainless harga besi beton 10harga besi wf 200 harga baja hollow harga besi 13 ulirbesi kanal c galvanis steel rangka besi betondaftar harga besi beton harga pipa hollow harga besi kgjual wiremesh besi beam sni besi betonsupplier besi profil baja iwf harga besi behel 8mmbesi baja pipa galvanized harga besi beton 10mm snikonstruksi baja wf jual expanded metal harga besi ulir 10daftar harga besi hollow besi wire mesh harga sikuharga wiremesh profil baja h beam harga besi siku 4x4Supplier besi harga beam 200 besi siku hargaharga besi baja harga besi cnp 100 harga pipa besi hitamharga pipa baja jual besi cnp pipa seamlessbesi beton murah harga besi unp 100 daftar harga pipa stainless steelharga kanal c besi kanal c harga harga pipaharga besi stainless harga besi cnp 125 pipa stainlessharga besi per kg besi u galvanisharga plat stainless steel besi c pipa besi galvanisbesi unp harga besi cnp 150 harga besi hollow untuk pagarjual besi wf kanal c pipa besi hitamharga baja h beam daftar harga besi kanal c harga besi hollow 40x40ironsteelcenter.com ironsteelcenter.comHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga besi cnp Harga besi cnpHarga besi unp Harga besi unpHarga wiremesh Harga wiremeshHarga besi wf Harga besi wfHarga besi h beam Harga besi h beamHarga Plat besi Harga Plat besiHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga besi siku Harga besi sikuHarga Plat kapal besi baja bki krakatau steel Harga Plat kapal besi baja bki krakatau steelHarga bondek Harga bondekHarga baja ringan Harga baja ringanHarga Atap spandek Harga atap spandekHarga stainless steel Harga stainless steeljasa konstruksi jasa konstruksi besi baja jasa konstruksi gudang jasa konstruksi gedung jasa konstruksi undangan pernikahan undangan pernikahan simpleundangan pernikahan online udangan pernikahan pinkundangan pernikahan unik undangan pernikahan onlineundangan pernikahan murah undangan pernikahan islamiundangan pernikahan islami undangan pernikahan murahundangan pernikahan elegan undangan pernikahan artisundangan pernikahan unik dan murah contoh undangan pernikahan
    www.gudangbesibaja.com www.gudangbesibaja.comHarga besi cnp Harga besi cnpHarga besi h beam baja Harga besi h beam bajaHarga Plat besi plat kapal Harga Plat besi plat kapalHarga besi siku Harga besi sikuHarga besi unp Harga besi unpHarga besi wf baja Harga besi wf bajaHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga wiremesh Harga wiremeshHarga bondek Harga bondekHarga besi Wf Baja Harga besi Wf Bajajasa konstruksi baja wf jasa konstruksi jembatan jasa konstruksi bangunan jasa konstruksi undangan pernikahan elegan dan murah undangan pernikahan eleganundangan pernikahan simple undangan pernikahan elegan dan murahundangan pernikahan artis undangan pernikahan putihudangan pernikahan pink undangan pernikahan unik dan murahundangan pernikahan putih undangan pernikahan unikContoh undangan pernikahan undangan pernikahan

    harga besi beton sni toko besi baja harga besi bahan bangunanharga pipa stainless steel pipa galvanis medium a besi bjkujual baja wf tabel baja krakatau steel harga besi ulir 16 mmharga stainless steel harga baja profil per kg harga besi 12 sniharga besi ulir harga besi wire mesh harga besi 8 mmdaftar harga pipa galvanis harga besi hollow stainless harga besi beton 10harga besi wf 200 harga baja hollow harga besi 13 ulirbesi kanal c galvanis steel rangka besi betondaftar harga besi beton harga pipa hollow harga besi kgjual wiremesh besi beam sni besi betonsupplier besi profil baja iwf harga besi behel 8mmbesi baja pipa galvanized harga besi beton 10mm snikonstruksi baja wf jual expanded metal harga besi ulir 10daftar harga besi hollow besi wire mesh harga sikuharga wiremesh profil baja h beam harga besi siku 4x4Supplier besi harga beam 200 besi siku hargaharga besi baja harga besi cnp 100 harga pipa besi hitamharga pipa baja jual besi cnp pipa seamlessbesi beton murah harga besi unp 100 daftar harga pipa stainless steelharga kanal c besi kanal c harga harga pipaharga besi stainless harga besi cnp 125 pipa stainlessharga besi per kg besi u galvanisharga plat stainless steel besi c pipa besi galvanisbesi unp harga besi cnp 150 harga besi hollow untuk pagarjual besi wf kanal c pipa besi hitamharga baja h beam daftar harga besi kanal c harga besi hollow 40x40

  35. evangelin says:
  36. roselina says:
  37. ayaan says:
  38. harsha says:
  39. mithal says:
  40. harsha says:
  41. teja says:

Leave a Reply