25.32/8.47 YES 25.32/8.49 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 25.32/8.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.32/8.49 25.32/8.49 25.32/8.49 Termination of the given C Problem could be proven: 25.32/8.49 25.32/8.49 (0) C Problem 25.32/8.49 (1) CToLLVMProof [EQUIVALENT, 176 ms] 25.32/8.49 (2) LLVM problem 25.32/8.49 (3) LLVMToTerminationGraphProof [EQUIVALENT, 4526 ms] 25.32/8.49 (4) LLVM Symbolic Execution Graph 25.32/8.49 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 25.32/8.49 (6) AND 25.32/8.49 (7) LLVM Symbolic Execution SCC 25.32/8.49 (8) SCC2IRS [SOUND, 61 ms] 25.32/8.49 (9) IntTRS 25.32/8.49 (10) IRS2T2 [EQUIVALENT, 0 ms] 25.32/8.49 (11) T2IntSys 25.32/8.49 (12) T2 [EQUIVALENT, 1216 ms] 25.32/8.49 (13) YES 25.32/8.49 (14) LLVM Symbolic Execution SCC 25.32/8.49 (15) SCC2IRS [SOUND, 35 ms] 25.32/8.49 (16) IntTRS 25.32/8.49 (17) IRS2T2 [EQUIVALENT, 0 ms] 25.32/8.49 (18) T2IntSys 25.32/8.49 (19) T2 [EQUIVALENT, 1202 ms] 25.32/8.49 (20) YES 25.32/8.49 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (0) 25.32/8.49 Obligation: 25.32/8.49 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (1) CToLLVMProof (EQUIVALENT) 25.32/8.49 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (2) 25.32/8.49 Obligation: 25.32/8.49 LLVM Problem 25.32/8.49 25.32/8.49 Aliases: 25.32/8.49 25.32/8.49 Data layout: 25.32/8.49 25.32/8.49 "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.32/8.49 25.32/8.49 Machine: 25.32/8.49 25.32/8.49 "x86_64-pc-linux-gnu" 25.32/8.49 25.32/8.49 Type definitions: 25.32/8.49 25.32/8.49 Global variables: 25.32/8.49 25.32/8.49 Function declarations and definitions: 25.32/8.49 25.32/8.49 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.32/8.49 0: 25.32/8.49 %1 = alloca i32, align 4 25.32/8.49 %i = alloca i32, align 4 25.32/8.49 %j = alloca i32, align 4 25.32/8.49 %c = alloca i32, align 4 25.32/8.49 store 0, %1 25.32/8.49 store 0, %c 25.32/8.49 store 0, %i 25.32/8.49 br %2 25.32/8.49 2: 25.32/8.49 %3 = load %i 25.32/8.49 %4 = icmp slt %3 10 25.32/8.49 br %4, %5, %21 25.32/8.49 5: 25.32/8.49 store 3, %j 25.32/8.49 br %6 25.32/8.49 6: 25.32/8.49 %7 = load %j 25.32/8.49 %8 = icmp slt %7 12 25.32/8.49 br %8, %9, %17 25.32/8.49 9: 25.32/8.49 %10 = load %j 25.32/8.49 %11 = sub %10 1 25.32/8.49 store %11, %j 25.32/8.49 %12 = load %c 25.32/8.49 %13 = add %12 1 25.32/8.49 store %13, %c 25.32/8.49 br %14 25.32/8.49 14: 25.32/8.49 %15 = load %j 25.32/8.49 %16 = add %15 2 25.32/8.49 store %16, %j 25.32/8.49 br %6 25.32/8.49 17: 25.32/8.49 br %18 25.32/8.49 18: 25.32/8.49 %19 = load %i 25.32/8.49 %20 = add %19 1 25.32/8.49 store %20, %i 25.32/8.49 br %2 25.32/8.49 21: 25.32/8.49 %22 = load %c 25.32/8.49 ret %22 25.32/8.49 25.32/8.49 25.32/8.49 Analyze Termination of all function calls matching the pattern: 25.32/8.49 main() 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (3) LLVMToTerminationGraphProof (EQUIVALENT) 25.32/8.49 Constructed symbolic execution graph for LLVM program and proved memory safety. 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (4) 25.32/8.49 Obligation: 25.32/8.49 SE Graph 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (5) SymbolicExecutionGraphToSCCProof (SOUND) 25.32/8.49 Splitted symbolic execution graph to 2 SCCs. 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (6) 25.32/8.49 Complex Obligation (AND) 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (7) 25.32/8.49 Obligation: 25.32/8.49 SCC 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (8) SCC2IRS (SOUND) 25.32/8.49 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.32/8.49 Generated rules. Obtained 35 rulesP rules: 25.32/8.49 f_523(v1035, v1036, v1037, v1038, v1039, 1, 3, 0, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 9, 8, 4) -> f_524(v1035, v1036, v1037, v1038, v1039, 1, 3, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 0, 9, 8, 4) :|: 0 = 0 25.32/8.49 f_524(v1035, v1036, v1037, v1038, v1039, 1, 3, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 0, 9, 8, 4) -> f_525(v1035, v1036, v1037, v1038, v1039, 1, 3, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 0, 9, 8, 4) :|: TRUE 25.32/8.49 f_525(v1035, v1036, v1037, v1038, v1039, 1, 3, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 0, 9, 8, 4) -> f_526(v1035, v1036, v1037, v1038, v1039, 1, 3, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) :|: TRUE 25.32/8.49 f_526(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1079, v1080, v1081, v1082, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) -> f_527(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1080, v1081, v1082, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) :|: 0 = 0 25.32/8.49 f_527(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1080, v1081, v1082, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) -> f_528(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1081, v1082, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) :|: 1 + v1090 = v1078 && 2 <= v1090 && v1090 <= 10 25.32/8.49 f_528(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1081, v1082, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) -> f_529(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1081, v1082, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) :|: TRUE 25.32/8.49 f_529(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1081, v1082, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) -> f_530(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) :|: 0 = 0 25.32/8.49 f_530(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) -> f_531(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) :|: v1092 = 1 + v1082 && 10 <= v1092 25.32/8.49 f_531(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) -> f_532(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) :|: TRUE 25.32/8.49 f_532(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) -> f_533(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) :|: TRUE 25.32/8.49 f_533(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1080, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 10, 4, 12, 8) -> f_534(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 6, 9, 11, 4, 12, 8, 2, 10) :|: 0 = 0 25.32/8.49 f_534(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1083, v1084, v1085, v1086, v1087, v1088, 0, 3, 6, 9, 11, 4, 12, 8, 2, 10) -> f_535(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) :|: v1098 = 2 + v1090 && 4 <= v1098 && v1098 <= 12 25.32/8.49 f_535(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_536(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) :|: TRUE 25.32/8.49 f_536(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_537(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) :|: TRUE 25.32/8.49 f_537(v1072, v1073, v1074, v1075, v1076, 1, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_538(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) :|: 0 = 0 25.32/8.49 f_538(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_539(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 10, 8, 4, 11) :|: v1098 < 12 && v1090 <= 9 && v1078 <= 10 25.32/8.49 f_538(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_540(v1072, v1073, v1074, v1075, v1076, 1, 12, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 9, 17, 8, 4, 18) :|: 12 <= v1098 && v1090 = 10 && v1098 = 12 && 0 = 0 && v1078 = 11 25.32/8.49 f_539(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 10, 8, 4, 11) -> f_541(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 10, 8, 4, 11) :|: 0 = 0 25.32/8.49 f_541(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 10, 8, 4, 11) -> f_543(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 10, 8, 4, 11) :|: TRUE 25.32/8.49 f_543(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 6, 9, 10, 8, 4, 11) -> f_526(v1072, v1073, v1074, v1075, v1076, 1, v1098, v1078, v1090, v1082, v1092, v1098, v1084, v1085, v1086, v1087, v1088, 0, 3, 2, 5, 9, 11, 10, 8, 4, 12) :|: TRUE 25.32/8.49 f_540(v1072, v1073, v1074, v1075, v1076, 1, 12, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 0, 3, 9, 17, 8, 4, 18) -> f_542(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 3, 9, 17, 8, 4, 18) :|: 0 = 0 25.32/8.49 f_542(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 3, 9, 17, 8, 4, 18) -> f_544(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 3, 9, 17, 8, 4, 18) :|: TRUE 25.32/8.49 f_544(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 3, 9, 17, 8, 4, 18) -> f_545(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 3, 9, 17, 8, 4, 18) :|: TRUE 25.32/8.49 f_545(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1084, v1085, v1086, v1087, v1088, 3, 9, 17, 8, 4, 18) -> f_546(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18) :|: 0 = 0 25.32/8.49 f_546(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18) -> f_547(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1155, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) :|: v1155 = 1 + v1076 && 2 <= v1155 && v1155 <= 10 25.32/8.49 f_547(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1155, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) -> f_548(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1155, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) :|: TRUE 25.32/8.49 f_548(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1155, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) -> f_549(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1155, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) :|: TRUE 25.32/8.49 f_549(v1072, v1073, v1074, v1075, v1076, 1, 12, 0, 11, 10, v1082, v1092, v1155, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) -> f_550(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) :|: 0 = 0 25.32/8.49 f_550(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 9, 17, 4, 18, 2) -> f_551(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) :|: v1155 < 10 && v1076 <= 8 25.32/8.49 f_551(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) -> f_553(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) :|: 0 = 0 25.32/8.49 f_553(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) -> f_555(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) :|: TRUE 25.32/8.49 f_555(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) -> f_557(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) :|: TRUE 25.32/8.49 f_557(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) -> f_559(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) :|: TRUE 25.32/8.49 f_559(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 8, 17, 4, 18, 2, 9) -> f_522(v1072, v1073, v1074, v1075, v1155, 1, 12, 0, 11, 10, v1082, v1092, v1076, v1085, v1086, v1087, v1088, 3, 9, 8, 4) :|: TRUE 25.32/8.49 f_522(v1035, v1036, v1037, v1038, v1039, 1, 12, 0, 11, 10, v1045, v1046, v1047, v1048, v1049, v1050, v1051, 3, 9, 8, 4) -> f_523(v1035, v1036, v1037, v1038, v1039, 1, 3, 0, 11, 10, v1045, v1046, 12, v1047, v1048, v1049, v1050, v1051, 9, 8, 4) :|: 0 = 0 25.32/8.49 Combined rules. Obtained 2 rulesP rules: 25.32/8.49 f_538(v1072:0, v1073:0, v1074:0, v1075:0, v1076:0, 1, 1 + v1090:1, v1078:0, v1090:0, v1082:0, v1092:0, v1084:0, v1085:0, v1086:0, v1087:0, v1088:0, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_538(v1072:0, v1073:0, v1074:0, v1075:0, v1076:0, 1, 2 + v1090:1, 1 + v1090:1, v1090:1, v1092:0, 1 + v1092:0, v1084:0, v1085:0, v1086:0, v1087:0, v1088:0, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) :|: v1090:1 > 1 && v1090:1 < 11 && v1092:0 > 8 && v1090:0 < 10 && v1078:0 < 11 25.32/8.49 f_538(v1072:0, v1073:0, v1074:0, v1075:0, v1076:0, 1, 12, 11, 10, v1082:0, v1092:0, v1084:0, v1085:0, v1086:0, v1087:0, v1088:0, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) -> f_538(v1072:0, v1073:0, v1074:0, v1075:0, 1 + v1076:0, 1, 4, 3, 2, v1092:0, 1 + v1092:0, v1076:0, v1085:0, v1086:0, v1087:0, v1088:0, 0, 3, 2, 6, 9, 11, 8, 4, 10, 12) :|: v1076:0 > 0 && v1076:0 < 10 && v1092:0 > 8 && v1076:0 < 9 25.32/8.49 Filtered unneeded arguments: 25.32/8.49 f_538(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26) -> f_538(x5, x7, x8, x9, x11) 25.32/8.49 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 25.32/8.49 f_538(v1076:0, sum~cons_1~v1090:1, v1078:0, v1090:0, v1092:0) -> f_538(v1076:0, 2 + v1090:1, 1 + v1090:1, v1090:1, 1 + v1092:0) :|: v1090:1 < 11 && v1090:1 > 1 && v1092:0 > 8 && v1078:0 < 11 && v1090:0 < 10 && sum~cons_1~v1090:1 = 1 + v1090:1 25.32/8.49 f_538(v1076:0, cons_12, cons_11, cons_10, v1092:0) -> f_538(1 + v1076:0, 4, 3, 2, 1 + v1092:0) :|: v1076:0 < 10 && v1076:0 > 0 && v1076:0 < 9 && v1092:0 > 8 && cons_12 = 12 && cons_11 = 11 && cons_10 = 10 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (9) 25.32/8.49 Obligation: 25.32/8.49 Rules: 25.32/8.49 f_538(v1076:0, sum~cons_1~v1090:1, v1078:0, v1090:0, v1092:0) -> f_538(v1076:0, 2 + v1090:1, 1 + v1090:1, v1090:1, 1 + v1092:0) :|: v1090:1 < 11 && v1090:1 > 1 && v1092:0 > 8 && v1078:0 < 11 && v1090:0 < 10 && sum~cons_1~v1090:1 = 1 + v1090:1 25.32/8.49 f_538(x, x1, x2, x3, x4) -> f_538(1 + x, 4, 3, 2, 1 + x4) :|: x < 10 && x > 0 && x < 9 && x4 > 8 && x1 = 12 && x2 = 11 && x3 = 10 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (10) IRS2T2 (EQUIVALENT) 25.32/8.49 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 25.32/8.49 25.32/8.49 (f_538_5,1) 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (11) 25.32/8.49 Obligation: 25.32/8.49 START: 0; 25.32/8.49 25.32/8.49 FROM: 0; 25.32/8.49 TO: 1; 25.32/8.49 25.32/8.49 FROM: 1; 25.32/8.49 oldX0 := x0; 25.32/8.49 oldX1 := x1; 25.32/8.49 oldX2 := x2; 25.32/8.49 oldX3 := x3; 25.32/8.49 oldX4 := x4; 25.32/8.49 oldX5 := oldX1 - 1; 25.32/8.49 assume(oldX5 < 11 && oldX5 > 1 && oldX4 > 8 && oldX2 < 11 && oldX3 < 10 && oldX1 = 1 + oldX5); 25.32/8.49 x0 := oldX0; 25.32/8.49 x1 := 2 + oldX5; 25.32/8.49 x2 := 1 + oldX5; 25.32/8.49 x3 := oldX1 - 1; 25.32/8.49 x4 := 1 + oldX4; 25.32/8.49 TO: 1; 25.32/8.49 25.32/8.49 FROM: 1; 25.32/8.49 oldX0 := x0; 25.32/8.49 oldX1 := x1; 25.32/8.49 oldX2 := x2; 25.32/8.49 oldX3 := x3; 25.32/8.49 oldX4 := x4; 25.32/8.49 assume(oldX0 < 10 && oldX0 > 0 && oldX0 < 9 && oldX4 > 8 && oldX1 = 12 && oldX2 = 11 && oldX3 = 10); 25.32/8.49 x0 := 1 + oldX0; 25.32/8.49 x1 := 4; 25.32/8.49 x2 := 3; 25.32/8.49 x3 := 2; 25.32/8.49 x4 := 1 + oldX4; 25.32/8.49 TO: 1; 25.32/8.49 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (12) T2 (EQUIVALENT) 25.32/8.49 Initially, performed program simplifications using lexicographic rank functions: 25.32/8.49 * Removed transitions 1, 4, 5 using the following rank functions: 25.32/8.49 - Rank function 1: 25.32/8.49 RF for loc. 5: 1-18*x0-2*x1 25.32/8.49 RF for loc. 6: -18*x0-2*x1 25.32/8.49 Bound for (chained) transitions 5: -168 25.32/8.49 - Rank function 2: 25.32/8.49 RF for loc. 5: -2*x1 25.32/8.49 RF for loc. 6: -1-2*x1 25.32/8.49 Bound for (chained) transitions 4: -23 25.32/8.49 - Rank function 3: 25.32/8.49 RF for loc. 5: 0 25.32/8.49 RF for loc. 6: -1 25.32/8.49 Bound for (chained) transitions 1: 0 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (13) 25.32/8.49 YES 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (14) 25.32/8.49 Obligation: 25.32/8.49 SCC 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (15) SCC2IRS (SOUND) 25.32/8.49 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.32/8.49 Generated rules. Obtained 16 rulesP rules: 25.32/8.49 f_235(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 11, 10, 8, 9, 4, 12) -> f_236(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 10, 9, 7, 8, 4, 11) :|: v120 < 12 && v117 <= 9 && v116 <= 10 && v118 <= 7 && v119 <= 8 25.32/8.49 f_236(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 10, 9, 7, 8, 4, 11) -> f_238(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 10, 9, 7, 8, 4, 11) :|: 0 = 0 25.32/8.49 f_238(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 10, 9, 7, 8, 4, 11) -> f_240(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 10, 9, 7, 8, 4, 11) :|: TRUE 25.32/8.49 f_240(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 10, 9, 7, 8, 4, 11) -> f_242(v110, v111, v112, v113, 0, 1, v120, v117, v118, v119, v121, v122, v123, v124, 3, 2, 9, 7, 8, 4, 11) :|: 0 = 0 25.32/8.49 f_242(v110, v111, v112, v113, 0, 1, v120, v117, v118, v119, v121, v122, v123, v124, 3, 2, 9, 7, 8, 4, 11) -> f_244(v110, v111, v112, v113, 0, 1, v120, v132, v118, v119, v117, v121, v122, v123, v124, 3, 2, 9, 7, 8, 4, 11, 10) :|: 1 + v132 = v120 && 3 <= v132 && v132 <= 10 25.32/8.49 f_244(v110, v111, v112, v113, 0, 1, v120, v132, v118, v119, v117, v121, v122, v123, v124, 3, 2, 9, 7, 8, 4, 11, 10) -> f_246(v110, v111, v112, v113, 0, 1, v120, v132, v118, v119, v117, v121, v122, v123, v124, 3, 2, 9, 7, 8, 4, 11, 10) :|: TRUE 25.32/8.49 f_246(v110, v111, v112, v113, 0, 1, v120, v132, v118, v119, v117, v121, v122, v123, v124, 3, 2, 9, 7, 8, 4, 11, 10) -> f_248(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) :|: 0 = 0 25.32/8.49 f_248(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) -> f_250(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) :|: v117 = 1 + v119 25.32/8.49 f_250(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) -> f_252(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) :|: TRUE 25.32/8.49 f_252(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) -> f_254(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) :|: TRUE 25.32/8.49 f_254(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) -> f_256(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) :|: 0 = 0 25.32/8.49 f_256(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10) -> f_258(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10, 5, 12) :|: v135 = 2 + v132 && 5 <= v135 && v135 <= 12 25.32/8.49 f_258(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10, 5, 12) -> f_260(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10, 5, 12) :|: TRUE 25.32/8.49 f_260(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10, 5, 12) -> f_262(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10, 5, 12) :|: TRUE 25.32/8.49 f_262(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 9, 8, 4, 11, 10, 5, 12) -> f_234(v110, v111, v112, v113, 0, 1, v120, v132, v119, v117, v135, v121, v122, v123, v124, 3, 2, 11, 10, 8, 9, 4, 12) :|: TRUE 25.32/8.49 f_234(v110, v111, v112, v113, 0, 1, v116, v117, v118, v119, v120, v121, v122, v123, v124, 3, 2, 11, 10, 8, 9, 4, 12) -> f_235(v110, v111, v112, v113, 0, 1, v120, v116, v117, v118, v119, v121, v122, v123, v124, 3, 2, 11, 10, 8, 9, 4, 12) :|: 0 = 0 25.32/8.49 Combined rules. Obtained 1 rulesP rules: 25.32/8.49 f_235(v110:0, v111:0, v112:0, v113:0, 0, 1, 1 + v132:0, v116:0, 1 + v119:0, v118:0, v119:0, v121:0, v122:0, v123:0, v124:0, 3, 2, 11, 10, 8, 9, 4, 12) -> f_235(v110:0, v111:0, v112:0, v113:0, 0, 1, 2 + v132:0, 1 + v132:0, v132:0, v119:0, 1 + v119:0, v121:0, v122:0, v123:0, v124:0, 3, 2, 11, 10, 8, 9, 4, 12) :|: v119:0 < 9 && v132:0 < 11 && v116:0 < 11 && v118:0 < 8 && v132:0 > 2 25.32/8.49 Filtered unneeded arguments: 25.32/8.49 f_235(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) -> f_235(x7, x8, x9, x10, x11) 25.32/8.49 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 25.32/8.49 f_235(sum~cons_1~v132:0, v116:0, sum~cons_1~v119:0, v118:0, v119:0) -> f_235(2 + v132:0, 1 + v132:0, v132:0, v119:0, 1 + v119:0) :|: v132:0 < 11 && v119:0 < 9 && v116:0 < 11 && v132:0 > 2 && v118:0 < 8 && sum~cons_1~v132:0 = 1 + v132:0 && sum~cons_1~v119:0 = 1 + v119:0 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (16) 25.32/8.49 Obligation: 25.32/8.49 Rules: 25.32/8.49 f_235(sum~cons_1~v132:0, v116:0, sum~cons_1~v119:0, v118:0, v119:0) -> f_235(2 + v132:0, 1 + v132:0, v132:0, v119:0, 1 + v119:0) :|: v132:0 < 11 && v119:0 < 9 && v116:0 < 11 && v132:0 > 2 && v118:0 < 8 && sum~cons_1~v132:0 = 1 + v132:0 && sum~cons_1~v119:0 = 1 + v119:0 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (17) IRS2T2 (EQUIVALENT) 25.32/8.49 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 25.32/8.49 25.32/8.49 (f_235_5,1) 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (18) 25.32/8.49 Obligation: 25.32/8.49 START: 0; 25.32/8.49 25.32/8.49 FROM: 0; 25.32/8.49 TO: 1; 25.32/8.49 25.32/8.49 FROM: 1; 25.32/8.49 oldX0 := x0; 25.32/8.49 oldX1 := x1; 25.32/8.49 oldX2 := x2; 25.32/8.49 oldX3 := x3; 25.32/8.49 oldX4 := x4; 25.32/8.49 oldX5 := oldX0 - 1; 25.32/8.49 assume(oldX5 < 11 && oldX4 < 9 && oldX1 < 11 && oldX5 > 2 && oldX3 < 8 && oldX0 = 1 + oldX5 && oldX2 = 1 + oldX4); 25.32/8.49 x0 := 2 + oldX5; 25.32/8.49 x1 := 1 + oldX5; 25.32/8.49 x2 := oldX0 - 1; 25.32/8.49 x3 := oldX4; 25.32/8.49 x4 := 1 + oldX4; 25.32/8.49 TO: 1; 25.32/8.49 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (19) T2 (EQUIVALENT) 25.32/8.49 Initially, performed program simplifications using lexicographic rank functions: 25.32/8.49 * Removed transitions 1, 3, 4 using the following rank functions: 25.32/8.49 - Rank function 1: 25.32/8.49 RF for loc. 5: 1-x0-x4 25.32/8.49 RF for loc. 6: -x0-x4 25.32/8.49 Bound for (chained) transitions 3: -19 25.32/8.49 Bound for (chained) transitions 4: -19 25.32/8.49 - Rank function 2: 25.32/8.49 RF for loc. 5: 0 25.32/8.49 RF for loc. 6: -1 25.32/8.49 Bound for (chained) transitions 1: 0 25.32/8.49 25.32/8.49 ---------------------------------------- 25.32/8.49 25.32/8.49 (20) 25.32/8.49 YES 25.32/8.52 EOF