java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-EXP.epf -i ../../../trunk/examples/svcomp/loops/linear_sea.ch_true-unreach-call.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-1dbac8b [2018-10-27 09:03:01,006 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-27 09:03:01,008 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-27 09:03:01,022 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-27 09:03:01,023 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-27 09:03:01,024 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-27 09:03:01,025 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-27 09:03:01,027 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-27 09:03:01,029 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-27 09:03:01,029 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-27 09:03:01,031 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-27 09:03:01,031 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-27 09:03:01,032 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-27 09:03:01,033 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-27 09:03:01,034 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-27 09:03:01,035 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-27 09:03:01,036 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-27 09:03:01,037 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-27 09:03:01,039 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-27 09:03:01,041 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-27 09:03:01,042 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-27 09:03:01,043 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-27 09:03:01,046 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-27 09:03:01,046 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-27 09:03:01,046 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-27 09:03:01,047 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-27 09:03:01,048 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-27 09:03:01,049 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-27 09:03:01,050 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-27 09:03:01,051 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-27 09:03:01,051 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-27 09:03:01,052 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-27 09:03:01,052 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-27 09:03:01,052 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-27 09:03:01,053 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-27 09:03:01,054 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-27 09:03:01,054 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-EXP.epf [2018-10-27 09:03:01,081 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-27 09:03:01,081 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-27 09:03:01,083 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-27 09:03:01,083 INFO L133 SettingsManager]: * User list type=DISABLED [2018-10-27 09:03:01,083 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-10-27 09:03:01,084 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-27 09:03:01,084 INFO L133 SettingsManager]: * Explicit value domain=true [2018-10-27 09:03:01,084 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-10-27 09:03:01,084 INFO L133 SettingsManager]: * Octagon Domain=false [2018-10-27 09:03:01,084 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-10-27 09:03:01,084 INFO L133 SettingsManager]: * Log string format=TERM [2018-10-27 09:03:01,085 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-10-27 09:03:01,085 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-27 09:03:01,086 INFO L133 SettingsManager]: * Interval Domain=false [2018-10-27 09:03:01,086 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-27 09:03:01,086 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-27 09:03:01,087 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-27 09:03:01,087 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-27 09:03:01,087 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-27 09:03:01,087 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-27 09:03:01,087 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-27 09:03:01,088 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-27 09:03:01,090 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-27 09:03:01,090 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-27 09:03:01,090 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-27 09:03:01,090 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-27 09:03:01,090 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-27 09:03:01,091 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-27 09:03:01,091 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-27 09:03:01,091 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-27 09:03:01,091 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-10-27 09:03:01,091 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-27 09:03:01,092 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-27 09:03:01,092 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-27 09:03:01,092 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-10-27 09:03:01,092 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-27 09:03:01,155 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-27 09:03:01,172 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-27 09:03:01,175 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-27 09:03:01,177 INFO L271 PluginConnector]: Initializing CDTParser... [2018-10-27 09:03:01,177 INFO L276 PluginConnector]: CDTParser initialized [2018-10-27 09:03:01,178 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/svcomp/loops/linear_sea.ch_true-unreach-call.i [2018-10-27 09:03:01,244 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/d7ce71a08/4b6bacc8f1b2465595126eddaf859c92/FLAG6de6f3838 [2018-10-27 09:03:01,663 INFO L298 CDTParser]: Found 1 translation units. [2018-10-27 09:03:01,663 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loops/linear_sea.ch_true-unreach-call.i [2018-10-27 09:03:01,669 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/d7ce71a08/4b6bacc8f1b2465595126eddaf859c92/FLAG6de6f3838 [2018-10-27 09:03:01,683 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/d7ce71a08/4b6bacc8f1b2465595126eddaf859c92 [2018-10-27 09:03:01,695 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-27 09:03:01,696 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-10-27 09:03:01,697 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-10-27 09:03:01,697 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-10-27 09:03:01,700 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-10-27 09:03:01,701 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.10 09:03:01" (1/1) ... [2018-10-27 09:03:01,704 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2aa2d024 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:01, skipping insertion in model container [2018-10-27 09:03:01,704 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.10 09:03:01" (1/1) ... [2018-10-27 09:03:01,715 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-10-27 09:03:01,745 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-10-27 09:03:01,980 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-27 09:03:01,990 INFO L189 MainTranslator]: Completed pre-run [2018-10-27 09:03:02,011 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-27 09:03:02,028 INFO L193 MainTranslator]: Completed translation [2018-10-27 09:03:02,029 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02 WrapperNode [2018-10-27 09:03:02,029 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-10-27 09:03:02,030 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-27 09:03:02,030 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-27 09:03:02,030 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-27 09:03:02,040 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,050 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,073 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-27 09:03:02,073 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-27 09:03:02,073 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-27 09:03:02,074 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-27 09:03:02,084 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,084 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,086 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,086 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,091 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,096 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,098 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... [2018-10-27 09:03:02,100 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-27 09:03:02,101 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-27 09:03:02,101 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-27 09:03:02,101 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-27 09:03:02,103 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-27 09:03:02,225 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-10-27 09:03:02,225 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-10-27 09:03:02,225 INFO L130 BoogieDeclarations]: Found specification of procedure linear_search [2018-10-27 09:03:02,225 INFO L138 BoogieDeclarations]: Found implementation of procedure linear_search [2018-10-27 09:03:02,226 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-27 09:03:02,226 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-27 09:03:02,226 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-10-27 09:03:02,226 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-10-27 09:03:02,226 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-10-27 09:03:02,227 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-10-27 09:03:02,617 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-27 09:03:02,617 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.10 09:03:02 BoogieIcfgContainer [2018-10-27 09:03:02,618 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-27 09:03:02,626 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-27 09:03:02,626 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-27 09:03:02,631 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-27 09:03:02,631 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.10 09:03:01" (1/3) ... [2018-10-27 09:03:02,632 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1b98f456 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.10 09:03:02, skipping insertion in model container [2018-10-27 09:03:02,632 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.10 09:03:02" (2/3) ... [2018-10-27 09:03:02,632 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1b98f456 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.10 09:03:02, skipping insertion in model container [2018-10-27 09:03:02,633 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.10 09:03:02" (3/3) ... [2018-10-27 09:03:02,635 INFO L112 eAbstractionObserver]: Analyzing ICFG linear_sea.ch_true-unreach-call.i [2018-10-27 09:03:02,646 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-27 09:03:02,655 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-27 09:03:02,670 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-27 09:03:02,704 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-27 09:03:02,704 INFO L383 AbstractCegarLoop]: Hoare is true [2018-10-27 09:03:02,704 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-27 09:03:02,704 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-27 09:03:02,704 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-27 09:03:02,705 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-27 09:03:02,705 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-27 09:03:02,705 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-27 09:03:02,724 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states. [2018-10-27 09:03:02,730 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-27 09:03:02,730 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:02,731 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:02,734 INFO L424 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:02,740 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:02,740 INFO L82 PathProgramCache]: Analyzing trace with hash 1679407704, now seen corresponding path program 1 times [2018-10-27 09:03:02,743 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:02,789 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:02,789 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:02,789 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:02,789 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:02,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:02,933 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:02,935 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-27 09:03:02,936 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-27 09:03:02,936 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 09:03:02,941 INFO L460 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-10-27 09:03:02,956 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-10-27 09:03:02,957 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-27 09:03:02,960 INFO L87 Difference]: Start difference. First operand 28 states. Second operand 2 states. [2018-10-27 09:03:02,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:02,984 INFO L93 Difference]: Finished difference Result 44 states and 50 transitions. [2018-10-27 09:03:02,984 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-10-27 09:03:02,985 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 17 [2018-10-27 09:03:02,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:02,994 INFO L225 Difference]: With dead ends: 44 [2018-10-27 09:03:02,995 INFO L226 Difference]: Without dead ends: 21 [2018-10-27 09:03:02,998 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-27 09:03:03,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-10-27 09:03:03,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-10-27 09:03:03,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-10-27 09:03:03,039 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 23 transitions. [2018-10-27 09:03:03,041 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 23 transitions. Word has length 17 [2018-10-27 09:03:03,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:03,041 INFO L481 AbstractCegarLoop]: Abstraction has 21 states and 23 transitions. [2018-10-27 09:03:03,042 INFO L482 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-10-27 09:03:03,042 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 23 transitions. [2018-10-27 09:03:03,043 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-27 09:03:03,043 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:03,043 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:03,044 INFO L424 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:03,044 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:03,044 INFO L82 PathProgramCache]: Analyzing trace with hash -1597240285, now seen corresponding path program 1 times [2018-10-27 09:03:03,044 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:03,046 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:03,046 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:03,046 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:03,047 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:03,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:03,459 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:03,460 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-27 09:03:03,460 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-27 09:03:03,460 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 09:03:03,462 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-27 09:03:03,462 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-27 09:03:03,462 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-27 09:03:03,463 INFO L87 Difference]: Start difference. First operand 21 states and 23 transitions. Second operand 6 states. [2018-10-27 09:03:03,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:03,560 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2018-10-27 09:03:03,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-27 09:03:03,560 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-27 09:03:03,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:03,561 INFO L225 Difference]: With dead ends: 29 [2018-10-27 09:03:03,562 INFO L226 Difference]: Without dead ends: 21 [2018-10-27 09:03:03,563 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-10-27 09:03:03,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-10-27 09:03:03,566 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-10-27 09:03:03,567 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-10-27 09:03:03,568 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-10-27 09:03:03,569 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 20 [2018-10-27 09:03:03,569 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:03,570 INFO L481 AbstractCegarLoop]: Abstraction has 21 states and 22 transitions. [2018-10-27 09:03:03,570 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-27 09:03:03,570 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 22 transitions. [2018-10-27 09:03:03,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-27 09:03:03,571 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:03,571 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:03,571 INFO L424 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:03,571 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:03,572 INFO L82 PathProgramCache]: Analyzing trace with hash 145570050, now seen corresponding path program 1 times [2018-10-27 09:03:03,572 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:03,573 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:03,573 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:03,574 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:03,574 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:03,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:03,909 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:03,910 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-27 09:03:03,910 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-10-27 09:03:03,910 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 09:03:03,910 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-27 09:03:03,911 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-27 09:03:03,911 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-27 09:03:03,911 INFO L87 Difference]: Start difference. First operand 21 states and 22 transitions. Second operand 5 states. [2018-10-27 09:03:04,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:04,158 INFO L93 Difference]: Finished difference Result 34 states and 36 transitions. [2018-10-27 09:03:04,158 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-27 09:03:04,159 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-10-27 09:03:04,159 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:04,160 INFO L225 Difference]: With dead ends: 34 [2018-10-27 09:03:04,160 INFO L226 Difference]: Without dead ends: 25 [2018-10-27 09:03:04,160 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-10-27 09:03:04,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-10-27 09:03:04,166 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-10-27 09:03:04,166 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-10-27 09:03:04,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2018-10-27 09:03:04,167 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 20 [2018-10-27 09:03:04,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:04,168 INFO L481 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2018-10-27 09:03:04,168 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-27 09:03:04,168 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2018-10-27 09:03:04,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-10-27 09:03:04,169 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:04,169 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:04,169 INFO L424 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:04,170 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:04,170 INFO L82 PathProgramCache]: Analyzing trace with hash -1819847252, now seen corresponding path program 1 times [2018-10-27 09:03:04,170 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:04,171 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:04,171 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:04,171 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:04,171 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:04,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:04,653 WARN L179 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 16 [2018-10-27 09:03:04,812 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:04,813 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:04,813 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:03:04,816 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 25 with the following transitions: [2018-10-27 09:03:04,818 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [17], [19], [26], [27], [31], [33], [37], [40], [42], [48], [49], [50], [52], [53], [54] [2018-10-27 09:03:04,873 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, ExplicitValueDomain] [2018-10-27 09:03:04,874 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-27 09:03:05,271 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-27 09:03:05,274 INFO L272 AbstractInterpreter]: Visited 21 different actions 37 times. Merged at 7 different actions 14 times. Never widened. Found 3 fixpoints after 2 different actions. Largest state had 29 variables. [2018-10-27 09:03:05,318 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:05,320 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-27 09:03:05,320 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:05,320 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 09:03:05,335 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:05,335 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 09:03:05,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:05,395 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:03:05,692 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:05,692 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:03:05,915 WARN L179 SmtUtils]: Spent 218.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 20 [2018-10-27 09:03:06,380 WARN L179 SmtUtils]: Spent 163.00 ms on a formula simplification that was a NOOP. DAG size: 27 [2018-10-27 09:03:06,849 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:06,881 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 09:03:06,881 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 15 [2018-10-27 09:03:06,881 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 09:03:06,882 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-27 09:03:06,882 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-27 09:03:06,883 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2018-10-27 09:03:06,883 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand 10 states. [2018-10-27 09:03:07,387 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:07,387 INFO L93 Difference]: Finished difference Result 43 states and 47 transitions. [2018-10-27 09:03:07,388 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-27 09:03:07,388 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 24 [2018-10-27 09:03:07,388 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:07,391 INFO L225 Difference]: With dead ends: 43 [2018-10-27 09:03:07,391 INFO L226 Difference]: Without dead ends: 34 [2018-10-27 09:03:07,393 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 38 SyntacticMatches, 5 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=97, Invalid=283, Unknown=0, NotChecked=0, Total=380 [2018-10-27 09:03:07,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-27 09:03:07,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 29. [2018-10-27 09:03:07,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-10-27 09:03:07,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 32 transitions. [2018-10-27 09:03:07,401 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 32 transitions. Word has length 24 [2018-10-27 09:03:07,401 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:07,402 INFO L481 AbstractCegarLoop]: Abstraction has 29 states and 32 transitions. [2018-10-27 09:03:07,402 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-27 09:03:07,402 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 32 transitions. [2018-10-27 09:03:07,403 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-10-27 09:03:07,403 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:07,403 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:07,404 INFO L424 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:07,404 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:07,404 INFO L82 PathProgramCache]: Analyzing trace with hash 2082093034, now seen corresponding path program 1 times [2018-10-27 09:03:07,404 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:07,405 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:07,405 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:07,406 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:07,406 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:07,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:08,104 WARN L179 SmtUtils]: Spent 555.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 27 [2018-10-27 09:03:08,488 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:08,488 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:08,488 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:03:08,489 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 25 with the following transitions: [2018-10-27 09:03:08,489 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [13], [17], [19], [26], [27], [31], [33], [37], [40], [42], [48], [49], [50], [52], [53], [54] [2018-10-27 09:03:08,491 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, ExplicitValueDomain] [2018-10-27 09:03:08,491 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-27 09:03:08,614 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-27 09:03:08,615 INFO L272 AbstractInterpreter]: Visited 22 different actions 49 times. Merged at 8 different actions 21 times. Never widened. Found 8 fixpoints after 4 different actions. Largest state had 29 variables. [2018-10-27 09:03:08,658 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:08,658 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-27 09:03:08,658 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:08,658 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-27 09:03:08,669 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:08,669 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 09:03:08,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:08,708 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:03:08,737 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 24 [2018-10-27 09:03:08,740 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:03:08,740 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-27 09:03:08,748 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:08,753 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 25 [2018-10-27 09:03:08,759 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:03:08,760 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-27 09:03:08,772 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:10,798 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:10,799 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:91, output treesize:17 [2018-10-27 09:03:11,354 WARN L179 SmtUtils]: Spent 234.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2018-10-27 09:03:11,878 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:11,878 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:03:12,020 WARN L179 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 49 [2018-10-27 09:03:12,573 WARN L179 SmtUtils]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-27 09:03:13,141 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:13,162 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 09:03:13,162 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 10] total 24 [2018-10-27 09:03:13,163 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 09:03:13,164 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-10-27 09:03:13,164 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-10-27 09:03:13,165 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=458, Unknown=0, NotChecked=0, Total=552 [2018-10-27 09:03:13,165 INFO L87 Difference]: Start difference. First operand 29 states and 32 transitions. Second operand 16 states. [2018-10-27 09:03:15,195 WARN L179 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 47 [2018-10-27 09:03:15,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:15,580 INFO L93 Difference]: Finished difference Result 55 states and 62 transitions. [2018-10-27 09:03:15,583 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-27 09:03:15,583 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 24 [2018-10-27 09:03:15,584 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:15,586 INFO L225 Difference]: With dead ends: 55 [2018-10-27 09:03:15,586 INFO L226 Difference]: Without dead ends: 43 [2018-10-27 09:03:15,587 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 146 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=141, Invalid=671, Unknown=0, NotChecked=0, Total=812 [2018-10-27 09:03:15,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-10-27 09:03:15,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 29. [2018-10-27 09:03:15,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-10-27 09:03:15,595 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 32 transitions. [2018-10-27 09:03:15,595 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 32 transitions. Word has length 24 [2018-10-27 09:03:15,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:15,596 INFO L481 AbstractCegarLoop]: Abstraction has 29 states and 32 transitions. [2018-10-27 09:03:15,596 INFO L482 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-10-27 09:03:15,596 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 32 transitions. [2018-10-27 09:03:15,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-10-27 09:03:15,597 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:15,597 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:15,597 INFO L424 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:15,598 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:15,598 INFO L82 PathProgramCache]: Analyzing trace with hash -1253110442, now seen corresponding path program 2 times [2018-10-27 09:03:15,598 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:15,599 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:15,599 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:15,599 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:15,599 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:15,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:16,077 WARN L179 SmtUtils]: Spent 163.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 8 [2018-10-27 09:03:16,246 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:16,247 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:16,247 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:03:16,247 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 09:03:16,247 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 09:03:16,247 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:16,248 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-27 09:03:16,257 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 09:03:16,257 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 09:03:16,285 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2018-10-27 09:03:16,285 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 09:03:16,289 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:03:16,420 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-10-27 09:03:16,421 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:03:17,264 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-10-27 09:03:17,292 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 09:03:17,293 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6, 6] total 17 [2018-10-27 09:03:17,293 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 09:03:17,293 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-27 09:03:17,294 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-27 09:03:17,294 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=219, Unknown=0, NotChecked=0, Total=272 [2018-10-27 09:03:17,294 INFO L87 Difference]: Start difference. First operand 29 states and 32 transitions. Second operand 13 states. [2018-10-27 09:03:18,396 WARN L179 SmtUtils]: Spent 214.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 26 [2018-10-27 09:03:18,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:18,533 INFO L93 Difference]: Finished difference Result 52 states and 58 transitions. [2018-10-27 09:03:18,534 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-27 09:03:18,534 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 28 [2018-10-27 09:03:18,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:18,535 INFO L225 Difference]: With dead ends: 52 [2018-10-27 09:03:18,535 INFO L226 Difference]: Without dead ends: 40 [2018-10-27 09:03:18,536 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=160, Invalid=542, Unknown=0, NotChecked=0, Total=702 [2018-10-27 09:03:18,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-10-27 09:03:18,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 29. [2018-10-27 09:03:18,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-10-27 09:03:18,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 32 transitions. [2018-10-27 09:03:18,542 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 32 transitions. Word has length 28 [2018-10-27 09:03:18,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:18,542 INFO L481 AbstractCegarLoop]: Abstraction has 29 states and 32 transitions. [2018-10-27 09:03:18,542 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-27 09:03:18,543 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 32 transitions. [2018-10-27 09:03:18,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-10-27 09:03:18,544 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:18,544 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:18,544 INFO L424 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:18,544 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:18,544 INFO L82 PathProgramCache]: Analyzing trace with hash -1646137452, now seen corresponding path program 2 times [2018-10-27 09:03:18,545 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:18,545 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:18,546 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 09:03:18,546 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:18,546 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:18,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:19,001 WARN L179 SmtUtils]: Spent 273.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 24 [2018-10-27 09:03:19,436 WARN L179 SmtUtils]: Spent 384.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 21 [2018-10-27 09:03:19,989 WARN L179 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 49 [2018-10-27 09:03:20,476 WARN L179 SmtUtils]: Spent 183.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 45 [2018-10-27 09:03:22,730 WARN L179 SmtUtils]: Spent 2.09 s on a formula simplification. DAG size of input: 79 DAG size of output: 41 [2018-10-27 09:03:22,736 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:22,737 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:22,737 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:03:22,737 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 09:03:22,737 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 09:03:22,737 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:22,738 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-27 09:03:22,753 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 09:03:22,753 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 09:03:22,824 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-10-27 09:03:22,824 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 09:03:22,828 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:03:22,872 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 27 [2018-10-27 09:03:22,883 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:03:22,884 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-27 09:03:22,925 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:22,932 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 28 [2018-10-27 09:03:22,934 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:03:22,935 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-27 09:03:22,941 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:24,970 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:24,971 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-27 09:03:25,590 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 53 [2018-10-27 09:03:25,788 WARN L179 SmtUtils]: Spent 141.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-10-27 09:03:26,173 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:26,174 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:03:26,384 WARN L179 SmtUtils]: Spent 208.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 69 [2018-10-27 09:03:27,707 WARN L179 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 59 [2018-10-27 09:03:27,735 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:27,756 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 09:03:27,756 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 13] total 33 [2018-10-27 09:03:27,756 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 09:03:27,757 INFO L460 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-27 09:03:27,757 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-27 09:03:27,758 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=930, Unknown=0, NotChecked=0, Total=1056 [2018-10-27 09:03:27,758 INFO L87 Difference]: Start difference. First operand 29 states and 32 transitions. Second operand 22 states. [2018-10-27 09:03:28,127 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 49 [2018-10-27 09:03:28,336 WARN L179 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 54 [2018-10-27 09:03:32,935 WARN L179 SmtUtils]: Spent 183.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 60 [2018-10-27 09:03:33,164 WARN L179 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 63 [2018-10-27 09:03:33,480 WARN L179 SmtUtils]: Spent 196.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 70 [2018-10-27 09:03:33,800 WARN L179 SmtUtils]: Spent 205.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 95 [2018-10-27 09:03:34,340 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 78 [2018-10-27 09:03:34,666 WARN L179 SmtUtils]: Spent 177.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 76 [2018-10-27 09:03:34,894 WARN L179 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 49 [2018-10-27 09:03:35,140 WARN L179 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 80 [2018-10-27 09:03:35,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:35,201 INFO L93 Difference]: Finished difference Result 59 states and 66 transitions. [2018-10-27 09:03:35,209 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-27 09:03:35,209 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 28 [2018-10-27 09:03:35,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:35,211 INFO L225 Difference]: With dead ends: 59 [2018-10-27 09:03:35,211 INFO L226 Difference]: Without dead ends: 47 [2018-10-27 09:03:35,212 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 34 SyntacticMatches, 3 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 418 ImplicationChecksByTransitivity, 13.1s TimeCoverageRelationStatistics Valid=281, Invalid=1974, Unknown=1, NotChecked=0, Total=2256 [2018-10-27 09:03:35,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-10-27 09:03:35,219 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 33. [2018-10-27 09:03:35,220 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-10-27 09:03:35,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 37 transitions. [2018-10-27 09:03:35,220 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 37 transitions. Word has length 28 [2018-10-27 09:03:35,221 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:35,221 INFO L481 AbstractCegarLoop]: Abstraction has 33 states and 37 transitions. [2018-10-27 09:03:35,221 INFO L482 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-27 09:03:35,221 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 37 transitions. [2018-10-27 09:03:35,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-10-27 09:03:35,222 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:35,222 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:35,222 INFO L424 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:35,223 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:35,223 INFO L82 PathProgramCache]: Analyzing trace with hash 1637712594, now seen corresponding path program 3 times [2018-10-27 09:03:35,223 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:35,224 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:35,224 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 09:03:35,224 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:35,224 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:35,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:35,302 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-10-27 09:03:35,303 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-27 09:03:35,303 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-27 09:03:35,303 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-27 09:03:35,303 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-27 09:03:35,304 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-27 09:03:35,304 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-27 09:03:35,304 INFO L87 Difference]: Start difference. First operand 33 states and 37 transitions. Second operand 3 states. [2018-10-27 09:03:35,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:03:35,352 INFO L93 Difference]: Finished difference Result 56 states and 63 transitions. [2018-10-27 09:03:35,352 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-27 09:03:35,352 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 28 [2018-10-27 09:03:35,352 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:03:35,353 INFO L225 Difference]: With dead ends: 56 [2018-10-27 09:03:35,353 INFO L226 Difference]: Without dead ends: 33 [2018-10-27 09:03:35,353 INFO L605 BasicCegarLoop]: 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-10-27 09:03:35,354 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-10-27 09:03:35,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-10-27 09:03:35,360 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-10-27 09:03:35,360 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 33 transitions. [2018-10-27 09:03:35,361 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 33 transitions. Word has length 28 [2018-10-27 09:03:35,361 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:03:35,361 INFO L481 AbstractCegarLoop]: Abstraction has 33 states and 33 transitions. [2018-10-27 09:03:35,361 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-27 09:03:35,361 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 33 transitions. [2018-10-27 09:03:35,362 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-27 09:03:35,362 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:03:35,362 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:03:35,362 INFO L424 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:03:35,363 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:03:35,363 INFO L82 PathProgramCache]: Analyzing trace with hash -1605254594, now seen corresponding path program 4 times [2018-10-27 09:03:35,363 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:03:35,364 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:35,364 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 09:03:35,364 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:03:35,364 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:03:35,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:36,192 WARN L179 SmtUtils]: Spent 585.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 35 [2018-10-27 09:03:36,446 WARN L179 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 32 [2018-10-27 09:03:36,765 WARN L179 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 48 [2018-10-27 09:03:45,155 WARN L179 SmtUtils]: Spent 6.13 s on a formula simplification that was a NOOP. DAG size: 50 [2018-10-27 09:03:47,484 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 35 [2018-10-27 09:03:47,490 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:47,490 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:47,490 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:03:47,490 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 09:03:47,491 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 09:03:47,491 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:03:47,491 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-27 09:03:47,499 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:03:47,499 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-27 09:03:47,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:03:47,550 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:03:47,591 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 28 [2018-10-27 09:03:47,606 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:03:47,607 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-27 09:03:47,697 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:47,703 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 27 [2018-10-27 09:03:47,705 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:03:47,705 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-27 09:03:47,714 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:53,755 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:03:53,755 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-27 09:03:56,178 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:56,178 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:03:56,309 WARN L179 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 63 [2018-10-27 09:03:57,086 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:03:57,108 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 09:03:57,108 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 10] total 30 [2018-10-27 09:03:57,109 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 09:03:57,109 INFO L460 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-27 09:03:57,109 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-27 09:03:57,110 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=778, Unknown=2, NotChecked=0, Total=870 [2018-10-27 09:03:57,110 INFO L87 Difference]: Start difference. First operand 33 states and 33 transitions. Second operand 22 states. [2018-10-27 09:03:57,842 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 59 [2018-10-27 09:03:58,220 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 74 [2018-10-27 09:03:58,464 WARN L179 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 65 [2018-10-27 09:04:01,654 WARN L179 SmtUtils]: Spent 747.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 55 [2018-10-27 09:04:02,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:04:02,266 INFO L93 Difference]: Finished difference Result 48 states and 48 transitions. [2018-10-27 09:04:02,267 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-27 09:04:02,267 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 32 [2018-10-27 09:04:02,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:04:02,268 INFO L225 Difference]: With dead ends: 48 [2018-10-27 09:04:02,269 INFO L226 Difference]: Without dead ends: 38 [2018-10-27 09:04:02,271 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 47 SyntacticMatches, 3 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 217 ImplicationChecksByTransitivity, 19.4s TimeCoverageRelationStatistics Valid=211, Invalid=1592, Unknown=3, NotChecked=0, Total=1806 [2018-10-27 09:04:02,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2018-10-27 09:04:02,277 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 37. [2018-10-27 09:04:02,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2018-10-27 09:04:02,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 37 transitions. [2018-10-27 09:04:02,278 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 37 transitions. Word has length 32 [2018-10-27 09:04:02,278 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:04:02,278 INFO L481 AbstractCegarLoop]: Abstraction has 37 states and 37 transitions. [2018-10-27 09:04:02,278 INFO L482 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-27 09:04:02,279 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 37 transitions. [2018-10-27 09:04:02,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-10-27 09:04:02,280 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:04:02,280 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:04:02,280 INFO L424 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:04:02,280 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:04:02,280 INFO L82 PathProgramCache]: Analyzing trace with hash 1810116584, now seen corresponding path program 5 times [2018-10-27 09:04:02,281 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:04:02,281 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:04:02,281 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-27 09:04:02,282 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:04:02,282 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:04:02,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:04:02,903 WARN L179 SmtUtils]: Spent 412.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 34 [2018-10-27 09:04:03,805 WARN L179 SmtUtils]: Spent 477.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 46 [2018-10-27 09:04:04,149 WARN L179 SmtUtils]: Spent 237.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 68 [2018-10-27 09:04:04,598 WARN L179 SmtUtils]: Spent 403.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 48 [2018-10-27 09:04:09,483 WARN L179 SmtUtils]: Spent 4.85 s on a formula simplification. DAG size of input: 80 DAG size of output: 62 [2018-10-27 09:04:32,300 WARN L179 SmtUtils]: Spent 22.74 s on a formula simplification. DAG size of input: 84 DAG size of output: 75 [2018-10-27 09:04:49,400 WARN L179 SmtUtils]: Spent 14.64 s on a formula simplification. DAG size of input: 81 DAG size of output: 72 [2018-10-27 09:04:49,637 WARN L179 SmtUtils]: Spent 168.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 52 [2018-10-27 09:04:49,653 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:04:49,653 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:04:49,653 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:04:49,654 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 09:04:49,654 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 09:04:49,654 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:04:49,654 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 09:04:49,663 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-27 09:04:49,663 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-27 09:04:56,436 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-10-27 09:04:56,436 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 09:04:56,444 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:04:56,461 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-27 09:04:56,461 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-27 09:05:04,510 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 18 [2018-10-27 09:05:04,514 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:05:04,514 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-27 09:05:04,516 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:05:04,521 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:05:04,521 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-27 09:05:11,279 WARN L179 SmtUtils]: Spent 224.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 64 [2018-10-27 09:05:11,822 WARN L179 SmtUtils]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 72 [2018-10-27 09:05:17,489 WARN L179 SmtUtils]: Spent 195.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 64 [2018-10-27 09:05:19,506 WARN L179 SmtUtils]: Spent 131.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-27 09:05:23,815 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:05:23,815 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:05:26,378 WARN L179 SmtUtils]: Spent 2.56 s on a formula simplification. DAG size of input: 139 DAG size of output: 109 [2018-10-27 09:05:26,573 WARN L179 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 70 [2018-10-27 09:05:28,000 WARN L179 SmtUtils]: Spent 242.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 54 [2018-10-27 09:05:28,343 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-27 09:05:29,098 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification that was a NOOP. DAG size: 67 [2018-10-27 09:05:29,547 WARN L179 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 66 [2018-10-27 09:05:30,216 WARN L179 SmtUtils]: Spent 183.00 ms on a formula simplification that was a NOOP. DAG size: 71 [2018-10-27 09:05:30,724 WARN L179 SmtUtils]: Spent 209.00 ms on a formula simplification that was a NOOP. DAG size: 75 [2018-10-27 09:05:32,178 WARN L179 SmtUtils]: Spent 221.00 ms on a formula simplification that was a NOOP. DAG size: 75 [2018-10-27 09:05:33,067 WARN L179 SmtUtils]: Spent 299.00 ms on a formula simplification that was a NOOP. DAG size: 78 [2018-10-27 09:05:34,578 WARN L179 SmtUtils]: Spent 689.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 80 [2018-10-27 09:05:35,629 WARN L179 SmtUtils]: Spent 365.00 ms on a formula simplification that was a NOOP. DAG size: 84 [2018-10-27 09:05:37,309 WARN L179 SmtUtils]: Spent 458.00 ms on a formula simplification that was a NOOP. DAG size: 86 [2018-10-27 09:05:37,422 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:05:37,456 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-27 09:05:37,456 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 18, 17] total 45 [2018-10-27 09:05:37,456 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-27 09:05:37,457 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-10-27 09:05:37,457 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-10-27 09:05:37,458 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=204, Invalid=1769, Unknown=7, NotChecked=0, Total=1980 [2018-10-27 09:05:37,459 INFO L87 Difference]: Start difference. First operand 37 states and 37 transitions. Second operand 30 states. [2018-10-27 09:05:55,980 WARN L179 SmtUtils]: Spent 258.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 79 [2018-10-27 09:06:03,518 WARN L179 SmtUtils]: Spent 283.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 67 [2018-10-27 09:06:03,717 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 64 [2018-10-27 09:06:04,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-27 09:06:04,575 INFO L93 Difference]: Finished difference Result 52 states and 52 transitions. [2018-10-27 09:06:04,578 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-27 09:06:04,578 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 36 [2018-10-27 09:06:04,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-27 09:06:04,579 INFO L225 Difference]: With dead ends: 52 [2018-10-27 09:06:04,579 INFO L226 Difference]: Without dead ends: 42 [2018-10-27 09:06:04,580 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 41 SyntacticMatches, 3 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 521 ImplicationChecksByTransitivity, 89.5s TimeCoverageRelationStatistics Valid=306, Invalid=2233, Unknown=11, NotChecked=0, Total=2550 [2018-10-27 09:06:04,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2018-10-27 09:06:04,587 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2018-10-27 09:06:04,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-27 09:06:04,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 41 transitions. [2018-10-27 09:06:04,588 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 41 transitions. Word has length 36 [2018-10-27 09:06:04,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-27 09:06:04,588 INFO L481 AbstractCegarLoop]: Abstraction has 41 states and 41 transitions. [2018-10-27 09:06:04,588 INFO L482 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-10-27 09:06:04,589 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 41 transitions. [2018-10-27 09:06:04,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-27 09:06:04,590 INFO L367 BasicCegarLoop]: Found error trace [2018-10-27 09:06:04,590 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-27 09:06:04,590 INFO L424 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-27 09:06:04,590 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-27 09:06:04,590 INFO L82 PathProgramCache]: Analyzing trace with hash 668186770, now seen corresponding path program 6 times [2018-10-27 09:06:04,591 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-27 09:06:04,591 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:06:04,591 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-27 09:06:04,592 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-27 09:06:04,592 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-27 09:06:04,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-27 09:06:05,588 WARN L179 SmtUtils]: Spent 782.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 34 [2018-10-27 09:06:06,336 WARN L179 SmtUtils]: Spent 263.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 67 [2018-10-27 09:06:08,621 WARN L179 SmtUtils]: Spent 2.25 s on a formula simplification. DAG size of input: 90 DAG size of output: 73 [2018-10-27 09:06:09,251 WARN L179 SmtUtils]: Spent 398.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 74 [2018-10-27 09:06:09,517 WARN L179 SmtUtils]: Spent 214.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 72 [2018-10-27 09:06:10,024 WARN L179 SmtUtils]: Spent 425.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 70 [2018-10-27 09:06:10,635 WARN L179 SmtUtils]: Spent 565.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 69 [2018-10-27 09:06:10,959 WARN L179 SmtUtils]: Spent 254.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 83 [2018-10-27 09:06:13,376 WARN L179 SmtUtils]: Spent 2.32 s on a formula simplification. DAG size of input: 92 DAG size of output: 75 [2018-10-27 09:06:13,589 WARN L179 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 67 [2018-10-27 09:06:15,873 WARN L832 $PredicateComparison]: unable to prove that (let ((.cse0 (div c_linear_search_~j~0 4294967296))) (let ((.cse1 (+ .cse0 1))) (and (or (<= 0 .cse0) (< 0 .cse1)) (let ((.cse2 (<= .cse1 0))) (or (and (<= c_linear_search_~j~0 5) (or (not (= 0 |c_linear_search_#in~a.offset|)) .cse2 (let ((.cse7 (- |c_linear_search_#in~n|))) (let ((.cse4 (- .cse7))) (let ((.cse3 (div (+ .cse4 (- 4)) 4294967296))) (let ((.cse6 (div (+ c_linear_search_~j~0 (+ (* 2 .cse7) (+ (* 12884901888 (div (+ .cse4 4294967281) 4294967296)) (+ (* (- 4294967296) .cse3) 8589934592)))) 8589934592))) (let ((.cse5 (* 17179869184 .cse6))) (and (<= |c_linear_search_#in~n| (+ (* 4294967296 (div (+ (- c_linear_search_~j~0) (+ (* 4294967296 .cse3) 5)) 4294967296)) 14)) (<= |c_linear_search_#in~n| (+ (* 4294967296 (div (+ .cse4 (- 5)) 4294967296)) 14)) (<= .cse5 0) (or (<= (+ .cse5 1) 0) (not (= (select (select |c_#memory_int| |c_linear_search_#in~a.base|) (- (+ (* (- 17179869184) .cse6) (- 8)))) |c_linear_search_#in~q|))) (<= (+ (* 4294967296 (div (+ (* 4294967296 .cse0) (+ .cse4 4294967290)) 4294967296)) 4) |c_linear_search_#in~n|))))))))) |c_linear_search_#t~short1| .cse2))))) is different from false [2018-10-27 09:07:09,432 WARN L179 SmtUtils]: Spent 39.51 s on a formula simplification. DAG size of input: 83 DAG size of output: 73 [2018-10-27 09:07:09,766 WARN L179 SmtUtils]: Spent 206.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 41 [2018-10-27 09:07:09,784 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 5 not checked. [2018-10-27 09:07:09,784 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:07:09,784 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-27 09:07:09,784 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-27 09:07:09,784 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-27 09:07:09,785 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-27 09:07:09,785 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 09:07:09,795 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-27 09:07:09,796 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-27 09:07:09,888 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-27 09:07:09,888 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-27 09:07:09,892 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-27 09:07:09,907 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 28 [2018-10-27 09:07:09,909 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:07:09,910 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-27 09:07:09,919 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:07:09,921 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 27 [2018-10-27 09:07:09,923 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-10-27 09:07:09,923 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-27 09:07:09,932 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:07:11,960 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-27 09:07:11,961 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-27 09:07:20,403 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 60 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-27 09:07:20,404 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-27 09:07:22,778 WARN L179 SmtUtils]: Spent 2.37 s on a formula simplification. DAG size of input: 118 DAG size of output: 98 [2018-10-27 09:07:28,897 WARN L179 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 55 Received shutdown request... [2018-10-27 09:07:37,039 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-27 09:07:37,240 WARN L522 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-27 09:07:37,241 WARN L550 AbstractCegarLoop]: Verification canceled [2018-10-27 09:07:37,246 WARN L205 ceAbstractionStarter]: Timeout [2018-10-27 09:07:37,246 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 27.10 09:07:37 BoogieIcfgContainer [2018-10-27 09:07:37,247 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-27 09:07:37,247 INFO L168 Benchmark]: Toolchain (without parser) took 275551.94 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 940.0 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -765.4 MB). Peak memory consumption was 174.7 MB. Max. memory is 7.1 GB. [2018-10-27 09:07:37,248 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-27 09:07:37,249 INFO L168 Benchmark]: CACSL2BoogieTranslator took 332.51 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-10-27 09:07:37,249 INFO L168 Benchmark]: Boogie Procedure Inliner took 43.00 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-27 09:07:37,250 INFO L168 Benchmark]: Boogie Preprocessor took 27.33 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-27 09:07:37,250 INFO L168 Benchmark]: RCFGBuilder took 522.86 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 750.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -801.0 MB). Peak memory consumption was 26.8 MB. Max. memory is 7.1 GB. [2018-10-27 09:07:37,251 INFO L168 Benchmark]: TraceAbstraction took 274620.80 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 189.3 MB). Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 25.0 MB). Peak memory consumption was 214.3 MB. Max. memory is 7.1 GB. [2018-10-27 09:07:37,257 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 332.51 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 43.00 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 27.33 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 522.86 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 750.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -801.0 MB). Peak memory consumption was 26.8 MB. Max. memory is 7.1 GB. * TraceAbstraction took 274620.80 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 189.3 MB). Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 25.0 MB). Peak memory consumption was 214.3 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 5]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 5). Cancelled while BasicCegarLoop was analyzing trace of length 41 with TraceHistMax 6,while TraceCheckSpWp was constructing backward predicates,while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 46 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 28 locations, 1 error locations. TIMEOUT Result, 274.5s OverallTime, 11 OverallIterations, 6 TraceHistogramMax, 44.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 199 SDtfs, 299 SDslu, 1128 SDs, 0 SdLazy, 1448 SolverSat, 96 SolverUnsat, 7 SolverUnknown, 0 SolverNotchecked, 17.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 484 GetRequests, 248 SyntacticMatches, 20 SemanticMatches, 216 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1441 ImplicationChecksByTransitivity, 130.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=41occurred in iteration=10, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.6s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 10 MinimizatonAttempts, 46 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 7.2s SatisfiabilityAnalysisTime, 128.9s InterpolantComputationTime, 429 NumberOfCodeBlocks, 421 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 579 ConstructedInterpolants, 102 QuantifiedInterpolants, 791905 SizeOfPredicates, 112 NumberOfNonLiveVariables, 839 ConjunctsInSsa, 260 ConjunctsInUnsatCore, 22 InterpolantComputations, 4 PerfectInterpolantSequences, 28/300 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown