java -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/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 13:26:48,289 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 13:26:48,296 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 13:26:48,307 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 13:26:48,308 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 13:26:48,309 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 13:26:48,314 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 13:26:48,316 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 13:26:48,318 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 13:26:48,319 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 13:26:48,320 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 13:26:48,320 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 13:26:48,321 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 13:26:48,322 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 13:26:48,322 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 13:26:48,327 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 13:26:48,329 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 13:26:48,340 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 13:26:48,342 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 13:26:48,343 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 13:26:48,344 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 13:26:48,347 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 13:26:48,348 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 13:26:48,356 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 13:26:48,357 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 13:26:48,358 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 13:26:48,359 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 13:26:48,359 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 13:26:48,360 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 13:26:48,361 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 13:26:48,361 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 13:26:48,362 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 13:26:48,362 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 13:26:48,363 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 13:26:48,364 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 13:26:48,369 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 13:26:48,382 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 13:26:48,382 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 13:26:48,383 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 13:26:48,383 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 13:26:48,384 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 13:26:48,384 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 13:26:48,385 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 13:26:48,385 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 13:26:48,385 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:26:48,385 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 13:26:48,385 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 13:26:48,386 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 13:26:48,386 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 13:26:48,386 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 13:26:48,386 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 13:26:48,386 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 13:26:48,387 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 13:26:48,388 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 13:26:48,388 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 13:26:48,440 INFO ]: Repository-Root is: /tmp [2018-06-18 13:26:48,455 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 13:26:48,460 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 13:26:48,461 INFO ]: Initializing SmtParser... [2018-06-18 13:26:48,461 INFO ]: SmtParser initialized [2018-06-18 13:26:48,462 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-18 13:26:48,463 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-18 13:26:48,554 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 unknown [2018-06-18 13:26:48,952 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-18 13:26:48,957 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 13:26:48,962 INFO ]: Walking toolchain with 4 elements. [2018-06-18 13:26:48,962 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 13:26:48,962 INFO ]: Initializing ChcToBoogie... [2018-06-18 13:26:48,963 INFO ]: ChcToBoogie initialized [2018-06-18 13:26:48,970 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:26:48" (1/1) ... [2018-06-18 13:26:49,077 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49 Unit [2018-06-18 13:26:49,077 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 13:26:49,078 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 13:26:49,078 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 13:26:49,078 INFO ]: Boogie Preprocessor initialized [2018-06-18 13:26:49,112 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,112 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,135 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,135 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,148 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,149 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,153 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (1/1) ... [2018-06-18 13:26:49,156 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 13:26:49,157 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 13:26:49,157 INFO ]: Initializing RCFGBuilder... [2018-06-18 13:26:49,157 INFO ]: RCFGBuilder initialized [2018-06-18 13:26:49,158 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (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-18 13:26:49,179 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 13:26:49,179 INFO ]: Found specification of procedure False [2018-06-18 13:26:49,179 INFO ]: Found implementation of procedure False [2018-06-18 13:26:49,179 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 13:26:49,179 INFO ]: Found specification of procedure state [2018-06-18 13:26:49,179 INFO ]: Found implementation of procedure state [2018-06-18 13:26:49,179 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 13:26:49,179 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 13:26:49,180 INFO ]: Found implementation of procedure Ultimate.START [2018-06-18 13:26:49,540 INFO ]: Using library mode [2018-06-18 13:26:49,541 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:26:49 BoogieIcfgContainer [2018-06-18 13:26:49,541 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 13:26:49,543 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 13:26:49,543 INFO ]: Initializing TraceAbstraction... [2018-06-18 13:26:49,546 INFO ]: TraceAbstraction initialized [2018-06-18 13:26:49,546 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:26:48" (1/3) ... [2018-06-18 13:26:49,547 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46378b98 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 01:26:49, skipping insertion in model container [2018-06-18 13:26:49,547 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:26:49" (2/3) ... [2018-06-18 13:26:49,548 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46378b98 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 01:26:49, skipping insertion in model container [2018-06-18 13:26:49,548 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:26:49" (3/3) ... [2018-06-18 13:26:49,550 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 13:26:49,560 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 13:26:49,570 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 13:26:49,620 INFO ]: Using default assertion order modulation [2018-06-18 13:26:49,621 INFO ]: Interprodecural is true [2018-06-18 13:26:49,621 INFO ]: Hoare is false [2018-06-18 13:26:49,621 INFO ]: Compute interpolants for FPandBP [2018-06-18 13:26:49,621 INFO ]: Backedges is TWOTRACK [2018-06-18 13:26:49,621 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 13:26:49,621 INFO ]: Difference is false [2018-06-18 13:26:49,621 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 13:26:49,621 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 13:26:49,635 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 13:26:49,649 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 13:26:49,649 INFO ]: Found error trace [2018-06-18 13:26:49,649 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:26:49,650 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:26:49,653 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 13:26:49,655 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:26:49,655 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:26:49,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:49,690 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:26:49,690 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:49,721 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:49,731 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:26:49,825 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 13:26:49,827 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 13:26:49,827 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 13:26:49,831 INFO ]: Interpolant automaton has 4 states [2018-06-18 13:26:49,845 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 13:26:49,846 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:26:49,847 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 13:26:49,938 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:26:49,939 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 13:26:49,939 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 13:26:49,941 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 13:26:49,941 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:26:49,952 INFO ]: With dead ends: 13 [2018-06-18 13:26:49,952 INFO ]: Without dead ends: 13 [2018-06-18 13:26:49,954 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-18 13:26:49,967 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 13:26:49,990 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 13:26:49,993 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 13:26:49,993 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 13:26:49,995 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 13:26:49,995 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:26:49,995 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 13:26:49,995 INFO ]: Interpolant automaton has 4 states. [2018-06-18 13:26:49,995 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 13:26:49,997 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 13:26:49,997 INFO ]: Found error trace [2018-06-18 13:26:49,997 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:26:49,997 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:26:49,997 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 13:26:49,997 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:26:49,997 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:26:49,998 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:49,998 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:26:49,998 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:50,111 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:50,112 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:26:50,458 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:26:50,458 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:26:50,458 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-18 13:26:50,472 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:26:50,549 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:50,560 INFO ]: Computing forward predicates... [2018-06-18 13:26:50,946 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:26:50,973 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:26:50,974 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-18 13:26:50,974 INFO ]: Interpolant automaton has 6 states [2018-06-18 13:26:50,974 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-18 13:26:50,974 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-18 13:26:50,975 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-18 13:26:51,174 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:26:51,175 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 13:26:51,176 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 13:26:51,176 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-18 13:26:51,176 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:26:51,177 INFO ]: With dead ends: 15 [2018-06-18 13:26:51,177 INFO ]: Without dead ends: 15 [2018-06-18 13:26:51,178 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-18 13:26:51,178 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 13:26:51,183 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 13:26:51,183 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 13:26:51,184 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 13:26:51,184 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 13:26:51,184 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:26:51,184 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 13:26:51,184 INFO ]: Interpolant automaton has 6 states. [2018-06-18 13:26:51,184 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 13:26:51,185 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 13:26:51,185 INFO ]: Found error trace [2018-06-18 13:26:51,185 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:26:51,185 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:26:51,185 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 13:26:51,185 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:26:51,185 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:26:51,186 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:51,186 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:26:51,186 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:51,298 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:51,299 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:26:51,648 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-18 13:26:51,974 WARN ]: Spent 270.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-18 13:26:52,275 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:26:52,275 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:26:52,275 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-18 13:26:52,287 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 13:26:52,365 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:26:52,365 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:52,369 INFO ]: Computing forward predicates... [2018-06-18 13:26:52,829 WARN ]: Spent 361.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 10 [2018-06-18 13:26:52,940 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:26:52,967 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:26:52,967 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-18 13:26:52,967 INFO ]: Interpolant automaton has 10 states [2018-06-18 13:26:52,968 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-18 13:26:52,968 INFO ]: CoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-18 13:26:52,968 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 10 states. [2018-06-18 13:26:53,244 WARN ]: Spent 224.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-06-18 13:26:53,510 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:26:53,510 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 13:26:53,512 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 13:26:53,512 INFO ]: Start accepts. Automaton has 10 states. Word has length 17 [2018-06-18 13:26:53,512 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:26:53,512 INFO ]: With dead ends: 17 [2018-06-18 13:26:53,512 INFO ]: Without dead ends: 17 [2018-06-18 13:26:53,513 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-06-18 13:26:53,513 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 13:26:53,516 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 13:26:53,516 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 13:26:53,517 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 13:26:53,517 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 13:26:53,517 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:26:53,517 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 13:26:53,517 INFO ]: Interpolant automaton has 10 states. [2018-06-18 13:26:53,517 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 13:26:53,518 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 13:26:53,518 INFO ]: Found error trace [2018-06-18 13:26:53,518 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:26:53,518 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:26:53,518 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-18 13:26:53,518 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:26:53,518 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:26:53,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:53,519 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:26:53,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:53,589 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:53,590 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:26:54,023 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:26:54,024 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:26:54,024 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-18 13:26:54,042 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:26:54,125 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 13:26:54,125 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:54,129 INFO ]: Computing forward predicates... [2018-06-18 13:26:54,399 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:26:54,419 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:26:54,419 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-18 13:26:54,419 INFO ]: Interpolant automaton has 10 states [2018-06-18 13:26:54,420 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-18 13:26:54,420 INFO ]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-06-18 13:26:54,420 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-18 13:26:54,619 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-18 13:26:54,888 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:26:54,888 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 13:26:54,889 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 13:26:54,889 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-18 13:26:54,889 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:26:54,889 INFO ]: With dead ends: 19 [2018-06-18 13:26:54,889 INFO ]: Without dead ends: 19 [2018-06-18 13:26:54,890 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-18 13:26:54,890 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 13:26:54,893 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 13:26:54,893 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 13:26:54,893 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 13:26:54,893 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 13:26:54,894 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:26:54,894 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 13:26:54,894 INFO ]: Interpolant automaton has 10 states. [2018-06-18 13:26:54,894 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 13:26:54,894 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 13:26:54,894 INFO ]: Found error trace [2018-06-18 13:26:54,894 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:26:54,894 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:26:54,895 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-18 13:26:54,895 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:26:54,895 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:26:54,895 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:54,895 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:26:54,895 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:26:54,996 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:54,997 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:26:55,984 WARN ]: Spent 663.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-18 13:26:56,223 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:26:56,223 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:26:56,223 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-18 13:26:56,230 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:26:56,325 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:26:56,325 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:26:56,331 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-18 13:28:00,002 WARN ]: Removed 2 from assertion stack [2018-06-18 13:28:00,002 INFO ]: Timeout while computing interpolants [2018-06-18 13:28:00,202 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:28:00,202 WARN ]: Verification canceled [2018-06-18 13:28:00,207 WARN ]: Timeout [2018-06-18 13:28:00,207 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 01:28:00 BoogieIcfgContainer [2018-06-18 13:28:00,207 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 13:28:00,208 INFO ]: Toolchain (without parser) took 71249.90 ms. Allocated memory was 308.3 MB in the beginning and 1.3 GB in the end (delta: 942.7 MB). Free memory was 248.7 MB in the beginning and 742.4 MB in the end (delta: -493.7 MB). Peak memory consumption was 1.0 GB. Max. memory is 3.6 GB. [2018-06-18 13:28:00,210 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 272.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:28:00,210 INFO ]: ChcToBoogie took 115.07 ms. Allocated memory is still 308.3 MB. Free memory was 248.7 MB in the beginning and 240.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:28:00,211 INFO ]: Boogie Preprocessor took 78.48 ms. Allocated memory is still 308.3 MB. Free memory was 240.8 MB in the beginning and 238.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:28:00,211 INFO ]: RCFGBuilder took 383.97 ms. Allocated memory is still 308.3 MB. Free memory was 238.8 MB in the beginning and 220.8 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:28:00,212 INFO ]: TraceAbstraction took 70664.33 ms. Allocated memory was 308.3 MB in the beginning and 1.3 GB in the end (delta: 942.7 MB). Free memory was 220.8 MB in the beginning and 742.4 MB in the end (delta: -521.6 MB). Peak memory consumption was 996.7 MB. Max. memory is 3.6 GB. [2018-06-18 13:28:00,220 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 308.3 MB. Free memory is still 272.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 115.07 ms. Allocated memory is still 308.3 MB. Free memory was 248.7 MB in the beginning and 240.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 78.48 ms. Allocated memory is still 308.3 MB. Free memory was 240.8 MB in the beginning and 238.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 383.97 ms. Allocated memory is still 308.3 MB. Free memory was 238.8 MB in the beginning and 220.8 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 70664.33 ms. Allocated memory was 308.3 MB in the beginning and 1.3 GB in the end (delta: 942.7 MB). Free memory was 220.8 MB in the beginning and 742.4 MB in the end (delta: -521.6 MB). Peak memory consumption was 996.7 MB. 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.5s OverallTime, 5 OverallIterations, 5 TraceHistogramMax, 1.3s 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.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 82 GetRequests, 52 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 2.5s 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, 3.0s 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_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_13-28-00-242.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_13-28-00-242.csv Completed graceful shutdown