3.41/1.59 YES 3.41/1.59 3.41/1.59 Solver Timeout: 4 3.41/1.59 Global Timeout: 300 3.41/1.59 Maximum number of concurrent processes: 900 3.41/1.59 ******************************************************************************************* 3.41/1.59 *********************** UNPROCESSED TRANSITION SYSTEMS PER FUNCTION *********************** 3.41/1.59 ******************************************************************************************* 3.41/1.59 3.41/1.59 3.41/1.59 List of LLVMGraphs + assumeNodes + staticAssertNodes [1] : 3.41/1.59 3.41/1.59 +++++++++++++++++++++++++++++++ main +++++++++++++++++++++++++++++++ 3.41/1.59 + + 3.41/1.59 Init Location: 0 3.41/1.59 Transitions: 3.41/1.59 0, main_x -> ¿functionCall(__VERIFIER_nondet_int), main_y -> ¿functionCall(__VERIFIER_nondet_int), main_z -> ¿functionCall(__VERIFIER_nondet_int)}> 3.41/1.59 3.41/1.59 0))> 3.41/1.59 0)> 3.41/1.59 (main_x + main_y), main_y -> main_z, main_z -> (~(main_z) - 1)}> 3.41/1.59 3.41/1.59 0}> 3.41/1.59 3.41/1.59 Fresh variables: 3.41/1.59 3.41/1.59 Undef variables: 3.41/1.59 3.41/1.59 Abstraction variables: 3.41/1.59 3.41/1.59 Exit nodes: 3.41/1.59 3.41/1.59 Accepting locations: 3.41/1.59 3.41/1.59 Asserts: 3.41/1.59 3.41/1.59 + Assume Nodes [0]: ++++++++++++++++++++++++++++++++++++++++++++++++ 3.41/1.59 3.41/1.59 + Static Assert Nodes [0]: +++++++++++++++++++++++++++++++++++++++++ 3.41/1.59 3.41/1.59 + After preprocess (paralelization): ++++++++++++++++++++++++++++++ 3.41/1.59 3.41/1.59 Init Location: 0 3.41/1.59 Transitions: 3.41/1.59 0}> 3.41/1.59 ¿functionCall(__VERIFIER_nondet_int)}> 3.41/1.59 varCall_1}> 3.41/1.59 ¿functionCall(__VERIFIER_nondet_int)}> 3.41/1.59 varCall_2}> 3.41/1.59 ¿functionCall(__VERIFIER_nondet_int)}> 3.41/1.59 varCall_3}> 3.41/1.59 3.41/1.59 0)> 3.41/1.59 0))> 3.41/1.59 (main_x + main_y), main_y -> main_z, main_z -> (~(main_z) - 1)}> 3.41/1.59 3.41/1.59 0}> 3.41/1.59 3.41/1.59 Fresh variables: 3.41/1.59 3.41/1.59 Undef variables: 3.41/1.59 3.41/1.59 Abstraction variables: 3.41/1.59 3.41/1.59 Exit nodes: 3.41/1.59 6, 3.41/1.59 Accepting locations: 3.41/1.59 3.41/1.59 Asserts: 3.41/1.59 3.41/1.59 + + 3.41/1.59 +++++++++++++++++++++++++++++++ main +++++++++++++++++++++++++++++++ 3.41/1.59 3.41/1.59 3.41/1.59 Function Return and Parameters Information [2 functions]: 3.41/1.59 function name: __VERIFIER_nondet_int [1 return + 0 parameters] demangled: __VERIFIER_nondet_int 3.41/1.59 __VERIFIER_nondet_int__func_return_ [function result] : int 3.41/1.59 function name: main [1 return + 0 parameters] demangled: main 3.41/1.59 main__func_return_ [function result] : int 3.41/1.59 3.41/1.59 3.41/1.59 AST Ident Scanner Information [5 idents]: 3.41/1.59 __VERIFIER_nondet_int | function | [integer, ()] | | 3.41/1.59 main | function | [integer, ()] | 3.41/1.59 x | local variable | integer | | 3.41/1.59 y | local variable | integer | | 3.41/1.59 z | local variable | integer | | 3.41/1.59 3.41/1.59 Main function: main 3.41/1.59 Preprocessed LLVMGraph 3.41/1.59 Init Location: 0 3.41/1.59 Transitions: 3.41/1.59 3.41/1.59 0), par{main_x -> (main_x + main_y), main_y -> main_z, main_z -> (~(main_z) - 1)}> 3.41/1.59 0))> 3.41/1.59 3.41/1.59 Fresh variables: 3.41/1.59 undef4, undef5, undef6, 3.41/1.59 3.41/1.59 Undef variables: 3.41/1.59 undef4, undef5, undef6, 3.41/1.59 3.41/1.59 Abstraction variables: 3.41/1.59 3.41/1.59 Exit nodes: 3.41/1.59 6, 3.41/1.59 Accepting locations: 3.41/1.59 3.41/1.59 Asserts: 3.41/1.59 3.41/1.59 ************************************************************* 3.41/1.59 ******************************************************************************************* 3.41/1.59 *********************** WORKING TRANSITION SYSTEM (DAG) *********************** 3.41/1.59 ******************************************************************************************* 3.41/1.59 3.41/1.59 Init Location: 0 3.41/1.59 Graph 0: 3.41/1.59 Transitions: 3.41/1.59 Variables: 3.41/1.59 3.41/1.59 Graph 1: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 3.41/1.59 Graph 2: 3.41/1.59 Transitions: 3.41/1.59 Variables: 3.41/1.59 3.41/1.59 Precedence: 3.41/1.59 Graph 0 3.41/1.59 3.41/1.59 Graph 1 3.41/1.59 3.41/1.59 3.41/1.59 Graph 2 3.41/1.59 3.41/1.59 3.41/1.59 Map Locations to Subgraph: 3.41/1.59 ( 0 , 0 ) 3.41/1.59 ( 2 , 1 ) 3.41/1.59 ( 6 , 2 ) 3.41/1.59 3.41/1.59 ******************************************************************************************* 3.41/1.59 ******************************** CHECKING ASSERTIONS ******************************** 3.41/1.59 ******************************************************************************************* 3.41/1.59 3.41/1.59 Proving termination of subgraph 0 3.41/1.59 Proving termination of subgraph 1 3.41/1.59 Checking unfeasibility... 3.41/1.59 Time used: 0.00241 3.41/1.59 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.000573s 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.001717s 3.41/1.59 [2312 : 2314] 3.41/1.59 [2312 : 2315] 3.41/1.59 Successful child: 2314 3.41/1.59 [ Invariant Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 It's unfeasible. Removing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 [ Termination Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 > It's unfeasible. Removing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 New Graphs: 3.41/1.59 3.41/1.59 LOG: CALL check - Post:1 + main_x <= 0 - Process 1 3.41/1.59 * Exit transition: 3.41/1.59 * Postcondition : 1 + main_x <= 0 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.000578s 3.41/1.59 > Postcondition is not implied! 3.41/1.59 3.41/1.59 LOG: RETURN check - Elapsed time: 0.000681s 3.41/1.59 INVARIANTS: 3.41/1.59 2: 3.41/1.59 Quasi-INVARIANTS to narrow Graph: 3.41/1.59 2: 1 + main_x <= 0 , 3.41/1.59 Narrowing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: Narrow transition size 1 3.41/1.59 invGraph after Narrowing: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.000536s 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.001844s 3.41/1.59 [2312 : 2319] 3.41/1.59 [2312 : 2320] 3.41/1.59 Successful child: 2319 3.41/1.59 [ Invariant Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 It's unfeasible. Removing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 [ Termination Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 It's unfeasible. Removing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 New Graphs: 3.41/1.59 3.41/1.59 LOG: CALL check - Post:main_x <= 0 - Process 2 3.41/1.59 * Exit transition: 3.41/1.59 * Postcondition : main_x <= 0 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.000625s 3.41/1.59 > Postcondition is not implied! 3.41/1.59 3.41/1.59 LOG: RETURN check - Elapsed time: 0.000729s 3.41/1.59 INVARIANTS: 3.41/1.59 2: 3.41/1.59 Quasi-INVARIANTS to narrow Graph: 3.41/1.59 2: main_x <= 0 , 3.41/1.59 Narrowing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: Narrow transition size 1 3.41/1.59 invGraph after Narrowing: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.000524s 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.001837s 3.41/1.59 [2312 : 2324] 3.41/1.59 [2312 : 2325] 3.41/1.59 Successful child: 2324 3.41/1.59 [ Invariant Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 [ Termination Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Ranking function: -main_z 3.41/1.59 New Graphs: 3.41/1.59 [2312 : 2329] 3.41/1.59 [2312 : 2330] 3.41/1.59 INVARIANTS: 3.41/1.59 2: 3.41/1.59 Quasi-INVARIANTS to narrow Graph: 3.41/1.59 2: main_x + main_z <= 0 , main_x + main_y <= 1 + main_z , 3.41/1.59 Narrowing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: Narrow transition size 2 3.41/1.59 invGraph after Narrowing: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.001222s 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.010407s 3.41/1.59 [2312 : 2331] 3.41/1.59 [2312 : 2332] 3.41/1.59 Successful child: 2331 3.41/1.59 [ Invariant Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 [ Termination Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Ranking function: 2*main_x - main_z 3.41/1.59 New Graphs: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.000735s 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.002767s 3.41/1.59 [2312 : 2336] 3.41/1.59 [2312 : 2337] 3.41/1.59 Successful child: 2336 3.41/1.59 [ Invariant Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 [ Termination Graph ] 3.41/1.59 Strengthening and disabling transitions... 3.41/1.59 3.41/1.59 LOG: CALL solverLinear in Graph for feasibility 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear in Graph for feasibility 3.41/1.59 Strengthening transition (result): 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Ranking function: 3*main_x - 2*main_z 3.41/1.59 New Graphs: 3.41/1.59 [2312 : 2341] 3.41/1.59 [2312 : 2342] 3.41/1.59 INVARIANTS: 3.41/1.59 2: 3.41/1.59 Quasi-INVARIANTS to narrow Graph: 3.41/1.59 2: 1 + main_y + main_z <= 0 , 3.41/1.59 [2312 : 2343] 3.41/1.59 [2312 : 2344] 3.41/1.59 [2312 : 2345] 3.41/1.59 INVARIANTS: 3.41/1.59 2: 3.41/1.59 Quasi-INVARIANTS to narrow Graph: 3.41/1.59 2: main_z <= 0 , 0 <= 1 + main_z , 3.41/1.59 Narrowing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: Narrow transition size 3 3.41/1.59 Narrowing transition: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 3.41/1.59 LOG: Narrow transition size 3 3.41/1.59 invGraph after Narrowing: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.004365s 3.41/1.59 Ranking function: -6 + 4*main_x + 4*main_y + 2*main_z 3.41/1.59 New Graphs: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.003002s 3.41/1.59 Ranking function: -1 + 2*main_x + 2*main_y + main_z 3.41/1.59 New Graphs: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.001997s 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.064205s 3.41/1.59 [2312 : 2346] 3.41/1.59 [2312 : 2347] 3.41/1.59 Successful child: 2347 3.41/1.59 Ranking function: 2*main_x - main_z 3.41/1.59 Ranking function and negation of Quasi-Invariant applied 3.41/1.59 New Graphs: 3.41/1.59 Transitions: 3.41/1.59 main_x + main_y, main_y -> main_z, main_z -> -1 - main_z, rest remain the same}> 3.41/1.59 Variables: 3.41/1.59 main_x, main_y, main_z 3.41/1.59 Checking conditional termination of SCC {l2}... 3.41/1.59 3.41/1.59 LOG: CALL solveLinear 3.41/1.59 3.41/1.59 LOG: RETURN solveLinear - Elapsed time: 0.001084s 3.41/1.59 Ranking function: (~(1) / 3) + (1 / 3)*main_z 3.41/1.59 New Graphs: 3.41/1.59 Proving termination of subgraph 2 3.41/1.59 Analyzing SCC {l6}... 3.41/1.59 No cycles found. 3.41/1.59 3.41/1.59 Program Terminates 3.41/1.59 EOF