wingolog

type folding in guile

29 October 2015 10:13 PM (guile | ssa | optimization | compilers | unboxing | constant folding)

A-hey hey hey, my peeps! Today's missive is about another optimization pass in Guile that we call "type folding". There's probably a more proper name for this, but for the moment we go with "type folding" as it's shorter than "abstract constant propagation, constant folding, and branch folding based on flow-sensitive type and range analysis".

on types

A word of warning to the type-system enthusiasts among my readers: here I'm using "type" in the dynamic-languages sense, to mean "a property about a value". For example, whether a value is a vector or a pair is a property of that value. I know that y'all use that word for other purposes, but there are other uses that do not falute so highly, and it's in the more pedestrian sense that I'm interested here.

To back up a bit: what are the sources of type information in dynamic languages? In Guile, there are three ways the compiler can learn about a value's type.

One source of type information is the compiler's knowledge of the result types of expressions in the language, especially constants and calls to the language's primitives. For example, in the Scheme definition (define y (vector-length z)), we know that y is a non-negative integer, and we probably also know a maximum value for z too, given that vectors have a maximum size.

Conditional branches with type predicates also provide type information. For example, in consider this Scheme expression:

(lambda (x)
  (if (pair? x)
      (car x)
      (error "not a pair" x)))

Here we can say that at the point of the (car x) expression, x is definitely a pair. Conditional branches are interesting because they add a second dimension to type analysis. The question is no longer "what is the type of all variables", but "what is the type of all variables at all points in the program".

Finally, we have the effect of argument type checks in function calls. For example in the (define y (vector-length z)) definition, after (vector-length z) has been evaluated, we know that z is indeed a vector, because if it weren't, then the primitive call would raise an exception.

In summary, the information that we would like to have is what type each variable has at each program point (label). This information comes from where the variables are defined (the first source of type information), conditional branches and control-flow joins (the second source), and variable use sites that imply type checks (the third). It's a little gnarly but in essence it's a classic flow analysis. We treat the "type" of a variable as a set of possible types. A solution to the flow equations results in a set of types for each variable at each label. We use the intmap data structures to share space between the solution at different program points, resulting in an O(n log n) space complexity.

In Guile we also solve for the range of values a variable may take, at the same time as solving for type. I started doing this as part of the Compost hack a couple years ago, where I needed to be able to prove that the operand to sqrt was non-negative in order to avoid sqrt producing complex numbers. Associating range with type turns out to generalize nicely to other data types which may be thought of as having a "magnitude" -- for example a successful (vector-ref v 3) implies that v is at least 4 elements long. Guile can propagate this information down the flow graph, or propagate it in the other way: if we know the vector was constructed as being 10 elements long, then a successful (vector-ref v n) can only mean that n is between 0 and 9.

what for the typing of the things

Guile's compiler uses type analysis in a few ways at a few different stages. One basic use is in dead code elimination (DCE). An expression can be eliminated from a program if its value is never used and if it causes no side effects. Guile models side effects (and memory dependencies between expressions) with effects analysis. I quote:

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.

In an expression like (vector-ref v n), type analysis may compute that in fact v is indeed a vector and n is an integer, and also that n is within the range of valid indexes of v. In that case we can remove the type check (T) bit from the expression's effects, opening up the expression for DCE.

Getting back to the topic of this article, Guile's "type folding" pass uses type inference in three ways.

The first use of type information is if we determine that, at a given use site, a variable has precisely one type and one value. In that case we can do constant folding over that expression, replacing its uses with its value. For example, let's say we have the expression (define len (vector-length v)). If we know that v is a vector of length length 5, we can replace any use of len with the constant, 5. As an implementation detail we actually keep the definition of len in place and let DCE remove it later. We can consider this to be abstract constant propagation: abstract in the sense that it folds over abstract values, represented just as type sets and ranges, and which materializes a concrete value only if it is able to do so. Since ranges propagate through operators as well, it can also be considered as abstract constant folding; the type inference operators act as constant folders.

Another use of type information is in branches. If Guile sees (if (< n (vector-length v)) 1 2) and n and v have the right types and disjoint ranges, then we can fold the test and choose 1 or 2 depending on how the test folds.

Finally type information can enable strength reduction. For example it's a common compiler trick to want to reduce (* n 16) to (ash n 4), but if n isn't an integer this isn't going to work. Likewise, (* n 0) can be 0, 0.0, 0.0+0.0i, something else, or an error, depending on the type of n and whether the * operator has been extended to apply over non-number types. Type folding uses type information to reduce the strength of operations like these, but only where it can prove that the transformation is valid.

So that's type folding! It's a pretty neat pass that does a few things as once. Code here, and code for the type inference itself here.

type-driven unboxing

Guile uses type information in one other way currently, and that is to determine when to unbox floating-point numbers. The current metric is that whenever an arithmetic operation will produce a floating-point number -- in Scheme parlance, an inexact real -- then that operation should be unboxed, if it has an unboxed counterpart. Unboxed operations on floating-point numbers are advantageous because they don't have to allocate space on the garbage-collected heap for their result. Since an unboxed operation like the fadd floating-point addition operator takes raw floating-point numbers as operands, it also will never cause a type check, unlike the polymorphic add instruction. Knowing that fadd has no effects lets the compiler do a better job at common subexpression elimination (CSE), dead code elimination, loop-invariant code motion, and so on.

To unbox an operation, its operands are unboxed, the operation itself is replaced with its unboxed counterpart, and the result is then boxed. This turns something like:

(+ a b)

into:

(f64->scm (fl+ (scm->f64 a) (scm->f64 b)))

You wouldn't think this would be an optimization, except that the CSE pass can eliminate many of these conversion pairs using its scalar elimination via fabricated expressions pass.

A proper flow-sensitive type analysis is what enables sound, effective unboxing. After arithmetic operations have been unboxed, Guile then goes through and tries to unbox loop variables and other variables with more than one definition ("phi' variables, for the elect). It mostly succeeds at this. The results are great: summing a packed vector of 10 million 32-bit floating-point values goes down from 500ms to 130ms, on my machine, with no time spent in the garbage collector. Once we start doing native compilation we should be up to about 5e8 or 10e8 floats per second in this microbenchmark, which is totally respectable and about what gcc's -O0 performance gets.

weaknesses

This kind of type inference works great in tight loops, and since that's how many programs spend most of their time, that's great. Of course, this situation is also a product of programmers knowing that tight loops are how computers go the fastest, or at least of how compilers do the best on their code.

Where this approach to type inference breaks down is at function boundaries. There are no higher-order types and no higher-order reasoning, and indeed no function types at all! This is partially mitigated by earlier partial evaluation and contification passes, which open up space in which the type inferrer can work. Method JIT compilers share this weakness with Guile; tracing JIT runtimes like LuaJIT and PyPy largely do not.

up summing

So that's the thing! I was finally motivated to dust off this draft given the recent work on unboxing in a development branch of Guile. Happy hacking and we promise we'll actually make releases so that you can use it soon soon :)

36 responses

  1. Arne Babenhauserheide says:

    It’s really cool how different topics are coming together here. “this does not look like an optimization, but it enables this optimization I wrote about a few months ago” ← yay!

  2. Ida says:

    These blog posts on the innards of the guile compiler are great. It would nice to see them become part of the official guile manual.

  3. free itunes codes says:

    The Blog is very wonderful really its imaging. Great concept of translation for different dialect.

  4. ramps says:

    While you write any thing 1st you should have conform knowledge about it. Please wrote clearly and explain with detail
    Thanks

  5. infinitymotion.com says:

    Hello
    It's great to come across a blog every once in a while that isn't the same out of date rehashed material. Fantastic read.
    Thanks

  6. guile says:

    True Healing Self Healing can be utilized likewise as correlative treatment, since it is really a corresponding consideration. It supplements and upgrades the social insurance the patient gets in the doctor’s facility or from other human services suppliers.

  7. zapatillas nike air max says:

    And I will be sure zapatillas nike air max to check out your link-up!

  8. Francene Ferguson says:

    Avail new and existing gaming experience with pokemesh these days its trending between games lover.

    https://pokemeshapk.net/

  9. apk says:

    I really love to read such a nice article. Thanks!Keep rocking.

  10. Case Study analysis says:

    I appreciate your efforts in preparing this post. I really like your blog articles.

  11. homework help case study says:

    Pretty helpful material, much thanks for this article.

  12. showbox latest version says:

    If you face any kind of trouble during movies downloading and you want to see latest movies in HD format then you need an app like showbox nowadays this app getting much popular because of its attractive and trendy features. This is an app which is compatible with all your devices.

  13. here says:

    Single gamer and also multiplayer game

  14. itunes codes says:

    This is so true that you can get codes of itunes.

  15. msp hack says:

    This is the true hack for the game.

  16. WiFi Kill App work says:

    WifiKill APK is basically a wifi network controller app. It can disable the internet connection of other devices connected to the same wifi network. It is a very usefull tool for wifi internet users - using which you can cut other people off form a common wifi network and allocate all the bandwidth to yourself. The app is for Android only and it requires root access.

  17. new year quotes says:

    New year quotes are words of wisdom and experience that have inspired many to strive for what they believe in and never settle down with mediocrity.

  18. befikre rating says:
  19. debra says:

    I don’t understand it about using type folding in guile. I feel like it’s very hard to understand. But I think it will be a good tool for optimization in guile. I am waiting for your new release so that I can start working on it. dish network channel list

  20. kingroot download says:

    This was a great read. I've been trying my hand at rooting devices, and I love Kingroot apk to bits.

  21. msqrd for windows says:

    Download MSQRD APK Android App for your Smartphone. MSQRD APK Download Appis provided here with official links.

  22. YO YO says:
  23. https://cinemaboxapkz.com says:

    good For those who are new and also do not know much concerning Cinema Box for iOS, cinema box for iOS is the rejuvenation of Play Box HD,nice.

  24. raima singh 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. dsadsad says:
  26. https://koditvguide.com says:

    good individual suppliers have done to their Kodi \ XBMC variations, neither do I consider mounting attachments from 3rd party designers nice.

  27. acerte na lotofacil says:

    I'm dumb of opinion with this article

  28. amy jackson says:

    amazing article thanks for sharing

  29. Jennifer Wise says:

    You have done a great job on this article. It’s very readable and highly intelligent. You have even managed to make it understandable and easy to read.Thank you. Here is a gift for you, hot android game collection!!! Excellent funny and highly erotic!! Feel the heat playing these games! |

    top 7 android adult games | boob scanner android game | girl seducer android game | shake me babes android game | erotica night hentai game | Custom maid 3D 18+ hentai game |

    how to find blog commenting sites | high PR forum posting sites | social bookmarking websites | high PR profile creation sites | dofollow forum posting sites | free SEO tools |

    easy methods to make money online | survey website review | GlobalTestMarket survey website review | ways to make money online | make money online with CashCrate | learn how to qualify for online surveys |

  30. Mangungur says:

    Entrepreneurial individuals leave their office places of work in favor of a personal business in the privacy of their homes. obat herbal memperbaiki fungsi hati These businesses can sell anything to internet users, starting from clothes and jewelry and finishing with houses and cars. In order to work, these internet marketing businesses use elaborate websites.

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

  32. Mangungur says:

    I simply had to thank you so much again. I am not sure the things that I would’ve implemented without the smart ideas shared by you on this concern. obat herbal memperbaiki fungsi hati It became the intimidating problem for me, however , taking a look at your expert way you solved the issue took me to jump with joy. I’m happier for this help and wish you know what an amazing job your are doing educating the rest all through your webpage. More than likely you’ve never met all of us.

  33. Nawly Booger says:

    Starting at a very early age China teaches its children that you can only succeed if you are better than the others. They are tested as soon as they come to school. Only the best can go to college and then get a good job. Examinations are held very often and lists of students rankings are posted on the walls of a school. Shanghai students study much harder than western pupils do and they spend less time on extracurricular activities or sport. Teachers are also respected , paid well and highly motivated .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

  34. Nawly Booger says:

    Starting at a very early age China teaches its children that you can only succeed if you are better than the others. They are tested as soon as they come to school. Only the best can go to college and then get a good job. Examinations are held very often and lists of students rankings are posted on the walls of a school. Shanghai students study much harder than western pupils do and they spend less time on extracurricular activities or sport. Teachers are also respected , paid well and highly motivated .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

  35. Khalid says:

    Absolutely right. Competition always force you to work hard and get more results. A healthy competition is good and encourage you to put more efforts and stretch more business. So it is good to have a competitor as this is the key driver of performance and inspires the adoption of innovation. Thanks.penyebab asam lambungkunyit obat asam lambunggejala asam lambungmadu untuk asam lambung

  36. james clark says:

    Valentine's Day, also called Saint happy valentines day Valentine's Day or the Feast ofvalentines day wishes Saint Valentine, is an annual holiday celebrated on February 14. It originated as a Western Christian liturgical feast day honoring one or more early saints named Valentinus, and is recognized as a significant cultural and commercial celebration in many regions around the world, although it is not a public holiday in any country. Valentine's Dayvalentines day quotes is celebrated on February 14 Valentine's Day is also a very popular date for weddings..It is a festival of romantic love and many people give cards, letters, flowers or presents to their spouse or partner. They may also arrange a romantic meal in a restaurant or night in a hotel. Common symbols of Valentine's Day are hearts, red roses and Cupid.The most common Valentine's Day symbols are the heart, particularly in reds and pinks, and pictures or models of Cupid. Cupid is usually portrayed as a small winged figure with a bow and arrow.Many people celebrate their love for their partner by sending cards or letters, giving gifts or flowers and arranging meals in restaurants or romantic nights in hotels. People who would like to have a romantic relationship with somebody may use the occasion to make this known, often anonymously. Valentine's cards are often decorated with images of hearts, red roses or Cupid.valentines day wallpapers Common Valentine's Day gifts are flowers chocolates, candy, lingerie and champagne or sparkling wine

Leave a Reply