wingolog

guile compiler tasks

4 February 2016 9:38 PM (guile | compilers | gnu | igalia | linkers)

Hey! We released Guile 2.1.2, including the unboxing work, and we fixed the slow bootstrap problem by shipping pre-built bootstraps in tarballs. A pretty OK solution in my opinion; check it out!

future work

At this point I think I'm happy with Guile's compiler and VM, enough for now. There is a lot more work to do but it's a good point at which to release a stable series. There will probably be a number of additional pre-releases, but not any more significant compiler/VM work that must be done before a release.

However, I was talking with Guilers at FOSDEM last weekend and we realized that although we do a pretty good job at communicating the haps in compiler-land, we don't do a good job at sharing a roadmap or making it possible for other folks to join the hack. And indeed, it's been difficult to do so while things were changing so much: I had to get things right in my head before joining in the confusion of other people's heads.

In that spirit I'd like to share a list of improvements that it would be nice to make at some point. If you take one of these tasks, be my guest: find me on IRC (wingo on freenode) and let me know, and I'll help as I am able. You need to be somewhat independent; I'm not offering a proper mentoring or anything, more like office hours or something, where you come with the problem you are having and I commiserate and give context/background/advice as I am able.

So with that out of the way, here's a huge list of stuff! Following this, more details on each one.

  1. stripping binaries

  2. full source in binaries

  3. cps in in binaries

  4. linking multiple modules together

  5. linking a single executable

  6. instruction explosion

  7. elisp optimizations

  8. prompt removal

  9. basic register allocation

  10. optimal register allocation

  11. unboxed record fields

  12. textual CPS

  13. avoiding arity checks

  14. unboxed calls and returns

  15. module-level inlining

  16. cross-module inlining

As a bonus, in the end I'll give some notes on native compilation. But first, the hacks!

stripping binaries

Guile uses ELF as its object file format, and currently includes source location information as DWARF data. On space-constrained devices this might be too much. Your task: add a hack to the linker that can strip existing binaries. Read Ian Lance Taylor's linker articles for more background, if you don't know things about linkers yet.

full source in binaries

Wouldn't it be nice if the ELF files that Guile generates actually included the source as well as the line numbers? We could do that, in a separate strippable ELF section. This point is like the reverse of the previous point :)

cps in in binaries

We could also include the CPS IR in ELF files too. This would enable some kinds of link-time optimization and cross-module inlining. You'd need to define a binary format for CPS, like LLVM bitcode or so. Neat stuff :)

linking multiple modules together

Currently in Guile, just about every module is a separate .go file. Loading a module will cause a few stat calls and some seeks and reads and all that. Wouldn't it be nice if you could link together all the .go files that were commonly used into one object? Again this is a linker hack, but it needs support from the run-time as well: when the run-time goes to load a file, it should first check in a registry if that file has been logically provided by some other file. We'd be able to de-duplicate constant data from various modules. However there is an initialization phase when loading a .go file which effectively performs all the relocations needed by constants that need a fix-up at load-time; see the ELF article I linked to above for more. For some uses, it would be OK to produce one relocation/initialization procedure. For others, if you expected to only load a fraction of the modules in a .go file, it would be a lose on startup time,
so you would probably need to support lazy relocation when a module is first loaded.

Anyway, your task would be to write a linker hack that loads a bunch of .go files, finds the relocations in them, de-duplicates the constants, and writes out a combined .go file that includes a table of files contained in it. Good luck :) This hack would work great for Emacs, where it's effectively a form of unexec that doesn't actually rely on unexec.

linking a single executable

In the previous task, you could end up with the small guile binary that links to libguile (or your binary linking to libguile), and then a .go file containing all the modules you are interestd in. It sure would be nice to be able to link those together into just one binary, or at least to link the .go into the Guile binary. If the Guile is statically linked itself, you would have a statically linked application. If it's dynamically linked, it would remain dynamically linked. Again, a linker hack, but one that could provide a nicer way to distribute Guile binaries.

instruction explosion

Now we get more to the compiler side of things. Currently in Guile's VM there are instructions like vector-ref. This is a little silly: there are also instructions to branch on the type of an object (br-if-tc7 in this case), to get the vector's length, and to do a branching integer comparison. Really we should replace vector-ref with a combination of these test-and-branches, with real control flow in the function, and then the actual ref should use some more primitive unchecked memory reference instruction. Optimization could end up hoisting everything but the primitive unchecked memory reference, while preserving safety, which would be a win. But probably in most cases optimization wouldn't manage to do
this, which would be a lose overall because you have more instruction dispatch.

Well, this transformation is something we need for native compilation anyway. I would accept a patch to do this kind of transformation on the master branch, after version 2.2.0 has forked. In theory this would remove most all high level instructions from the VM, making the bytecode closer to a virtual CPU, and likewise making it easier for the compiler to emit native code as it's working at a lower level.

elisp optimizations

Guile implements Emacs Lisp, and does so well. However it hasn't been the focus of a lot of optimization. Emacs has a lot of stuff going on on its side, and so have we, so we haven't managed to replace the Elisp interpreter in Emacs with one written in Guile, though Robin Templeton has brought us a long way forward. We need someone to do both the integration work but also to poke the compiler and make sure it's a clear win.

prompt removal

It's pretty natural to use delimited continuations when compiling some kind of construct that includes a break statement to Guile, whether that compiler is part of Elisp or just implemented as a Scheme macro. But, many instances of prompts can be contified, resulting in no overhead at run-time. Read up on contification and contify the hell out of some prompts!

basic register allocation

Guile usually tries its best to be safe-for-space: only the data which might be used in the future of a program is kept alive, and the rest is available for garbage collection. Notably, this applies to function arguments, temporaries, and lexical variables: if a value is dead, the GC can collect it and re-use its space. However this isn't always what you want. Sometimes you might want to have all variables that are in scope to be available, for better debugging. Your task would be to implement a "slot allocator" (which is really register allocation) that keeps values alive in the parts of the programs that they dominate.

optimal register allocation

On the other hand, our slot allocator -- which is basically register allocation, but for stack slots -- isn't so great. It does OK but you can often end up shuffling values in a loop, which is the worst. Your task would be to implement a proper register allocator: puzzle-solving, graph-coloring, iterative coalescing, something that really tries to do a good job. Good luck!

unboxed record fields

Guile's "structs", on which records are implemented, support unboxed values, but these values are untyped, not really integrated with the record layer, and always boxed in the VM. Your task would be to design a language facility that allows us to declare records with typed fields, and to store unboxed values in those fields, and to cause access to their values to emit boxing/unboxing instructions around them. The optimizer will get rid of those boxing/unboxing instructions if it can. Good luck!

textual CPS

The CPS language is key to all compiler work in Guile, but it doesn't have a nice textual form like LLVM IR does. Design one, and implement a parser and an unparser!

avoiding arity checks

If you know the procedure you are calling, like if it's lexically visible, then if you are calling it with the right number of arguments you can skip past the argument check and instead do a call-label directly into the body. Would be pretty neat!

unboxed calls and returns

Likewise if a function's callers are all known, it might be able to unbox its arguments or return value, if that's a good idea. Tricky! You could start with a type inference pass or so, and maybe that could produce some good debugging feedback too.

module-level inlining

Guile currently doesn't inline anything that's not lexically visible. Unfortunately this restriction extends to top-level definitions in a module: they are treated as mutable and so never inlined/optimized/etc. Probably we need to change the semantics here such that a module can be compiled as a unit, and all values which are never mutated can be assumed to be constant. Probably you also want a knob to turn off this behavior, but really you can always re-compile and re-load a module as a whole if re-loading a function at run-time doesn't work because it was inlined. Anyway. Some semantic work here, but some peval work as well. Be careful!

cross-module inlining

Likewise Guile currently doesn't inline definitions from other modules. However for small functions this really hurts. Guile should probably serialize tree-il for small definitions in .go files, and allow peval to speculatively inline imported definitions. This is related to the previous point and has some semantic implications.

bobobobobobonus! native compilation

Thinking realistically, native compilation is the next step. We have the object file format, cool. We will need the ability to call out from machine code in .go files to run-time functions, so we need to enhance the linker, possibly even with things like PLT/GOT sections to avoid dirtying too many pages. We need to lower the CPS even further, to get closer to some kind of machine model, then go specific, with an assembler for each architecture. The priority in the beginning will be simplicity and minimal complexity; good codegen will come later. This is obviously the most attractive thing but it's also the most tricky, design-wise. I want to do at least part of this, so though you can't have it all, you are welcome to help :)

That's it for now. I'll amend the post with more things as and when I think of them. Comments welcome too, as always. Happy hacking!

63 responses

  1. Johnny says:

    I had a 3x speedup for a macro expander for pascal. We have some crazy recursive macros with lots of precomputation. They were slow on 2.0, so I had a look around for different scheme impementations. A friend suggested trying the 2.1 branch, and you sure sprinkled some magic optimization dust over that. Thanks!

  2. STATA Online Homework Help says:

    STATA Stats Homework, assignment and Project Help, STATA Assignment Help Stata is a statistical software package; it was created by Stata Corporation in 1985. Most of its own users work in research.

  3. Session Tracking Java Help says:

    Session Tracking Java Assignment Help, Online Java Project Help Session Tracking  HTIP is a stateless protocol, which means that each request is independent of the -previous one, However, in some applications

  4. trustworthy research paper writing says:

    When you compose a c++ program, the following stride is to gather the project before running it. The accumulation is the procedure which change over the system written in intelligible dialect like C, C++ and so on into a machine code

  5. Research Paper Writers For Hire says:

    Most of the technological task competition my use box using guile as a developed system predictor rather than as an addition language.

  6. check this says:

    There are many tool to generate free codes online and this one is truely a blessing for all as they can generate free cards for the music of itunes.

  7. 640-911 test says:

    Thank you very much for this valuable contribution and informative.

  8. Human Resource Dissertation Help says:

    Hi buddy, your blog' s design is simple and clean and i like it. Your blog posts about Online Dissertation Help are superb. Please keep them coming. Greets!!

  9. Managerial Accounting Assignment Help says:

    Get the dissertation writing service students look for these days with the prime focus being creating a well researched and lively content on any topic.

  10. assignment writing help Quuensland says:

    If you want local quuensland photos to be added in your assignment then you can hire assignment writing help Quuensland where you will find a local writer

  11. nguyen thi quynh says:

    thank for you sharing

  12. thesis writing service reviews says:

    Information about guile compiler task is a new one for me. It is completely related to technology. I am honestly say that i have weak in this field and the post really helped me. Thanks a lot!

  13. clash royale hack says:

    Hello friends, do you know about the clash royale gems generator. If not then you should know more about these generator and generate free unlimited gems as you need and this will helps in wining fights in clash royale game.

  14. sneakers isabel marant says:

    It's a lot of sneakers isabel marant work. But it's so worth it in the end.

  15. Java Assignment Help says:

    Looking for java assignment help service?
    Awesome!!
    I am providing you one of the trustworthy online java Homework help. Once you will use my java programming homework help service, your grade in your java subject will be boosted.
    So, what are you waiting for? Just contact me now to get instant help.

  16. Java Assignment Help says:

    I will help you in your java programming assignment. I am a oracle certified java programmer.
    I will do your java project, java assignment, java homework or any other java programming task.

  17. guru of writing says:

    Awesome article, it worked for me, thanks!

  18. Accounting Project Help says:

    I'm getting excited about this kind of beneficial information of your stuff in the future

  19. Finance Thesis Assistance says:

    They are not able to finish the writing assignments on time. For some students, writing any writing assignments is able to waste their time

  20. Dissertation writing service UK says:

    The stable release is released with a verity features. it is nice that will probably be a number of additional pre-releases, but not any more significant compile work that must be done before a release.

  21. Essay Writing Service says:

    I think ikt has a seperate code to compile default at any instant for any file that it have not been compiled or encountered yet. It makes the compilation process faster

  22. Scalp Psoriasis says:

    I enjoyed over read your blog post. Your blog have nice information, I got good ideas from this amazing blog. I am always searching like this type blog post. I hope I will see again.

  23. Matlab Assignment Help says:

    Thanks for sharing the info, keep up the good work going.... I really enjoyed exploring your site. good resource. 

  24. http://mpghserialgames.net/ says:

    Incredible sight of pixel car racer hack you got there buddy.

  25. videomix pro says:

    thanks for posting

  26. Ivey case study analysis says:

    Amazing article thanks or sharing..

  27. HBR Case Analysis says:

    Pretty helpful material, much thanks for this article

  28. IT Management essay writing Help says:

    I loved the way you discuss the topic great work thanks for the share Your informative post.

  29. MBA Dissertation Editing Help says:

    Thanx for sharing such useful post keep it up :)

  30. apk says:

    Your website is so cool. I am impressed by the info that you have on this site. I will be wanting ahead for additional of your respective posts. Stick with it!

  31. login says:

    Your blog is really exciting and inspiration to several. It reveals how nicely you understand this subject

  32. windgio says:

    http://images.google.mn/url?q=http://thammycatmimat.com
    http://images.google.ms/url?q=http://thammycatmimat.com
    http://images.google.mv/url?q=http://thammycatmimat.com
    http://images.google.mu/url?q=http://thammycatmimat.com
    http://images.google.nl/url?q=http://thammycatmimat.com
    http://images.google.mw/url?q=http://thammycatmimat.com
    http://images.google.no/url?q=http://thammycatmimat.com
    http://images.google.pl/url?q=http://thammycatmimat.com
    http://images.google.ps/url?q=http://thammycatmimat.com
    http://images.google.pt/url?q=http://thammycatmimat.com
    http://images.google.ro/url?q=http://thammycatmimat.com
    http://images.google.rs/url?q=http://thammycatmimat.com
    http://images.google.ru/url?q=http://thammycatmimat.com
    http://images.google.rw/url?q=http://thammycatmimat.com
    http://images.google.se/url?q=http://thammycatmimat.com
    http://images.google.sh/url?q=http://thammycatmimat.com
    http://images.google.si/url?q=http://thammycatmimat.com
    http://images.google.sk/url?q=http://thammycatmimat.com
    http://images.google.sn/url?q=http://thammycatmimat.com
    http://images.google.sr/url?q=http://thammycatmimat.com
    http://images.google.tg/url?q=http://thammycatmimat.com
    http://images.google.tm/url?q=http://thammycatmimat.com
    http://images.google.tn/url?q=http://thammycatmimat.com
    http://images.google.tt/url?q=http://thammycatmimat.com
    http://images.google.vg/url?q=http://thammycatmimat.com

  33. plaque psoriasis says:

    Great website. A lot of useful information here. I’m sending it to several pals ans also sharing in delicious.

  34. njvgrtsd says:

    Yahoo
    [url=https://www.google.co.uk/] Yahoo [/url]
    [Yahoo ](https://www.google.co.uk/"Yahoo ")
    https://www.google.co.uk/

  35. dhruva live updates says:
  36. economics help says:

    This is really great work. Thank you for sharing such a useful information here in the blog.

  37. YO YO says:
  38. henderson locksmith says:

    I definitely enjoying every little bit of it. It is a great website and nice share. henderson locksmith

  39. leasoa says:
  40. lost car keys says:

    This is great information for students. This article is very helpful i really like this blog thanks. I also have some information relevant for online dissertation help. lost car keys

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

  42. Edward Jones Redding CA says:

    Great post! I am actually getting ready to across this information, is very helpful my friend. Also great blog here with all of the valuable information you have. Keep up the good work you are doing here. Edward Jones Redding CA

  43. how to train your dog not to bark says:

    I admit. I have not been on this web page in a long time... however it was another joy to see It is such an important topic and ignored by so many. even professionals. professionals. I thank you to help making people more aware of possible issues. how to train your dog not to bark

  44. life size batman hot toys says:

    Nice knowledge gaining article. This post is really the best on this valuable topic. life size batman hot toys

  45. homeopathy treatment for sexual problems says:

    wow really good energy programs. very interesting. homeopathy treatment for sexual problems

  46. real estate services duluth mn says:

    impressed that there is so much information about this subject that have been uncovered and you’ve done your best, with so much class. If wanted to know more about green smoke reviews, than by all means come in and check our stuff. real estate services duluth mn

  47. interracial match says:

    Thanks very much for your great contribution useful contents and information. interracial match

  48. e juice flavors list says:

    The Usa offers a lot of choices which choosing it's possible to be difficult! Narrow lower your best choices as well as let your whole family choose. e juice flavors list

  49. host a local rust server says:

    This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! host a local rust server

  50. facebook like app says:

    I read this article. I think You put a lot of effort to create this article. I appreciate your work. facebook like app

  51. automotive technician job description says:

    This is a great article thanks for sharing this informative information. I will visit your blog regularly for some latest post. I will visit your blog regularly for Some latest post. automotive technician job description

  52. spy mobile without installing software says:

    Thanks for the nice blog. It was very useful for me. I'm happy I found this blog. Thank you for sharing with us.I too always learn something new from your post. spy mobile without installing software

  53. mesa gun safe says:

    wow, great, I was wondering how to cure acne naturally. and found your site by google, learned a lot, now i’m a bit clear. I’ve bookmark your site and also add rss. keep us updated. mesa gun safe

  54. bmw x1 lease price says:

    Thank you very much for writing such an interesting article on this topic. This has really made me think and I hope to read more. bmw x1 lease price

  55. best site to buy real instagram followers says:

    I love the way you write and share your niche! Very interesting and different! Keep it coming! best site to buy real instagram followers

  56. mile high locksmithmile high locksmith says:

    Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. mile high locksmith

  57. eliza says:

    Very interesting blog. A lot of blogs I see these days don’t really provide anything that I’m interested in, but I’m most definitely interested in this one. website design westchester ny

  58. Dark Web says:

    Thank you SO MUCH for the useful information! I spent hours upon hours researching this over a year ago to start a blog, but my mother fell ill, so the blog was put on the back burner. I’m now having to re educate myself on the best way to go. Hopefully your suggestions will save me more hours upon hours of research! Thank you again!Techlazy.comHowmate.comCrazyask.comUpdateLand.comFeedegg.comTechube.comDeep web linksDark web linksDarknet MarketsHow to access the Dark WebHow to access the Deep Web

  59. Assigment help says:

    I have to say that it is some quality site I have visited. The blogs have good content and the site is well-designed as well. Students struggling to write their assignments can try our online assignment help and can get a quality academic assignment written from us. https://www.allassignmenthelp.com

  60. Game of Thrones Season 7 Episode 1 says:

    How to watch game of thrones season 7 online for free. Are you exited about season 7 of Game of thrones then you are on right place.

  61. buy instagram followers free trial says:

    I read a article under the same title some time ago, but this articles quality is much, much better. How you do this buy instagram followers free trial

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

  63. ada says:

    mobil2
    [url=http://bit.ly/1bdDlXc]mobil5[/url]

Leave a Reply