This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Improve infinite loop detection
ClosedPublic

Authored by kuhar on Dec 18 2019, 1:00 PM.

Details

Summary

This patch limits the default number of iterations performed by InstCombine. It also exposes a new option that allows to specify how many iterations is considered getting stuck in an infinite loop.

Based on experiments performed on real-world C++ programs, InstCombine seems to perform at most ~8-20 iterations, so treating 1000 iterations as an infinite loop seems like a safe choice. See D71145 for details.

The two limits can be specified via command line options.

Diff Detail

Event Timeline

kuhar created this revision.Dec 18 2019, 1:00 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a subscriber: hiraditya. · View Herald Transcript
spatel accepted this revision.Dec 20 2019, 9:57 AM

LGTM

This revision is now accepted and ready to land.Dec 20 2019, 9:57 AM
This revision was automatically updated to reflect the committed changes.
lebedev.ri added inline comments.Jul 4 2020, 6:25 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
125–126

I'm guessing that the general understanding that ideally these should become 2 in the end.
Now, that might never happen, but that should be the trend.
So far no one seems to have come up with any cases where 1000 limit is reached.
Can we periodically ~halve them, starting now?

mdchen added a subscriber: mdchen.Nov 26 2020, 4:32 AM

@kuhar @lebedev.ri I'm lucky to have a test case which requires exactly 1001 times iteration thus aborts. And would it be better just break out rather than report a fatal error?

Test case(only stucks in our customized pipeline, paste it here in case it helps):

int a, g;
union b {
  long c;
} f;
long d, h;
short *e;
static short j();
void k() {
  union b i;
  j(0, i);
}
short j(int l, union b m) {
  d = 0;
  for (; d <= 24; d = d + 2)
    if (m.c) {
      h = 0;
      for (; h < 59; h++) {
        *e = l > g ^ f.c;
        g = a < 0 ?: a;
      }
    }
}
int main() {}