Questions concerning the LLVM backend - i.e. 'proc point splitting'

[David Spitzenberg]

Simon

> |  Could you explain the need of further info-tables for 'inner'
> |  proc-points (those, which are not the entry-block of a function) to
> |  me, please?
> 
> The main purpose of inner info tables is this.  Given (case e of blah) we push a return address (for 'blah') on the stack and evaluate 'e'.  During evaluation of 'e', garbage collection may take place.  So the garbage collector needs to walk the stack to follow live pointers.  Who knows what pointers are live?  Answer: the code for 'blah' clearly knows what pointers are alive in the current stack frame, because it is going to access them.  So the return address gets an info table that makes that implicit knowledge explicit, as a bitmap describing the liveness/pointer-hood of the stack frame.
> 
> Addresses that are only jumped to don’t need info tables.
> 
> It would be great if, as you learn about this stuff, you could add to the Commentary
> https://ghc.haskell.org/trac/ghc/wiki/Commentary
> to capture what you have learned.

Thank you very much! In cases I find the current description imprecise
or incomplete I can add what I've learned to the Commentary of course.

> |  The documentation states, that proc-point splitting is only required
> |  by the LLVM backend (see [2]). Does the cmm-pipeline perform proc-
> |  point splitting even when using the native code generator?
> 
> I'm not certain, but I don't think so.
> 
> |  As stated above, the major problem of LLVM seems to be inferring
> |  control flow when it comes to call proc-points. As it's hard to avoid
> |  proc-point splitting, we leave the cmm-pipeline 'as-is'. We modify the
> 
> I regard the whole proc-point thing as a major wart.  I think we should work hard to eliminate it.  So: another line of thought might be: how could we influence LLVM so that we didn't need proc-point splitting?

I totally agree with you here. However, determining how LLVM needs to be
influenced to eliminate proc-point splitting is a thing I won't be
capable of doing mid term because of my current knowledge and lack of time.

> |  To make control flow more apparent to LLVM, they came up with the
> |  following idea. Remark before showing the idea: I know that it greatly
> 
> I'm sorry to say that I didn't really understand the idea.  Maybe someone else did?  David Terei?

My apologies for being imprecise. I hope to find the time to
work out a little demonstration during the upcoming holidays. I'm
currently fully occupied by university because of upcoming exams this week.

> If you are seriously about investing effort in the back end, I'd be happy to help; in that case a Skype call is probably the best way.

That is a great idea. Due to the above mentioned time constraints I
propose that we follow up in January.

Regards,

David





> Simon
> 
> |  interferes with CPS. It leaves parts of the continuation-handling to
> |  the implicit LLVM call-stack. Further, this does not solve the problem
> |  of proc-point splitting at all. It is more a workaround than a
> |  solution.
> |  But it would greatly increase LLVM's possibilities to optimize code
> |  later on. That's why I found this idea worth mentioning. Especially
> |  because after reading your answer, Ben, I'm somewhat convinced that
> |  solving the problem of proc-point splitting is nearly impossible with
> |  the capabilities of LLVM IR available at the moment. Now back to the
> |  idea.
> |  
> |  As stated above, the major problem of LLVM seems to be inferring
> |  control flow when it comes to call proc-points. As it's hard to avoid
> |  proc-point splitting, we leave the cmm-pipeline 'as-is'. We modify the
> |  code, llvmGen produces when it comes to call proc-points instead. All
> |  other types of proc-points remain unchanged.
> |  
> |  Initial situation in pseudo cmm:
> |  
> |  foo() {
> |  ...
> |  call bar() returns to cont // bar defined externally
> |  
> |  cont:
> |  ...
> |  }
> |  
> |  After proc-point splitting, this is converted into LLVM IR similar to
> |  the following:
> |  
> |  @foo() {
> |  ...
> |  store @cont(), %Sp ; push continuation on the stack tail call @bar() ;
> |  @bar defined externally }
> |  
> |  @cont() {
> |  ...
> |  }
> |  
> |  To fix the above issue, we introduce a method, which restores the
> |  pointers Sp, Hp and the register R1 (among everything else, what has
> |  to be restored) and 'fakes' the continuation. Note, that '@restore'
> |  returns without calling into the continuation. This way, the call into
> |  the continuation can be made direct. The above code would be
> |  transformed into something similar to the following:
> |  
> |  @foo() {
> |  ...
> |  store @restore(), %Sp ; 'fake' continuation call @bar() ; br label
> |  restore
> |  
> |  restore:
> |  %Sp = load (getelementptr @environment 0, 0) ; restore what has to be
> |  ... ; restored tail call @cont() }
> |  
> |  @cont() {
> |  ...
> |  }
> |  
> |  @restore(%Sp, %Hp, %R1, ...) {
> |  store %Sp, (getelementptr @environment 0, 0) ; store everything into
> |  ... ; global variable ret void }
> |  
> |  @environment ; structure of type similar to {i64*, i64*, i64*, i64,
> |  i64, ..}
> |  
> |  As an alternative, the above transformation could be done by a LLVM
> |  pass. llvmGen could then annotate the continuation of calls call cite.
> |  This would greatly simplify the detection of the correct continuation.
> |  
> |  What do you think about this idea? Especially when thinking about the
> |  interference with CPS?
> |  
> |  Regards,
> |  
> |  David
> |  
> |  
> |  
> |  
> |  [1]
> |  https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/GeneratedCod
> |  e#Importantconceptsinthemachine
> |  
> |  [2]
> |  https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/CodeGen#Seco
> |  ndstage:theCmmpipeline
> |  
> |  
> |  
> |  
> |  On 11/21/2015 12:00 AM, Ben Gamari wrote:
> |  > Simon Peyton Jones <simonpj at microsoft.com> writes:
> |  >
> |  >> David
> |  >>
> |  >> All this stuff is terribly paged-out for me. But I'd love someone
> |  to
> |  >> pay attention to some of this back-end stuff, so if you'd like to
> |  >> work there, I'd like to help you.
> |  >>
> |  >> David Terei was also thinking of getting rid of proc point
> |  splitting
> |  >> for LLVM (see attached email and the notes attached to it)
> |  >>
> |  >> Simon Marlow also was thinking about this; see his attached email.
> |  >>
> |  >> The main *reason* for establishing a proc-point is so that, when
> |  >> generating C code (which we don't do any more) you can take its
> |  >> address. E.g.
> |  >>
> |  >> foo() { ... Push &bar onto the stack (effectively a return address)
> |  >>   Jump to thingumpy }
> |  >>
> |  >> bar() { ... }
> |  >>
> |  >> Really bar is part of foo, but we have make it a separate top level
> |  >> thing so that we can take the address of bar and push it on the
> |  stack.
> |  >>
> |  >> The trouble is that if there is a label inside bar that foo wants
> |  to
> |  >> jump to (i.e. without pushing &bar etc) then we have to make that
> |  >> label too into a proc-point, so that both foo and bar can see it.
> |  >> Urgh.
> |  >>
> |  >> In LLVM this probably is not true; presumably you can take the
> |  >> address of any label?
> |  >>
> |  > This is true. While labels themselves have function-local scope in
> |  > LLVM, there is an expression, `blockaddress`, which allows you to
> |  take
> |  > an address to a label in another function [1]. That being said, in
> |  > reading through the documentation it's not at all clear to me that
> |  it
> |  > would be safe to jump to such an address. In fact, given that the
> |  > instruction that this expression is supposed to be used with,
> |  > `indirectbr`, can only be used for local blocks, I suspect it is
> |  not.
> |  > More information about this feature can be found here [2].
> |  >
> |  > The jump issue aside, I don't know how you would deal with
> |  > tables-next-to-code. The prefix data support that currently
> |  available
> |  > in LLVM is attached to functions and I unfortunately don't see that
> |  > changing any time soon.
> |  >
> |  > Ultimately it seems that trying to refer to labels defined in other
> |  > functions is using LLVM against the way it was intended. One
> |  > alternative would be to teach llvmGen to merge mutually recusive
> |  > top-level functions into a single LLVM function during code
> |  > generation. Otherwise I'm afraid you are stuck with either the
> |  status
> |  > quo or attempting to improve on LLVM's own cross-procedure
> |  optimization ability.
> |  >
> |  > That being said, it sounds as though eliminating proc-point
> |  splitting
> |  > would make for quite a nice project in the native code generator.
> |  >
> |  > Cheers,
> |  >
> |  > - Ben
> |  >
> |  >
> |  > [1]
> |  >
> |  https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fllvm.o
> |  > rg%2fdocs%2fLangRef.html%23addresses-of-basic-
> |  blocks&data=01%7c01%7csi
> |  >
> |  monpj%40064d.mgd.microsoft.com%7c7fdbfda0b4514a098c4d08d2f74448f1%7c72
> |  >
> |  f988bf86f141af91ab2d7cd011db47%7c1&sdata=nKVLgmZezUdEYL%2fma1exMMPLbcT
> |  > RkaE1JrvVaR1EesY%3d [2]
> |  >
> |  https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fblog.l
> |  > lvm.org%2f2010%2f01%2faddress-of-label-and-indirect-
> |  branches.html&data
> |  >
> |  =01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c7fdbfda0b4514a098c4d08d2
> |  >
> |  f74448f1%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=BTMdZESwYS4tZa5W
> |  > sOAqyFutoI5xNNFDe0b%2bdKC3ODs%3d [3]
> |  >
> |  https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fllvm.o
> |  > rg%2fdocs%2fLangRef.html%23prefix-
> |  data&data=01%7c01%7csimonpj%40064d.m
> |  >
> |  gd.microsoft.com%7c7fdbfda0b4514a098c4d08d2f74448f1%7c72f988bf86f141af
> |  >
> |  91ab2d7cd011db47%7c1&sdata=rdo4ZLjjE%2bWxNykVL%2bSuToWioY6nzQpflSk296E
> |  > 8W70%3d
> |  >
>