java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:12:45,049 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:12:45,051 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:12:45,066 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:12:45,066 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:12:45,067 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:12:45,068 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:12:45,070 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:12:45,072 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:12:45,072 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:12:45,073 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:12:45,073 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:12:45,074 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:12:45,075 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:12:45,076 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:12:45,080 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:12:45,082 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:12:45,085 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:12:45,087 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:12:45,088 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:12:45,089 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:12:45,091 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:12:45,092 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:12:45,092 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:12:45,093 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:12:45,094 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:12:45,094 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:12:45,095 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:12:45,096 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:12:45,096 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:12:45,097 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:12:45,098 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:12:45,098 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:12:45,099 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:12:45,099 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:12:45,100 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:12:45,113 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:12:45,113 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:12:45,114 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:12:45,114 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:12:45,115 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:12:45,115 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:12:45,115 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:12:45,115 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:12:45,116 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:12:45,117 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:12:45,117 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:12:45,117 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:12:45,117 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:12:45,117 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:12:45,118 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:12:45,118 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:12:45,118 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:12:45,118 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:12:45,118 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:12:45,120 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:12:45,120 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:12:45,155 INFO ]: Repository-Root is: /tmp [2018-06-22 15:12:45,173 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:12:45,178 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:12:45,180 INFO ]: Initializing SmtParser... [2018-06-22 15:12:45,180 INFO ]: SmtParser initialized [2018-06-22 15:12:45,180 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-22 15:12:45,181 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:12:45,273 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 unknown [2018-06-22 15:12:45,718 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-22 15:12:45,723 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:12:45,732 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:12:45,733 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:12:45,733 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:12:45,733 INFO ]: ChcToBoogie initialized [2018-06-22 15:12:45,736 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,780 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45 Unit [2018-06-22 15:12:45,780 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:12:45,781 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:12:45,781 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:12:45,781 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:12:45,804 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,804 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,824 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,824 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,840 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,841 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,845 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... [2018-06-22 15:12:45,848 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:12:45,849 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:12:45,849 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:12:45,849 INFO ]: RCFGBuilder initialized [2018-06-22 15:12:45,850 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:12:45,871 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:12:45,871 INFO ]: Found specification of procedure False [2018-06-22 15:12:45,871 INFO ]: Found implementation of procedure False [2018-06-22 15:12:45,871 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:12:45,871 INFO ]: Found specification of procedure state [2018-06-22 15:12:45,872 INFO ]: Found implementation of procedure state [2018-06-22 15:12:45,872 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:12:45,872 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:12:45,872 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 15:12:46,189 INFO ]: Using library mode [2018-06-22 15:12:46,190 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:12:46 BoogieIcfgContainer [2018-06-22 15:12:46,190 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:12:46,194 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:12:46,194 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:12:46,197 INFO ]: TraceAbstraction initialized [2018-06-22 15:12:46,197 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:12:45" (1/3) ... [2018-06-22 15:12:46,200 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@55e13d04 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:12:46, skipping insertion in model container [2018-06-22 15:12:46,201 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:12:45" (2/3) ... [2018-06-22 15:12:46,201 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@55e13d04 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:12:46, skipping insertion in model container [2018-06-22 15:12:46,201 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:12:46" (3/3) ... [2018-06-22 15:12:46,203 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:12:46,212 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:12:46,224 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:12:46,274 INFO ]: Using default assertion order modulation [2018-06-22 15:12:46,274 INFO ]: Interprodecural is true [2018-06-22 15:12:46,274 INFO ]: Hoare is false [2018-06-22 15:12:46,275 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:12:46,275 INFO ]: Backedges is TWOTRACK [2018-06-22 15:12:46,275 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:12:46,275 INFO ]: Difference is false [2018-06-22 15:12:46,275 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:12:46,275 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:12:46,288 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:12:46,303 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:12:46,303 INFO ]: Found error trace [2018-06-22 15:12:46,304 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:46,304 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:46,310 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:12:46,312 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:46,312 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:46,343 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:46,343 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:46,343 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:46,371 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:46,483 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:12:46,485 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:12:46,485 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:12:46,487 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:12:46,501 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:12:46,501 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:12:46,503 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:12:46,642 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:46,642 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:12:46,643 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:12:46,644 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:12:46,644 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:46,656 INFO ]: With dead ends: 13 [2018-06-22 15:12:46,656 INFO ]: Without dead ends: 13 [2018-06-22 15:12:46,658 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:12:46,671 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:12:46,700 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:12:46,701 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:12:46,702 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:12:46,703 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:12:46,703 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:46,704 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:12:46,704 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:12:46,704 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:12:46,705 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:12:46,705 INFO ]: Found error trace [2018-06-22 15:12:46,705 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:46,705 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:46,705 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:12:46,705 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:46,705 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:46,706 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:46,706 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:46,706 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:46,812 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:47,021 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:12:47,021 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:47,021 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:12:47,030 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:47,095 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:47,105 INFO ]: Computing forward predicates... [2018-06-22 15:12:47,359 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:12:47,385 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:47,385 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:12:47,385 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:12:47,386 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:12:47,386 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:12:47,386 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:12:47,549 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:47,549 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:12:47,550 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:12:47,550 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:12:47,550 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:47,550 INFO ]: With dead ends: 15 [2018-06-22 15:12:47,550 INFO ]: Without dead ends: 15 [2018-06-22 15:12:47,551 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:12:47,551 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:12:47,556 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:12:47,556 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:12:47,557 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:12:47,557 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:12:47,557 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:47,557 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:12:47,557 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:12:47,557 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:12:47,558 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:12:47,558 INFO ]: Found error trace [2018-06-22 15:12:47,558 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:47,558 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:47,559 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:12:47,559 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:47,559 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:47,560 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:47,560 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:12:47,560 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:47,667 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:48,030 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:12:48,030 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:48,030 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:12:48,038 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:12:48,116 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:12:48,116 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:48,120 INFO ]: Computing forward predicates... [2018-06-22 15:12:48,537 WARN ]: Spent 333.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 10 [2018-06-22 15:12:48,882 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:12:48,914 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:48,914 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 15:12:48,915 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:12:48,915 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:12:48,915 INFO ]: CoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:12:48,915 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 10 states. [2018-06-22 15:12:49,422 WARN ]: Spent 351.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-06-22 15:12:49,571 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:49,571 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:12:49,572 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:12:49,572 INFO ]: Start accepts. Automaton has 10 states. Word has length 17 [2018-06-22 15:12:49,572 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:49,573 INFO ]: With dead ends: 17 [2018-06-22 15:12:49,573 INFO ]: Without dead ends: 17 [2018-06-22 15:12:49,573 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:12:49,573 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:12:49,576 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:12:49,576 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:12:49,577 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:12:49,577 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:12:49,577 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:49,577 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:12:49,577 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:12:49,577 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:12:49,578 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:12:49,578 INFO ]: Found error trace [2018-06-22 15:12:49,578 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:49,578 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:49,578 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:12:49,578 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:49,578 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:49,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:49,579 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:49,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:49,636 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:50,040 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:12:50,040 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:50,040 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:12:50,054 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:12:50,121 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:12:50,121 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:50,125 INFO ]: Computing forward predicates... [2018-06-22 15:12:50,325 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:12:50,345 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:12:50,346 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 15:12:50,346 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:12:50,346 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:12:50,346 INFO ]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:12:50,346 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-22 15:12:50,514 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-22 15:12:50,765 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:12:50,765 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:12:50,766 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:12:50,766 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 15:12:50,767 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:12:50,767 INFO ]: With dead ends: 19 [2018-06-22 15:12:50,767 INFO ]: Without dead ends: 19 [2018-06-22 15:12:50,767 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=52, Invalid=130, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:12:50,767 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:12:50,770 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:12:50,770 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:12:50,770 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:12:50,770 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:12:50,771 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:12:50,771 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:12:50,771 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:12:50,771 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:12:50,771 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:12:50,771 INFO ]: Found error trace [2018-06-22 15:12:50,772 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:12:50,774 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:12:50,774 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:12:50,774 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:12:50,774 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:12:50,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:50,775 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:12:50,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:12:50,872 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:51,260 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-22 15:12:51,515 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:12:51,515 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:12:51,515 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:12:51,521 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:12:51,609 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:12:51,609 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:12:51,615 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:13:56,495 WARN ]: Removed 2 from assertion stack [2018-06-22 15:13:56,495 INFO ]: Timeout while computing interpolants [2018-06-22 15:13:56,696 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:13:56,696 WARN ]: Verification canceled [2018-06-22 15:13:56,699 WARN ]: Timeout [2018-06-22 15:13:56,699 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:13:56 BoogieIcfgContainer [2018-06-22 15:13:56,699 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:13:56,700 INFO ]: Toolchain (without parser) took 70975.85 ms. Allocated memory was 307.8 MB in the beginning and 1.3 GB in the end (delta: 978.3 MB). Free memory was 249.3 MB in the beginning and 1.2 GB in the end (delta: -919.5 MB). Peak memory consumption was 1.1 GB. Max. memory is 3.6 GB. [2018-06-22 15:13:56,700 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 307.8 MB. Free memory is still 273.4 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:13:56,703 INFO ]: ChcToBoogie took 48.21 ms. Allocated memory is still 307.8 MB. Free memory was 249.3 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:13:56,704 INFO ]: Boogie Preprocessor took 67.39 ms. Allocated memory is still 307.8 MB. Free memory was 247.4 MB in the beginning and 245.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:13:56,705 INFO ]: RCFGBuilder took 340.42 ms. Allocated memory is still 307.8 MB. Free memory was 245.4 MB in the beginning and 229.3 MB in the end (delta: 16.1 MB). Peak memory consumption was 16.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:13:56,705 INFO ]: TraceAbstraction took 70504.96 ms. Allocated memory was 307.8 MB in the beginning and 1.3 GB in the end (delta: 978.3 MB). Free memory was 229.3 MB in the beginning and 1.2 GB in the end (delta: -939.6 MB). Peak memory consumption was 1.0 GB. Max. memory is 3.6 GB. [2018-06-22 15:13:56,713 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 307.8 MB. Free memory is still 273.4 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 48.21 ms. Allocated memory is still 307.8 MB. Free memory was 249.3 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 67.39 ms. Allocated memory is still 307.8 MB. Free memory was 247.4 MB in the beginning and 245.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 340.42 ms. Allocated memory is still 307.8 MB. Free memory was 245.4 MB in the beginning and 229.3 MB in the end (delta: 16.1 MB). Peak memory consumption was 16.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 70504.96 ms. Allocated memory was 307.8 MB in the beginning and 1.3 GB in the end (delta: 978.3 MB). Free memory was 229.3 MB in the beginning and 1.2 GB in the end (delta: -939.6 MB). Peak memory consumption was 1.0 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 26 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 4735. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 70.4s OverallTime, 5 OverallIterations, 5 TraceHistogramMax, 1.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 44 SDtfs, 31 SDslu, 89 SDs, 0 SdLazy, 72 SolverSat, 32 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 82 GetRequests, 52 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 2.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=4, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 2.3s InterpolantComputationTime, 111 NumberOfCodeBlocks, 111 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 104 ConstructedInterpolants, 0 QuantifiedInterpolants, 11272 SizeOfPredicates, 183 NumberOfNonLiveVariables, 654 ConjunctsInSsa, 71 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 20/68 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-13-56-726.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-13-56-726.csv Completed graceful shutdown