Page MenuHomePhabricator

Initial implementation of optimization bisect
AbandonedPublic

Authored by andrew.w.kaylor on Mar 29 2016, 2:08 PM.

Details

Summary

This patch implements a new class that can be used to allow optimizations to be selectively disabled at compile time in response to a command line option. This will allow a binary search for optimization related failures to be performed directly from LLVM-based front end invocations without otherwise changing the compiler's behavior.

I still need to create some sort of test for this code, but I wanted to begin the review process first to see if I could get consensus on this general approach.

The behavior is fairly straightforward. Any time a pass manager is about to run an optimization, it checks with the OptBisect helper object to see whether or not the pass should be run. The OptBisect tool maintains a simple count of the number of optimizations that have been run and returns false once the specified limit is reached. I am also providing (but not currently using) a function that optimization passes can use to opt in for a finer grained control of individual optimizations.

I am making two choices that require discussion. First, I am currently allowing all analysis passes (at least with the legacy pass manager) regardless of the optimization count. My reasoning is that any given analysis pass may be needed for some later pass that cannot be skipped (register allocation passes, for instance) and so running all analysis passes avoids the problem of anticipating such dependencies. I am not currently attempting this with the new pass manager as I haven't yet found a clean and simple way to identify passes as analysis passes at the level at which I am hooking in to the control flow.

Second, because the intention is that a front end will be able to produce object files while using the bisecting feature, certain passes may not be skipped. I am currently handling this in a very clumsy and fragile way by maintaining a hard-coded list of passes which must not be skipped. I hope that a better solution can be implemented and that the current approach will be short-lived (perhaps not even surviving the review process). My list is almost certainly incomplete and may also be overly conservative. I generated the list using x86 targets. Additional passes will need to be added for other target architectures.

Diff Detail

Repository
rL LLVM

Event Timeline

andrew.w.kaylor retitled this revision from to Initial implementation of optimization bisect.
andrew.w.kaylor updated this object.
andrew.w.kaylor set the repository for this revision to rL LLVM.
andrew.w.kaylor added a subscriber: llvm-commits.

Hmmm. When we first did the 'optnone' attribute, we designed in a feature where each pass would identify itself as skippable or not, and the pass manager would run only non-skippable passes on an 'optnone' function.

Chandler was adamant that we NOT do it this way, that the pass manager should remain ignorant of this sort of trickery and each individual pass would need to decide for itself whether 'optnone' was something to pay attention to. So, you now find at the top of a good many passes, a quick check to bail out early for 'optnone' functions. The fiddly bits are all factored out into a base class method, but each pass has to have a two-liner at the top of its Run method to (ahem) opt-in to optnone.

This feels morally equivalent, and I think this mechanism and 'optnone' ought to behave in similar ways.
So, rather than a list of passes that are allowed to run regardless of the bisection state, you'd have each individual pass opt-in to participating in bisection.
It makes for a lot of cut-and-paste across the Transform passes, but that's the existing practice.

I definitely agree that the pass manager, and by extension the OptBisect class, shouldn't know anything about the passes.

I'd like to have some mechanism to ask the pass (or its pass registry entry) if it can be skipped. That would be pretty trivial to fit into the legacy pass manager interface with a default response (I think it should default to skippable, but we can debate that). I suppose a conceptually similar thing could be done with the new pass manager, but it feels more forced in that case in as much as it is one more bit of interface imposed on the pass concept.

The one thing I'm sure of is that the way I'm currently doing it is wrong.

MatzeB edited edge metadata.Mar 29 2016, 5:29 PM

I definitely agree that the pass manager, and by extension the OptBisect class, shouldn't know anything about the passes.

I'd like to have some mechanism to ask the pass (or its pass registry entry) if it can be skipped. That would be pretty trivial to fit into the legacy pass manager interface with a default response (I think it should default to skippable, but we can debate that). I suppose a conceptually similar thing could be done with the new pass manager, but it feels more forced in that case in as much as it is one more bit of interface imposed on the pass concept.

The one thing I'm sure of is that the way I'm currently doing it is wrong.

Maybe the passes that should be skipped for optnone functions are the same passes that can be disabled by OptBisect? Which would mean we could design a common helper functions for both replacing all the optnone checks with it.

Maybe the passes that should be skipped for optnone functions are the same passes that can be disabled by OptBisect? Which would mean we could design a common helper functions for both replacing all the optnone checks with it.

I'd naively expect that the set of passes that should pay attention to optnone and bisection would be the same, and a common mechanism could work. But I'm not an optimizer person, by any stretch of the imagination.

One difference I see is that "optnone" is an attribute within the IR and so the pass manager shouldn't be looking for it (maybe that's the "trickery" that Chandler didn't want the pass manager to be in on?) whereas the OptBisect class exists for the sole purpose of deciding to skip optimizations, and so it necessarily (maybe) needs to be aware that there are some passes that can't be skipped.

The obvious alternative is to not have the pass manager involved in any of this and put the shouldRunPass() check directly into the passes themselves. I was trying to avoid having to change a lot of different places to get this working, but that feels a bit more natural and it matches what's going to have to happen to skip individual optimizations.

Hi,

I don't think optnone-aware passes and the passes we might want to bisect are the same. Even with optnone we probably want to run some very trivial optimizations (e.g. ConstantProp), and I think bisection should cover those too.

Michael

PS: Thanks for doing this, I'm really excited about this feature!

One difference I see is that "optnone" is an attribute within the IR and so the pass manager shouldn't be looking for it (maybe that's the "trickery" that Chandler didn't want the pass manager to be in on?) whereas the OptBisect class exists for the sole purpose of deciding to skip optimizations, and so it necessarily (maybe) needs to be aware that there are some passes that can't be skipped.

The obvious alternative is to not have the pass manager involved in any of this and put the shouldRunPass() check directly into the passes themselves. I was trying to avoid having to change a lot of different places to get this working, but that feels a bit more natural and it matches what's going to have to happen to skip individual optimizations.

Maintaining a list of necessary passes in the pass manager sounds wrong to me. The pass author should know best whether a pass is necessary and it would be naturally to specify it together with the pass instead of in a separate file. It also works better for out-of-tree targets or passes loaded as plugins.

mehdi_amini added inline comments.Mar 29 2016, 6:08 PM
lib/IR/OptBisect.cpp
119

Ew, that's pretty terrible to have this inlined here. But I agree it is not easy to decouple...
Maybe having a new (optional?) API on the Passes themselves may be cleaner.
Something like bool isRequiredForCorrectness()?

Maintaining a list of necessary passes in the pass manager sounds wrong to me. The pass author should know best whether a pass is necessary and it would be naturally to specify it together with the pass instead of in a separate file. It also works better for out-of-tree targets or passes loaded as plugins.

Agreed. In spite of that being the code I submitted for review, I really don't want to do it that way. I just wanted to have something functional while searching for a better solution.

The two options I see are:

  1. Have the pass managers invoke the "shouldRunPass" check and implement some way for OptBisect to query a pass to see if it is skippable.
  2. Have every pass that is skippable make a shouldRunPass call at each skippable level.

I like the first option because it "automatically" provides the capability to skip passes unless the pass author explicitly does something to indicate that the pass shouldn't be skipped, but I like the second option because it gives each pass the ability to determine the granularity at which things can be skipped.

I don't think optnone-aware passes and the passes we might want to bisect are the same. Even with optnone we probably want to run some very trivial optimizations (e.g. ConstantProp), and I think bisection should cover those too.

optnone tries to be as much like -O0 as it can, and I'd think that after you get to the end of the bisection range you'd want to be as much like -O0 as you can. FWIW I'm not seeing ConstantProp run at -O0.

andrew.w.kaylor edited edge metadata.

Updated the means of determining whether or not a pass is can be skipped -- I added a new function (isSkippable) to the Pass base class and the PassConcept template with default implementations (in the PassClass and the PassInfoMixin template) that returns true and updated individual passes that I believe cannot be skipped if they are present with an override that returns false.

Adding one more unskippable pass (unreachable MBB elimination). With this change, I am able to run clang against a test file I was using at -O3 with -opt-bisect-limit=0. Previously the live variable analysis was asserting because of an unreachable block in a machine function that had been added very early by the AddDiscriminators pass (which I believe must not be skipped).

Added tests
Moved a few checks so that the bisect check happened before the debug message saying the pass was being executed
Made printing passes unskippable
Updated adapter passes to call the contained pass' isSkippable function

-Rebased
-Added new unskippable passes (Bitcode Writer and pseudo instruction expansion for ARM and AArch64)
-Added a test to verify code generation works with all skippable passes skipped
-Minor updates to make tests less flaky

If we can agree on the approach I have taken here, I believe that this code is ready to go. I'm now awaiting review feedback and don't have any more updates to this change set in progress.

I still wonder whether we can reuse, the existing OptNone, handling. Would something like this work (pseudo patch):

-  /// skipOptnoneFunction - This function has Attribute::OptimizeNone
-  /// and most transformation passes should skip it.
-  bool skipOptnoneFunction(const Function &F) const;
+  /// Optional passes call this function to check whether the pass should be
+  /// skipped. This is the case when Attribute::OptimizeNone is set or when
+  /// optimization bisect is over the limit.
+  bool skipFunction(const Function &F) const;
-bool FunctionPass::skipOptnoneFunction(const Function &F) const {
+bool FunctionPass::skipFunction(const Function &F) const {
+  LLVMContext &C = F.getContext();
+  if (C.getOptBisect().shouldSkipPass(F))
+    return true;
 bool MyPass::runOnMachineFunction(MachineFunction &MF) {
-  if (skipOptnoneFunction(*MF.getFunction()))
+  if (skipFunction(*MF.getFunction()))

We could add an additional parameter if we find instances where we really want to run a pass when OptNone is set but not in an optimization bisect.

include/llvm/Pass.h
118

Don't repeat the function name in the doxygen comment (we avoid this in new code).

mehdi_amini edited edge metadata.Apr 12 2016, 2:08 PM

-bool FunctionPass::skipOptnoneFunction(const Function &F) const {
+bool FunctionPass::skipFunction(const Function &F) const {
+ LLVMContext &C = F.getContext();
+ if (C.getOptBisect().shouldSkipPass(F))
+ return true;

I don't really get how the LLVMContext becomes involved here?

In D18576#399022, @joker.eph wrote:

-bool FunctionPass::skipOptnoneFunction(const Function &F) const {
+bool FunctionPass::skipFunction(const Function &F) const {
+ LLVMContext &C = F.getContext();
+ if (C.getOptBisect().shouldSkipPass(F))
+ return true;

I don't really get how the LLVMContext becomes involved here?

We have to count how many passes we skipped/did not skip and compare that against the bisect number. This is global information.

I still wonder whether we can reuse, the existing OptNone, handling.

I can model that and throw up an alternate implementation. My concern is that would require all passes to opt in to the bisection whereas I'm trying to get it so that everything is included unless it specifically excludes itself. We'll need passes to opt in to the case-by-case handling to get fine grained, but I'd like to avoid that at the pass level so that we don't run into problems where there is a problem in pass A but bisect points to pass B because pass A didn't make the call to opt in.

Otherwise, I agree that having the skip initiated from within the pass itself has some definite benefits from a design perspective. The implementation I have up right now felt particularly awkward with the new pass manager and the propagation of the desired default behavior is a good bit less "automatic" in that case, in that it only happens for passes that derive from the right mix-in templates.

The "OptNone" handling that currently exists only applies to function passes, right? Obviously something analogous can be added to other pass types.

I still wonder whether we can reuse, the existing OptNone, handling.

I can model that and throw up an alternate implementation. My concern is that would require all passes to opt in to the bisection whereas I'm trying to get it so that everything is included unless it specifically excludes itself. We'll need passes to opt in to the case-by-case handling to get fine grained, but I'd like to avoid that at the pass level so that we don't run into problems where there is a problem in pass A but bisect points to pass B because pass A didn't make the call to opt in.

Otherwise, I agree that having the skip initiated from within the pass itself has some definite benefits from a design perspective. The implementation I have up right now felt particularly awkward with the new pass manager and the propagation of the desired default behavior is a good bit less "automatic" in that case, in that it only happens for passes that derive from the right mix-in templates.

The "OptNone" handling that currently exists only applies to function passes, right? Obviously something analogous can be added to other pass types.

skipOptnoneFunction() is available in FunctionPass, BasicBlockPass and LoopPass and seems to be consistently used there.

We have to count how many passes we skipped/did not skip and compare that against the bisect number. This is global information.

Is there a good way to get the context from a CallGraphSCC? This is what I came up with:

static LLVMContext *getCGNodeContext(CallGraphNode *Node) {
  Function *F = Node->getFunction();
  if (F)
    return &F->getContext();
  for (CallGraphNode::iterator I = Node->begin(), E = Node->end(); I != E;
       ++I) {
    if (I->first)
      return &cast<Function>(I->first)->getContext();
    Function *CalledFn = I->second->getFunction();
    // A null CalledFn indicates a call to an external node.
    if (!CalledFn)
      continue;
    return &(CalledFn->getContext());
  }
}

bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
  CallGraphNode *Node = *(SCC.begin());
  assert(Node);
  if (!Node)
    return false;
  LLVMContext *Context = nullptr;
  for (CallGraphNode *Node : SCC) {
    Context = getCGNodeContext(Node);
    if (Context)
      break;
  }
  assert(Context);
  // If we can't get the context, assume the pass can't be skipped.
  if (!Context)
    return false;
  return !Context->getOptBisect().shouldRunPass(this, &SCC);
}

It feels awful. Is there a better way to do that?

We have to count how many passes we skipped/did not skip and compare that against the bisect number. This is global information.

Is there a good way to get the context from a CallGraphSCC? This is what I came up with:

static LLVMContext *getCGNodeContext(CallGraphNode *Node) {
  Function *F = Node->getFunction();
  if (F)
    return &F->getContext();
  for (CallGraphNode::iterator I = Node->begin(), E = Node->end(); I != E;
       ++I) {
    if (I->first)
      return &cast<Function>(I->first)->getContext();
    Function *CalledFn = I->second->getFunction();
    // A null CalledFn indicates a call to an external node.
    if (!CalledFn)
      continue;
    return &(CalledFn->getContext());
  }
}

bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
  CallGraphNode *Node = *(SCC.begin());
  assert(Node);
  if (!Node)
    return false;
  LLVMContext *Context = nullptr;
  for (CallGraphNode *Node : SCC) {
    Context = getCGNodeContext(Node);
    if (Context)
      break;
  }
  assert(Context);
  // If we can't get the context, assume the pass can't be skipped.
  if (!Context)
    return false;
  return !Context->getOptBisect().shouldRunPass(this, &SCC);
}

It feels awful. Is there a better way to do that?

This does indeed look ugly. The best solution I can see would be to give the CallGraphSCC class a reference to the CallGraph (from there you should be able to go CallGraph.getModule().getContext()). CallGraphSCC is only instantiated once per CallGraphSCCPassManager as far as I can see so an extra reference shouldn't hurt.

The new pass manager design also presents a problem in terms of creating a single, simple check function that goes through the LLVMContext. Right now, I'm testing with the global singleton like this:

if (!getOptBisect().shouldRunPass(name(), &F))
  return PreservedAnalyses::all();

Trying to move that into the context yields something like this:

if (!F.getContext().getOptBisect().shouldRunPass(name(), &F))
  return PreservedAnalyses::all();

That's not terrible, but for loop passes it becomes this:

if (auto *F = L->getHeader()->getParent()) {
  LLVMContext &Context = F->getContext();
  if (!Context.getOptBisect().shouldRunPass(this, L))
    return PreservedAnalyses::all();
}

I could provide global helper functions that perform this check, but that has the feel of false encapsulation.

I have just created a new differential (D19172) which implements the optnone-based approach. Assuming we agree that approach is preferable, that patch will supersede this one.

andrew.w.kaylor abandoned this revision.Apr 19 2016, 4:32 PM