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/lustre/MESI_1_e2_162_e7_1545.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 18:45:17,598 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 18:45:17,600 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 18:45:17,614 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 18:45:17,614 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 18:45:17,615 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 18:45:17,619 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 18:45:17,621 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 18:45:17,622 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 18:45:17,624 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 18:45:17,625 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 18:45:17,625 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 18:45:17,626 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 18:45:17,631 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 18:45:17,632 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 18:45:17,633 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 18:45:17,645 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 18:45:17,647 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 18:45:17,648 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 18:45:17,649 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 18:45:17,650 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 18:45:17,652 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 18:45:17,653 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 18:45:17,656 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 18:45:17,657 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 18:45:17,658 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 18:45:17,659 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 18:45:17,659 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 18:45:17,663 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 18:45:17,663 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 18:45:17,664 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 18:45:17,664 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 18:45:17,664 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 18:45:17,670 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 18:45:17,671 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 18:45:17,671 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 18:45:17,691 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 18:45:17,691 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 18:45:17,691 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 18:45:17,692 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 18:45:17,693 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 18:45:17,693 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 18:45:17,693 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 18:45:17,693 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 18:45:17,694 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 18:45:17,694 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 18:45:17,694 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 18:45:17,695 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 18:45:17,695 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 18:45:17,695 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 18:45:17,695 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 18:45:17,695 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 18:45:17,696 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 18:45:17,696 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 18:45:17,696 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 18:45:17,697 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 18:45:17,699 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 18:45:17,747 INFO ]: Repository-Root is: /tmp [2018-06-22 18:45:17,761 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 18:45:17,766 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 18:45:17,767 INFO ]: Initializing SmtParser... [2018-06-22 18:45:17,767 INFO ]: SmtParser initialized [2018-06-22 18:45:17,769 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1_e2_162_e7_1545.smt2 [2018-06-22 18:45:17,770 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 18:45:17,855 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1_e2_162_e7_1545.smt2 unknown [2018-06-22 18:45:18,267 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1_e2_162_e7_1545.smt2 [2018-06-22 18:45:18,271 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 18:45:18,277 INFO ]: Walking toolchain with 4 elements. [2018-06-22 18:45:18,278 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 18:45:18,278 INFO ]: Initializing ChcToBoogie... [2018-06-22 18:45:18,278 INFO ]: ChcToBoogie initialized [2018-06-22 18:45:18,281 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,339 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18 Unit [2018-06-22 18:45:18,339 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 18:45:18,339 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 18:45:18,339 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 18:45:18,339 INFO ]: Boogie Preprocessor initialized [2018-06-22 18:45:18,386 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,386 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,401 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,401 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,418 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,425 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,427 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (1/1) ... [2018-06-22 18:45:18,430 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 18:45:18,439 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 18:45:18,439 INFO ]: Initializing RCFGBuilder... [2018-06-22 18:45:18,439 INFO ]: RCFGBuilder initialized [2018-06-22 18:45:18,440 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (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 18:45:18,460 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 18:45:18,460 INFO ]: Found specification of procedure False [2018-06-22 18:45:18,460 INFO ]: Found implementation of procedure False [2018-06-22 18:45:18,460 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 18:45:18,460 INFO ]: Found specification of procedure state [2018-06-22 18:45:18,460 INFO ]: Found implementation of procedure state [2018-06-22 18:45:18,460 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 18:45:18,460 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 18:45:18,460 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 18:45:18,739 INFO ]: Using library mode [2018-06-22 18:45:18,740 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 06:45:18 BoogieIcfgContainer [2018-06-22 18:45:18,740 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 18:45:18,741 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 18:45:18,741 INFO ]: Initializing TraceAbstraction... [2018-06-22 18:45:18,746 INFO ]: TraceAbstraction initialized [2018-06-22 18:45:18,746 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 06:45:18" (1/3) ... [2018-06-22 18:45:18,747 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70406afc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 06:45:18, skipping insertion in model container [2018-06-22 18:45:18,747 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:18" (2/3) ... [2018-06-22 18:45:18,747 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70406afc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 06:45:18, skipping insertion in model container [2018-06-22 18:45:18,747 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 06:45:18" (3/3) ... [2018-06-22 18:45:18,749 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 18:45:18,759 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 18:45:18,770 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 18:45:18,819 INFO ]: Using default assertion order modulation [2018-06-22 18:45:18,819 INFO ]: Interprodecural is true [2018-06-22 18:45:18,819 INFO ]: Hoare is false [2018-06-22 18:45:18,819 INFO ]: Compute interpolants for FPandBP [2018-06-22 18:45:18,819 INFO ]: Backedges is TWOTRACK [2018-06-22 18:45:18,819 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 18:45:18,819 INFO ]: Difference is false [2018-06-22 18:45:18,819 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 18:45:18,820 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 18:45:18,837 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 18:45:18,848 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 18:45:18,848 INFO ]: Found error trace [2018-06-22 18:45:18,848 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:45:18,849 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:45:18,854 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 18:45:18,856 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:45:18,856 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:45:18,898 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:18,898 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:18,898 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:18,997 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:19,151 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 18:45:19,154 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 18:45:19,154 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 18:45:19,156 INFO ]: Interpolant automaton has 4 states [2018-06-22 18:45:19,166 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 18:45:19,167 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 18:45:19,168 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 18:45:19,295 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:45:19,295 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 18:45:19,296 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 18:45:19,297 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 18:45:19,297 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:45:19,308 INFO ]: With dead ends: 13 [2018-06-22 18:45:19,308 INFO ]: Without dead ends: 13 [2018-06-22 18:45:19,309 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 18:45:19,323 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 18:45:19,345 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 18:45:19,347 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 18:45:19,347 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 18:45:19,349 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 18:45:19,349 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:45:19,349 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 18:45:19,349 INFO ]: Interpolant automaton has 4 states. [2018-06-22 18:45:19,349 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 18:45:19,350 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 18:45:19,351 INFO ]: Found error trace [2018-06-22 18:45:19,351 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:45:19,351 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:45:19,351 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 18:45:19,351 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:45:19,351 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:45:19,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:19,352 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:19,352 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:19,456 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:20,156 WARN ]: Spent 479.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 30 [2018-06-22 18:45:20,277 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 11 [2018-06-22 18:45:20,289 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 18:45:20,289 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:45:20,289 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 18:45:20,301 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:20,409 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:20,421 INFO ]: Computing forward predicates... [2018-06-22 18:45:21,445 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,463 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,475 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,478 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,485 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,486 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,510 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,524 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,531 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,539 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:21,569 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,573 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,579 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:21,605 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,635 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,644 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,645 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,648 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,661 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,673 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,714 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,720 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,723 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:21,749 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,760 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,761 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,771 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,775 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,795 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,808 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:21,834 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:21,861 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,865 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,890 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:21,905 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:21,927 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:21,932 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:21,994 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:22,011 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:22,028 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:22,073 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 18:45:22,458 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:22,464 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:22,467 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:22,476 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:22,477 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:22,482 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:22,483 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:22,484 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:22,488 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:22,498 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:22,501 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:22,501 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:22,503 WARN ]: expecting exponential blowup for input size 11 [2018-06-22 18:45:37,143 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 13 [2018-06-22 18:45:37,191 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 18:45:37,222 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:45:37,222 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 18:45:37,222 INFO ]: Interpolant automaton has 8 states [2018-06-22 18:45:37,222 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 18:45:37,222 INFO ]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-06-22 18:45:37,223 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-22 18:45:37,473 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:45:37,473 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 18:45:37,473 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 18:45:37,473 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 18:45:37,474 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:45:37,474 INFO ]: With dead ends: 15 [2018-06-22 18:45:37,474 INFO ]: Without dead ends: 15 [2018-06-22 18:45:37,475 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-06-22 18:45:37,475 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 18:45:37,477 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 18:45:37,477 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 18:45:37,478 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 18:45:37,478 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 18:45:37,478 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:45:37,478 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 18:45:37,478 INFO ]: Interpolant automaton has 8 states. [2018-06-22 18:45:37,478 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 18:45:37,478 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 18:45:37,478 INFO ]: Found error trace [2018-06-22 18:45:37,479 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:45:37,479 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:45:37,479 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 18:45:37,479 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:45:37,479 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:45:37,480 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:37,480 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:37,480 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:37,543 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:38,231 WARN ]: Spent 349.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 68 [2018-06-22 18:45:38,405 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 18:45:38,405 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:45:38,405 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 18:45:38,415 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 18:45:38,501 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 18:45:38,501 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:38,508 INFO ]: Computing forward predicates... [2018-06-22 18:45:38,818 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:38,826 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:38,827 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:38,831 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:38,835 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:38,838 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:38,883 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:38,884 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:38,885 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:38,906 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:38,910 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:38,920 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:38,921 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:38,925 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:38,932 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 18:45:39,147 WARN ]: expecting exponential blowup for input size 11 [2018-06-22 18:45:39,343 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:39,375 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:39,538 WARN ]: Simplifying disjunction of 33840 conjuctions. This might take some time... Received shutdown request... [2018-06-22 18:46:29,199 INFO ]: Timeout while computing interpolants [2018-06-22 18:46:29,400 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:46:29,400 WARN ]: Verification canceled [2018-06-22 18:46:29,405 WARN ]: Timeout [2018-06-22 18:46:29,405 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 06:46:29 BoogieIcfgContainer [2018-06-22 18:46:29,405 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 18:46:29,406 INFO ]: Toolchain (without parser) took 71134.33 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 251.3 MB in the beginning and 906.3 MB in the end (delta: -655.1 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 18:46:29,412 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 18:46:29,412 INFO ]: ChcToBoogie took 61.38 ms. Allocated memory is still 308.8 MB. Free memory was 251.3 MB in the beginning and 247.3 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:46:29,413 INFO ]: Boogie Preprocessor took 90.88 ms. Allocated memory is still 308.8 MB. Free memory was 247.3 MB in the beginning and 245.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:46:29,413 INFO ]: RCFGBuilder took 300.43 ms. Allocated memory is still 308.8 MB. Free memory was 245.3 MB in the beginning and 225.3 MB in the end (delta: 20.0 MB). Peak memory consumption was 20.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:46:29,414 INFO ]: TraceAbstraction took 70664.43 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 225.3 MB in the beginning and 906.3 MB in the end (delta: -681.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 18:46:29,416 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 61.38 ms. Allocated memory is still 308.8 MB. Free memory was 251.3 MB in the beginning and 247.3 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 90.88 ms. Allocated memory is still 308.8 MB. Free memory was 247.3 MB in the beginning and 245.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 300.43 ms. Allocated memory is still 308.8 MB. Free memory was 245.3 MB in the beginning and 225.3 MB in the end (delta: 20.0 MB). Peak memory consumption was 20.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 70664.43 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 225.3 MB in the beginning and 906.3 MB in the end (delta: -681.0 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 18 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 33840 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 70.5s OverallTime, 3 OverallIterations, 3 TraceHistogramMax, 0.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 22 SDtfs, 7 SDslu, 47 SDs, 0 SdLazy, 33 SolverSat, 8 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 25 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred in iteration=2, 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, 2 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 17.7s InterpolantComputationTime, 35 NumberOfCodeBlocks, 35 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 32 ConstructedInterpolants, 0 QuantifiedInterpolants, 1548 SizeOfPredicates, 31 NumberOfNonLiveVariables, 425 ConjunctsInSsa, 45 ConjunctsInUnsatCore, 3 InterpolantComputations, 1 PerfectInterpolantSequences, 2/6 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/MESI_1_e2_162_e7_1545.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_18-46-29-433.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/MESI_1_e2_162_e7_1545.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_18-46-29-433.csv Completed graceful shutdown