9.73/3.34 YES 9.73/3.34 9.73/3.34 Solver Timeout: 4 9.73/3.34 Global Timeout: 300 9.73/3.34 Maximum number of concurrent processes: 900 9.73/3.34 ******************************************************************************************* 9.73/3.34 *********************** UNPROCESSED TRANSITION SYSTEMS PER FUNCTION *********************** 9.73/3.34 ******************************************************************************************* 9.73/3.34 9.73/3.34 9.73/3.34 List of LLVMGraphs + assumeNodes + staticAssertNodes [1] : 9.73/3.34 9.73/3.34 +++++++++++++++++++++++++++++++ main +++++++++++++++++++++++++++++++ 9.73/3.34 + + 9.73/3.34 Init Location: 0 9.73/3.34 Transitions: 9.73/3.34 0, main_x -> ¿functionCall(__VERIFIER_nondet_int), main_y -> ¿functionCall(__VERIFIER_nondet_int), main_N -> ¿functionCall(__VERIFIER_nondet_int)}> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 = ~(1073741824))> 9.73/3.34 = ~(1073741824)))> 9.73/3.34 = 0)> 9.73/3.34 = 0))> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 ((2 * main_x) + main_y), main_y -> (main_y + 1)}> 9.73/3.34 9.73/3.34 (main_x + 1)}> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 0}> 9.73/3.34 9.73/3.34 Fresh variables: 9.73/3.34 9.73/3.34 Undef variables: 9.73/3.34 9.73/3.34 Abstraction variables: 9.73/3.34 9.73/3.34 Exit nodes: 9.73/3.34 9.73/3.34 Accepting locations: 9.73/3.34 9.73/3.34 Asserts: 9.73/3.34 9.73/3.34 + Assume Nodes [0]: ++++++++++++++++++++++++++++++++++++++++++++++++ 9.73/3.34 9.73/3.34 + Static Assert Nodes [0]: +++++++++++++++++++++++++++++++++++++++++ 9.73/3.34 9.73/3.34 + After preprocess (paralelization): ++++++++++++++++++++++++++++++ 9.73/3.34 9.73/3.34 Init Location: 0 9.73/3.34 Transitions: 9.73/3.34 0}> 9.73/3.34 ¿functionCall(__VERIFIER_nondet_int)}> 9.73/3.34 varCall_1}> 9.73/3.34 ¿functionCall(__VERIFIER_nondet_int)}> 9.73/3.34 varCall_2}> 9.73/3.34 ¿functionCall(__VERIFIER_nondet_int)}> 9.73/3.34 varCall_3}> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 = ~(1073741824))> 9.73/3.34 = ~(1073741824)))> 9.73/3.34 = 0)> 9.73/3.34 = 0))> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 ¿functionCall(__VERIFIER_nondet_int)}> 9.73/3.34 9.73/3.34 9.73/3.34 ((2 * main_x) + main_y), main_y -> (main_y + 1)}> 9.73/3.34 9.73/3.34 (main_x + 1)}> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 0}> 9.73/3.34 9.73/3.34 Fresh variables: 9.73/3.34 9.73/3.34 Undef variables: 9.73/3.34 9.73/3.34 Abstraction variables: 9.73/3.34 9.73/3.34 Exit nodes: 9.73/3.34 17, 9.73/3.34 Accepting locations: 9.73/3.34 9.73/3.34 Asserts: 9.73/3.34 9.73/3.34 + + 9.73/3.34 +++++++++++++++++++++++++++++++ main +++++++++++++++++++++++++++++++ 9.73/3.34 9.73/3.34 9.73/3.34 Function Return and Parameters Information [2 functions]: 9.73/3.34 function name: __VERIFIER_nondet_int [1 return + 0 parameters] demangled: __VERIFIER_nondet_int 9.73/3.34 __VERIFIER_nondet_int__func_return_ [function result] : int 9.73/3.34 function name: main [1 return + 0 parameters] demangled: main 9.73/3.34 main__func_return_ [function result] : int 9.73/3.34 9.73/3.34 9.73/3.34 AST Ident Scanner Information [5 idents]: 9.73/3.34 __VERIFIER_nondet_int | function | [integer, ()] | | 9.73/3.34 main | function | [integer, ()] | 9.73/3.34 x | local variable | integer | | 9.73/3.34 y | local variable | integer | | 9.73/3.34 N | local variable | integer | | 9.73/3.34 9.73/3.34 Main function: main 9.73/3.34 Preprocessed LLVMGraph 9.73/3.34 Init Location: 0 9.73/3.34 Transitions: 9.73/3.34 = ~(1073741824)) /\ ((undef5 + undef6) >= 0)> 9.73/3.34 = ~(1073741824)) /\ not(((undef5 + undef6) >= 0))> 9.73/3.34 = ~(1073741824)))> 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 (main_x + 1)}> 9.73/3.34 ((2 * main_x) + main_y), main_y -> (main_y + 1)}> 9.73/3.34 9.73/3.34 9.73/3.34 Fresh variables: 9.73/3.34 undef5, undef6, undef7, undef8, 9.73/3.34 9.73/3.34 Undef variables: 9.73/3.34 undef5, undef6, undef7, undef8, 9.73/3.34 9.73/3.34 Abstraction variables: 9.73/3.34 9.73/3.34 Exit nodes: 9.73/3.34 17, 9.73/3.34 Accepting locations: 9.73/3.34 9.73/3.34 Asserts: 9.73/3.34 9.73/3.34 ************************************************************* 9.73/3.34 ******************************************************************************************* 9.73/3.34 *********************** WORKING TRANSITION SYSTEM (DAG) *********************** 9.73/3.34 ******************************************************************************************* 9.73/3.34 9.73/3.34 Init Location: 0 9.73/3.34 Graph 0: 9.73/3.34 Transitions: 9.73/3.34 Variables: 9.73/3.34 9.73/3.34 Graph 1: 9.73/3.34 Transitions: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Variables: 9.73/3.34 main_x, main_N, main_y 9.73/3.34 9.73/3.34 Graph 2: 9.73/3.34 Transitions: 9.73/3.34 Variables: 9.73/3.34 9.73/3.34 Precedence: 9.73/3.34 Graph 0 9.73/3.34 9.73/3.34 Graph 1 9.73/3.34 9.73/3.34 9.73/3.34 Graph 2 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 9.73/3.34 Map Locations to Subgraph: 9.73/3.34 ( 0 , 0 ) 9.73/3.34 ( 7 , 1 ) 9.73/3.34 ( 17 , 2 ) 9.73/3.34 9.73/3.34 ******************************************************************************************* 9.73/3.34 ******************************** CHECKING ASSERTIONS ******************************** 9.73/3.34 ******************************************************************************************* 9.73/3.34 9.73/3.34 Proving termination of subgraph 0 9.73/3.34 Proving termination of subgraph 1 9.73/3.34 Checking unfeasibility... 9.73/3.34 Time used: 0.005887 9.73/3.34 9.73/3.34 Checking conditional termination of SCC {l7}... 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.001406s 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.004343s 9.73/3.34 [55069 : 55071] 9.73/3.34 [55069 : 55072] 9.73/3.34 Successful child: 55071 9.73/3.34 [ Invariant Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 [ Termination Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Ranking function: -main_x + main_N 9.73/3.34 New Graphs: 9.73/3.34 Transitions: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Variables: 9.73/3.34 main_x, main_y, main_N 9.73/3.34 Checking conditional termination of SCC {l7}... 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.000691s 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.002471s 9.73/3.34 [55069 : 55076] 9.73/3.34 [55069 : 55077] 9.73/3.34 Successful child: 55076 9.73/3.34 [ Invariant Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 [ Termination Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 New Graphs: 9.73/3.34 INVARIANTS: 9.73/3.34 7: 0 <= main_x + main_y , 9.73/3.34 Quasi-INVARIANTS to narrow Graph: 9.73/3.34 7: 9.73/3.34 9.73/3.34 LOG: CALL check - Post:1 + main_y + main_N <= 0 - Process 1 9.73/3.34 * Exit transition: 9.73/3.34 * Postcondition : 1 + main_y + main_N <= 0 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.000704s 9.73/3.34 > Postcondition is not implied! 9.73/3.34 9.73/3.34 LOG: RETURN check - Elapsed time: 0.000869s 9.73/3.34 INVARIANTS: 9.73/3.34 7: 0 <= main_x + main_y , 9.73/3.34 Quasi-INVARIANTS to narrow Graph: 9.73/3.34 7: 1 + main_y + main_N <= 0 , 9.73/3.34 Narrowing transition: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: Narrow transition size 1 9.73/3.34 Narrowing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: Narrow transition size 1 9.73/3.34 invGraph after Narrowing: 9.73/3.34 Transitions: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Variables: 9.73/3.34 main_x, main_N, main_y 9.73/3.34 Checking conditional termination of SCC {l7}... 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.001941s 9.73/3.34 Ranking function: -main_x + main_N 9.73/3.34 New Graphs: 9.73/3.34 Transitions: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Variables: 9.73/3.34 main_x, main_y, main_N 9.73/3.34 Checking conditional termination of SCC {l7}... 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.000717s 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.002811s 9.73/3.34 [55069 : 55234] 9.73/3.34 [55069 : 55235] 9.73/3.34 Successful child: 55234 9.73/3.34 [ Invariant Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 [ Termination Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 New Graphs: 9.73/3.34 9.73/3.34 LOG: CALL check - Post:1 + main_N <= main_x - Process 2 9.73/3.34 * Exit transition: 9.73/3.34 * Postcondition : 1 + main_N <= main_x 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.000674s 9.73/3.34 > Postcondition is not implied! 9.73/3.34 9.73/3.34 LOG: RETURN check - Elapsed time: 0.000857s 9.73/3.34 INVARIANTS: 9.73/3.34 7: 9.73/3.34 Quasi-INVARIANTS to narrow Graph: 9.73/3.34 7: 1 + main_N <= main_x , 0 <= 1 + main_x + main_y , 9.73/3.34 Narrowing transition: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: Narrow transition size 2 9.73/3.34 Narrowing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: Narrow transition size 2 9.73/3.34 invGraph after Narrowing: 9.73/3.34 Transitions: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Variables: 9.73/3.34 main_x, main_N, main_y 9.73/3.34 Checking conditional termination of SCC {l7}... 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.001939s 9.73/3.34 Ranking function: -main_x + main_N 9.73/3.34 New Graphs: 9.73/3.34 Transitions: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Variables: 9.73/3.34 main_x, main_y, main_N 9.73/3.34 Checking conditional termination of SCC {l7}... 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.000733s 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.002817s 9.73/3.34 [55069 : 55240] 9.73/3.34 [55069 : 55241] 9.73/3.34 Successful child: 55240 9.73/3.34 [ Invariant Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 [ Termination Graph ] 9.73/3.34 Strengthening and disabling transitions... 9.73/3.34 9.73/3.34 LOG: CALL solverLinear in Graph for feasibility 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear in Graph for feasibility 9.73/3.34 Strengthening transition (result): 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 Ranking function: -main_x + main_N 9.73/3.34 New Graphs: 9.73/3.34 9.73/3.34 LOG: CALL check - Post:1 <= main_x + main_y - Process 3 9.73/3.34 * Exit transition: 9.73/3.34 * Postcondition : 1 <= main_x + main_y 9.73/3.34 9.73/3.34 LOG: CALL solveLinear 9.73/3.34 9.73/3.34 LOG: RETURN solveLinear - Elapsed time: 0.000607s 9.73/3.34 > Postcondition is not implied! 9.73/3.34 9.73/3.34 LOG: RETURN check - Elapsed time: 0.000787s 9.73/3.34 INVARIANTS: 9.73/3.34 7: 0 <= main_x + main_y , 9.73/3.34 Quasi-INVARIANTS to narrow Graph: 9.73/3.34 7: 1 <= main_x + main_y , 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 1 + main_x, rest remain the same}> 9.73/3.34 It's unfeasible. Removing transition: 9.73/3.34 2*main_x + main_y, main_y -> 1 + main_y, rest remain the same}> 9.73/3.34 invGraph after Narrowing: 9.73/3.34 Transitions: 9.73/3.34 Variables: 9.73/3.34 main_x, main_N, main_y 9.73/3.34 Analyzing SCC {l7}... 9.73/3.34 No cycles found. 9.73/3.34 9.73/3.34 Proving termination of subgraph 2 9.73/3.34 Analyzing SCC {l17}... 9.73/3.34 No cycles found. 9.73/3.34 9.73/3.34 Program Terminates 9.73/3.34 EOF