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/cav12/bist_cell.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 13:57:04,300 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 13:57:04,302 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 13:57:04,317 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 13:57:04,318 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 13:57:04,318 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 13:57:04,319 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 13:57:04,321 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 13:57:04,323 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 13:57:04,324 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 13:57:04,326 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 13:57:04,326 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 13:57:04,327 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 13:57:04,328 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 13:57:04,328 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 13:57:04,332 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 13:57:04,333 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 13:57:04,343 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 13:57:04,345 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 13:57:04,346 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 13:57:04,347 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 13:57:04,352 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 13:57:04,353 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 13:57:04,353 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 13:57:04,354 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 13:57:04,354 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 13:57:04,355 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 13:57:04,359 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 13:57:04,360 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 13:57:04,360 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 13:57:04,361 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 13:57:04,361 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 13:57:04,361 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 13:57:04,364 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 13:57:04,365 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 13:57:04,365 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 13:57:04,379 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 13:57:04,379 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 13:57:04,380 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 13:57:04,380 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 13:57:04,381 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 13:57:04,381 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 13:57:04,381 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 13:57:04,381 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 13:57:04,382 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 13:57:04,382 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 13:57:04,382 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 13:57:04,382 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 13:57:04,382 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 13:57:04,382 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 13:57:04,383 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 13:57:04,383 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 13:57:04,383 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 13:57:04,383 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 13:57:04,383 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 13:57:04,385 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 13:57:04,385 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 13:57:04,433 INFO ]: Repository-Root is: /tmp [2018-06-22 13:57:04,449 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 13:57:04,455 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 13:57:04,457 INFO ]: Initializing SmtParser... [2018-06-22 13:57:04,458 INFO ]: SmtParser initialized [2018-06-22 13:57:04,458 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/bist_cell.smt2 [2018-06-22 13:57:04,459 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 13:57:04,551 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bist_cell.smt2 unknown [2018-06-22 13:57:04,996 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bist_cell.smt2 [2018-06-22 13:57:05,005 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 13:57:05,019 INFO ]: Walking toolchain with 4 elements. [2018-06-22 13:57:05,019 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 13:57:05,019 INFO ]: Initializing ChcToBoogie... [2018-06-22 13:57:05,020 INFO ]: ChcToBoogie initialized [2018-06-22 13:57:05,022 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,104 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05 Unit [2018-06-22 13:57:05,104 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 13:57:05,105 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 13:57:05,105 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 13:57:05,105 INFO ]: Boogie Preprocessor initialized [2018-06-22 13:57:05,127 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,127 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,138 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,138 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,156 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,167 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,169 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (1/1) ... [2018-06-22 13:57:05,172 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 13:57:05,172 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 13:57:05,172 INFO ]: Initializing RCFGBuilder... [2018-06-22 13:57:05,172 INFO ]: RCFGBuilder initialized [2018-06-22 13:57:05,173 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (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-22 13:57:05,197 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 13:57:05,197 INFO ]: Found specification of procedure False [2018-06-22 13:57:05,197 INFO ]: Found implementation of procedure False [2018-06-22 13:57:05,197 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 13:57:05,197 INFO ]: Found specification of procedure state [2018-06-22 13:57:05,197 INFO ]: Found implementation of procedure state [2018-06-22 13:57:05,198 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 13:57:05,198 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 13:57:05,198 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-22 13:57:05,441 INFO ]: Using library mode [2018-06-22 13:57:05,442 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:57:05 BoogieIcfgContainer [2018-06-22 13:57:05,443 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 13:57:05,444 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 13:57:05,444 INFO ]: Initializing TraceAbstraction... [2018-06-22 13:57:05,449 INFO ]: TraceAbstraction initialized [2018-06-22 13:57:05,449 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:57:05" (1/3) ... [2018-06-22 13:57:05,450 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2e514f3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:57:05, skipping insertion in model container [2018-06-22 13:57:05,450 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:05" (2/3) ... [2018-06-22 13:57:05,451 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2e514f3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:57:05, skipping insertion in model container [2018-06-22 13:57:05,451 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:57:05" (3/3) ... [2018-06-22 13:57:05,452 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 13:57:05,463 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 13:57:05,474 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 13:57:05,518 INFO ]: Using default assertion order modulation [2018-06-22 13:57:05,519 INFO ]: Interprodecural is true [2018-06-22 13:57:05,519 INFO ]: Hoare is false [2018-06-22 13:57:05,519 INFO ]: Compute interpolants for FPandBP [2018-06-22 13:57:05,519 INFO ]: Backedges is TWOTRACK [2018-06-22 13:57:05,519 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 13:57:05,519 INFO ]: Difference is false [2018-06-22 13:57:05,519 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 13:57:05,519 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 13:57:05,531 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 13:57:05,541 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 13:57:05,541 INFO ]: Found error trace [2018-06-22 13:57:05,542 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:57:05,542 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:57:05,547 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 13:57:05,549 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:57:05,550 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:57:05,586 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:05,586 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:57:05,586 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:05,629 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:05,740 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 13:57:05,742 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 13:57:05,742 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 13:57:05,743 INFO ]: Interpolant automaton has 4 states [2018-06-22 13:57:05,754 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 13:57:05,754 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 13:57:05,756 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 13:57:05,878 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:57:05,878 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 13:57:05,879 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 13:57:05,880 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 13:57:05,880 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:57:05,889 INFO ]: With dead ends: 13 [2018-06-22 13:57:05,889 INFO ]: Without dead ends: 13 [2018-06-22 13:57:05,891 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 13:57:05,905 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 13:57:05,924 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 13:57:05,925 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 13:57:05,926 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 13:57:05,927 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 13:57:05,927 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:57:05,927 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 13:57:05,927 INFO ]: Interpolant automaton has 4 states. [2018-06-22 13:57:05,927 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 13:57:05,929 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 13:57:05,929 INFO ]: Found error trace [2018-06-22 13:57:05,929 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:57:05,929 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:57:05,929 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 13:57:05,929 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:57:05,929 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:57:05,930 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:05,930 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:57:05,930 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:06,026 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:06,482 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 13:57:06,482 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:57:06,482 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 13:57:06,491 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:57:06,593 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:06,604 INFO ]: Computing forward predicates... [2018-06-22 13:57:07,660 WARN ]: Spent 564.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2018-06-22 13:57:07,772 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 13:57:07,793 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 13:57:07,793 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 13:57:07,794 INFO ]: Interpolant automaton has 8 states [2018-06-22 13:57:07,794 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 13:57:07,794 INFO ]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-06-22 13:57:07,794 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-22 13:57:08,218 WARN ]: Spent 211.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2018-06-22 13:57:08,274 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:57:08,308 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 13:57:08,309 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 13:57:08,309 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 13:57:08,309 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:57:08,310 INFO ]: With dead ends: 15 [2018-06-22 13:57:08,310 INFO ]: Without dead ends: 15 [2018-06-22 13:57:08,311 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-22 13:57:08,311 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 13:57:08,313 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 13:57:08,313 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 13:57:08,314 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 13:57:08,314 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 13:57:08,314 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:57:08,314 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 13:57:08,314 INFO ]: Interpolant automaton has 8 states. [2018-06-22 13:57:08,314 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 13:57:08,315 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 13:57:08,315 INFO ]: Found error trace [2018-06-22 13:57:08,315 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:57:08,315 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:57:08,315 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 13:57:08,315 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:57:08,315 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:57:08,316 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:08,316 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:57:08,316 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:08,379 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:09,009 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 13:57:09,009 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:57:09,009 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 13:57:09,016 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 13:57:09,100 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 13:57:09,100 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:09,108 INFO ]: Computing forward predicates... [2018-06-22 13:57:10,011 INFO ]: Checked inductivity of 10 backedges. 1 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 13:57:10,031 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 13:57:10,031 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-22 13:57:10,031 INFO ]: Interpolant automaton has 12 states [2018-06-22 13:57:10,031 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 13:57:10,032 INFO ]: CoverageRelationStatistics Valid=42, Invalid=90, Unknown=0, NotChecked=0, Total=132 [2018-06-22 13:57:10,032 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 12 states. [2018-06-22 13:57:10,220 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:57:10,220 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 13:57:10,220 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 13:57:10,220 INFO ]: Start accepts. Automaton has 12 states. Word has length 17 [2018-06-22 13:57:10,220 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:57:10,221 INFO ]: With dead ends: 19 [2018-06-22 13:57:10,221 INFO ]: Without dead ends: 19 [2018-06-22 13:57:10,221 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=69, Invalid=141, Unknown=0, NotChecked=0, Total=210 [2018-06-22 13:57:10,221 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 13:57:10,224 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 13:57:10,224 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 13:57:10,225 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 13:57:10,225 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 13:57:10,225 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:57:10,225 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 13:57:10,225 INFO ]: Interpolant automaton has 12 states. [2018-06-22 13:57:10,225 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 13:57:10,226 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 13:57:10,226 INFO ]: Found error trace [2018-06-22 13:57:10,226 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:57:10,226 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:57:10,226 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 3 times [2018-06-22 13:57:10,226 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:57:10,226 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:57:10,227 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:10,227 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 13:57:10,227 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:57:10,300 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:10,722 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 13:57:10,722 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:57:10,722 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 13:57:10,736 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 13:57:10,842 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 13:57:10,842 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:57:10,852 INFO ]: Computing forward predicates... [2018-06-22 13:57:14,216 WARN ]: Simplifying disjunction of 6250 conjuctions. This might take some time... [2018-06-22 13:57:17,258 INFO ]: Simplified to disjunction of 6250 conjuctions. [2018-06-22 13:57:17,304 WARN ]: Simplifying disjunction of 6250 conjuctions. This might take some time... [2018-06-22 13:57:21,225 INFO ]: Simplified to disjunction of 6250 conjuctions. [2018-06-22 13:57:21,265 WARN ]: Simplifying disjunction of 6250 conjuctions. This might take some time... [2018-06-22 13:57:24,824 INFO ]: Simplified to disjunction of 6250 conjuctions. [2018-06-22 13:57:24,871 WARN ]: Simplifying disjunction of 6250 conjuctions. This might take some time... [2018-06-22 13:57:27,623 INFO ]: Simplified to disjunction of 6250 conjuctions. [2018-06-22 13:57:27,759 WARN ]: Simplifying disjunction of 6250 conjuctions. This might take some time... [2018-06-22 13:57:31,641 INFO ]: Simplified to disjunction of 6250 conjuctions. [2018-06-22 13:57:31,716 WARN ]: Simplifying disjunction of 10310 conjuctions. This might take some time... [2018-06-22 13:57:49,937 INFO ]: Simplified to disjunction of 10310 conjuctions. [2018-06-22 13:57:50,048 WARN ]: Simplifying disjunction of 10310 conjuctions. This might take some time... [2018-06-22 13:58:07,120 INFO ]: Simplified to disjunction of 10310 conjuctions. [2018-06-22 13:58:07,312 WARN ]: Simplifying disjunction of 20620 conjuctions. This might take some time... Received shutdown request... [2018-06-22 13:58:24,294 INFO ]: Timeout while computing interpolants [2018-06-22 13:58:24,495 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 13:58:24,495 WARN ]: Verification canceled [2018-06-22 13:58:24,499 WARN ]: Timeout [2018-06-22 13:58:24,500 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:58:24 BoogieIcfgContainer [2018-06-22 13:58:24,500 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 13:58:24,500 INFO ]: Toolchain (without parser) took 79495.04 ms. Allocated memory was 307.8 MB in the beginning and 428.3 MB in the end (delta: 120.6 MB). Free memory was 249.2 MB in the beginning and 293.7 MB in the end (delta: -44.5 MB). Peak memory consumption was 197.6 MB. Max. memory is 3.6 GB. [2018-06-22 13:58:24,501 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 307.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 13:58:24,502 INFO ]: ChcToBoogie took 85.49 ms. Allocated memory is still 307.8 MB. Free memory was 248.2 MB in the beginning and 246.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 13:58:24,502 INFO ]: Boogie Preprocessor took 66.41 ms. Allocated memory is still 307.8 MB. Free memory was 246.2 MB in the beginning and 244.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 13:58:24,504 INFO ]: RCFGBuilder took 270.86 ms. Allocated memory is still 307.8 MB. Free memory was 244.2 MB in the beginning and 225.2 MB in the end (delta: 19.0 MB). Peak memory consumption was 19.0 MB. Max. memory is 3.6 GB. [2018-06-22 13:58:24,512 INFO ]: TraceAbstraction took 79055.78 ms. Allocated memory was 307.8 MB in the beginning and 428.3 MB in the end (delta: 120.6 MB). Free memory was 225.2 MB in the beginning and 293.7 MB in the end (delta: -68.5 MB). Peak memory consumption was 173.6 MB. Max. memory is 3.6 GB. [2018-06-22 13:58:24,515 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.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 85.49 ms. Allocated memory is still 307.8 MB. Free memory was 248.2 MB in the beginning and 246.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 66.41 ms. Allocated memory is still 307.8 MB. Free memory was 246.2 MB in the beginning and 244.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 270.86 ms. Allocated memory is still 307.8 MB. Free memory was 244.2 MB in the beginning and 225.2 MB in the end (delta: 19.0 MB). Peak memory consumption was 19.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 79055.78 ms. Allocated memory was 307.8 MB in the beginning and 428.3 MB in the end (delta: 120.6 MB). Free memory was 225.2 MB in the beginning and 293.7 MB in the end (delta: -68.5 MB). Peak memory consumption was 173.6 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 PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 20620 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 78.9s OverallTime, 4 OverallIterations, 5 TraceHistogramMax, 0.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 34 SDtfs, 12 SDslu, 78 SDs, 0 SdLazy, 57 SolverSat, 5 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 50 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 2.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=3, 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, 3 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 3.2s InterpolantComputationTime, 69 NumberOfCodeBlocks, 69 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 64 ConstructedInterpolants, 0 QuantifiedInterpolants, 3504 SizeOfPredicates, 277 NumberOfNonLiveVariables, 436 ConjunctsInSsa, 23 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 9/26 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/bist_cell.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_13-58-24-529.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bist_cell.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_13-58-24-529.csv Completed graceful shutdown