java -Xss4m -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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/svd1.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:36:43,661 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:36:43,663 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:36:43,674 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:36:43,674 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:36:43,675 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:36:43,676 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:36:43,678 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:36:43,679 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:36:43,680 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:36:43,681 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:36:43,681 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:36:43,682 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:36:43,683 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:36:43,684 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:36:43,685 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:36:43,686 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:36:43,688 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:36:43,690 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:36:43,691 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:36:43,692 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:36:43,694 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:36:43,695 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:36:43,695 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:36:43,696 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:36:43,697 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:36:43,697 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:36:43,698 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:36:43,699 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:36:43,700 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:36:43,700 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:36:43,701 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:36:43,701 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:36:43,702 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:36:43,703 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:36:43,703 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 13:36:43,717 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:36:43,717 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:36:43,718 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:36:43,718 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:36:43,719 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:36:43,719 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:36:43,719 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:36:43,720 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:36:43,720 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:36:43,720 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:36:43,721 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:36:43,721 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:36:43,721 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:36:43,721 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:36:43,722 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:36:43,722 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:36:43,722 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:36:43,722 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:36:43,723 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:36:43,723 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:36:43,723 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:36:43,724 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:36:43,725 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:36:43,767 INFO ]: Repository-Root is: /tmp [2018-06-25 13:36:43,779 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:36:43,783 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:36:43,784 INFO ]: Initializing SmtParser... [2018-06-25 13:36:43,784 INFO ]: SmtParser initialized [2018-06-25 13:36:43,785 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/svd1.c.smt2 [2018-06-25 13:36:43,786 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-25 13:36:43,880 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/svd1.c.smt2 unknown [2018-06-25 13:36:44,331 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/svd1.c.smt2 [2018-06-25 13:36:44,335 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:36:44,343 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:36:44,343 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:36:44,343 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:36:44,344 INFO ]: ChcToBoogie initialized [2018-06-25 13:36:44,347 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,411 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44 Unit [2018-06-25 13:36:44,412 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:36:44,412 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:36:44,412 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:36:44,412 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:36:44,432 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,432 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,454 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,454 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,471 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,473 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,485 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (1/1) ... [2018-06-25 13:36:44,489 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:36:44,490 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:36:44,490 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:36:44,490 INFO ]: RCFGBuilder initialized [2018-06-25 13:36:44,491 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (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) [2018-06-25 13:36:44,517 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:36:44,518 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:36:44,518 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:36:44,518 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:36:44,518 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:36:44,518 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:36:44,858 INFO ]: Using library mode [2018-06-25 13:36:44,858 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:36:44 BoogieIcfgContainer [2018-06-25 13:36:44,859 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:36:44,860 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:36:44,860 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:36:44,863 INFO ]: TraceAbstraction initialized [2018-06-25 13:36:44,863 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:36:44" (1/3) ... [2018-06-25 13:36:44,864 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c668f0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:36:44, skipping insertion in model container [2018-06-25 13:36:44,864 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:36:44" (2/3) ... [2018-06-25 13:36:44,864 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c668f0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:36:44, skipping insertion in model container [2018-06-25 13:36:44,864 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:36:44" (3/3) ... [2018-06-25 13:36:44,866 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:36:44,875 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:36:44,884 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:36:44,948 INFO ]: Using default assertion order modulation [2018-06-25 13:36:44,949 INFO ]: Interprodecural is true [2018-06-25 13:36:44,949 INFO ]: Hoare is false [2018-06-25 13:36:44,949 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:36:44,949 INFO ]: Backedges is TWOTRACK [2018-06-25 13:36:44,949 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:36:44,949 INFO ]: Difference is false [2018-06-25 13:36:44,949 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:36:44,949 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:36:44,959 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:36:44,969 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:36:44,970 INFO ]: Found error trace [2018-06-25 13:36:44,970 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:36:44,971 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:36:44,976 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 13:36:44,978 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:36:44,979 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:36:45,023 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:45,023 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:36:45,023 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:45,087 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:45,215 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:36:45,218 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:36:45,218 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:36:45,220 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:36:45,231 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:36:45,231 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:36:45,234 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:36:45,324 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:36:45,324 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:36:45,327 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:36:45,328 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:36:45,329 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:36:45,339 INFO ]: With dead ends: 9 [2018-06-25 13:36:45,339 INFO ]: Without dead ends: 9 [2018-06-25 13:36:45,341 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:36:45,359 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:36:45,387 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:36:45,388 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:36:45,388 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:36:45,394 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:36:45,394 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:36:45,394 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:36:45,394 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:36:45,394 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:36:45,395 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:36:45,395 INFO ]: Found error trace [2018-06-25 13:36:45,395 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:36:45,395 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:36:45,395 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 13:36:45,395 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:36:45,395 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:36:45,396 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:45,396 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:36:45,396 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:45,528 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:45,735 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:36:45,735 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:36:45,735 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) [2018-06-25 13:36:45,751 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:36:45,842 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:45,853 INFO ]: Computing forward predicates... [2018-06-25 13:36:47,052 WARN ]: Spent 324.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 17 [2018-06-25 13:36:49,790 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:36:49,821 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:36:49,821 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:36:49,821 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:36:49,821 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:36:49,821 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:36:49,822 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:36:50,030 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2018-06-25 13:36:50,047 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:36:50,047 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 13:36:50,047 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 13:36:50,047 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:36:50,047 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:36:50,048 INFO ]: With dead ends: 10 [2018-06-25 13:36:50,048 INFO ]: Without dead ends: 10 [2018-06-25 13:36:50,048 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:36:50,048 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 13:36:50,049 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 13:36:50,049 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 13:36:50,050 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 13:36:50,050 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 13:36:50,050 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:36:50,050 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 13:36:50,050 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:36:50,050 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 13:36:50,050 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 13:36:50,050 INFO ]: Found error trace [2018-06-25 13:36:50,050 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:36:50,050 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:36:50,051 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 13:36:50,051 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:36:50,051 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:36:50,052 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:50,052 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:36:50,052 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:50,170 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:50,689 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 10 [2018-06-25 13:36:50,729 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:36:50,729 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:36:50,729 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-25 13:36:50,750 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:36:50,838 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:36:50,838 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:50,841 INFO ]: Computing forward predicates... [2018-06-25 13:36:51,990 WARN ]: Spent 873.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 11 [2018-06-25 13:36:53,961 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:36:53,994 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:36:53,994 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 13:36:53,994 INFO ]: Interpolant automaton has 6 states [2018-06-25 13:36:53,994 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 13:36:53,994 INFO ]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:36:53,995 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 13:36:54,388 WARN ]: Spent 338.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 20 [2018-06-25 13:36:54,517 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 12 [2018-06-25 13:36:54,550 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:36:54,550 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:36:54,550 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:36:54,550 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 13:36:54,550 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:36:54,550 INFO ]: With dead ends: 11 [2018-06-25 13:36:54,550 INFO ]: Without dead ends: 11 [2018-06-25 13:36:54,551 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2018-06-25 13:36:54,551 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:36:54,552 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:36:54,552 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:36:54,552 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:36:54,552 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 13:36:54,552 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:36:54,552 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:36:54,552 INFO ]: Interpolant automaton has 6 states. [2018-06-25 13:36:54,552 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:36:54,552 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:36:54,552 INFO ]: Found error trace [2018-06-25 13:36:54,552 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:36:54,553 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:36:54,553 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 13:36:54,553 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:36:54,553 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:36:54,554 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:54,554 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:36:54,554 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:36:54,650 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:54,956 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:36:54,956 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:36:55,066 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-25 13:36:55,072 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:36:55,203 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:36:55,203 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:36:55,208 INFO ]: Computing forward predicates... [2018-06-25 13:36:56,263 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 12 [2018-06-25 13:37:04,186 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:04,188 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:04,192 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:04,196 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:04,198 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:04,201 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:06,007 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:09,024 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:37:09,044 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:37:09,044 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 13:37:09,045 INFO ]: Interpolant automaton has 7 states [2018-06-25 13:37:09,045 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 13:37:09,045 INFO ]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-06-25 13:37:09,045 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 13:37:09,337 WARN ]: Spent 206.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 10 [2018-06-25 13:37:09,453 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:37:09,453 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 13:37:09,453 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 13:37:09,453 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 13:37:09,454 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:37:09,454 INFO ]: With dead ends: 12 [2018-06-25 13:37:09,454 INFO ]: Without dead ends: 12 [2018-06-25 13:37:09,454 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=38, Invalid=72, Unknown=0, NotChecked=0, Total=110 [2018-06-25 13:37:09,455 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 13:37:09,456 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 13:37:09,456 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 13:37:09,456 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 13:37:09,456 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 13:37:09,456 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:37:09,456 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 13:37:09,456 INFO ]: Interpolant automaton has 7 states. [2018-06-25 13:37:09,456 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 13:37:09,456 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 13:37:09,457 INFO ]: Found error trace [2018-06-25 13:37:09,457 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:37:09,457 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:37:09,457 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 13:37:09,457 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:37:09,457 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:37:09,458 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:37:09,458 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:37:09,458 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:37:09,557 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:37:09,856 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 17 [2018-06-25 13:37:10,039 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:37:10,039 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:37:10,039 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-25 13:37:10,045 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 13:37:10,153 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 13:37:10,153 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:37:10,158 INFO ]: Computing forward predicates... [2018-06-25 13:37:13,279 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:37:13,548 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 13:37:48,522 INFO ]: Timeout while computing interpolants [2018-06-25 13:37:48,723 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:37:48,723 WARN ]: Verification canceled [2018-06-25 13:37:48,726 WARN ]: Timeout [2018-06-25 13:37:48,726 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:37:48 BoogieIcfgContainer [2018-06-25 13:37:48,726 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:37:48,727 INFO ]: Toolchain (without parser) took 64390.99 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 236.1 MB in the beginning and 636.7 MB in the end (delta: -400.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:37:48,728 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:37:48,728 INFO ]: ChcToBoogie took 68.58 ms. Allocated memory is still 304.6 MB. Free memory was 236.1 MB in the beginning and 233.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:37:48,729 INFO ]: Boogie Preprocessor took 77.04 ms. Allocated memory is still 304.6 MB. Free memory was 233.1 MB in the beginning and 231.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:37:48,729 INFO ]: RCFGBuilder took 368.78 ms. Allocated memory is still 304.6 MB. Free memory was 231.1 MB in the beginning and 205.3 MB in the end (delta: 25.8 MB). Peak memory consumption was 25.8 MB. Max. memory is 3.6 GB. [2018-06-25 13:37:48,729 INFO ]: TraceAbstraction took 63866.29 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 205.3 MB in the beginning and 636.7 MB in the end (delta: -431.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:37:48,732 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 304.6 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 68.58 ms. Allocated memory is still 304.6 MB. Free memory was 236.1 MB in the beginning and 233.1 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 77.04 ms. Allocated memory is still 304.6 MB. Free memory was 233.1 MB in the beginning and 231.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 368.78 ms. Allocated memory is still 304.6 MB. Free memory was 231.1 MB in the beginning and 205.3 MB in the end (delta: 25.8 MB). Peak memory consumption was 25.8 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63866.29 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 205.3 MB in the beginning and 636.7 MB in the end (delta: -431.4 MB). Peak memory consumption was 1.3 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 12 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 24 quantified variables from 10 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 63.7s OverallTime, 5 OverallIterations, 4 TraceHistogramMax, 1.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 5 SDslu, 50 SDs, 0 SdLazy, 23 SolverSat, 11 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 50 GetRequests, 23 SyntacticMatches, 6 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 3.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=12occurred 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.6s SatisfiabilityAnalysisTime, 22.0s InterpolantComputationTime, 61 NumberOfCodeBlocks, 61 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 54 ConstructedInterpolants, 0 QuantifiedInterpolants, 2101 SizeOfPredicates, 21 NumberOfNonLiveVariables, 1089 ConjunctsInSsa, 93 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/20 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/svd1.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-37-48-744.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/svd1.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-37-48-744.csv Completed graceful shutdown