java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-24 22:21:16,377 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-24 22:21:16,379 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-24 22:21:16,390 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-24 22:21:16,391 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-24 22:21:16,392 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-24 22:21:16,395 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-24 22:21:16,399 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-24 22:21:16,402 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-24 22:21:16,403 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-24 22:21:16,404 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-24 22:21:16,404 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-24 22:21:16,405 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-24 22:21:16,407 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-24 22:21:16,408 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-24 22:21:16,409 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-24 22:21:16,410 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-24 22:21:16,412 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-24 22:21:16,414 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-24 22:21:16,414 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-24 22:21:16,415 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-24 22:21:16,418 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-24 22:21:16,418 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-24 22:21:16,418 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-24 22:21:16,419 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-24 22:21:16,420 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-24 22:21:16,421 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-24 22:21:16,421 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-24 22:21:16,422 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-24 22:21:16,423 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-24 22:21:16,423 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-24 22:21:16,424 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-24 22:21:16,424 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-24 22:21:16,425 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-24 22:21:16,425 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-24 22:21:16,426 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-24 22:21:16,439 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-24 22:21:16,440 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-24 22:21:16,440 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-24 22:21:16,440 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-24 22:21:16,441 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-24 22:21:16,441 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-24 22:21:16,441 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-24 22:21:16,442 INFO L133 SettingsManager]: * Use SBE=true [2018-06-24 22:21:16,442 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-24 22:21:16,442 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-24 22:21:16,442 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-24 22:21:16,443 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-24 22:21:16,443 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 22:21:16,443 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-24 22:21:16,443 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-24 22:21:16,443 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-24 22:21:16,444 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-24 22:21:16,444 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-24 22:21:16,444 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-24 22:21:16,444 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-24 22:21:16,444 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-24 22:21:16,446 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-24 22:21:16,446 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-24 22:21:16,495 INFO ]: Repository-Root is: /tmp [2018-06-24 22:21:16,508 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-24 22:21:16,511 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-24 22:21:16,513 INFO ]: Initializing SmtParser... [2018-06-24 22:21:16,513 INFO ]: SmtParser initialized [2018-06-24 22:21:16,514 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 [2018-06-24 22:21:16,515 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-24 22:21:16,605 INFO ]: Executing SMT file /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 unknown [2018-06-24 22:21:16,954 INFO ]: Succesfully executed SMT file /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 [2018-06-24 22:21:16,958 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-24 22:21:16,963 INFO ]: Walking toolchain with 5 elements. [2018-06-24 22:21:16,964 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-24 22:21:16,964 INFO ]: Initializing ChcToBoogie... [2018-06-24 22:21:16,964 INFO ]: ChcToBoogie initialized [2018-06-24 22:21:16,967 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 10:21:16" (1/1) ... [2018-06-24 22:21:17,060 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17 Unit [2018-06-24 22:21:17,060 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-24 22:21:17,061 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-24 22:21:17,061 INFO ]: Initializing Boogie Preprocessor... [2018-06-24 22:21:17,061 INFO ]: Boogie Preprocessor initialized [2018-06-24 22:21:17,099 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,099 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,121 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,122 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,137 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,139 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,141 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,145 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-24 22:21:17,146 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-24 22:21:17,146 INFO ]: Initializing RCFGBuilder... [2018-06-24 22:21:17,146 INFO ]: RCFGBuilder initialized [2018-06-24 22:21:17,146 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (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-24 22:21:17,162 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-24 22:21:17,162 INFO ]: Found specification of procedure gotoProc [2018-06-24 22:21:17,162 INFO ]: Found implementation of procedure gotoProc [2018-06-24 22:21:17,162 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-24 22:21:17,162 INFO ]: Found specification of procedure Ultimate.START [2018-06-24 22:21:17,162 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-24 22:21:17,549 INFO ]: Using library mode [2018-06-24 22:21:17,553 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 10:21:17 BoogieIcfgContainer [2018-06-24 22:21:17,553 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-24 22:21:17,553 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-24 22:21:17,553 INFO ]: Initializing BlockEncodingV2... [2018-06-24 22:21:17,554 INFO ]: BlockEncodingV2 initialized [2018-06-24 22:21:17,555 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 10:21:17" (1/1) ... [2018-06-24 22:21:17,572 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-24 22:21:17,574 INFO ]: Using Remove infeasible edges [2018-06-24 22:21:17,574 INFO ]: Using Maximize final states [2018-06-24 22:21:17,575 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-24 22:21:17,575 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-24 22:21:17,581 INFO ]: Using Remove sink states [2018-06-24 22:21:17,582 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-24 22:21:17,582 INFO ]: Using Use SBE [2018-06-24 22:21:18,224 INFO ]: SBE split 1 edges [2018-06-24 22:21:18,240 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-24 22:21:18,242 INFO ]: 0 new accepting states [2018-06-24 22:21:18,303 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-24 22:21:18,305 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 22:21:18,332 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-24 22:21:18,332 INFO ]: 0 new accepting states [2018-06-24 22:21:18,332 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 22:21:18,332 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 22:21:18,363 INFO ]: Encoded RCFG 6 locations, 217 edges [2018-06-24 22:21:18,363 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 10:21:18 BasicIcfg [2018-06-24 22:21:18,363 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-24 22:21:18,364 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-24 22:21:18,364 INFO ]: Initializing TraceAbstraction... [2018-06-24 22:21:18,373 INFO ]: TraceAbstraction initialized [2018-06-24 22:21:18,374 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 10:21:16" (1/4) ... [2018-06-24 22:21:18,374 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@663781ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 24.06 10:21:18, skipping insertion in model container [2018-06-24 22:21:18,374 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 10:21:17" (2/4) ... [2018-06-24 22:21:18,375 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@663781ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.06 10:21:18, skipping insertion in model container [2018-06-24 22:21:18,375 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 10:21:17" (3/4) ... [2018-06-24 22:21:18,375 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@663781ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 10:21:18, skipping insertion in model container [2018-06-24 22:21:18,375 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 10:21:18" (4/4) ... [2018-06-24 22:21:18,376 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-24 22:21:18,387 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-24 22:21:18,396 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-24 22:21:18,447 INFO ]: Using default assertion order modulation [2018-06-24 22:21:18,448 INFO ]: Interprodecural is true [2018-06-24 22:21:18,448 INFO ]: Hoare is false [2018-06-24 22:21:18,448 INFO ]: Compute interpolants for FPandBP [2018-06-24 22:21:18,448 INFO ]: Backedges is TWOTRACK [2018-06-24 22:21:18,448 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-24 22:21:18,448 INFO ]: Difference is false [2018-06-24 22:21:18,448 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-24 22:21:18,448 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-24 22:21:18,462 INFO ]: Start isEmpty. Operand 6 states. [2018-06-24 22:21:18,478 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-24 22:21:18,478 INFO ]: Found error trace [2018-06-24 22:21:18,480 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-24 22:21:18,480 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 22:21:18,486 INFO ]: Analyzing trace with hash 41921986, now seen corresponding path program 1 times [2018-06-24 22:21:18,488 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 22:21:18,488 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 22:21:18,537 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:18,537 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 22:21:18,537 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:18,625 INFO ]: Conjunction of SSA is unsat [2018-06-24 22:21:18,776 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 22:21:18,779 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 22:21:18,779 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 22:21:18,781 INFO ]: Interpolant automaton has 3 states [2018-06-24 22:21:18,796 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 22:21:18,796 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 22:21:18,799 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-24 22:21:21,514 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 22:21:21,514 INFO ]: Finished difference Result 7 states and 164 transitions. [2018-06-24 22:21:21,539 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 22:21:21,540 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-24 22:21:21,540 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 22:21:21,549 INFO ]: With dead ends: 7 [2018-06-24 22:21:21,549 INFO ]: Without dead ends: 7 [2018-06-24 22:21:21,551 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-24 22:21:21,569 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-24 22:21:21,587 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-24 22:21:21,588 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-24 22:21:21,589 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 164 transitions. [2018-06-24 22:21:21,589 INFO ]: Start accepts. Automaton has 7 states and 164 transitions. Word has length 5 [2018-06-24 22:21:21,590 INFO ]: Finished accepts. word is rejected. [2018-06-24 22:21:21,590 INFO ]: Abstraction has 7 states and 164 transitions. [2018-06-24 22:21:21,590 INFO ]: Interpolant automaton has 3 states. [2018-06-24 22:21:21,590 INFO ]: Start isEmpty. Operand 7 states and 164 transitions. [2018-06-24 22:21:21,591 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 22:21:21,591 INFO ]: Found error trace [2018-06-24 22:21:21,591 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 22:21:21,591 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 22:21:21,591 INFO ]: Analyzing trace with hash 1294722909, now seen corresponding path program 1 times [2018-06-24 22:21:21,591 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 22:21:21,591 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 22:21:21,593 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:21,593 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 22:21:21,593 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:21,636 INFO ]: Conjunction of SSA is unsat [2018-06-24 22:21:21,735 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 22:21:21,735 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 22:21:21,735 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 22:21:21,737 INFO ]: Interpolant automaton has 3 states [2018-06-24 22:21:21,737 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 22:21:21,737 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 22:21:21,737 INFO ]: Start difference. First operand 7 states and 164 transitions. Second operand 3 states. [2018-06-24 22:21:22,718 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 22:21:22,718 INFO ]: Finished difference Result 9 states and 269 transitions. [2018-06-24 22:21:22,719 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 22:21:22,719 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-24 22:21:22,720 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 22:21:22,721 INFO ]: With dead ends: 9 [2018-06-24 22:21:22,721 INFO ]: Without dead ends: 9 [2018-06-24 22:21:22,722 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-24 22:21:22,722 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-24 22:21:22,728 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-24 22:21:22,728 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 22:21:22,729 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 269 transitions. [2018-06-24 22:21:22,729 INFO ]: Start accepts. Automaton has 9 states and 269 transitions. Word has length 6 [2018-06-24 22:21:22,729 INFO ]: Finished accepts. word is rejected. [2018-06-24 22:21:22,729 INFO ]: Abstraction has 9 states and 269 transitions. [2018-06-24 22:21:22,729 INFO ]: Interpolant automaton has 3 states. [2018-06-24 22:21:22,730 INFO ]: Start isEmpty. Operand 9 states and 269 transitions. [2018-06-24 22:21:22,730 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-24 22:21:22,730 INFO ]: Found error trace [2018-06-24 22:21:22,730 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-24 22:21:22,730 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 22:21:22,730 INFO ]: Analyzing trace with hash 1479378093, now seen corresponding path program 1 times [2018-06-24 22:21:22,730 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 22:21:22,730 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 22:21:22,732 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:22,732 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 22:21:22,732 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:22,775 INFO ]: Conjunction of SSA is unsat [2018-06-24 22:21:22,843 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 22:21:22,843 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 22:21:22,843 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 22:21:22,843 INFO ]: Interpolant automaton has 3 states [2018-06-24 22:21:22,843 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 22:21:22,843 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 22:21:22,844 INFO ]: Start difference. First operand 9 states and 269 transitions. Second operand 3 states. [2018-06-24 22:21:23,567 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 22:21:23,568 INFO ]: Finished difference Result 11 states and 386 transitions. [2018-06-24 22:21:23,568 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 22:21:23,568 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-24 22:21:23,568 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 22:21:23,569 INFO ]: With dead ends: 11 [2018-06-24 22:21:23,569 INFO ]: Without dead ends: 11 [2018-06-24 22:21:23,569 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-24 22:21:23,570 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-24 22:21:23,576 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-24 22:21:23,576 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-24 22:21:23,578 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 386 transitions. [2018-06-24 22:21:23,578 INFO ]: Start accepts. Automaton has 11 states and 386 transitions. Word has length 7 [2018-06-24 22:21:23,578 INFO ]: Finished accepts. word is rejected. [2018-06-24 22:21:23,578 INFO ]: Abstraction has 11 states and 386 transitions. [2018-06-24 22:21:23,578 INFO ]: Interpolant automaton has 3 states. [2018-06-24 22:21:23,578 INFO ]: Start isEmpty. Operand 11 states and 386 transitions. [2018-06-24 22:21:23,579 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-24 22:21:23,579 INFO ]: Found error trace [2018-06-24 22:21:23,579 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 22:21:23,579 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 22:21:23,579 INFO ]: Analyzing trace with hash -1389969670, now seen corresponding path program 1 times [2018-06-24 22:21:23,579 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 22:21:23,579 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 22:21:23,580 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:23,581 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 22:21:23,581 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:23,658 INFO ]: Conjunction of SSA is unsat [2018-06-24 22:21:23,766 INFO ]: Checked inductivity of 6 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 22:21:23,766 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 22:21:23,766 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 22:21:23,766 INFO ]: Interpolant automaton has 3 states [2018-06-24 22:21:23,766 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 22:21:23,766 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 22:21:23,766 INFO ]: Start difference. First operand 11 states and 386 transitions. Second operand 3 states. [2018-06-24 22:21:24,348 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 22:21:24,348 INFO ]: Finished difference Result 13 states and 515 transitions. [2018-06-24 22:21:24,348 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 22:21:24,348 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-24 22:21:24,348 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 22:21:24,350 INFO ]: With dead ends: 13 [2018-06-24 22:21:24,350 INFO ]: Without dead ends: 13 [2018-06-24 22:21:24,350 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-24 22:21:24,350 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-24 22:21:24,356 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-24 22:21:24,356 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-24 22:21:24,357 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 515 transitions. [2018-06-24 22:21:24,357 INFO ]: Start accepts. Automaton has 13 states and 515 transitions. Word has length 8 [2018-06-24 22:21:24,358 INFO ]: Finished accepts. word is rejected. [2018-06-24 22:21:24,358 INFO ]: Abstraction has 13 states and 515 transitions. [2018-06-24 22:21:24,358 INFO ]: Interpolant automaton has 3 states. [2018-06-24 22:21:24,358 INFO ]: Start isEmpty. Operand 13 states and 515 transitions. [2018-06-24 22:21:24,358 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 22:21:24,358 INFO ]: Found error trace [2018-06-24 22:21:24,358 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 22:21:24,358 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 22:21:24,359 INFO ]: Analyzing trace with hash -139240579, now seen corresponding path program 1 times [2018-06-24 22:21:24,359 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 22:21:24,359 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 22:21:24,359 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:24,359 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 22:21:24,359 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 22:21:24,408 INFO ]: Conjunction of SSA is unsat [2018-06-24 22:21:24,574 INFO ]: Checked inductivity of 10 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 22:21:24,574 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 22:21:24,574 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-24 22:21:24,585 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 22:21:24,776 INFO ]: Conjunction of SSA is unsat [2018-06-24 22:21:24,788 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-24 22:22:27,275 INFO ]: Timeout while computing interpolants [2018-06-24 22:22:27,477 WARN ]: Destroyed unattended storables created during the last iteration: 3 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 22:22:27,477 WARN ]: Verification canceled [2018-06-24 22:22:27,479 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-24 22:22:27,480 WARN ]: Timeout [2018-06-24 22:22:27,480 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 10:22:27 BasicIcfg [2018-06-24 22:22:27,480 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-24 22:22:27,480 INFO ]: Toolchain (without parser) took 70521.84 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 253.9 MB in the beginning and 537.3 MB in the end (delta: -283.5 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-24 22:22:27,482 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 273.9 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 22:22:27,482 INFO ]: ChcToBoogie took 96.74 ms. Allocated memory is still 309.3 MB. Free memory was 253.9 MB in the beginning and 251.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 22:22:27,483 INFO ]: Boogie Preprocessor took 84.25 ms. Allocated memory is still 309.3 MB. Free memory is still 249.9 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 22:22:27,483 INFO ]: RCFGBuilder took 407.33 ms. Allocated memory is still 309.3 MB. Free memory was 249.9 MB in the beginning and 221.9 MB in the end (delta: 28.0 MB). Peak memory consumption was 28.0 MB. Max. memory is 3.6 GB. [2018-06-24 22:22:27,484 INFO ]: BlockEncodingV2 took 810.01 ms. Allocated memory was 309.3 MB in the beginning and 332.4 MB in the end (delta: 23.1 MB). Free memory was 221.9 MB in the beginning and 261.4 MB in the end (delta: -39.6 MB). Peak memory consumption was 41.1 MB. Max. memory is 3.6 GB. [2018-06-24 22:22:27,484 INFO ]: TraceAbstraction took 69115.51 ms. Allocated memory was 332.4 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 261.4 MB in the beginning and 537.3 MB in the end (delta: -275.9 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-24 22:22:27,487 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 10 locations, 10 edges - StatisticsResult: Encoded RCFG 6 locations, 217 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 273.9 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 96.74 ms. Allocated memory is still 309.3 MB. Free memory was 253.9 MB in the beginning and 251.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 84.25 ms. Allocated memory is still 309.3 MB. Free memory is still 249.9 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 407.33 ms. Allocated memory is still 309.3 MB. Free memory was 249.9 MB in the beginning and 221.9 MB in the end (delta: 28.0 MB). Peak memory consumption was 28.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 810.01 ms. Allocated memory was 309.3 MB in the beginning and 332.4 MB in the end (delta: 23.1 MB). Free memory was 221.9 MB in the beginning and 261.4 MB in the end (delta: -39.6 MB). Peak memory consumption was 41.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 69115.51 ms. Allocated memory was 332.4 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 261.4 MB in the beginning and 537.3 MB in the end (delta: -275.9 MB). Peak memory consumption was 1.4 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 Cancelled while BasicCegarLoop was analyzing trace of length 10 with TraceHistMax 1, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 5 quantified variables from 11 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 69.0s OverallTime, 5 OverallIterations, 1 TraceHistogramMax, 5.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 20 SDtfs, 0 SDslu, 12 SDs, 0 SdLazy, 823 SolverSat, 743 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 4.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred 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.2s SatisfiabilityAnalysisTime, 0.4s InterpolantComputationTime, 26 NumberOfCodeBlocks, 26 NumberOfCodeBlocksAsserted, 4 NumberOfCheckSat, 22 ConstructedInterpolants, 0 QuantifiedInterpolants, 166 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 4 InterpolantComputations, 4 PerfectInterpolantSequences, 10/10 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/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-24_22-22-27-499.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-24_22-22-27-499.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-24_22-22-27-499.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-24_22-22-27-499.csv Completed graceful shutdown