Page MenuHomePhabricator

[InlineCost] Prevent infinite recursion on function pointers
AcceptedPublic

Authored by paquette on Jan 3 2018, 2:40 PM.

Details

Summary

Compile the following at -Os:

typedef void (*Foo)(void*);

void Bar(void* FunctionPtr)
{
	((Foo)FunctionPtr)((void*)Bar);
}

int main(int argc, char *argv[]) {
	Bar((void*)Bar);	
}

The inliner will recurse infinitely because it doesn't handle the case where a function takes a function pointer argument, and is called using a pointer to itself as an argument. This patch makes the inliner quit when the examined callsite involves a function pointer parameter.

Diff Detail

Event Timeline

paquette created this revision.Jan 3 2018, 2:40 PM
arsenm added a subscriber: arsenm.Jan 3 2018, 3:03 PM

Needs test

lib/Analysis/InlineCost.cpp
1278–1279

I don't think you can rely on the pointee type this way

The bug that's getting triggered by the testcase is that CallAnalyzer::analyzeCall is recursive, without any recursion limit, so it crashes by overflowing the stack.

Your patch doesn't solve that issue in general; it only solves the problem for your specific testcase. You could trigger a similar crash with a program that isn't recursive. Or there might be some other way to trick CallAnalyzer into following a recursive program. If you want to actually fix the bug, the solution is to either add a recursion depth limit, or make the algorithm iterative and add an iteration limit.

paquette updated this revision to Diff 128673.Jan 4 2018, 4:24 PM

Updated patch to prevent general recursion instead of just the one edgecase. Also added some information to the dump function for CallAnalyzer to make it clear if the inliner bailed out because of the recursion limit.

We must have some pre-existing recursion check already as clang doesn't fail for obviously recursive cases. (I guess it's the code setting IsRecursiveCall).
I assume that code isn't working correctly with the testcases here can't we just fix that?

If we are going for arbitrary recursion limits, then we should probably have a comment for why the limit is 100 (and not 50 or 200) and it would probably be a good idea to add a cl::opt so people can tweak the limit if it doesn't work for them.

I assume that code isn't working correctly with the testcases here can't we just fix that?

Even if we did, we would still need some sort of arbitrary limit to handle large callgraphs (if you have Bar1 calls Bar2 calls Bar3...Bar1000, or something like that, we'll eventually overflow compiler's stack through recursion even if the IR doesn't contain any recursion).

paquette updated this revision to Diff 128977.Jan 8 2018, 1:39 PM

Got rid of the magic 100 for the maximum depth and put in a command line option (-inline-recursion-limit) instead. I tried a few different limits with the knob and found that this test crashes around a recursion depth of 3500 on my machine. A max depth of 2000 seemed like a good middle-ground.

MatzeB accepted this revision.Jan 9 2018, 4:04 PM
MatzeB added a reviewer: chandlerc.

Makes sense to me from all I've seen. So tentative LGTM: Wait a few days and if noone else chimes in, it's fine :)

lib/Analysis/InlineCost.cpp
92–94

typo in the help text.

1289

I would recommend duplicating some code we had earlier for known call sites here:

if (F == CS.getInstruction()->getFunction()) {
  // This flag will fully abort the analysis, so don't bother with anything
  // else.
  IsRecursiveCall = true;
  return false;
}

as we won't inline recursively anyway after this.

This revision is now accepted and ready to land.Jan 9 2018, 4:04 PM
eraman added a comment.Jan 9 2018, 5:07 PM

There are two problems this patch is trying to address:
a. A call chain I1->I2->I3...Ik, where each of the I_i ->I_(i+1) are indirect calls that become direct (because we know the target through inline analysis). No recursion in the callgraph of the module being compiled.
b. The callgraph has recursion through a sequence of indirect calls. This is similar to the example in this patch description but could be a more broader cycle (not just self recursion).

One consequence of this patch is that in the second example, we will end up applying a huge bonus to the original callee that is being analyzed. Note that the intent of recursively calling analyzeCall is to apply a bonus (negative cost) by subtracting the cost of indirect call from the indirect threshold parameter. Let's say that you have a self recursive call where the original cost of the body is 25. IndirectCallThreshold is 150. At the maximum depth R, we don't analyze any further and return a cost of 25. In the previous level (R-1), we give a bonus by subtracting 125 (IndirectCallThreshold - call cost (25)). So the cost becomes -125. So at the topmost level the bonus will be something like -125R. While the intent of the heuristic is to give some small bonus to each indirect call promoted to a direct call, this will end up applying the bonus multiple times to a call instruction.

One way to fix this is by keeping track of the callsites visited in this process and not revisit a callsite. A simpler alternative is to limit the recursion depth to just 1 (or some very small number). I don't think we will lose out much doing so.