Created attachment 15253 [details] Test case Polly with 252451 times out when running polly-opt -polly-process-unprofitable timeout.ll It seems that the sets we are creating during scop construction are becoming very complex. We could probably timeout on this, but my feeling is that at least for this test case we should be able to compute the scop represenation more efficiently?
This test case is triggered in a couple of LNT failures I see.
I am not sure how we can compute something more efficiently here, sorry. The example test case simply has up to 2^10 many paths from the region entry to the exit, thus it is not suprising it takes a while to describe them all. I would suggest to bail out, maybe if the number of parameters is too high or maybe if there are to many conditional branches in the same loop.
Created attachment 15254 [details] Test case With the following patch and the attached test case I get a very simple set of conditions (precisely the ones I expect): --- a/lib/Analysis/ScopInfo.cpp +++ b/lib/Analysis/ScopInfo.cpp @@ -1930,7 +1930,6 @@ void Scop::buildDomainsWithBranchConstraints(Region *R) { // executed at runtime. if (containsErrorBlock(RN, getRegion(), LI, DT)) { HasErrorBlock = true; - continue; } BasicBlock *BB = getRegionNodeBasicBlock(RN); Stmt_bb15 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb15[] }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb15[] -> [0] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb15[] -> MemRef_A[0] }; Stmt_bb19 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb19[] : tmp17 <= -1 or tmp17 >= 1 }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb19[] -> [1] : tmp17 <= -1 or tmp17 >= 1 }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb19[] -> MemRef_A[0] }; Stmt_bb24 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb24[] }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb24[] -> [2] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb24[] -> MemRef_A[0] }; Stmt_bb29 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb29[] : tmp27 = 3 }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb29[] -> [3] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb29[] -> MemRef_A[0] }; Stmt_bb34 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb34[] }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb34[] -> [4] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb34[] -> MemRef_A[0] }; Stmt_bb39 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb39[] : tmp37 <= -1 or tmp37 >= 1 }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb39[] -> [5] : tmp37 <= -1 or tmp37 >= 1 }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb39[] -> MemRef_A[0] }; Stmt_bb43 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb43[] : (tmp37 <= -1 and tmp41 <= -1) or (tmp37 <= -1 and tmp41 >= 1) or (tmp37 >= 1 and tmp41 <= -1) or (tmp37 >= 1 and tmp41 >= 1) }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb43[] -> [6] : (tmp37 <= -1 and tmp41 <= -1) or (tmp37 <= -1 and tmp41 >= 1) or (tmp37 >= 1 and tmp41 <= -1) or (tmp37 >= 1 and tmp41 >= 1) }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb43[] -> MemRef_A[0] }; Stmt_bb49 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb49[] }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb49[] -> [7] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb49[] -> MemRef_A[0] }; Stmt_bb54 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb54[] : tmp52 <= -1 or tmp52 >= 1 }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb54[] -> [8] : tmp52 <= -1 or tmp52 >= 1 }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb54[] -> MemRef_A[0] }; Stmt_bb59 Domain := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb59[] : tmp52 <= -1 or tmp52 >= 0 }; Schedule := [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb59[] -> [9] }; MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { Stmt_bb59[] -> MemRef_A[0] }; So the issue is that isl_set_coalesce() does not work due to us bailing out at error blocks. I think either we should not bail out for error blocks or we should try to propagate conditions forward from earlier basic blocks. Maybe the ones that dominate the block we look at, that are at themselves postdominated by the block we look at and that are at the same loop depth as the basic block we look at. This test case also computes a rather complex assumed context (even after me commenting out the continue). My feeling is this assumed context could also be described with simpler sets.
This has been addressed in r252750.
Move to Polly Product.