Page MenuHomePhabricator

[KnownBits] Limited recursion through phi operands
Needs ReviewPublic

Authored by reames on Aug 17 2022, 3:12 PM.

Details

Summary

This change adjusts the phi handling in known-bits to allow recursing into phi operands, but adjusts the depth parameter to avoid potential exponential compile time growth. Specifically, the remaining depth limit is even divided across the number of operands with the depth per operand adjusted upwards so that the total number of recursion steps is limited to the same value we'd perform on a tree of e.g. binary instructions.

This looks on the surface like it might allow a large degree of fan out, but it doesn't. Some examples follow to help explain.

Term the difference between current depth and max depth as "budget". Max depth currently defaults to 6.

Consider:

  • A one operand phi increases depth by one. This behaves just like any non-phi instruction.
  • A two operand phi increases depth by half of budget.
  • A three operand phi increases depth by two thirds of the remaining budget.
  • Etc..

Put this together, and we can only recurse through at most two (non-single operand) phis. The first phi splits the budget, and the second one splits it again. For 2 operands, that means we'd divided budget by 4. Since max budget is 6, that means we're down to per operand budget of 1 (required to preserve prior behavior), and won't recurse further.

Diff Detail

Event Timeline

reames created this revision.Aug 17 2022, 3:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 17 2022, 3:12 PM
Herald added subscribers: foad, zzheng, bollu and 2 others. · View Herald Transcript
reames requested review of this revision.Aug 17 2022, 3:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 17 2022, 3:12 PM
reames updated this revision to Diff 453447.Aug 17 2022, 3:14 PM

Hoist invariant code out of the loop.

Thanks for looking at this! I guess it comes down to increased compile time - do you have a branch that could be tested on https://llvm-compile-time-tracker.com ?

foad added a comment.Aug 23 2022, 5:38 AM

Specifically, the remaining depth limit is even divided across the number of operands with the depth per operand adjusted upwards so that the total number of recursion steps is limited to the same value we'd perform on a tree of e.g. binary instructions.

I don't quite get the logic here. Are you saying that for a tree of binary instructions we do about 2^6 recursive steps, and for a tree of N-operand phis you'd like to keep the same limit of about 2^6 steps instead of risking it blow up to N^6 steps? If so then I think you'd need to reduce depth by log2(N) at each step. Or perhaps max(log2(N), 1) to handle the 1-operand phi case gracefully.