RFC: Enabling Module passes post-ISel

Hi,

[Apologies to those receiving this mail twice - used the old list address by accident]

In LLVM it is currently not possible to write a Module-level pass (a pass that modifies or analyzes multiple MachineFunctions) after DAG formation. This inhibits some optimizations[1] and is something I’d like to see changed.

The problem is that in the backend, we emit a function at a time, from DAG formation to object emission. So no two MachineFunctions ever exist at any one time. Changing this necessarily means increasing memory usage.

I’ve prototyped this change and have measured peak memory usage in the worst case scenario - LTO’ing llc and clang. Without further ado:

llvm-lto llc: before: 1.44GB maximum resident set size
after: 1.68GB (+17%)

llvm-lto clang: before: 2.48GB maximum resident set size
after: 3.42GB (+33%)

The increases are very large. This is worst-case (non-LTO builds would see the peak usage of the backend masked by the peak of the midend) but still - pretty big. Thoughts? Is this completely no-go? is this something that we just need to do? Is crippling the backend architecture to keep memory down justified? Is this something we could enable under an option?

Any input appreciated. I can also provide a proof-of-concept patch for people to test if wanted.

Cheers,

James

[1] A concrete (and the motivating) example is the sharing of constants in constantpools across multiple functions. Two small functions that use the same constant must currently create their own copy of that constant. For many reasons that I’d not like to go into in this thread, we can’t implement this at all in the current infrastructure.

I also recently did a prototype that enables MachineModulePasses (https://github.com/MatzeB/llvm/tree/MachineModulePass). I assume your patch looks similar (I did not do any measurements with mine).

I believe this could be done in a way so the memory stays at current levels if no machine module pass issued (simply remove the memory used by the MachineFunction after we AsmPrinted it). So that would at least make the infrastructure available for people to experiment with. So maybe that is a good first step?

So far all the uses I have seen did not convince me that the increased memory consumption is worth it (by default). But IMO if we can provide by infrastructure for MachineModulePasses with nearly zero cost in case no machinemodulepass is used, then I’d say we should go for it.

  • Matthias

Hi James, Matthias

I recently proposed the idea of deleting the IR for a function after its reached the AsmPrinter. This was before the idea of MachineModulePasses. I was seeing peak memory savings of 20% when LTOing clang itself.

So it might be possible to trade the memory so that IR and MachineIR aren’t live at the same time for all functions. But that depends on whether a MachineModulePass would want access to the IR. AA is the typical example of MachineIR referencing back to IR. I knew it was safe to delete IR when we hit the AsmPrinter because nothing at (or beyond) that point needs AA.

Cheers,
Pete

These are non-debug build, mind you trying with debug info?

Thanks,

Hi Mehdi,

I’ve just done an LTO build of llc with debug info:
before: 7.66GB maximum resident set size
after: 8.05GB (+5.1%)

Cheers,

James

James Molloy via llvm-dev <llvm-dev@lists.llvm.org> writes:

In LLVM it is currently not possible to write a Module-level pass (a pass that
modifies or analyzes multiple MachineFunctions) after DAG formation. This
inhibits some optimizations[1] and is something I'd like to see changed.

The problem is that in the backend, we emit a function at a time, from DAG
formation to object emission. So no two MachineFunctions ever exist at any one
time. Changing this necessarily means increasing memory usage.

I've prototyped this change and have measured peak memory usage in the worst
case scenario - LTO'ing llc and clang. Without further ado:

  llvm-lto llc: before: 1.44GB maximum resident set size
                  after: 1.68GB (+17%)

  llvm-lto clang: before: 2.48GB maximum resident set size
                  after: 3.42GB (+33%)

The increases are very large. This is worst-case (non-LTO builds would see the
peak usage of the backend masked by the peak of the midend) but still - pretty
big. Thoughts? Is this completely no-go? is this something that we *just need*
to do? Is crippling the backend architecture to keep memory down justified? Is
this something we could enable under an option?

Personally, I think this price is too high. I think that if we want to
enable machine module passes (which we probably do) we need to turn
MachineFunction into more of a first class object that isn't just a
wrapper around IR.

This can and should be designed to work something like Pete's solution,
where we get rid of the IR and just have machine level stuff in memory.
This way, we may still increase the memory usage here, but it should be
far less dramatic.

You'll note that doing this also has tangential benefits - it should be
helpful for simplifying MIR and generally improving testability of the
backends.

Hi all,

I like all the ideas so far. Here are my thoughts:

I think that fundamentally users of LLVM should be able to opt-in to more aggressive or intensive computation at compile time if they wish. Users’ needs differ, and while a 33% increase in clang LTO is absolutely out of the question for some people, for those developing microcontrollers or HPC applications that may well be irrelevant. Either the volume of code expected is significantly smaller or they’re happy to trade off compile time for expensive server time. That does not mean that we shouldn’t strive for a solution that can be acceptable by all users. On the other hand making something opt-in makes it non-default, and that increases the testing surface.

Tangentially I think that LLVM currently doesn’t have the right tuning knobs to allow the user to select their desired tradeoff. We have one optimization flag -O{s,z,0,1,2,3} which encodes both optimization goal (a point on the pareto curve between size and speed) and amount of effort to expend at compile time achieving that goal. Anyway, that’s besides the point.

I like Justin’s idea of removing IR from the backend to free up memory. I think it’s a very long term project though, one that requires significant (re)design; alias analysis access in the backend would be completely broken and BasicAA among others depends on seeing the IR at query time. We’d need to work out a way of providing alias analysis with no IR present. I don’t think that is feasible for the near future.

So my suggestion is that we go with Matthias’ idea - do the small amount of refactoring needed to allow MachineModulePasses on an opt-in basis. The knobs to enable that opt-in might need some more bikeshedding.

Cheers,

James

I think that fundamentally users of LLVM should be able to opt-in to more
aggressive or intensive computation at compile time if they wish. Users'
needs differ, and while a 33% increase in clang LTO is absolutely out of the
question for some people, for those developing microcontrollers or HPC
applications that may well be irrelevant. Either the volume of code expected
is significantly smaller or they're happy to trade off compile time for
expensive server time. That does not mean that we shouldn't strive for a
solution that can be acceptable by all users. On the other hand making
something opt-in makes it non-default, and that increases the testing
surface.

I agree with this reasoning in principle. LTO is already an example of
that trade off.

The problem is, as with LTO, how to make sure those options don't
bit-rot, without duplicating testing infrastructure. I don't have a
good solution for that.

Another thing that this raises (and we should have done that for LTO)
is monitoring not just compile and run times, but also compile and run
time memory consumption.

I believe some people are already doing it ad-hoc, but it would be
good to have that, for example, in LNT.

So my suggestion is that we go with Matthias' idea - do the small amount of
refactoring needed to allow MachineModulePasses on an opt-in basis. The
knobs to enable that opt-in might need some more bikeshedding.

We have prior art on that, so I think it should be mostly fine.
Bikeshedding won't be necessary, not for the flags, I think.

We just have to make sure this is not something that will encumber
other changes in the area (and I'm being vague on purpose, as I can't
think of anything). :slight_smile:

cheers,
--renato

Dear All,

Just to add my two cents to the discussion, we're working on a project that will require inter-procedural analysis on the MachineInstr IR that will also use inter-procedural analysis information from the LLVM IR level. It isn't clear yet whether we will need to keep the LLVM IR around or if we can encode the LLVM IR analysis results into the MI IR during code generation and throw the LLVM IR away, but for now, I'm thinking that we'll need both LLVM IR and MI IR in memory at once. Memory consumption isn't a problem for us as we're doing static analysis for security, so buying big hardware is a reasonable solution for us, and analysis time can grow large if needed.

If the MachineModulePass functionality is added, then we will probably use it. If no one adds it, we will probably just hack LLVM to not delete the MachineFunction's during code generation.

Regards,

John Criswell

On the idea of deleting the IR after the AsmPrinting phase: It’s a good thing to do but won’t help with MachineModule memory consumption as at the point of the MachineModulePass the AsmPrinter hasn’t run yet but we have all the IR and MIR constructed.
More notes below:

Hi all,

I like all the ideas so far. Here are my thoughts:

I think that fundamentally users of LLVM should be able to opt-in to more aggressive or intensive computation at compile time if they wish. Users’ needs differ, and while a 33% increase in clang LTO is absolutely out of the question for some people, for those developing microcontrollers or HPC applications that may well be irrelevant. Either the volume of code expected is significantly smaller or they’re happy to trade off compile time for expensive server time. That does not mean that we shouldn’t strive for a solution that can be acceptable by all users. On the other hand making something opt-in makes it non-default, and that increases the testing surface.

Tangentially I think that LLVM currently doesn’t have the right tuning knobs to allow the user to select their desired tradeoff. We have one optimization flag -O{s,z,0,1,2,3} which encodes both optimization goal (a point on the pareto curve between size and speed) and amount of effort to expend at compile time achieving that goal. Anyway, that’s besides the point.

I like Justin’s idea of removing IR from the backend to free up memory. I think it’s a very long term project though, one that requires significant (re)design; alias analysis access in the backend would be completely broken and BasicAA among others depends on seeing the IR at query time. We’d need to work out a way of providing alias analysis with no IR present. I don’t think that is feasible for the near future.

Yep, would be great to cut the IR ties but I fear it is a big project we won’t just do on the side…

So my suggestion is that we go with Matthias’ idea - do the small amount of refactoring needed to allow MachineModulePasses on an opt-in basis. The knobs to enable that opt-in might need some more bikeshedding.

My current patches probably need some more work and I’d prefer it if someone with a actual use case pushes this forward (my prototype was to help out an intern project where I don’t know when it will get upstreamed). I’d be happy to review patches.

As far as the patches go:

  • The general idea of moving the ownership of the MachineFunction from the MachineFunctionAnalysis to a Function->MachineFunction map in MachineModuleInfo worked nicely and is the way to go IMO. The API is simply a function in MachineModuleInfo that gives you the corresponding MachineFunction for a given IR Function.
  • Currently my patches do a map lookup in MachineFunction::runOnMachineFunction() to find the MachineFunction, we may want to bring MachineFunctionAnalysis back simply as a caching layer to get to the MachineFunction* faster.
  • My patches currently disable .mir file loading but that shouldn’t be too hard to fix.
  • Adding a pass after the AsmPrinter that deletes the MachineFunction will get us the current behavior where we only 1 MachineFunction is alive at the same time provided there is no ModulePass in the codegen pipeline.

Given how simple the approach turned out in the end I am not worried about correctness problems/testing when we add this code.
I do agree though that we need more testing infrastructure for compiletime / memory consumption! It is hard to notice an accidental 5-10% increase in memory usage or compiletime when you are not measuring for it. In this case it would be hard to notice the effects of accidentally adding a module pass into the codegen pipeline.

  • Matthias

From: "James Molloy" <james@jamesmolloy.co.uk>
To: "Justin Bogner" <mail@justinbogner.com>, "James Molloy via
llvm-dev" <llvm-dev@lists.llvm.org>
Cc: "Hal Finkel" <hfinkel@anl.gov>, "Chandler Carruth"
<chandlerc@google.com>, "Matthias Braun" <matze@braunis.de>, "Pete
Cooper" <peter_cooper@apple.com>
Sent: Tuesday, July 19, 2016 9:16:02 AM
Subject: Re: [llvm-dev] RFC: Enabling Module passes post-ISel

Hi all,

I like all the ideas so far. Here are my thoughts:

I think that fundamentally users of LLVM should be able to opt-in to
more aggressive or intensive computation at compile time if they
wish. Users' needs differ, and while a 33% increase in clang LTO is
absolutely out of the question for some people, for those developing
microcontrollers or HPC applications that may well be irrelevant.

I agree. A 33% increase is absorbable in many environments.

Either the volume of code expected is significantly smaller or
they're happy to trade off compile time for expensive server time.
That does not mean that we shouldn't strive for a solution that can
be acceptable by all users. On the other hand making something
opt-in makes it non-default, and that increases the testing surface.

Tangentially I think that LLVM currently doesn't have the right
tuning knobs to allow the user to select their desired tradeoff. We
have one optimization flag -O{s,z,0,1,2,3} which encodes both
optimization *goal* (a point on the pareto curve between size and
speed) and amount of effort to expend at compile time achieving that
goal. Anyway, that's besides the point.

I like Justin's idea of removing IR from the backend to free up
memory. I think it's a very long term project though, one that
requires significant (re)design; alias analysis access in the
backend would be completely broken and BasicAA among others depends
on seeing the IR at query time. We'd need to work out a way of
providing alias analysis with no IR present. I don't think that is
feasible for the near future.

So my suggestion is that we go with Matthias' idea - do the small
amount of refactoring needed to allow MachineModulePasses on an
opt-in basis. The knobs to enable that opt-in might need some more
bikeshedding.

This makes sense to me. I expect that targets will be able to opt-in in some optimization-level-dependent fashion.

-Hal

I submitted a cleaned up patch here: https://reviews.llvm.org/D23736

  • Matthias