Page MenuHomePhabricator

[ORC] WIP Speculative compilation
ClosedPublic

Authored by pree-jackie on Jun 15 2019, 8:13 AM.

Details

Reviewers
lhames
dblaikie
Summary

Initial Patch to Support Speculative Compilation in ORC v2 APIs. Idea is to replicate the mapping provided by the lazyreexports utility (SymbolAliasMap) to find which Callable Symbol the stubs symbols lazy reexports and where the Callable Symbol lives (Impl JITDylibs).

Instrument IR with calls to the run time function orc_speculate_for at the entry block of Functions which calls other functions. At run time the call to __orc_speculate_for triggers the compilation of functions and update the pointer of the lazy reexports stubs.

This Patch introduces two maps : Imap and SpeculationMap,

Imap - replicates the source symbols and impl JITDylibs for each alias.
Speculation Map - lives inside the Speculator, which keeps track of for each function address what are the likely functions that the function may call at runtime.

Simple flow is at runtime Speculator queries the Imap to find the source symbols and impl JITDylibs.

Things to do:

  • Write run time function implementation.
  • Make Stub Pointer Updation through Notify Resolved
  • Test Cases

Current Implementation finds likely functions one hop at a time, in my opinion is it not a drawback.

Diff Detail

Event Timeline

pree-jackie created this revision.Jun 15 2019, 8:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 15 2019, 8:13 AM
pree-jackie retitled this revision from Speculative compilation in ORC to [ORC] WIP Speculative compilation.Jun 15 2019, 8:37 AM
pree-jackie edited the summary of this revision. (Show Details)
pree-jackie edited the summary of this revision. (Show Details)
pree-jackie edited the summary of this revision. (Show Details)
pree-jackie removed subscribers: mgorny, hiraditya.
pree-jackie edited the summary of this revision. (Show Details)Jun 15 2019, 8:39 AM

Can you please update this patch with full context?

I assume that you're posting this for initial feedback, but a patch description explaining the usage model would be helpful.

llvm/include/llvm/ExecutionEngine/Orc/Speculation.h
55

Don't use assert(0 && ..., use llvm_unreachable.

I assume that you're posting this for initial feedback, but a patch description explaining the usage model would be helpful.

Ignore this; you just did ;)

This is an excellent start!

llvm/include/llvm/ExecutionEngine/Orc/Speculation.h
46–47

This should be:

assert(It.second && "Source Entities are already tracked for this symbol?");
55

LLVM's coding style does not use braces for single conditional statements, so it should be:

if (Position != Maps.end())
  return Position->getSecond();

rather than

if (Position != Maps.end()) {
  return Position->getSecond();
}

More generally, this function can be reduced to:

ImplPair getImplFor(SymbolStringPtr StubAddr) {
  auto Position = Maps.find(StubAddr);
  assert(Position != Maps.end() &&
         "Source Entities are not tracked for Symbol?");
  return Position->getSecond();
}
78–84

Applying the coding conventions (no braces for single statements, folding assert conditions into the assert):

auto It = GlobalSpecMap.find(FAddr);
assert(It != GlobalSpecMap.end() && "launching compiles for Unexpected function Address?");
for (auto &Pos : It->getSecond())
  auto SourceEntities = AliaseeImplTable.getImplFor(Pos);

"Pos" is not a very descriptive name here. "Callee" ?

Likewise for SourceEntities. "ImplSymbol"?

SourceEntities is currently unused, but all you should need to do is issue an asynchronous lookup for it with a no-op 'OnComplete' callback. OnComplete takes an error, so you'll have to deal with that, but the usual way is just to log it to the ExecutionSession:

auto ImplSymbol = AliaseeImplTable.getImplFor(Callee);
const auto &ImplSymbolName = ImplSymbol.first;
auto *ImplJD = *ImplSymbol.second;
ES.lookup({ImplJD, true}, {ImplSymbolName},
          SymbolState::Ready,
          [](Expected<SymbolMap> Result) {
            if (auto Err = Result.takeError())
            ES.reportError(std::move(Err));
          });
98–99

"Walking" functions describes how you build this set, but not what it is. CalleeSet might be a better name for now?

llvm/lib/ExecutionEngine/Orc/Speculation.cpp
57

What line is this comment in reference to?

83

Variable names should be capitalized, so this should be 'Likely'.

106–108

No braces needed here either, since the body is a single statement.

lhames added inline comments.Jun 15 2019, 10:23 AM
llvm/lib/ExecutionEngine/Orc/Speculation.cpp
91

If I have understood your patch correctly, you could test Dave Blaikie's proof-of-concept speculation idea by issuing a call to:

SpecMap.speculateFor(RAddr);

You would need to remove the std::move from RAddr on the previous line. JITTargetAddresses are cheap to copy so that's fine to get rid of.

To test that this is really working you could compile a test module:

void a() {}
void b() {}

int main(int argc, char *argv[]) {
  if (argc > 2)
    a();
  else
    b();
  return 0;
}

If your simple speculator is working you should see modules for both a() and b() pass through your speculation layer when main is called, even though only one will ever be executed.

Hi Lang, thank you for the comments.
I'm reading those and I'll address those shortly.

Regarding, testing I have already done it in single and multi-threaded JIT mode with one and more JITDylibs. The expected behavior was achieved in my test cases. Only thing that blocks this patch to support speculative compiles without run time call is issuing a ES.lookup, I will add that here shortly.

pree-jackie marked 2 inline comments as done.Jun 18 2019, 9:07 PM
pree-jackie added inline comments.
llvm/lib/ExecutionEngine/Orc/Speculation.cpp
57

Converting the function definition address to the unsigned int of 64 bits. Which are used as the key in Speculator to lookup likely functions.

91

Not exactly, registering the symbols with speculator doesn't mean in any way that the Impl Symbols are recorded in the Imap. To replicate the lazyreexports symbol mapping we use the same technique as earlier.

Triggering a call at run time is easy, because we can guarantee that when we call the function, all the external references by the function are already stub materialized. So when we call the function at run time through __orc_speculate_for, Imap has the Impl Symbols.

But triggering speculative compiles without the run time function, requires 2 look ups
1 ) Lookup likely Symbols to Stub Materialize and handover the remaining to the linking layer.
2 ) Lookup based on the Imap Entries of the likely functions for speculative compiles.

I have done it, it is working and I have to write tests.

Actually, it work along with the same sequence of actions that ORC v2 do.

pree-jackie marked 7 inline comments as done.

Fixed comments,

pree-jackie marked an inline comment as done.Jun 26 2019, 12:40 PM
pree-jackie added inline comments.
llvm/lib/ExecutionEngine/Orc/Speculation.cpp
91

This becomes meaning less, since Callback changed from Resolved to Ready

Added __orc_speculate_for , and orc_speculator. Remaining are test-cases, once test case is added I think it is ready to go, without major changes

Additions in this Change Set

  1. Functionality for LLVM and Custom Analysis Integration with Speculator.
  1. Speculator Class is refactored to let the client with different program representations re-use the common functionality.
  1. Template Parameter is Added to IRSpeculator class to identify the top-level analysis the clients want to run.

Can you please upload a patch with full context?

Can you please upload a patch with full context?

I have updated

pree-jackie marked an inline comment as done.Jul 8 2019, 1:42 PM
pree-jackie added inline comments.
lib/ExecutionEngine/Orc/Speculation.cpp
32 ↗(On Diff #208493)

Resolve warning in Release build

Hi Praveen,

I'm not sure the IRSpeculator is necessary. My instinct would be to just have the Speculator class as the global repository of estimates of the form "execution point -> { candidates to speculatively compile }" (i.e. your GlobalSpecMap). Then the IRSpeculationLayer should take a reference to the Speculator and use a custom FunctionPass to populates the estimates.

I've attached an example of a hand rolled pass pipeline that should give you access to statically calculated block frequency estimates:

  • Lang.

Hi Praveen,

I'm not sure the IRSpeculator is necessary. My instinct would be to just have the Speculator class as the global repository of estimates of the form "execution point -> { candidates to speculatively compile }" (i.e. your GlobalSpecMap). Then the IRSpeculationLayer should take a reference to the Speculator and use a custom FunctionPass to populates the estimates.

I've attached an example of a hand rolled pass pipeline that should give you access to statically calculated block frequency estimates:

  • Lang.

I think it is really a matter of separation, that is where we analysis the module and retrieve the results that means whether in a layer or a speculator object, If we take over the layer approach we have to make the Pass to be aware of speculator.

Hi Praveen,

I'm not sure the IRSpeculator is necessary. My instinct would be to just have the Speculator class as the global repository of estimates of the form "execution point -> { candidates to speculatively compile }" (i.e. your GlobalSpecMap). Then the IRSpeculationLayer should take a reference to the Speculator and use a custom FunctionPass to populates the estimates.

I've attached an example of a hand rolled pass pipeline that should give you access to statically calculated block frequency estimates:

  • Lang.

I think it is really a matter of separation, that is where we analysis the module and retrieve the results that means whether in a layer or a speculator object, If we take over the layer approach we have to make the Pass to be aware of speculator.

Also, we have an extra argument (JITDylib*) which cannot be passed around.. Is there any strong reason we should go with your approach?

In my point of view, we don't need to setup whole Pass Manager Pipeline, the minimalistic requirement is FunctionAnalysisManager.

lhames idea :

Remove Speculator variants for different program representations and handle them via ORC Layers.

lhames idea :

Remove Speculator variants for different program representations and handle them via ORC Layers.

Plus, remove code boilerplate.

pree-jackie marked an inline comment as done.Jul 9 2019, 11:30 AM
pree-jackie added inline comments.
lib/ExecutionEngine/Orc/Speculation.cpp
32 ↗(On Diff #208493)

Addressed.

This is looking good. I think it would be nice to have an example QueryAnalysis implementation to demonstrate how that is supposed to work.

include/llvm/ExecutionEngine/Orc/Speculation.h
144–151 ↗(On Diff #208755)

One minor observation: I think that adding the ability to configure the pass pipeline here provides more degrees of freedom than necessary. If the aim is to simplify the QueryAnalysis by providing a preconfigured pass pipeline then the IRSpeculationLayer should configure that pipeline (and expose no registration mechanism). If the aim is for the pipeline to remain configurable (which seems like a good idea) then you can remove the PassBuilder and FunctionPassManager from the layer entirely (simplifying the layer implementation) and have the QueryAnalysis capture them when it is created.

Note that this is just polish if you have time. I would not let it block your progress on real experiments.

pree-jackie edited the summary of this revision. (Show Details)Jul 17 2019, 1:48 PM
  1. Included a Example to show how to use speculation,
  1. With the current implementation, we see speedups but it is not benchmark and quantized yet, the analysis are experimental.
  1. Launching lookup's for already compiled symbols are avoided by a simple pre map lookup, but the jump can be avoided entirely by having a global variable and creating the new entry Basic Block, which comparison failure : jump into the JIT compiler memory and on success branch to original "pre entry Basic Block of function".
pree-jackie marked an inline comment as not done.Jul 31 2019, 9:42 AM
lhames accepted this revision.Jul 31 2019, 10:44 AM

Minor style nits aside, this looks great. Once you've addressed them (and run clang-format over the patch) feel free to commit this to the mainline and continue development there. :)

llvm/examples/SpeculativeJIT/SpeculativeJIT.cpp
198

There should be a newline here.

llvm/include/llvm/ExecutionEngine/Orc/LazyReexports.h
23

Is this FileOutputBuffer include needed?

188

The SrcJDLoc parameter should have a default value of nullptr, so that people who are not using speculation can ignore it.

llvm/include/llvm/ExecutionEngine/Orc/Speculation.h
54

It's best to use "return None" rather than "return {}". I've seen some older compilers struggle with the latter.

71

The LLVM style guide says that variable names should start with a capital letter, so lockit should be Lockit.

80

Lockit should start with a capital letter here too.

114

Speculator doesn't seem to have any virtual methods. Are you intending for this to be subclassed? If not, you can remove the virtual destructor too.

163–170

I think this should be able to be removed now?

llvm/lib/ExecutionEngine/Orc/SpeculateAnalyses.cpp
76

topk should start with a capital letter.

llvm/lib/ExecutionEngine/Orc/Speculation.cpp
30

lockit should start with a capital letter.

This revision is now accepted and ready to land.Jul 31 2019, 10:44 AM
pree-jackie marked 3 inline comments as done.Jul 31 2019, 1:22 PM
pree-jackie added inline comments.
llvm/include/llvm/ExecutionEngine/Orc/Speculation.h
163–170

I tend to keep this interface, because it helps us to register analysis which uses already available LLVM pass results, without this, it may cumbersome at the client code (SpeculativeJIT).
Let's keep it, and see if it is not worthy we can kill this.

Resolve comments

Adapt to new locking scheme

pree-jackie closed this revision.Aug 4 2019, 5:57 AM

The change set is committed in rL367756.