/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.c # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 179 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 5690 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 1 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 76 ms] (9) IntTRS (10) IRS2T2 [EQUIVALENT, 0 ms] (11) T2IntSys (12) T2 [EQUIVALENT, 1145 ms] (13) YES (14) LLVM Symbolic Execution SCC (15) SCC2IRS [SOUND, 94 ms] (16) IntTRS (17) IRS2T2 [EQUIVALENT, 0 ms] (18) T2IntSys (19) T2 [EQUIVALENT, 942 ms] (20) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "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" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %i = alloca i32, align 4 %j = alloca i32, align 4 %c = alloca i32, align 4 store 0, %1 store 0, %c store 0, %i br %2 2: %3 = load %i %4 = icmp slt %3 10 br %4, %5, %21 5: store 3, %j br %6 6: %7 = load %j %8 = icmp slt %7 12 br %8, %9, %17 9: %10 = load %j %11 = sub %10 1 store %11, %j %12 = load %c %13 = add %12 1 store %13, %c br %14 14: %15 = load %j %16 = add %15 2 store %16, %j br %6 17: br %18 18: %19 = load %i %20 = add %19 1 store %20, %i br %2 21: %22 = load %c ret %22 Analyze Termination of all function calls matching the pattern: main() ---------------------------------------- (3) LLVMToTerminationGraphProof (EQUIVALENT) Constructed symbolic execution graph for LLVM program and proved memory safety. ---------------------------------------- (4) Obligation: SE Graph ---------------------------------------- (5) SymbolicExecutionGraphToSCCProof (SOUND) Splitted symbolic execution graph to 2 SCCs. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC ---------------------------------------- (8) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 35 rulesP rules: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Combined rules. Obtained 2 rulesP rules: 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 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 Filtered unneeded arguments: 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) Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 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 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 ---------------------------------------- (9) Obligation: Rules: 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 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 ---------------------------------------- (10) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_538_5,1) ---------------------------------------- (11) Obligation: START: 0; FROM: 0; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := oldX1 - 1; assume(oldX5 < 11 && oldX5 > 1 && oldX4 > 8 && oldX2 < 11 && oldX3 < 10 && oldX1 = 1 + oldX5); x0 := oldX0; x1 := 2 + oldX5; x2 := 1 + oldX5; x3 := oldX1 - 1; x4 := 1 + oldX4; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; assume(oldX0 < 10 && oldX0 > 0 && oldX0 < 9 && oldX4 > 8 && oldX1 = 12 && oldX2 = 11 && oldX3 = 10); x0 := 1 + oldX0; x1 := 4; x2 := 3; x3 := 2; x4 := 1 + oldX4; TO: 1; ---------------------------------------- (12) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 4, 5 using the following rank functions: - Rank function 1: RF for loc. 5: 1-18*x0-2*x1 RF for loc. 6: -18*x0-2*x1 Bound for (chained) transitions 5: -168 - Rank function 2: RF for loc. 5: -2*x1 RF for loc. 6: -1-2*x1 Bound for (chained) transitions 4: -23 - Rank function 3: RF for loc. 5: 0 RF for loc. 6: -1 Bound for (chained) transitions 1: 0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: SCC ---------------------------------------- (15) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 16 rulesP rules: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Combined rules. Obtained 1 rulesP rules: 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 Filtered unneeded arguments: 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) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 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 ---------------------------------------- (16) Obligation: Rules: 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 ---------------------------------------- (17) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_235_5,1) ---------------------------------------- (18) Obligation: START: 0; FROM: 0; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := oldX0 - 1; assume(oldX5 < 11 && oldX4 < 9 && oldX1 < 11 && oldX5 > 2 && oldX3 < 8 && oldX0 = 1 + oldX5 && oldX2 = 1 + oldX4); x0 := 2 + oldX5; x1 := 1 + oldX5; x2 := oldX0 - 1; x3 := oldX4; x4 := 1 + oldX4; TO: 1; ---------------------------------------- (19) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 3, 4 using the following rank functions: - Rank function 1: RF for loc. 5: 1-x0-x4 RF for loc. 6: -x0-x4 Bound for (chained) transitions 3: -19 Bound for (chained) transitions 4: -19 - Rank function 2: RF for loc. 5: 0 RF for loc. 6: -1 Bound for (chained) transitions 1: 0 ---------------------------------------- (20) YES