Page MenuHomePhabricator

[SCEV] Limit recursion depth of constant evolving
ClosedPublic

Authored by hliao on Jan 12 2017, 3:58 PM.

Details

Summary

For a loop body with complicated exit condition evaluation, constant evolving may run out of stack on some platforms, such as Windows. Need to limit the recursion depth.

Diff Detail

Repository
rL LLVM

Event Timeline

hliao updated this revision to Diff 84183.Jan 12 2017, 3:58 PM
hliao retitled this revision from to [SCEV] Limit recursion depth of constant evolving.
hliao updated this object.
hliao added reviewers: sanjoy, atrick.
hliao set the repository for this revision to rL LLVM.
hliao added a subscriber: llvm-commits.
atrick edited edge metadata.Jan 12 2017, 4:13 PM

Rather than a command line option, can you find the recursion limit hit by the LLVM test suite (and SPEC if you have access) and set the limit a bit higher with sufficient comments?

hliao added a comment.Jan 12 2017, 4:15 PM

sure, I will schedule that test this night to see whether we need to raise that limit.

sanjoy edited edge metadata.Jan 12 2017, 5:08 PM

Please upload with context?

Did you try to see how much work it would be to avoid recursion altogether (and do an iterative scheme instead)?

hliao added a comment.Jan 12 2017, 7:32 PM

iterative one is quite straight-forward but I don't see whether it's necessary. 'getConstantEvolvingPHI' is used in 'computeExitCountExhaustively' to evolve loop symbolically to check trip count in brute-force manner. I hardly to see it's widely applied. Ofc, let's check the statistics to see whether that's reasonable.

In addition, if ' getConstantEvolvingPHI' is re-written in iterative scheme, 'EvaluateExpression' needs to be re-written too as the later is predicated from the former and may push the out-of-stack into the later.

hliao added a comment.Jan 13 2017, 8:44 AM

I collected the maximum depth of 'getConstantEvolvingPHIOperands' when it returns successfully or otherwise. Here is the statistics collected on SingleSource, MultiSource, and External (spec2000 and spec2006).

  • when 'getConstantEvolvingPHIOperands' returns null
MAX-DEPTH-PER-CUNITNUM-OF-CUNITS
0103
1169
2653
3187
4145
576
665
718
894
95
1012
1110
125
133
  • when 'getConstantEvolvingPHIOperands' return non-null
MAX-DEPTH-PER-CUNITNUM-OF-CUNITS
0159
1323
2502
3218
4546
5167
6100
749
8432
946
1029
1110
124
1310
161
173
181
191

It sounds to me that 32 is a reasonable choice.

atrick accepted this revision.Jan 13 2017, 10:04 AM
atrick edited edge metadata.

Sounds good to me. I don't think you need to add a command line flag.

FWIW, I'm also in favor of moving to iterative solutions, although that does not always eliminate the need for arbitrary thresholds to bound the compute time.

I'm strongly against unbounded recursion anywhere in the compiler.

This revision is now accepted and ready to land.Jan 13 2017, 10:04 AM

Sure, I will look into the rewriting them later as we need to rewrite both getConstantEvolvingPHIOperands and EvaluateExpression. The command line option is still preferred as platforms targetting for very different target may found it's necessary to goes deep due to aggressive inlining and other code bloating optimizations. Thanks for the review.

This revision was automatically updated to reflect the committed changes.