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/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 01:07:10,493 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 01:07:10,495 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 01:07:10,508 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 01:07:10,508 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 01:07:10,511 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 01:07:10,513 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 01:07:10,515 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 01:07:10,518 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 01:07:10,519 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 01:07:10,520 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 01:07:10,520 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 01:07:10,521 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 01:07:10,522 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 01:07:10,523 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 01:07:10,523 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 01:07:10,525 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 01:07:10,528 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 01:07:10,530 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 01:07:10,531 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 01:07:10,532 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 01:07:10,534 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 01:07:10,535 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 01:07:10,535 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 01:07:10,536 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 01:07:10,537 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 01:07:10,537 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 01:07:10,538 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 01:07:10,539 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 01:07:10,539 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 01:07:10,540 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 01:07:10,541 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 01:07:10,541 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 01:07:10,542 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 01:07:10,542 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 01:07:10,543 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 01:07:10,557 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 01:07:10,558 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 01:07:10,558 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 01:07:10,558 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 01:07:10,559 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 01:07:10,560 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 01:07:10,560 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 01:07:10,560 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 01:07:10,560 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 01:07:10,561 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 01:07:10,561 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 01:07:10,561 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 01:07:10,561 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 01:07:10,562 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 01:07:10,562 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 01:07:10,562 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 01:07:10,562 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 01:07:10,562 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 01:07:10,562 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 01:07:10,563 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 01:07:10,563 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 01:07:10,564 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 01:07:10,565 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 01:07:10,609 INFO ]: Repository-Root is: /tmp [2018-06-25 01:07:10,629 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 01:07:10,633 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 01:07:10,634 INFO ]: Initializing SmtParser... [2018-06-25 01:07:10,634 INFO ]: SmtParser initialized [2018-06-25 01:07:10,635 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-25 01:07:10,636 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-25 01:07:10,707 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 unknown [2018-06-25 01:07:11,183 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-25 01:07:11,188 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 01:07:11,193 INFO ]: Walking toolchain with 5 elements. [2018-06-25 01:07:11,193 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 01:07:11,194 INFO ]: Initializing ChcToBoogie... [2018-06-25 01:07:11,194 INFO ]: ChcToBoogie initialized [2018-06-25 01:07:11,197 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,266 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11 Unit [2018-06-25 01:07:11,266 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 01:07:11,267 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 01:07:11,267 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 01:07:11,267 INFO ]: Boogie Preprocessor initialized [2018-06-25 01:07:11,289 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,289 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,309 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,309 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,318 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,320 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,322 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,325 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 01:07:11,326 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 01:07:11,326 INFO ]: Initializing RCFGBuilder... [2018-06-25 01:07:11,326 INFO ]: RCFGBuilder initialized [2018-06-25 01:07:11,327 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-25 01:07:11,344 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 01:07:11,344 INFO ]: Found specification of procedure gotoProc [2018-06-25 01:07:11,344 INFO ]: Found implementation of procedure gotoProc [2018-06-25 01:07:11,344 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 01:07:11,344 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 01:07:11,344 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 01:07:11,611 INFO ]: Using library mode [2018-06-25 01:07:11,612 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:07:11 BoogieIcfgContainer [2018-06-25 01:07:11,612 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 01:07:11,613 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-25 01:07:11,613 INFO ]: Initializing BlockEncodingV2... [2018-06-25 01:07:11,614 INFO ]: BlockEncodingV2 initialized [2018-06-25 01:07:11,614 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:07:11" (1/1) ... [2018-06-25 01:07:11,629 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-25 01:07:11,631 INFO ]: Using Remove infeasible edges [2018-06-25 01:07:11,631 INFO ]: Using Maximize final states [2018-06-25 01:07:11,631 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-25 01:07:11,632 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-25 01:07:11,633 INFO ]: Using Remove sink states [2018-06-25 01:07:11,634 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-25 01:07:11,634 INFO ]: Using Use SBE [2018-06-25 01:07:11,639 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:07:11,685 WARN ]: aborting because of expected exponential blowup for input size 57 [2018-06-25 01:07:11,686 INFO ]: SBE split 0 edges [2018-06-25 01:07:11,691 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-25 01:07:11,693 INFO ]: 0 new accepting states [2018-06-25 01:07:11,749 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-25 01:07:11,751 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-25 01:07:11,758 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-25 01:07:11,758 INFO ]: 0 new accepting states [2018-06-25 01:07:11,759 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-25 01:07:11,759 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-25 01:07:11,759 INFO ]: Encoded RCFG 6 locations, 6 edges [2018-06-25 01:07:11,759 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 25.06 01:07:11 BasicIcfg [2018-06-25 01:07:11,759 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-25 01:07:11,761 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 01:07:11,761 INFO ]: Initializing TraceAbstraction... [2018-06-25 01:07:11,764 INFO ]: TraceAbstraction initialized [2018-06-25 01:07:11,764 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:07:11" (1/4) ... [2018-06-25 01:07:11,765 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4eca7c20 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:07:11, skipping insertion in model container [2018-06-25 01:07:11,765 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:07:11" (2/4) ... [2018-06-25 01:07:11,766 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4eca7c20 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:07:11, skipping insertion in model container [2018-06-25 01:07:11,770 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:07:11" (3/4) ... [2018-06-25 01:07:11,770 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4eca7c20 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:07:11, skipping insertion in model container [2018-06-25 01:07:11,770 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 25.06 01:07:11" (4/4) ... [2018-06-25 01:07:11,772 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-25 01:07:11,782 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 01:07:11,793 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 01:07:11,847 INFO ]: Using default assertion order modulation [2018-06-25 01:07:11,847 INFO ]: Interprodecural is true [2018-06-25 01:07:11,847 INFO ]: Hoare is false [2018-06-25 01:07:11,847 INFO ]: Compute interpolants for FPandBP [2018-06-25 01:07:11,847 INFO ]: Backedges is TWOTRACK [2018-06-25 01:07:11,847 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 01:07:11,847 INFO ]: Difference is false [2018-06-25 01:07:11,847 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 01:07:11,847 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 01:07:11,857 INFO ]: Start isEmpty. Operand 6 states. [2018-06-25 01:07:11,867 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-25 01:07:11,867 INFO ]: Found error trace [2018-06-25 01:07:11,868 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-25 01:07:11,868 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:07:11,873 INFO ]: Analyzing trace with hash 35402562, now seen corresponding path program 1 times [2018-06-25 01:07:11,875 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:07:11,876 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:07:11,915 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:11,915 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:07:11,915 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:11,966 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:12,059 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:12,064 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 01:07:12,064 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 01:07:12,066 INFO ]: Interpolant automaton has 3 states [2018-06-25 01:07:12,077 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 01:07:12,077 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 01:07:12,080 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-25 01:07:12,178 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:07:12,178 INFO ]: Finished difference Result 7 states and 7 transitions. [2018-06-25 01:07:12,181 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 01:07:12,183 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-25 01:07:12,183 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:07:12,193 INFO ]: With dead ends: 7 [2018-06-25 01:07:12,195 INFO ]: Without dead ends: 7 [2018-06-25 01:07:12,197 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 01:07:12,215 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-25 01:07:12,237 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-25 01:07:12,238 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-25 01:07:12,238 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-06-25 01:07:12,239 INFO ]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-06-25 01:07:12,240 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:07:12,240 INFO ]: Abstraction has 7 states and 7 transitions. [2018-06-25 01:07:12,240 INFO ]: Interpolant automaton has 3 states. [2018-06-25 01:07:12,240 INFO ]: Start isEmpty. Operand 7 states and 7 transitions. [2018-06-25 01:07:12,241 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-25 01:07:12,241 INFO ]: Found error trace [2018-06-25 01:07:12,241 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-25 01:07:12,241 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:07:12,241 INFO ]: Analyzing trace with hash 1097213384, now seen corresponding path program 1 times [2018-06-25 01:07:12,241 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:07:12,241 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:07:12,242 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:12,242 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:07:12,242 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:12,370 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:12,577 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:12,577 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:07:12,577 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 01:07:12,595 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:07:12,708 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:12,720 INFO ]: Computing forward predicates... [2018-06-25 01:07:13,103 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:13,136 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:07:13,136 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 01:07:13,136 INFO ]: Interpolant automaton has 5 states [2018-06-25 01:07:13,136 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 01:07:13,136 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 01:07:13,137 INFO ]: Start difference. First operand 7 states and 7 transitions. Second operand 5 states. [2018-06-25 01:07:13,355 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:07:13,355 INFO ]: Finished difference Result 8 states and 8 transitions. [2018-06-25 01:07:13,356 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 01:07:13,356 INFO ]: Start accepts. Automaton has 5 states. Word has length 6 [2018-06-25 01:07:13,356 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:07:13,357 INFO ]: With dead ends: 8 [2018-06-25 01:07:13,357 INFO ]: Without dead ends: 8 [2018-06-25 01:07:13,358 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 01:07:13,358 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-25 01:07:13,358 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-25 01:07:13,359 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-25 01:07:13,359 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-06-25 01:07:13,359 INFO ]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-06-25 01:07:13,359 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:07:13,359 INFO ]: Abstraction has 8 states and 8 transitions. [2018-06-25 01:07:13,359 INFO ]: Interpolant automaton has 5 states. [2018-06-25 01:07:13,359 INFO ]: Start isEmpty. Operand 8 states and 8 transitions. [2018-06-25 01:07:13,359 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 01:07:13,359 INFO ]: Found error trace [2018-06-25 01:07:13,359 INFO ]: trace histogram [2, 1, 1, 1, 1, 1] [2018-06-25 01:07:13,359 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:07:13,359 INFO ]: Analyzing trace with hash -346389502, now seen corresponding path program 2 times [2018-06-25 01:07:13,360 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:07:13,360 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:07:13,360 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:13,360 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:07:13,360 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:13,453 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:13,814 WARN ]: Spent 147.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 01:07:13,908 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:13,909 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:07:13,909 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:07:13,915 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 01:07:14,014 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 01:07:14,014 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:14,018 INFO ]: Computing forward predicates... [2018-06-25 01:07:15,117 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:15,137 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:07:15,137 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 01:07:15,138 INFO ]: Interpolant automaton has 6 states [2018-06-25 01:07:15,138 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 01:07:15,138 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 01:07:15,138 INFO ]: Start difference. First operand 8 states and 8 transitions. Second operand 6 states. [2018-06-25 01:07:15,330 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:07:15,330 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 01:07:15,330 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 01:07:15,330 INFO ]: Start accepts. Automaton has 6 states. Word has length 7 [2018-06-25 01:07:15,330 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:07:15,331 INFO ]: With dead ends: 9 [2018-06-25 01:07:15,331 INFO ]: Without dead ends: 9 [2018-06-25 01:07:15,331 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-25 01:07:15,331 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 01:07:15,332 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 01:07:15,332 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 01:07:15,332 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 01:07:15,332 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 01:07:15,333 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:07:15,333 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 01:07:15,333 INFO ]: Interpolant automaton has 6 states. [2018-06-25 01:07:15,333 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 01:07:15,333 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 01:07:15,333 INFO ]: Found error trace [2018-06-25 01:07:15,333 INFO ]: trace histogram [3, 1, 1, 1, 1, 1] [2018-06-25 01:07:15,333 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:07:15,333 INFO ]: Analyzing trace with hash 2146561288, now seen corresponding path program 3 times [2018-06-25 01:07:15,333 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:07:15,333 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:07:15,334 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:15,334 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:07:15,334 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:15,395 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:15,707 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:15,708 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:07:15,708 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:07:15,722 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 01:07:15,804 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 01:07:15,804 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:15,808 INFO ]: Computing forward predicates... [2018-06-25 01:07:16,194 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:07:24,598 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:24,619 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:07:24,619 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 01:07:24,619 INFO ]: Interpolant automaton has 7 states [2018-06-25 01:07:24,619 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 01:07:24,620 INFO ]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-25 01:07:24,620 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 7 states. [2018-06-25 01:07:24,744 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:07:24,744 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 01:07:24,744 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 01:07:24,744 INFO ]: Start accepts. Automaton has 7 states. Word has length 8 [2018-06-25 01:07:24,744 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:07:24,744 INFO ]: With dead ends: 10 [2018-06-25 01:07:24,744 INFO ]: Without dead ends: 10 [2018-06-25 01:07:24,745 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 5 SyntacticMatches, 3 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=36, Invalid=54, Unknown=0, NotChecked=0, Total=90 [2018-06-25 01:07:24,745 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 01:07:24,746 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 01:07:24,746 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 01:07:24,746 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 01:07:24,747 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 01:07:24,747 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:07:24,747 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 01:07:24,747 INFO ]: Interpolant automaton has 7 states. [2018-06-25 01:07:24,747 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 01:07:24,747 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 01:07:24,747 INFO ]: Found error trace [2018-06-25 01:07:24,747 INFO ]: trace histogram [4, 1, 1, 1, 1, 1] [2018-06-25 01:07:24,747 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:07:24,747 INFO ]: Analyzing trace with hash 2118624450, now seen corresponding path program 4 times [2018-06-25 01:07:24,747 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:07:24,747 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:07:24,748 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:24,748 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:07:24,748 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:24,836 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:25,014 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:25,014 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:07:25,014 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:07:25,036 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 01:07:25,135 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 01:07:25,135 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:25,140 INFO ]: Computing forward predicates... [2018-06-25 01:07:26,153 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 01:07:31,503 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:07:31,554 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:31,574 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:07:31,574 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-25 01:07:31,574 INFO ]: Interpolant automaton has 8 states [2018-06-25 01:07:31,575 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 01:07:31,575 INFO ]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-25 01:07:31,575 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-25 01:07:31,802 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:07:31,802 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 01:07:31,802 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 01:07:31,802 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-25 01:07:31,802 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:07:31,803 INFO ]: With dead ends: 11 [2018-06-25 01:07:31,803 INFO ]: Without dead ends: 11 [2018-06-25 01:07:31,803 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 6 SyntacticMatches, 3 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=54, Invalid=78, Unknown=0, NotChecked=0, Total=132 [2018-06-25 01:07:31,803 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 01:07:31,804 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 01:07:31,804 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 01:07:31,804 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 01:07:31,805 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 01:07:31,805 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:07:31,805 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 01:07:31,805 INFO ]: Interpolant automaton has 8 states. [2018-06-25 01:07:31,805 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 01:07:31,805 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 01:07:31,805 INFO ]: Found error trace [2018-06-25 01:07:31,805 INFO ]: trace histogram [5, 1, 1, 1, 1, 1] [2018-06-25 01:07:31,805 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:07:31,805 INFO ]: Analyzing trace with hash 1252582472, now seen corresponding path program 5 times [2018-06-25 01:07:31,805 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:07:31,805 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:07:31,806 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:31,806 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:07:31,806 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:07:31,913 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:33,097 WARN ]: Spent 854.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 23 [2018-06-25 01:07:33,443 WARN ]: Spent 163.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 01:07:33,444 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:07:33,444 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:07:33,444 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 01:07:33,458 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:07:33,596 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 01:07:33,596 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:07:33,601 INFO ]: Computing forward predicates... [2018-06-25 01:07:34,518 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 16 [2018-06-25 01:07:38,741 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 01:08:18,944 INFO ]: Timeout while computing interpolants [2018-06-25 01:08:19,144 WARN ]: Destroyed unattended storables created during the last iteration: 7 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:08:19,145 WARN ]: Verification canceled [2018-06-25 01:08:19,147 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-25 01:08:19,147 WARN ]: Timeout [2018-06-25 01:08:19,148 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:08:19 BasicIcfg [2018-06-25 01:08:19,148 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 01:08:19,149 INFO ]: Toolchain (without parser) took 67959.83 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 247.8 MB in the beginning and 925.8 MB in the end (delta: -678.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 01:08:19,150 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 271.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 01:08:19,150 INFO ]: ChcToBoogie took 73.23 ms. Allocated memory is still 309.3 MB. Free memory was 247.8 MB in the beginning and 245.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:08:19,150 INFO ]: Boogie Preprocessor took 58.37 ms. Allocated memory is still 309.3 MB. Free memory was 245.8 MB in the beginning and 243.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:08:19,151 INFO ]: RCFGBuilder took 286.13 ms. Allocated memory is still 309.3 MB. Free memory was 243.8 MB in the beginning and 227.8 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:08:19,151 INFO ]: BlockEncodingV2 took 146.93 ms. Allocated memory is still 309.3 MB. Free memory was 225.8 MB in the beginning and 221.8 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:08:19,163 INFO ]: TraceAbstraction took 67386.69 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 221.8 MB in the beginning and 925.8 MB in the end (delta: -703.9 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 01:08:19,167 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, 6 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 271.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 73.23 ms. Allocated memory is still 309.3 MB. Free memory was 247.8 MB in the beginning and 245.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 58.37 ms. Allocated memory is still 309.3 MB. Free memory was 245.8 MB in the beginning and 243.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 286.13 ms. Allocated memory is still 309.3 MB. Free memory was 243.8 MB in the beginning and 227.8 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 146.93 ms. Allocated memory is still 309.3 MB. Free memory was 225.8 MB in the beginning and 221.8 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 67386.69 ms. Allocated memory was 309.3 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 221.8 MB in the beginning and 925.8 MB in the end (delta: -703.9 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 Cancelled while BasicCegarLoop was analyzing trace of length 11 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 5828 quantified variables from 14 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 67.3s OverallTime, 6 OverallIterations, 5 TraceHistogramMax, 0.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 25 SDtfs, 0 SDslu, 51 SDs, 0 SdLazy, 34 SolverSat, 16 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 61 GetRequests, 24 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 1.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=11occurred in iteration=5, 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, 5 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 17.9s InterpolantComputationTime, 65 NumberOfCodeBlocks, 65 NumberOfCodeBlocksAsserted, 12 NumberOfCheckSat, 56 ConstructedInterpolants, 0 QuantifiedInterpolants, 1792 SizeOfPredicates, 24 NumberOfNonLiveVariables, 1102 ConjunctsInSsa, 115 ConjunctsInUnsatCore, 9 InterpolantComputations, 1 PerfectInterpolantSequences, 0/40 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-25_01-08-19-183.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-25_01-08-19-183.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-25_01-08-19-183.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_01-08-19-183.csv Completed graceful shutdown