25.35/7.90 YES 25.48/7.92 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 25.48/7.92 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.48/7.92 25.48/7.92 25.48/7.92 Termination of the given C Problem could be proven: 25.48/7.92 25.48/7.92 (0) C Problem 25.48/7.92 (1) CToLLVMProof [EQUIVALENT, 172 ms] 25.48/7.92 (2) LLVM problem 25.48/7.92 (3) LLVMToTerminationGraphProof [EQUIVALENT, 2899 ms] 25.48/7.92 (4) LLVM Symbolic Execution Graph 25.48/7.92 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 25.48/7.92 (6) AND 25.48/7.92 (7) LLVM Symbolic Execution SCC 25.48/7.92 (8) SCC2IRS [SOUND, 70 ms] 25.48/7.92 (9) IntTRS 25.48/7.92 (10) IRS2T2 [EQUIVALENT, 0 ms] 25.48/7.92 (11) T2IntSys 25.48/7.92 (12) T2 [EQUIVALENT, 873 ms] 25.48/7.92 (13) YES 25.48/7.92 (14) LLVM Symbolic Execution SCC 25.48/7.92 (15) SCC2IRS [SOUND, 62 ms] 25.48/7.92 (16) IntTRS 25.48/7.92 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 25.48/7.92 (18) IntTRS 25.48/7.92 (19) RankingReductionPairProof [EQUIVALENT, 27 ms] 25.48/7.92 (20) YES 25.48/7.92 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (0) 25.48/7.92 Obligation: 25.48/7.92 c file /export/starexec/sandbox/benchmark/theBenchmark.c 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (1) CToLLVMProof (EQUIVALENT) 25.48/7.92 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (2) 25.48/7.92 Obligation: 25.48/7.92 LLVM Problem 25.48/7.92 25.48/7.92 Aliases: 25.48/7.92 25.48/7.92 Data layout: 25.48/7.92 25.48/7.92 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" 25.48/7.92 25.48/7.92 Machine: 25.48/7.92 25.48/7.92 "x86_64-pc-linux-gnu" 25.48/7.92 25.48/7.92 Type definitions: 25.48/7.92 25.48/7.92 Global variables: 25.48/7.92 25.48/7.92 Function declarations and definitions: 25.48/7.92 25.48/7.92 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.48/7.92 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.48/7.92 0: 25.48/7.92 %1 = alloca i32, align 4 25.48/7.92 %2 = alloca i32, align 4 25.48/7.92 %c = alloca i32, align 4 25.48/7.92 store %x, %1 25.48/7.92 store %y, %2 25.48/7.92 store 0, %c 25.48/7.92 br %3 25.48/7.92 3: 25.48/7.92 %4 = load %1 25.48/7.92 %5 = icmp sgt %4 0 25.48/7.92 br %5, %6, %19 25.48/7.92 6: 25.48/7.92 store 0, %2 25.48/7.92 br %7 25.48/7.92 7: 25.48/7.92 %8 = load %2 25.48/7.92 %9 = load %1 25.48/7.92 %10 = icmp slt %8 %9 25.48/7.92 br %10, %11, %16 25.48/7.92 11: 25.48/7.92 %12 = load %2 25.48/7.92 %13 = add %12 1 25.48/7.92 store %13, %2 25.48/7.92 %14 = load %c 25.48/7.92 %15 = add %14 1 25.48/7.92 store %15, %c 25.48/7.92 br %7 25.48/7.92 16: 25.48/7.92 %17 = load %1 25.48/7.92 %18 = sub %17 1 25.48/7.92 store %18, %1 25.48/7.92 br %3 25.48/7.92 19: 25.48/7.92 %20 = load %c 25.48/7.92 ret %20 25.48/7.92 25.48/7.92 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.48/7.92 0: 25.48/7.92 %1 = alloca i32, align 4 25.48/7.92 store 0, %1 25.48/7.92 %2 = call i32 @__VERIFIER_nondet_int() 25.48/7.92 %3 = call i32 @__VERIFIER_nondet_int() 25.48/7.92 %4 = call i32 @test_fun(i32 %2, i32 %3) 25.48/7.92 ret %4 25.48/7.92 25.48/7.92 25.48/7.92 Analyze Termination of all function calls matching the pattern: 25.48/7.92 main() 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (3) LLVMToTerminationGraphProof (EQUIVALENT) 25.48/7.92 Constructed symbolic execution graph for LLVM program and proved memory safety. 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (4) 25.48/7.92 Obligation: 25.48/7.92 SE Graph 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (5) SymbolicExecutionGraphToSCCProof (SOUND) 25.48/7.92 Splitted symbolic execution graph to 2 SCCs. 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (6) 25.48/7.92 Complex Obligation (AND) 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (7) 25.48/7.92 Obligation: 25.48/7.92 SCC 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (8) SCC2IRS (SOUND) 25.48/7.92 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.48/7.92 Generated rules. Obtained 32 rulesP rules: 25.48/7.92 f_403(v483, v484, v485, v486, v487, v488, 1, v490, v492, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_404(v483, v484, v485, v486, v487, v488, 1, v490, v502, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: v502 = 1 + v490 && 1 <= v502 25.48/7.92 f_404(v483, v484, v485, v486, v487, v488, 1, v490, v502, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_405(v483, v484, v485, v486, v487, v488, 1, v490, v502, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_405(v483, v484, v485, v486, v487, v488, 1, v490, v502, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_406(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_406(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_407(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: v504 = 1 + v494 && 3 <= v504 25.48/7.92 f_407(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_408(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_408(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_409(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_409(v483, v484, v485, v486, v487, v488, 1, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_410(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_410(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_411(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_411(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_412(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: v502 < v488 && 2 <= v488 && 3 <= v495 && 3 <= v483 25.48/7.92 f_411(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_413(v483, v484, v485, v486, v487, v502, 1, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: v488 <= v502 && v488 = v502 25.48/7.92 f_412(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_414(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_414(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_416(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_416(v483, v484, v485, v486, v487, v488, 1, v502, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_402(v483, v484, v485, v486, v487, v488, 1, v502, v490, v502, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_402(v483, v484, v485, v486, v487, v488, 1, v490, v491, v492, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_403(v483, v484, v485, v486, v487, v488, 1, v490, v492, v493, v494, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_413(v483, v484, v485, v486, v487, v502, 1, v490, v494, v504, v495, v496, v497, v498, v499, v500, 0, 3, 2, 4) -> f_415(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v495, v496, v497, v498, v499, v500, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_415(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v495, v496, v497, v498, v499, v500, 3, 2, 4) -> f_417(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v495, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_417(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v495, v496, v497, v498, v499, v500, 3, 2, 4) -> f_418(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_418(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_419(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: 1 + v490 = v502 25.48/7.92 f_419(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_420(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_420(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_421(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_421(v483, v484, v485, v486, v487, v502, 1, 0, v490, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_422(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_422(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_423(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: 0 < v490 && 2 <= v502 && 3 <= v483 25.48/7.92 f_423(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_425(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_425(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_427(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_427(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_429(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_429(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_431(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_431(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) -> f_432(v483, v484, v485, v486, v487, v490, 1, v502, 0, v494, v504, v496, v497, v498, v499, v500, 3, 2, 4) :|: TRUE 25.48/7.92 f_432(v586, v587, v588, v589, v590, v591, 1, v593, 0, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) -> f_434(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_434(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) -> f_435(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_435(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) -> f_436(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_436(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) -> f_437(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) :|: TRUE 25.48/7.92 f_437(v586, v587, v588, v589, v590, v591, 1, 0, v593, v595, v596, v597, v598, v599, v600, v601, 3, 2, 4) -> f_402(v586, v587, v588, v589, v590, v591, 1, 0, v591, v593, v595, v596, v593, v597, v598, v599, v600, v601, 0, 3, 2, 4) :|: TRUE 25.48/7.92 Combined rules. Obtained 2 rulesP rules: 25.48/7.92 f_403(v483:0, v484:0, v485:0, v486:0, v487:0, 1 + v490:0, 1, v490:0, v492:0, v493:0, v494:0, v495:0, v496:0, v497:0, v498:0, v499:0, v500:0, 0, 3, 2, 4) -> f_403(v483:0, v484:0, v485:0, v486:0, v487:0, v490:0, 1, 0, 1 + v490:0, v494:0, 1 + v494:0, 1 + v490:0, v496:0, v497:0, v498:0, v499:0, v500:0, 0, 3, 2, 4) :|: v490:0 > 0 && v494:0 > 1 && v483:0 > 2 25.48/7.92 f_403(v483:0, v484:0, v485:0, v486:0, v487:0, v488:0, 1, v490:0, v492:0, v493:0, v494:0, v495:0, v496:0, v497:0, v498:0, v499:0, v500:0, 0, 3, 2, 4) -> f_403(v483:0, v484:0, v485:0, v486:0, v487:0, v488:0, 1, 1 + v490:0, 1 + v490:0, v494:0, 1 + v494:0, v495:0, v496:0, v497:0, v498:0, v499:0, v500:0, 0, 3, 2, 4) :|: v490:0 > -1 && v494:0 > 1 && v488:0 > 1 && v488:0 > 1 + v490:0 && v483:0 > 2 && v495:0 > 2 25.48/7.92 Filtered unneeded arguments: 25.48/7.92 f_403(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) -> f_403(x1, x6, x8, x11, x12) 25.48/7.92 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 25.48/7.92 f_403(v483:0, sum~cons_1~v490:0, v490:0, v494:0, v495:0) -> f_403(v483:0, v490:0, 0, 1 + v494:0, 1 + v490:0) :|: v494:0 > 1 && v483:0 > 2 && v490:0 > 0 && sum~cons_1~v490:0 = 1 + v490:0 25.48/7.92 f_403(v483:0, v488:0, v490:0, v494:0, v495:0) -> f_403(v483:0, v488:0, 1 + v490:0, 1 + v494:0, v495:0) :|: v494:0 > 1 && v490:0 > -1 && v488:0 > 1 && v488:0 > 1 + v490:0 && v495:0 > 2 && v483:0 > 2 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (9) 25.48/7.92 Obligation: 25.48/7.92 Rules: 25.48/7.92 f_403(v483:0, sum~cons_1~v490:0, v490:0, v494:0, v495:0) -> f_403(v483:0, v490:0, 0, 1 + v494:0, 1 + v490:0) :|: v494:0 > 1 && v483:0 > 2 && v490:0 > 0 && sum~cons_1~v490:0 = 1 + v490:0 25.48/7.92 f_403(x, x1, x2, x3, x4) -> f_403(x, x1, 1 + x2, 1 + x3, x4) :|: x3 > 1 && x2 > -1 && x1 > 1 && x1 > 1 + x2 && x4 > 2 && x > 2 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (10) IRS2T2 (EQUIVALENT) 25.48/7.92 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 25.48/7.92 25.48/7.92 (f_403_5,1) 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (11) 25.48/7.92 Obligation: 25.48/7.92 START: 0; 25.48/7.92 25.48/7.92 FROM: 0; 25.48/7.92 TO: 1; 25.48/7.92 25.48/7.92 FROM: 1; 25.48/7.92 oldX0 := x0; 25.48/7.92 oldX1 := x1; 25.48/7.92 oldX2 := x2; 25.48/7.92 oldX3 := x3; 25.48/7.92 oldX4 := x4; 25.48/7.92 assume(oldX3 > 1 && oldX0 > 2 && oldX2 > 0 && oldX1 = 1 + oldX2); 25.48/7.92 x0 := oldX0; 25.48/7.92 x1 := oldX2; 25.48/7.92 x2 := 0; 25.48/7.92 x3 := 1 + oldX3; 25.48/7.92 x4 := 1 + oldX2; 25.48/7.92 TO: 1; 25.48/7.92 25.48/7.92 FROM: 1; 25.48/7.92 oldX0 := x0; 25.48/7.92 oldX1 := x1; 25.48/7.92 oldX2 := x2; 25.48/7.92 oldX3 := x3; 25.48/7.92 oldX4 := x4; 25.48/7.92 assume(oldX3 > 1 && oldX2 > -1 && oldX1 > 1 && oldX1 > 1 + oldX2 && oldX4 > 2 && oldX0 > 2); 25.48/7.92 x0 := oldX0; 25.48/7.92 x1 := oldX1; 25.48/7.92 x2 := 1 + oldX2; 25.48/7.92 x3 := 1 + oldX3; 25.48/7.92 x4 := oldX4; 25.48/7.92 TO: 1; 25.48/7.92 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (12) T2 (EQUIVALENT) 25.48/7.92 Initially, performed program simplifications using lexicographic rank functions: 25.48/7.92 * Removed transitions 1, 4, 5 using the following rank functions: 25.48/7.92 - Rank function 1: 25.48/7.92 RF for loc. 5: 2*x1 25.48/7.92 RF for loc. 6: 2*x1 25.48/7.92 Bound for (chained) transitions 4: 4 25.48/7.92 - Rank function 2: 25.48/7.92 RF for loc. 5: 2*x1-2*x2 25.48/7.92 RF for loc. 6: -1+2*x1-2*x2 25.48/7.92 Bound for (chained) transitions 5: 3 25.48/7.92 - Rank function 3: 25.48/7.92 RF for loc. 5: 1 25.48/7.92 RF for loc. 6: 0 25.48/7.92 Bound for (chained) transitions 1: 1 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (13) 25.48/7.92 YES 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (14) 25.48/7.92 Obligation: 25.48/7.92 SCC 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (15) SCC2IRS (SOUND) 25.48/7.92 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.48/7.92 Generated rules. Obtained 13 rulesP rules: 25.48/7.92 f_258(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 4) -> f_259(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 4) :|: 0 = 0 25.48/7.92 f_259(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 4) -> f_260(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: v92 < v85 && 2 <= v85 25.48/7.92 f_260(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_262(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_262(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_264(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_264(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_266(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_266(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_268(v85, v86, v87, v88, v89, 1, v92, v99, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: v99 = 1 + v92 && 2 <= v99 25.48/7.92 f_268(v85, v86, v87, v88, v89, 1, v92, v99, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_270(v85, v86, v87, v88, v89, 1, v92, v99, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_270(v85, v86, v87, v88, v89, 1, v92, v99, v91, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_272(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: 0 = 0 25.48/7.92 f_272(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_274(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: v99 = 1 + v92 25.48/7.92 f_274(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_276(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_276(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_279(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) :|: TRUE 25.48/7.92 f_279(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 2, 4) -> f_257(v85, v86, v87, v88, v89, 1, v92, v99, v93, v94, v95, v96, v97, 0, 3, 4) :|: TRUE 25.48/7.92 f_257(v85, v86, v87, v88, v89, 1, v91, v92, v93, v94, v95, v96, v97, 0, 3, 4) -> f_258(v85, v86, v87, v88, v89, 1, v92, v91, v93, v94, v95, v96, v97, 0, 3, 4) :|: 0 = 0 25.48/7.92 Combined rules. Obtained 1 rulesP rules: 25.48/7.92 f_258(v85:0, v86:0, v87:0, v88:0, v89:0, 1, v92:0, v91:0, v93:0, v94:0, v95:0, v96:0, v97:0, 0, 3, 4) -> f_258(v85:0, v86:0, v87:0, v88:0, v89:0, 1, 1 + v92:0, v92:0, v93:0, v94:0, v95:0, v96:0, v97:0, 0, 3, 4) :|: v85:0 > 1 && v92:0 > 0 && v92:0 < v85:0 25.48/7.92 Filtered unneeded arguments: 25.48/7.92 f_258(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16) -> f_258(x1, x7) 25.48/7.92 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 25.48/7.92 f_258(v85:0, v92:0) -> f_258(v85:0, 1 + v92:0) :|: v92:0 > 0 && v92:0 < v85:0 && v85:0 > 1 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (16) 25.48/7.92 Obligation: 25.48/7.92 Rules: 25.48/7.92 f_258(v85:0, v92:0) -> f_258(v85:0, 1 + v92:0) :|: v92:0 > 0 && v92:0 < v85:0 && v85:0 > 1 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (17) IntTRSCompressionProof (EQUIVALENT) 25.48/7.92 Compressed rules. 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (18) 25.48/7.92 Obligation: 25.48/7.92 Rules: 25.48/7.92 f_258(v85:0:0, v92:0:0) -> f_258(v85:0:0, 1 + v92:0:0) :|: v92:0:0 > 0 && v92:0:0 < v85:0:0 && v85:0:0 > 1 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (19) RankingReductionPairProof (EQUIVALENT) 25.48/7.92 Interpretation: 25.48/7.92 [ f_258 ] = -1*f_258_2 + f_258_1 25.48/7.92 25.48/7.92 The following rules are decreasing: 25.48/7.92 f_258(v85:0:0, v92:0:0) -> f_258(v85:0:0, 1 + v92:0:0) :|: v92:0:0 > 0 && v92:0:0 < v85:0:0 && v85:0:0 > 1 25.48/7.92 25.48/7.92 The following rules are bounded: 25.48/7.92 f_258(v85:0:0, v92:0:0) -> f_258(v85:0:0, 1 + v92:0:0) :|: v92:0:0 > 0 && v92:0:0 < v85:0:0 && v85:0:0 > 1 25.48/7.92 25.48/7.92 25.48/7.92 ---------------------------------------- 25.48/7.92 25.48/7.92 (20) 25.48/7.92 YES 25.53/7.96 EOF