Differential D41719
[InlineCost] Prevent infinite recursion on function pointers Authored by paquette on Jan 3 2018, 2:40 PM.
Details 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 TimelineComment Actions Needs test
Comment Actions 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. Comment Actions 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. Comment Actions 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). 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. Comment Actions
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). Comment Actions 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. Comment Actions 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 :)
Comment Actions There are two problems this patch is trying to address: 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. | |||||||||||||||
typo in the help text.