25.30/7.56 YES 28.26/9.87 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 28.26/9.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 28.26/9.87 28.26/9.87 28.26/9.87 Termination of the given C Problem could be proven: 28.26/9.87 28.26/9.87 (0) C Problem 28.26/9.87 (1) CToLLVMProof [EQUIVALENT, 175 ms] 28.26/9.87 (2) LLVM problem 28.26/9.87 (3) LLVMToTerminationGraphProof [EQUIVALENT, 1483 ms] 28.26/9.87 (4) LLVM Symbolic Execution Graph 28.26/9.87 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 28.26/9.87 (6) AND 28.26/9.87 (7) LLVM Symbolic Execution SCC 28.26/9.87 (8) SCC2IRS [SOUND, 111 ms] 28.26/9.87 (9) IntTRS 28.26/9.87 (10) IRS2T2 [EQUIVALENT, 0 ms] 28.26/9.87 (11) T2IntSys 28.26/9.87 (12) T2 [EQUIVALENT, 845 ms] 28.26/9.87 (13) YES 28.26/9.87 (14) LLVM Symbolic Execution SCC 28.26/9.87 (15) SCC2IRS [SOUND, 72 ms] 28.26/9.87 (16) IntTRS 28.26/9.87 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 28.26/9.87 (18) IntTRS 28.26/9.87 (19) RankingReductionPairProof [EQUIVALENT, 21 ms] 28.26/9.87 (20) YES 28.26/9.87 (21) LLVM Symbolic Execution SCC 28.26/9.87 (22) SCC2IRS [SOUND, 34 ms] 28.26/9.87 (23) IntTRS 28.26/9.87 (24) IRS2T2 [EQUIVALENT, 0 ms] 28.26/9.87 (25) T2IntSys 28.26/9.87 (26) T2 [EQUIVALENT, 843 ms] 28.26/9.87 (27) YES 28.26/9.87 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (0) 28.26/9.87 Obligation: 28.26/9.87 c file /export/starexec/sandbox/benchmark/theBenchmark.c 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (1) CToLLVMProof (EQUIVALENT) 28.26/9.87 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (2) 28.26/9.87 Obligation: 28.26/9.87 LLVM Problem 28.26/9.87 28.26/9.87 Aliases: 28.26/9.87 28.26/9.87 Data layout: 28.26/9.87 28.26/9.87 "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" 28.26/9.87 28.26/9.87 Machine: 28.26/9.87 28.26/9.87 "x86_64-pc-linux-gnu" 28.26/9.87 28.26/9.87 Type definitions: 28.26/9.87 28.26/9.87 Global variables: 28.26/9.87 28.26/9.87 Function declarations and definitions: 28.26/9.87 28.26/9.87 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 28.26/9.87 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 28.26/9.87 0: 28.26/9.87 %1 = alloca i32, align 4 28.26/9.87 %i = alloca i32, align 4 28.26/9.87 %j = alloca i32, align 4 28.26/9.87 store 0, %1 28.26/9.87 %2 = call i32 @__VERIFIER_nondet_int() 28.26/9.87 store %2, %i 28.26/9.87 %3 = call i32 @__VERIFIER_nondet_int() 28.26/9.87 store %3, %j 28.26/9.87 br %4 28.26/9.87 4: 28.26/9.87 %5 = load %i 28.26/9.87 %6 = icmp slt %5 5 28.26/9.87 br %6, %7, %22 28.26/9.87 7: 28.26/9.87 store 0, %j 28.26/9.87 br %8 28.26/9.87 8: 28.26/9.87 %9 = load %i 28.26/9.87 %10 = icmp sgt %9 2 28.26/9.87 br %10, %11, %14 28.26/9.87 11: 28.26/9.87 %12 = load %j 28.26/9.87 %13 = icmp sle %12 9 28.26/9.87 br %14 28.26/9.87 14: 28.26/9.87 %15 = phi [0, %8], [%13, %11] 28.26/9.87 br %15, %16, %19 28.26/9.87 16: 28.26/9.87 %17 = load %j 28.26/9.87 %18 = add %17 1 28.26/9.87 store %18, %j 28.26/9.87 br %8 28.26/9.87 19: 28.26/9.87 %20 = load %i 28.26/9.87 %21 = add %20 1 28.26/9.87 store %21, %i 28.26/9.87 br %4 28.26/9.87 22: 28.26/9.87 ret 0 28.26/9.87 28.26/9.87 28.26/9.87 Analyze Termination of all function calls matching the pattern: 28.26/9.87 main() 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (3) LLVMToTerminationGraphProof (EQUIVALENT) 28.26/9.87 Constructed symbolic execution graph for LLVM program and proved memory safety. 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (4) 28.26/9.87 Obligation: 28.26/9.87 SE Graph 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (5) SymbolicExecutionGraphToSCCProof (SOUND) 28.26/9.87 Splitted symbolic execution graph to 3 SCCs. 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (6) 28.26/9.87 Complex Obligation (AND) 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (7) 28.26/9.87 Obligation: 28.26/9.87 SCC 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (8) SCC2IRS (SOUND) 28.26/9.87 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 28.26/9.87 Generated rules. Obtained 36 rulesP rules: 28.26/9.87 f_397(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1071, v1072, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 10, 2) -> f_399(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1072, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 10, 2) :|: 0 = 0 28.26/9.87 f_399(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1072, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 10, 2) -> f_401(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1112, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 2, 10) :|: v1112 = 1 + v1070 && 1 <= v1112 && v1112 <= 10 28.26/9.87 f_401(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1112, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 2, 10) -> f_403(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1112, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 2, 10) :|: TRUE 28.26/9.87 f_403(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1112, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 2, 10) -> f_405(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1112, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 2, 10) :|: TRUE 28.26/9.87 f_405(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1112, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 2, 10) -> f_406(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1073, v1070, v1112, v1074, v1075, v1076, 0, 3, 4, 2, 9, 10) :|: TRUE 28.26/9.87 f_406(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) -> f_407(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) :|: 0 = 0 28.26/9.87 f_407(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) -> f_408(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) :|: 0 = 0 28.26/9.87 f_408(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) -> f_409(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) :|: TRUE 28.26/9.87 f_409(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1150, v1151, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) -> f_410(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) :|: 0 = 0 28.26/9.87 f_410(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) -> f_411(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 8, 9) :|: v1151 <= 9 && v1150 <= 8 28.26/9.87 f_410(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 9, 10) -> f_412(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, 10, 9, v1152, v1153, v1154, 0, 3, 4, 2) :|: 9 < v1151 && v1150 = 9 && v1151 = 10 && 0 = 0 28.26/9.87 f_411(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 8, 9) -> f_413(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 8, 9) :|: 0 = 0 28.26/9.87 f_413(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 8, 9) -> f_415(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 8, 9) :|: 0 = 0 28.26/9.87 f_415(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, v1151, v1150, v1152, v1153, v1154, 0, 3, 4, 2, 8, 9) -> f_395(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1151, v1150, v1151, v1149, v1152, v1153, v1154, 0, 3, 4, 9, 10, 2) :|: TRUE 28.26/9.87 f_395(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1071, v1072, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 10, 2) -> f_397(v1063, v1064, v1065, v1066, v1067, v1068, 1, v1070, v1071, v1072, v1073, v1074, v1075, v1076, 0, 3, 4, 9, 10, 2) :|: TRUE 28.26/9.87 f_412(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, 10, 9, v1152, v1153, v1154, 0, 3, 4, 2) -> f_414(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, 10, 0, 9, v1152, v1153, v1154, 3, 4, 2) :|: 0 = 0 28.26/9.87 f_414(v1142, v1143, v1144, v1145, v1146, v1147, 1, v1149, 10, 0, 9, v1152, v1153, v1154, 3, 4, 2) -> f_416(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1149, 10, 9, v1152, v1153, v1154, 3, 4, 2) :|: 0 = 0 28.26/9.87 f_416(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1149, 10, 9, v1152, v1153, v1154, 3, 4, 2) -> f_417(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1149, 10, 9, v1152, v1153, v1154, 3, 4, 2) :|: TRUE 28.26/9.87 f_417(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1149, 10, 9, v1152, v1153, v1154, 3, 4, 2) -> f_418(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, 10, 9, v1152, v1153, v1154, 3, 4) :|: 0 = 0 28.26/9.87 f_418(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, 10, 9, v1152, v1153, v1154, 3, 4) -> f_419(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1275, 10, 9, v1152, v1153, v1154, 3, 4, 5) :|: v1275 = 1 + v1147 && 4 <= v1275 && v1275 <= 5 28.26/9.87 f_419(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1275, 10, 9, v1152, v1153, v1154, 3, 4, 5) -> f_420(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1275, 10, 9, v1152, v1153, v1154, 3, 4, 5) :|: TRUE 28.26/9.87 f_420(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1275, 10, 9, v1152, v1153, v1154, 3, 4, 5) -> f_421(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1275, 10, 9, v1152, v1153, v1154, 3, 4, 5) :|: TRUE 28.26/9.87 f_421(v1142, v1143, v1144, v1145, v1146, v1147, 1, 0, v1275, 10, 9, v1152, v1153, v1154, 3, 4, 5) -> f_422(v1142, v1143, v1144, v1145, v1146, v1275, 1, v1147, 0, 10, 9, v1152, v1153, v1154, 3, 4, 5) :|: 0 = 0 28.26/9.87 f_422(v1142, v1143, v1144, v1145, v1146, v1275, 1, v1147, 0, 10, 9, v1152, v1153, v1154, 3, 4, 5) -> f_423(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) :|: v1275 < 5 && v1147 = 3 && v1275 = 4 && 0 = 0 28.26/9.87 f_423(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) -> f_425(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) :|: 0 = 0 28.26/9.87 f_425(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) -> f_427(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) :|: TRUE 28.26/9.87 f_427(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) -> f_429(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) :|: TRUE 28.26/9.87 f_429(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) -> f_430(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) :|: TRUE 28.26/9.87 f_430(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 0, 10, 9, v1152, v1153, v1154) -> f_431(v1142, v1143, v1144, v1145, v1146, 4, 1, 3, 10, 0, 9, v1152, v1153, v1154) :|: TRUE 28.26/9.87 f_431(v1309, v1310, v1311, v1312, v1313, 4, 1, 3, 10, 0, 9, v1320, v1321, v1322) -> f_432(v1309, v1310, v1311, v1312, v1313, 4, 1, 10, 0, 9, 3, v1320, v1321, v1322) :|: 0 = 0 28.26/9.87 f_432(v1309, v1310, v1311, v1312, v1313, 4, 1, 10, 0, 9, 3, v1320, v1321, v1322) -> f_433(v1309, v1310, v1311, v1312, v1313, 4, 1, 10, 0, 9, 3, v1320, v1321, v1322) :|: 0 = 0 28.26/9.87 f_433(v1309, v1310, v1311, v1312, v1313, 4, 1, 10, 0, 9, 3, v1320, v1321, v1322) -> f_434(v1309, v1310, v1311, v1312, v1313, 4, 1, 10, 0, 9, 3, v1320, v1321, v1322) :|: TRUE 28.26/9.87 f_434(v1309, v1310, v1311, v1312, v1313, 4, 1, 10, 0, 9, 3, v1320, v1321, v1322) -> f_435(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322) :|: 0 = 0 28.26/9.87 f_435(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322) -> f_436(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322) :|: 0 = 0 28.26/9.87 f_436(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322) -> f_437(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322) :|: 0 = 0 28.26/9.87 f_437(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322) -> f_395(v1309, v1310, v1311, v1312, v1313, 4, 1, 0, 9, 10, 3, v1320, v1321, v1322, 0, 3, 4, 9, 10, 2) :|: TRUE 28.26/9.87 Combined rules. Obtained 2 rulesP rules: 28.26/9.87 f_397(v1063:0, v1064:0, v1065:0, v1066:0, v1067:0, v1068:0, 1, v1070:0, v1071:0, v1072:0, v1073:0, v1074:0, v1075:0, v1076:0, 0, 3, 4, 9, 10, 2) -> f_397(v1063:0, v1064:0, v1065:0, v1066:0, v1067:0, v1068:0, 1, 1 + v1070:0, v1070:0, 1 + v1070:0, v1073:0, v1074:0, v1075:0, v1076:0, 0, 3, 4, 9, 10, 2) :|: v1070:0 > -1 && v1070:0 < 10 && v1070:0 < 9 28.26/9.87 f_397(v1063:0, v1064:0, v1065:0, v1066:0, v1067:0, 3, 1, 9, v1071:0, v1072:0, v1073:0, v1074:0, v1075:0, v1076:0, 0, 3, 4, 9, 10, 2) -> f_397(v1063:0, v1064:0, v1065:0, v1066:0, v1067:0, 4, 1, 0, 9, 10, 3, v1074:0, v1075:0, v1076:0, 0, 3, 4, 9, 10, 2) :|: TRUE 28.26/9.87 Filtered unneeded arguments: 28.26/9.87 f_397(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20) -> f_397(x6, x8) 28.26/9.87 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 28.26/9.87 f_397(v1068:0, v1070:0) -> f_397(v1068:0, 1 + v1070:0) :|: v1070:0 < 10 && v1070:0 < 9 && v1070:0 > -1 28.26/9.87 f_397(cons_3, cons_9) -> f_397(4, 0) :|: TRUE && cons_3 = 3 && cons_9 = 9 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (9) 28.26/9.87 Obligation: 28.26/9.87 Rules: 28.26/9.87 f_397(v1068:0, v1070:0) -> f_397(v1068:0, 1 + v1070:0) :|: v1070:0 < 10 && v1070:0 < 9 && v1070:0 > -1 28.26/9.87 f_397(cons_3, cons_9) -> f_397(4, 0) :|: TRUE && cons_3 = 3 && cons_9 = 9 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (10) IRS2T2 (EQUIVALENT) 28.26/9.87 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 28.26/9.87 28.26/9.87 (f_397_2,1) 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (11) 28.26/9.87 Obligation: 28.26/9.87 START: 0; 28.26/9.87 28.26/9.87 FROM: 0; 28.26/9.87 TO: 1; 28.26/9.87 28.26/9.87 FROM: 1; 28.26/9.87 oldX0 := x0; 28.26/9.87 oldX1 := x1; 28.26/9.87 assume(oldX1 < 10 && oldX1 < 9 && oldX1 > -1); 28.26/9.87 x0 := oldX0; 28.26/9.87 x1 := 1 + oldX1; 28.26/9.87 TO: 1; 28.26/9.87 28.26/9.87 FROM: 1; 28.26/9.87 oldX0 := x0; 28.26/9.87 oldX1 := x1; 28.26/9.87 assume(0 = 0 && oldX0 = 3 && oldX1 = 9); 28.26/9.87 x0 := 4; 28.26/9.87 x1 := 0; 28.26/9.87 TO: 1; 28.26/9.87 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (12) T2 (EQUIVALENT) 28.26/9.87 Initially, performed program simplifications using lexicographic rank functions: 28.26/9.87 * Removed transitions 1, 4, 5 using the following rank functions: 28.26/9.87 - Rank function 1: 28.26/9.87 RF for loc. 5: -10*x0-x1 28.26/9.87 RF for loc. 6: -10*x0-x1 28.26/9.87 Bound for (chained) transitions 5: -39 28.26/9.87 - Rank function 2: 28.26/9.87 RF for loc. 5: -2*x1 28.26/9.87 RF for loc. 6: -1-2*x1 28.26/9.87 Bound for (chained) transitions 4: -17 28.26/9.87 - Rank function 3: 28.26/9.87 RF for loc. 5: 0 28.26/9.87 RF for loc. 6: -1 28.26/9.87 Bound for (chained) transitions 1: 0 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (13) 28.26/9.87 YES 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (14) 28.26/9.87 Obligation: 28.26/9.87 SCC 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (15) SCC2IRS (SOUND) 28.26/9.87 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 28.26/9.87 Generated rules. Obtained 13 rulesP rules: 28.26/9.87 f_289(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) -> f_291(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) :|: 0 = 0 28.26/9.87 f_291(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) -> f_293(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) :|: TRUE 28.26/9.87 f_293(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) -> f_295(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 9, 10) :|: 0 = 0 28.26/9.87 f_295(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 9, 10) -> f_297(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) :|: v394 <= 9 && v393 <= 8 28.26/9.87 f_297(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) -> f_300(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) :|: 0 = 0 28.26/9.87 f_300(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) -> f_303(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) :|: 0 = 0 28.26/9.87 f_303(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) -> f_306(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) :|: TRUE 28.26/9.87 f_306(v387, v388, v389, v390, v391, 1, v394, v393, v395, v396, v397, 0, 3, 4, 8, 9) -> f_310(v387, v388, v389, v390, v391, 1, v394, v395, v396, v397, 0, 3, 4, 9) :|: 0 = 0 28.26/9.87 f_310(v387, v388, v389, v390, v391, 1, v394, v395, v396, v397, 0, 3, 4, 9) -> f_313(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 2, 10) :|: v516 = 1 + v394 && 2 <= v516 && v516 <= 10 28.26/9.87 f_313(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 2, 10) -> f_316(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 2, 10) :|: TRUE 28.26/9.87 f_316(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 2, 10) -> f_319(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 2, 10) :|: TRUE 28.26/9.87 f_319(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 2, 10) -> f_287(v387, v388, v389, v390, v391, 1, v394, v516, v395, v396, v397, 0, 3, 4, 9, 10) :|: TRUE 28.26/9.87 f_287(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) -> f_289(v387, v388, v389, v390, v391, 1, v393, v394, v395, v396, v397, 0, 3, 4, 9, 10) :|: 0 = 0 28.26/9.87 Combined rules. Obtained 1 rulesP rules: 28.26/9.87 f_289(v387:0, v388:0, v389:0, v390:0, v391:0, 1, v393:0, v394:0, v395:0, v396:0, v397:0, 0, 3, 4, 9, 10) -> f_289(v387:0, v388:0, v389:0, v390:0, v391:0, 1, v394:0, 1 + v394:0, v395:0, v396:0, v397:0, 0, 3, 4, 9, 10) :|: v393:0 < 9 && v394:0 < 10 && v394:0 > 0 28.26/9.87 Filtered unneeded arguments: 28.26/9.87 f_289(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16) -> f_289(x7, x8) 28.26/9.87 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 28.26/9.87 f_289(v393:0, v394:0) -> f_289(v394:0, 1 + v394:0) :|: v394:0 < 10 && v394:0 > 0 && v393:0 < 9 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (16) 28.26/9.87 Obligation: 28.26/9.87 Rules: 28.26/9.87 f_289(v393:0, v394:0) -> f_289(v394:0, 1 + v394:0) :|: v394:0 < 10 && v394:0 > 0 && v393:0 < 9 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (17) IntTRSCompressionProof (EQUIVALENT) 28.26/9.87 Compressed rules. 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (18) 28.26/9.87 Obligation: 28.26/9.87 Rules: 28.26/9.87 f_289(v393:0:0, v394:0:0) -> f_289(v394:0:0, 1 + v394:0:0) :|: v394:0:0 < 10 && v394:0:0 > 0 && v393:0:0 < 9 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (19) RankingReductionPairProof (EQUIVALENT) 28.26/9.87 Interpretation: 28.26/9.87 [ f_289 ] = -1*f_289_2 28.26/9.87 28.26/9.87 The following rules are decreasing: 28.26/9.87 f_289(v393:0:0, v394:0:0) -> f_289(v394:0:0, 1 + v394:0:0) :|: v394:0:0 < 10 && v394:0:0 > 0 && v393:0:0 < 9 28.26/9.87 28.26/9.87 The following rules are bounded: 28.26/9.87 f_289(v393:0:0, v394:0:0) -> f_289(v394:0:0, 1 + v394:0:0) :|: v394:0:0 < 10 && v394:0:0 > 0 && v393:0:0 < 9 28.26/9.87 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (20) 28.26/9.87 YES 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (21) 28.26/9.87 Obligation: 28.26/9.87 SCC 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (22) SCC2IRS (SOUND) 28.26/9.87 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 28.26/9.87 Generated rules. Obtained 15 rulesP rules: 28.26/9.87 f_209(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) -> f_211(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) :|: 0 = 0 28.26/9.87 f_211(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) -> f_213(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_213(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) -> f_215(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_215(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) -> f_217(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_217(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) -> f_219(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) :|: 0 = 0 28.26/9.87 f_219(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) -> f_222(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) :|: v133 <= 2 && v130 <= 1 && v128 <= 1 28.26/9.87 f_222(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) -> f_226(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) :|: 0 = 0 28.26/9.87 f_226(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) -> f_229(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) :|: 0 = 0 28.26/9.87 f_229(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) -> f_232(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_232(v125, v126, v127, v128, v129, v133, 1, 0, v130, v134, v135, v136, 3, 2, 4) -> f_235(v125, v126, v127, v128, v129, v133, 1, 0, v134, v135, v136, 3, 2, 4) :|: 0 = 0 28.26/9.87 f_235(v125, v126, v127, v128, v129, v133, 1, 0, v134, v135, v136, 3, 2, 4) -> f_238(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) :|: v178 = 1 + v133 && v178 <= 3 28.26/9.87 f_238(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) -> f_241(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_241(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) -> f_244(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_244(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) -> f_207(v125, v126, v127, v128, v129, v133, 1, 0, v178, v134, v135, v136, 3, 2, 4) :|: TRUE 28.26/9.87 f_207(v125, v126, v127, v128, v129, v130, 1, 0, v133, v134, v135, v136, 3, 2, 4) -> f_209(v125, v126, v127, v128, v129, v133, 1, v130, 0, v134, v135, v136, 3, 2, 4) :|: 0 = 0 28.26/9.87 Combined rules. Obtained 1 rulesP rules: 28.26/9.87 f_209(v125:0, v126:0, v127:0, v128:0, v129:0, v133:0, 1, v130:0, 0, v134:0, v135:0, v136:0, 3, 2, 4) -> f_209(v125:0, v126:0, v127:0, v128:0, v129:0, 1 + v133:0, 1, v133:0, 0, v134:0, v135:0, v136:0, 3, 2, 4) :|: v130:0 < 2 && v133:0 < 3 && v128:0 < 2 28.26/9.87 Filtered unneeded arguments: 28.26/9.87 f_209(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) -> f_209(x4, x6, x8) 28.26/9.87 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 28.26/9.87 f_209(v128:0, v133:0, v130:0) -> f_209(v128:0, 1 + v133:0, v133:0) :|: v133:0 < 3 && v128:0 < 2 && v130:0 < 2 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (23) 28.26/9.87 Obligation: 28.26/9.87 Rules: 28.26/9.87 f_209(v128:0, v133:0, v130:0) -> f_209(v128:0, 1 + v133:0, v133:0) :|: v133:0 < 3 && v128:0 < 2 && v130:0 < 2 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (24) IRS2T2 (EQUIVALENT) 28.26/9.87 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 28.26/9.87 28.26/9.87 (f_209_3,1) 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (25) 28.26/9.87 Obligation: 28.26/9.87 START: 0; 28.26/9.87 28.26/9.87 FROM: 0; 28.26/9.87 TO: 1; 28.26/9.87 28.26/9.87 FROM: 1; 28.26/9.87 oldX0 := x0; 28.26/9.87 oldX1 := x1; 28.26/9.87 oldX2 := x2; 28.26/9.87 assume(oldX1 < 3 && oldX0 < 2 && oldX2 < 2); 28.26/9.87 x0 := oldX0; 28.26/9.87 x1 := 1 + oldX1; 28.26/9.87 x2 := oldX1; 28.26/9.87 TO: 1; 28.26/9.87 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (26) T2 (EQUIVALENT) 28.26/9.87 Initially, performed program simplifications using lexicographic rank functions: 28.26/9.87 * Removed transitions 1, 3, 4 using the following rank functions: 28.26/9.87 - Rank function 1: 28.26/9.87 RF for loc. 5: 1-2*x1 28.26/9.87 RF for loc. 6: -2*x1 28.26/9.87 Bound for (chained) transitions 4: -4 28.26/9.87 - Rank function 2: 28.26/9.87 RF for loc. 5: 1-2*x1 28.26/9.87 RF for loc. 6: -2*x1 28.26/9.87 Bound for (chained) transitions 3: -4 28.26/9.87 - Rank function 3: 28.26/9.87 RF for loc. 5: 0 28.26/9.87 RF for loc. 6: -1 28.26/9.87 Bound for (chained) transitions 1: 0 28.26/9.87 28.26/9.87 ---------------------------------------- 28.26/9.87 28.26/9.87 (27) 28.26/9.87 YES 28.26/9.90 EOF