ScopInfo: Bail out in case of complex branch structures
authorTobias Grosser <tobias@grosser.es>
Sun, 20 Dec 2015 13:31:48 +0000 (13:31 +0000)
committerTobias Grosser <tobias@grosser.es>
Sun, 20 Dec 2015 13:31:48 +0000 (13:31 +0000)
commit75dc40c3bee1ee9addc3106678c541d31040bb00
treea4f564cf3fc88c4a6b47ebecce94b63da65c1d73
parent591278c08dc89a542a41113f563cecd2f1f0bb57
ScopInfo: Bail out in case of complex branch structures

Scops that contain many complex branches are likely to result in complex domain
conditions that consist of a large (> 100) number of conjucts.  Transforming
such domains is expensive and unlikely to result in efficient code.  To avoid
long compile times we detect this case and skip such scops. In the future we may
improve this by either using non-affine subregions to hide such complex
condition structures or by exploiting in certain cases properties (e.g.,
dominance) that allow us to construct the domains of a scop in a way that
results in a smaller number improving conjuncts.

Example of a code that results in complex iteration spaces:

      loop.header
     /    |    \ \
   A0    A2    A4 \
     \  /  \  /    \
      A1    A3      \
     /  \  /  \     |
   B0    B2    B4   |
     \  /  \  /     |
      B1    B3      ^
     /  \  /  \     |
   C0    C2    C4   |
     \  /  \  /    /
      C1    C3    /
       \   /     /
    loop backedge

llvm-svn: 256123
polly/include/polly/ScopInfo.h
polly/lib/Analysis/ScopInfo.cpp
polly/test/ScopInfo/complex-branch-structure.ll [new file with mode: 0644]