java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf -i ../../../trunk/examples/svcomp/loop-crafted/simple_array_index_value_true-unreach-call2_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-df4b876 [2018-11-07 05:03:48,258 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-07 05:03:48,260 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-07 05:03:48,271 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-07 05:03:48,272 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-07 05:03:48,273 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-07 05:03:48,274 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-07 05:03:48,276 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-07 05:03:48,277 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-07 05:03:48,278 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-07 05:03:48,279 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-07 05:03:48,279 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-07 05:03:48,280 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-07 05:03:48,281 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-07 05:03:48,282 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-07 05:03:48,283 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-07 05:03:48,284 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-07 05:03:48,285 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-07 05:03:48,287 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-07 05:03:48,289 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-07 05:03:48,290 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-07 05:03:48,291 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-07 05:03:48,293 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-07 05:03:48,294 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-07 05:03:48,294 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-07 05:03:48,295 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-07 05:03:48,296 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-07 05:03:48,296 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-07 05:03:48,297 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-07 05:03:48,298 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-07 05:03:48,299 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-07 05:03:48,299 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-07 05:03:48,299 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-07 05:03:48,300 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-07 05:03:48,301 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-07 05:03:48,301 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-07 05:03:48,302 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf [2018-11-07 05:03:48,317 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-07 05:03:48,318 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-07 05:03:48,318 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-07 05:03:48,318 INFO L133 SettingsManager]: * User list type=DISABLED [2018-11-07 05:03:48,319 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-11-07 05:03:48,319 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-11-07 05:03:48,319 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-11-07 05:03:48,319 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-11-07 05:03:48,319 INFO L133 SettingsManager]: * Log string format=TERM [2018-11-07 05:03:48,320 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-11-07 05:03:48,320 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-11-07 05:03:48,320 INFO L133 SettingsManager]: * Interval Domain=false [2018-11-07 05:03:48,321 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-07 05:03:48,321 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-07 05:03:48,321 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-07 05:03:48,321 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-07 05:03:48,321 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-07 05:03:48,322 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-07 05:03:48,322 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-07 05:03:48,322 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-07 05:03:48,322 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-07 05:03:48,322 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-07 05:03:48,323 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-07 05:03:48,323 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-07 05:03:48,323 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-07 05:03:48,323 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-07 05:03:48,323 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-07 05:03:48,324 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-07 05:03:48,324 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-11-07 05:03:48,324 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-07 05:03:48,324 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-07 05:03:48,324 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-07 05:03:48,324 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-07 05:03:48,325 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-11-07 05:03:48,366 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-07 05:03:48,378 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-07 05:03:48,382 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-07 05:03:48,383 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-07 05:03:48,383 INFO L276 PluginConnector]: CDTParser initialized [2018-11-07 05:03:48,384 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/loop-crafted/simple_array_index_value_true-unreach-call2_true-termination.i [2018-11-07 05:03:48,440 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1ec834800/926b850b5dca482888d1f637debaafaf/FLAG95aca030b [2018-11-07 05:03:48,867 INFO L298 CDTParser]: Found 1 translation units. [2018-11-07 05:03:48,868 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loop-crafted/simple_array_index_value_true-unreach-call2_true-termination.i [2018-11-07 05:03:48,874 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1ec834800/926b850b5dca482888d1f637debaafaf/FLAG95aca030b [2018-11-07 05:03:48,890 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1ec834800/926b850b5dca482888d1f637debaafaf [2018-11-07 05:03:48,900 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-07 05:03:48,902 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-07 05:03:48,903 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-07 05:03:48,903 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-07 05:03:48,907 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-07 05:03:48,908 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 05:03:48" (1/1) ... [2018-11-07 05:03:48,910 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1a760589 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:48, skipping insertion in model container [2018-11-07 05:03:48,911 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 05:03:48" (1/1) ... [2018-11-07 05:03:48,921 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-07 05:03:48,941 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-07 05:03:49,167 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 05:03:49,171 INFO L189 MainTranslator]: Completed pre-run [2018-11-07 05:03:49,192 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 05:03:49,211 INFO L193 MainTranslator]: Completed translation [2018-11-07 05:03:49,211 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49 WrapperNode [2018-11-07 05:03:49,211 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-07 05:03:49,212 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-07 05:03:49,212 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-07 05:03:49,213 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-07 05:03:49,220 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,228 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,234 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-07 05:03:49,234 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-07 05:03:49,234 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-07 05:03:49,234 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-07 05:03:49,242 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,242 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,244 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,244 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,250 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,255 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,256 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... [2018-11-07 05:03:49,257 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-07 05:03:49,258 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-07 05:03:49,258 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-07 05:03:49,258 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-07 05:03:49,259 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-07 05:03:49,390 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2018-11-07 05:03:49,390 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-07 05:03:49,390 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-07 05:03:49,390 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-11-07 05:03:49,391 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-07 05:03:49,391 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-07 05:03:49,391 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-07 05:03:49,391 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-07 05:03:49,391 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2018-11-07 05:03:49,391 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-11-07 05:03:49,392 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-11-07 05:03:49,392 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-11-07 05:03:49,837 INFO L276 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-07 05:03:49,837 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 05:03:49 BoogieIcfgContainer [2018-11-07 05:03:49,837 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-07 05:03:49,838 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-07 05:03:49,838 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-07 05:03:49,841 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-07 05:03:49,842 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.11 05:03:48" (1/3) ... [2018-11-07 05:03:49,842 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@663b756 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 05:03:49, skipping insertion in model container [2018-11-07 05:03:49,843 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:03:49" (2/3) ... [2018-11-07 05:03:49,843 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@663b756 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 05:03:49, skipping insertion in model container [2018-11-07 05:03:49,843 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 05:03:49" (3/3) ... [2018-11-07 05:03:49,845 INFO L112 eAbstractionObserver]: Analyzing ICFG simple_array_index_value_true-unreach-call2_true-termination.i [2018-11-07 05:03:49,853 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-07 05:03:49,861 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-07 05:03:49,875 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-07 05:03:49,908 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-07 05:03:49,909 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-07 05:03:49,909 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-07 05:03:49,909 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-07 05:03:49,909 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-07 05:03:49,910 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-07 05:03:49,910 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-07 05:03:49,910 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-07 05:03:49,927 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states. [2018-11-07 05:03:49,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-11-07 05:03:49,932 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:03:49,933 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:03:49,935 INFO L423 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:03:49,941 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:03:49,941 INFO L82 PathProgramCache]: Analyzing trace with hash 1868031892, now seen corresponding path program 1 times [2018-11-07 05:03:49,943 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:03:49,985 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:49,985 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:03:49,985 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:49,985 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:03:50,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:03:50,066 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:03:50,068 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 05:03:50,068 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-07 05:03:50,068 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:03:50,072 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-07 05:03:50,084 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-07 05:03:50,084 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-07 05:03:50,087 INFO L87 Difference]: Start difference. First operand 30 states. Second operand 2 states. [2018-11-07 05:03:50,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:03:50,109 INFO L93 Difference]: Finished difference Result 49 states and 56 transitions. [2018-11-07 05:03:50,109 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-07 05:03:50,111 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 16 [2018-11-07 05:03:50,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:03:50,119 INFO L225 Difference]: With dead ends: 49 [2018-11-07 05:03:50,120 INFO L226 Difference]: Without dead ends: 24 [2018-11-07 05:03:50,123 INFO L604 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-11-07 05:03:50,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2018-11-07 05:03:50,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2018-11-07 05:03:50,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-11-07 05:03:50,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 25 transitions. [2018-11-07 05:03:50,163 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 25 transitions. Word has length 16 [2018-11-07 05:03:50,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:03:50,163 INFO L480 AbstractCegarLoop]: Abstraction has 24 states and 25 transitions. [2018-11-07 05:03:50,163 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-07 05:03:50,165 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 25 transitions. [2018-11-07 05:03:50,165 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-11-07 05:03:50,167 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:03:50,167 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:03:50,167 INFO L423 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:03:50,168 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:03:50,168 INFO L82 PathProgramCache]: Analyzing trace with hash 255747955, now seen corresponding path program 1 times [2018-11-07 05:03:50,168 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:03:50,170 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:50,170 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:03:50,170 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:50,170 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:03:50,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:03:50,332 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:03:50,332 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 05:03:50,332 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-07 05:03:50,333 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:03:50,334 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-11-07 05:03:50,335 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-11-07 05:03:50,335 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-07 05:03:50,335 INFO L87 Difference]: Start difference. First operand 24 states and 25 transitions. Second operand 3 states. [2018-11-07 05:03:50,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:03:50,454 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2018-11-07 05:03:50,455 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-07 05:03:50,455 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 17 [2018-11-07 05:03:50,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:03:50,458 INFO L225 Difference]: With dead ends: 47 [2018-11-07 05:03:50,458 INFO L226 Difference]: Without dead ends: 34 [2018-11-07 05:03:50,459 INFO L604 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-11-07 05:03:50,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-11-07 05:03:50,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2018-11-07 05:03:50,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-11-07 05:03:50,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2018-11-07 05:03:50,473 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 17 [2018-11-07 05:03:50,474 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:03:50,474 INFO L480 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2018-11-07 05:03:50,474 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-11-07 05:03:50,474 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2018-11-07 05:03:50,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-11-07 05:03:50,475 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:03:50,475 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:03:50,476 INFO L423 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:03:50,476 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:03:50,476 INFO L82 PathProgramCache]: Analyzing trace with hash -1253038918, now seen corresponding path program 1 times [2018-11-07 05:03:50,477 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:03:50,478 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:50,479 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:03:50,479 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:50,479 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:03:50,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:03:50,612 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:03:50,613 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:03:50,613 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:03:50,614 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 22 with the following transitions: [2018-11-07 05:03:50,616 INFO L202 CegarAbsIntRunner]: [0], [1], [5], [6], [10], [13], [15], [16], [18], [22], [26], [31], [32], [43], [46], [48], [54], [55], [56], [58] [2018-11-07 05:03:50,668 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-11-07 05:03:50,669 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 05:03:50,813 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-07 05:03:51,205 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 05:03:51,208 INFO L272 AbstractInterpreter]: Visited 20 different actions 84 times. Merged at 5 different actions 53 times. Widened at 1 different actions 7 times. Found 10 fixpoints after 2 different actions. Largest state had 17 variables. [2018-11-07 05:03:51,255 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:03:51,258 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 05:03:51,259 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:03:51,259 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-07 05:03:51,275 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:03:51,276 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:03:51,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:03:51,322 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:03:51,479 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 11 treesize of output 8 [2018-11-07 05:03:51,494 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 8 treesize of output 7 [2018-11-07 05:03:51,495 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:03:51,521 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:51,534 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:51,534 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:17, output treesize:9 [2018-11-07 05:03:51,685 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 23 treesize of output 19 [2018-11-07 05:03:51,711 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:03:51,713 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-07 05:03:51,714 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:03:51,773 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:51,799 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:51,800 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:26, output treesize:9 [2018-11-07 05:03:51,901 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:03:51,902 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:03:52,041 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 18 treesize of output 16 [2018-11-07 05:03:52,146 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 7 treesize of output 5 [2018-11-07 05:03:52,148 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:03:52,155 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:03:52,192 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:03:52,193 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:13 [2018-11-07 05:03:54,053 WARN L179 SmtUtils]: Spent 1.78 s on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-11-07 05:03:54,069 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:03:54,100 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:03:54,100 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 9, 9] total 16 [2018-11-07 05:03:54,100 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:03:54,101 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-11-07 05:03:54,102 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-11-07 05:03:54,102 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=197, Unknown=0, NotChecked=0, Total=240 [2018-11-07 05:03:54,103 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand 10 states. [2018-11-07 05:03:54,859 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:03:54,859 INFO L93 Difference]: Finished difference Result 83 states and 91 transitions. [2018-11-07 05:03:54,861 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-11-07 05:03:54,862 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-11-07 05:03:54,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:03:54,863 INFO L225 Difference]: With dead ends: 83 [2018-11-07 05:03:54,863 INFO L226 Difference]: Without dead ends: 70 [2018-11-07 05:03:54,865 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=71, Invalid=309, Unknown=0, NotChecked=0, Total=380 [2018-11-07 05:03:54,865 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-11-07 05:03:54,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 43. [2018-11-07 05:03:54,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-11-07 05:03:54,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 45 transitions. [2018-11-07 05:03:54,875 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 45 transitions. Word has length 21 [2018-11-07 05:03:54,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:03:54,876 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 45 transitions. [2018-11-07 05:03:54,876 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-11-07 05:03:54,876 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 45 transitions. [2018-11-07 05:03:54,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-11-07 05:03:54,877 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:03:54,877 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:03:54,878 INFO L423 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:03:54,878 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:03:54,878 INFO L82 PathProgramCache]: Analyzing trace with hash 2321608, now seen corresponding path program 2 times [2018-11-07 05:03:54,878 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:03:54,879 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:54,879 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:03:54,880 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:54,880 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:03:54,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:03:55,433 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:03:55,433 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:03:55,433 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:03:55,434 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:03:55,434 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:03:55,434 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:03:55,434 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:03:55,453 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:03:55,453 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:03:55,480 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-11-07 05:03:55,480 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:03:55,483 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:03:55,537 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 11 treesize of output 8 [2018-11-07 05:03:55,539 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 8 treesize of output 7 [2018-11-07 05:03:55,540 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,542 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,548 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,548 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:17, output treesize:9 [2018-11-07 05:03:55,597 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 22 [2018-11-07 05:03:55,629 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 22 treesize of output 36 [2018-11-07 05:03:55,632 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-07 05:03:55,666 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,678 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:03:55,678 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:34, output treesize:27 [2018-11-07 05:03:55,736 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 22 [2018-11-07 05:03:55,772 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 22 treesize of output 36 [2018-11-07 05:03:55,775 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-07 05:03:55,787 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,799 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:03:55,799 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:34, output treesize:27 [2018-11-07 05:03:55,849 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 23 treesize of output 19 [2018-11-07 05:03:55,868 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:03:55,869 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-07 05:03:55,870 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,875 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,905 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:03:55,905 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:26, output treesize:9 [2018-11-07 05:03:55,980 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-07 05:03:55,980 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:03:56,248 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 18 treesize of output 16 [2018-11-07 05:03:56,266 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 7 treesize of output 5 [2018-11-07 05:03:56,269 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:03:56,275 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:03:56,282 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:03:56,282 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:13 [2018-11-07 05:03:58,138 WARN L179 SmtUtils]: Spent 1.77 s on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-11-07 05:03:58,149 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-07 05:03:58,169 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:03:58,169 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 10, 10] total 20 [2018-11-07 05:03:58,169 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:03:58,170 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-11-07 05:03:58,170 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-11-07 05:03:58,170 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=325, Unknown=0, NotChecked=0, Total=380 [2018-11-07 05:03:58,172 INFO L87 Difference]: Start difference. First operand 43 states and 45 transitions. Second operand 13 states. [2018-11-07 05:03:59,210 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:03:59,210 INFO L93 Difference]: Finished difference Result 90 states and 97 transitions. [2018-11-07 05:03:59,212 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-11-07 05:03:59,212 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 29 [2018-11-07 05:03:59,213 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:03:59,214 INFO L225 Difference]: With dead ends: 90 [2018-11-07 05:03:59,214 INFO L226 Difference]: Without dead ends: 68 [2018-11-07 05:03:59,216 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 40 SyntacticMatches, 7 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=117, Invalid=695, Unknown=0, NotChecked=0, Total=812 [2018-11-07 05:03:59,216 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2018-11-07 05:03:59,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 46. [2018-11-07 05:03:59,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-11-07 05:03:59,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-11-07 05:03:59,226 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 29 [2018-11-07 05:03:59,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:03:59,227 INFO L480 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-11-07 05:03:59,227 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-11-07 05:03:59,227 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-11-07 05:03:59,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-11-07 05:03:59,228 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:03:59,228 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:03:59,229 INFO L423 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:03:59,229 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:03:59,229 INFO L82 PathProgramCache]: Analyzing trace with hash 41131456, now seen corresponding path program 1 times [2018-11-07 05:03:59,229 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:03:59,230 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:59,230 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:03:59,230 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:03:59,230 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:03:59,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:03:59,573 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 2 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-07 05:03:59,573 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:03:59,573 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:03:59,573 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 44 with the following transitions: [2018-11-07 05:03:59,574 INFO L202 CegarAbsIntRunner]: [0], [1], [5], [6], [10], [13], [15], [16], [18], [22], [26], [31], [32], [34], [36], [43], [46], [48], [51], [53], [54], [55], [56], [58], [59] [2018-11-07 05:03:59,577 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-11-07 05:03:59,577 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 05:03:59,589 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-07 05:04:00,016 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 05:04:00,017 INFO L272 AbstractInterpreter]: Visited 25 different actions 221 times. Merged at 11 different actions 119 times. Widened at 2 different actions 14 times. Found 11 fixpoints after 3 different actions. Largest state had 18 variables. [2018-11-07 05:04:00,053 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:04:00,053 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 05:04:00,053 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:04:00,054 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:04:00,067 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:04:00,067 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:04:00,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:04:00,101 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:04:00,184 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 17 treesize of output 14 [2018-11-07 05:04:00,189 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 14 treesize of output 13 [2018-11-07 05:04:00,189 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:04:00,192 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:04:00,213 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:04:00,214 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:47, output treesize:40 [2018-11-07 05:04:00,321 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 35 treesize of output 30 [2018-11-07 05:04:00,359 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:04:00,361 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:04:00,382 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:04:02,448 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:04:02,449 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:64, output treesize:57 [2018-11-07 05:04:02,566 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 35 treesize of output 30 [2018-11-07 05:04:02,685 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:04:02,688 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:04:02,709 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:04:04,755 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:04:04,755 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:64, output treesize:57 [2018-11-07 05:04:11,201 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 27 [2018-11-07 05:04:11,213 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:04:11,214 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2018-11-07 05:04:11,214 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:04:11,223 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:04:11,237 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:04:11,238 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:56, output treesize:33 [2018-11-07 05:04:11,547 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-07 05:04:11,547 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:04:14,049 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 20 treesize of output 18 [2018-11-07 05:04:14,071 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 9 treesize of output 5 [2018-11-07 05:04:14,089 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:04:14,142 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:04:14,146 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:04:14,147 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:13 [2018-11-07 05:04:16,098 WARN L179 SmtUtils]: Spent 1.85 s on a formula simplification. DAG size of input: 19 DAG size of output: 11 [2018-11-07 05:04:18,766 WARN L179 SmtUtils]: Spent 714.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-11-07 05:04:18,878 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 2 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-11-07 05:04:18,897 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:04:18,897 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 13, 13] total 27 [2018-11-07 05:04:18,897 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:04:18,899 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-11-07 05:04:18,900 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-11-07 05:04:18,900 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=614, Unknown=4, NotChecked=0, Total=702 [2018-11-07 05:04:18,900 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 16 states. [2018-11-07 05:04:23,540 WARN L179 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 44 [2018-11-07 05:04:23,922 WARN L179 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 41 [2018-11-07 05:04:31,222 WARN L179 SmtUtils]: Spent 391.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 40 [2018-11-07 05:04:45,641 WARN L179 SmtUtils]: Spent 2.19 s on a formula simplification that was a NOOP. DAG size: 56 [2018-11-07 05:05:09,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:05:09,314 INFO L93 Difference]: Finished difference Result 110 states and 115 transitions. [2018-11-07 05:05:09,315 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-11-07 05:05:09,315 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 43 [2018-11-07 05:05:09,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:05:09,317 INFO L225 Difference]: With dead ends: 110 [2018-11-07 05:05:09,317 INFO L226 Difference]: Without dead ends: 89 [2018-11-07 05:05:09,318 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 62 SyntacticMatches, 15 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 316 ImplicationChecksByTransitivity, 25.3s TimeCoverageRelationStatistics Valid=178, Invalid=1222, Unknown=6, NotChecked=0, Total=1406 [2018-11-07 05:05:09,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-11-07 05:05:09,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 60. [2018-11-07 05:05:09,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-11-07 05:05:09,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 61 transitions. [2018-11-07 05:05:09,330 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 61 transitions. Word has length 43 [2018-11-07 05:05:09,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:05:09,330 INFO L480 AbstractCegarLoop]: Abstraction has 60 states and 61 transitions. [2018-11-07 05:05:09,330 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-11-07 05:05:09,330 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 61 transitions. [2018-11-07 05:05:09,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2018-11-07 05:05:09,332 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:05:09,332 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:05:09,332 INFO L423 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:05:09,332 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:05:09,333 INFO L82 PathProgramCache]: Analyzing trace with hash 115368056, now seen corresponding path program 2 times [2018-11-07 05:05:09,333 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:05:09,334 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:05:09,334 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:05:09,334 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:05:09,334 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:05:09,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:05:09,596 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 4 proven. 50 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-11-07 05:05:09,596 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:05:09,596 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:05:09,596 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:05:09,596 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:05:09,597 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:05:09,597 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:05:09,608 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:05:09,608 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:05:09,927 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-11-07 05:05:09,927 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:05:09,932 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:05:10,029 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 17 treesize of output 14 [2018-11-07 05:05:10,032 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 14 treesize of output 13 [2018-11-07 05:05:10,032 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,034 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,043 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,043 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-11-07 05:05:10,119 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 29 treesize of output 24 [2018-11-07 05:05:10,121 INFO L700 Elim1Store]: detected not equals via solver [2018-11-07 05:05:10,123 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 37 [2018-11-07 05:05:10,124 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,130 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,140 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,140 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:18 [2018-11-07 05:05:10,215 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 29 treesize of output 24 [2018-11-07 05:05:10,218 INFO L700 Elim1Store]: detected not equals via solver [2018-11-07 05:05:10,221 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 37 [2018-11-07 05:05:10,222 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,230 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,244 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:10,245 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:35 [2018-11-07 05:05:10,309 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-11-07 05:05:10,309 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:05:12,147 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 20 treesize of output 18 [2018-11-07 05:05:12,182 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 9 treesize of output 5 [2018-11-07 05:05:12,187 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:12,190 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:12,198 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:12,198 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:15 [2018-11-07 05:05:14,322 WARN L854 $PredicateComparison]: unable to prove that (or (forall ((v_main_~tmp~0_13 Int)) (<= (mod v_main_~tmp~0_13 4294967296) (mod c_main_~index~0 4294967296))) (< (mod (+ c_main_~index~0 3) 4294967296) 10000) (<= 10000 (mod (+ c_main_~index~0 1) 4294967296)) (<= 10000 (mod c_main_~index~0 4294967296))) is different from true [2018-11-07 05:05:18,046 WARN L179 SmtUtils]: Spent 2.13 s on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-11-07 05:05:18,307 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 4 proven. 54 refuted. 0 times theorem prover too weak. 4 trivial. 10 not checked. [2018-11-07 05:05:18,326 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:05:18,327 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 13, 19] total 36 [2018-11-07 05:05:18,327 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:05:18,327 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-07 05:05:18,328 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-07 05:05:18,328 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=239, Invalid=954, Unknown=1, NotChecked=66, Total=1260 [2018-11-07 05:05:18,329 INFO L87 Difference]: Start difference. First operand 60 states and 61 transitions. Second operand 19 states. [2018-11-07 05:05:19,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:05:19,070 INFO L93 Difference]: Finished difference Result 123 states and 129 transitions. [2018-11-07 05:05:19,070 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-11-07 05:05:19,070 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 57 [2018-11-07 05:05:19,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:05:19,072 INFO L225 Difference]: With dead ends: 123 [2018-11-07 05:05:19,072 INFO L226 Difference]: Without dead ends: 92 [2018-11-07 05:05:19,074 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 83 SyntacticMatches, 6 SemanticMatches, 39 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=317, Invalid=1246, Unknown=1, NotChecked=76, Total=1640 [2018-11-07 05:05:19,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-11-07 05:05:19,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 64. [2018-11-07 05:05:19,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-11-07 05:05:19,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 65 transitions. [2018-11-07 05:05:19,086 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 65 transitions. Word has length 57 [2018-11-07 05:05:19,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:05:19,086 INFO L480 AbstractCegarLoop]: Abstraction has 64 states and 65 transitions. [2018-11-07 05:05:19,087 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-07 05:05:19,087 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 65 transitions. [2018-11-07 05:05:19,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2018-11-07 05:05:19,088 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:05:19,089 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:05:19,089 INFO L423 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:05:19,089 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:05:19,089 INFO L82 PathProgramCache]: Analyzing trace with hash -937620801, now seen corresponding path program 3 times [2018-11-07 05:05:19,089 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:05:19,090 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:05:19,090 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:05:19,090 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:05:19,090 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:05:19,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:05:19,310 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 4 proven. 72 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-11-07 05:05:19,311 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:05:19,311 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:05:19,311 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:05:19,311 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:05:19,311 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:05:19,311 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:05:19,326 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:05:19,326 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:05:19,376 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:05:19,376 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:05:19,380 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:05:19,499 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 17 treesize of output 14 [2018-11-07 05:05:19,502 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 14 treesize of output 13 [2018-11-07 05:05:19,502 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:19,505 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:19,520 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:19,521 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-11-07 05:05:19,602 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 35 treesize of output 30 [2018-11-07 05:05:19,620 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:05:19,621 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:05:19,640 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:19,661 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:19,661 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:05:19,751 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 35 treesize of output 30 [2018-11-07 05:05:19,769 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:05:19,770 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:05:19,791 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:19,812 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:19,812 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:05:19,958 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 35 treesize of output 30 [2018-11-07 05:05:19,977 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:05:19,979 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:05:19,996 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:20,334 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:20,334 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:05:20,935 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 27 [2018-11-07 05:05:20,942 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:05:20,943 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2018-11-07 05:05:20,943 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:20,951 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:20,967 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:20,967 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:55, output treesize:32 [2018-11-07 05:05:21,149 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 0 proven. 69 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-11-07 05:05:21,149 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:05:23,767 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 20 treesize of output 18 [2018-11-07 05:05:23,784 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 9 treesize of output 5 [2018-11-07 05:05:23,786 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:23,790 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:05:23,795 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:05:23,796 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:13 [2018-11-07 05:05:25,752 WARN L179 SmtUtils]: Spent 1.81 s on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-11-07 05:05:27,670 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 4 proven. 65 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-11-07 05:05:27,689 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:05:27,690 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 15, 15] total 33 [2018-11-07 05:05:27,690 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:05:27,690 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-11-07 05:05:27,690 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-11-07 05:05:27,691 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=940, Unknown=2, NotChecked=0, Total=1056 [2018-11-07 05:05:27,691 INFO L87 Difference]: Start difference. First operand 64 states and 65 transitions. Second operand 20 states. [2018-11-07 05:05:50,822 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:05:50,822 INFO L93 Difference]: Finished difference Result 137 states and 144 transitions. [2018-11-07 05:05:50,823 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-11-07 05:05:50,823 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 61 [2018-11-07 05:05:50,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:05:50,824 INFO L225 Difference]: With dead ends: 137 [2018-11-07 05:05:50,824 INFO L226 Difference]: Without dead ends: 106 [2018-11-07 05:05:50,826 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 89 SyntacticMatches, 16 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 445 ImplicationChecksByTransitivity, 11.3s TimeCoverageRelationStatistics Valid=217, Invalid=1760, Unknown=3, NotChecked=0, Total=1980 [2018-11-07 05:05:50,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2018-11-07 05:05:50,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 78. [2018-11-07 05:05:50,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2018-11-07 05:05:50,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 79 transitions. [2018-11-07 05:05:50,844 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 79 transitions. Word has length 61 [2018-11-07 05:05:50,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:05:50,845 INFO L480 AbstractCegarLoop]: Abstraction has 78 states and 79 transitions. [2018-11-07 05:05:50,845 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-11-07 05:05:50,845 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 79 transitions. [2018-11-07 05:05:50,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2018-11-07 05:05:50,847 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:05:50,847 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:05:50,847 INFO L423 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:05:50,848 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:05:50,848 INFO L82 PathProgramCache]: Analyzing trace with hash -723282185, now seen corresponding path program 4 times [2018-11-07 05:05:50,848 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:05:50,849 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:05:50,849 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:05:50,849 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:05:50,849 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:05:50,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:05:51,393 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 6 proven. 98 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2018-11-07 05:05:51,394 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:05:51,394 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:05:51,394 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:05:51,394 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:05:51,394 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:05:51,394 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:05:51,404 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:05:51,404 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:05:51,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:05:51,439 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:05:51,574 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 17 treesize of output 14 [2018-11-07 05:05:51,576 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 14 treesize of output 13 [2018-11-07 05:05:51,576 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:51,583 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:51,599 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:51,599 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-11-07 05:05:51,687 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 35 treesize of output 30 [2018-11-07 05:05:51,707 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:05:51,709 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:05:51,730 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:51,774 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:51,775 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:05:51,894 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 35 treesize of output 30 [2018-11-07 05:05:51,916 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:05:51,917 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:05:51,942 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:51,996 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:51,997 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:05:52,121 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 35 treesize of output 30 [2018-11-07 05:05:52,147 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:05:52,148 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:05:52,164 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:52,189 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:52,189 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:05:53,196 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 27 [2018-11-07 05:05:53,211 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:05:53,211 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2018-11-07 05:05:53,212 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:53,219 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:05:53,231 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:05:53,232 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:55, output treesize:32 [2018-11-07 05:05:53,388 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 0 proven. 113 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-11-07 05:05:53,388 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:05:53,951 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 20 treesize of output 18 [2018-11-07 05:05:53,965 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 9 treesize of output 5 [2018-11-07 05:05:53,967 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:05:53,972 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:05:53,978 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-11-07 05:05:53,979 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:13 [2018-11-07 05:05:55,932 WARN L179 SmtUtils]: Spent 1.82 s on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-11-07 05:05:56,842 WARN L179 SmtUtils]: Spent 850.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-11-07 05:05:57,857 WARN L179 SmtUtils]: Spent 858.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-11-07 05:05:59,132 WARN L179 SmtUtils]: Spent 811.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-11-07 05:05:59,157 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 6 proven. 107 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-11-07 05:05:59,177 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:05:59,177 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 17, 17] total 38 [2018-11-07 05:05:59,177 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:05:59,178 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-11-07 05:05:59,178 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-11-07 05:05:59,178 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=1271, Unknown=0, NotChecked=0, Total=1406 [2018-11-07 05:05:59,179 INFO L87 Difference]: Start difference. First operand 78 states and 79 transitions. Second operand 23 states. [2018-11-07 05:06:24,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:06:24,540 INFO L93 Difference]: Finished difference Result 161 states and 168 transitions. [2018-11-07 05:06:24,540 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-11-07 05:06:24,540 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 75 [2018-11-07 05:06:24,541 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:06:24,541 INFO L225 Difference]: With dead ends: 161 [2018-11-07 05:06:24,542 INFO L226 Difference]: Without dead ends: 120 [2018-11-07 05:06:24,543 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 107 SyntacticMatches, 18 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 598 ImplicationChecksByTransitivity, 11.4s TimeCoverageRelationStatistics Valid=238, Invalid=2211, Unknown=1, NotChecked=0, Total=2450 [2018-11-07 05:06:24,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-11-07 05:06:24,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 92. [2018-11-07 05:06:24,561 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2018-11-07 05:06:24,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 93 transitions. [2018-11-07 05:06:24,562 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 93 transitions. Word has length 75 [2018-11-07 05:06:24,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:06:24,562 INFO L480 AbstractCegarLoop]: Abstraction has 92 states and 93 transitions. [2018-11-07 05:06:24,562 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-11-07 05:06:24,563 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 93 transitions. [2018-11-07 05:06:24,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2018-11-07 05:06:24,564 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:06:24,564 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:06:24,564 INFO L423 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:06:24,565 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:06:24,565 INFO L82 PathProgramCache]: Analyzing trace with hash -1888574225, now seen corresponding path program 5 times [2018-11-07 05:06:24,565 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:06:24,566 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:06:24,566 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:06:24,566 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:06:24,566 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:06:24,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:06:24,872 INFO L134 CoverageAnalysis]: Checked inductivity of 212 backedges. 8 proven. 128 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2018-11-07 05:06:24,873 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:06:24,873 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:06:24,873 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:06:24,873 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:06:24,873 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:06:24,873 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-11-07 05:06:24,883 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:06:24,883 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:07:39,117 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-11-07 05:07:39,117 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:07:39,229 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:39,495 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 17 treesize of output 14 [2018-11-07 05:07:39,509 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 14 treesize of output 13 [2018-11-07 05:07:39,510 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:39,521 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:39,537 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:07:39,537 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-11-07 05:07:39,638 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 35 treesize of output 30 [2018-11-07 05:07:39,654 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:07:39,655 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:07:39,813 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:39,957 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:07:39,958 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:07:40,662 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 35 treesize of output 30 [2018-11-07 05:07:40,854 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:07:40,855 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:07:40,999 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:41,134 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-11-07 05:07:41,135 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 05:07:41,306 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 35 treesize of output 30 [2018-11-07 05:07:41,326 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 30 treesize of output 50 [2018-11-07 05:07:41,328 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-07 05:07:41,343 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:41,372 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:07:41,372 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:63, output treesize:56 [2018-11-07 05:07:50,838 WARN L179 SmtUtils]: Spent 554.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2018-11-07 05:08:22,163 WARN L179 SmtUtils]: Spent 4.36 s on a formula simplification that was a NOOP. DAG size: 75 Received shutdown request... [2018-11-07 05:08:31,507 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-07 05:08:31,708 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:08:31,709 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-07 05:08:31,714 WARN L205 ceAbstractionStarter]: Timeout [2018-11-07 05:08:31,714 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.11 05:08:31 BoogieIcfgContainer [2018-11-07 05:08:31,714 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-07 05:08:31,715 INFO L168 Benchmark]: Toolchain (without parser) took 282814.10 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 972.6 MB). Free memory was 1.4 GB in the beginning and 1.8 GB in the end (delta: -322.9 MB). Peak memory consumption was 649.6 MB. Max. memory is 7.1 GB. [2018-11-07 05:08:31,715 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-11-07 05:08:31,716 INFO L168 Benchmark]: CACSL2BoogieTranslator took 309.12 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-11-07 05:08:31,716 INFO L168 Benchmark]: Boogie Procedure Inliner took 21.69 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-11-07 05:08:31,717 INFO L168 Benchmark]: Boogie Preprocessor took 23.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-11-07 05:08:31,717 INFO L168 Benchmark]: RCFGBuilder took 579.49 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 759.2 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -805.9 MB). Peak memory consumption was 14.8 MB. Max. memory is 7.1 GB. [2018-11-07 05:08:31,718 INFO L168 Benchmark]: TraceAbstraction took 281876.11 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 213.4 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 472.4 MB). Peak memory consumption was 685.8 MB. Max. memory is 7.1 GB. [2018-11-07 05:08:31,720 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 309.12 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 21.69 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 23.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 579.49 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 759.2 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -805.9 MB). Peak memory consumption was 14.8 MB. Max. memory is 7.1 GB. * TraceAbstraction took 281876.11 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 213.4 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 472.4 MB). Peak memory consumption was 685.8 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 12]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 12). Cancelled while BasicCegarLoop was analyzing trace of length 90 with TraceHistMax 9,while TraceCheckSpWp was constructing forward predicates,while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 24 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 30 locations, 1 error locations. TIMEOUT Result, 281.8s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 101.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 280 SDtfs, 530 SDslu, 2043 SDs, 0 SdLazy, 2951 SolverSat, 231 SolverUnsat, 32 SolverUnknown, 0 SolverNotchecked, 79.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 690 GetRequests, 415 SyntacticMatches, 63 SemanticMatches, 212 ConstructedPredicates, 1 IntricatePredicates, 3 DeprecatedPredicates, 1981 ImplicationChecksByTransitivity, 62.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=92occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 1.1s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 170 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 50.5s InterpolantComputationTime, 605 NumberOfCodeBlocks, 605 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 871 ConstructedInterpolants, 152 QuantifiedInterpolants, 645857 SizeOfPredicates, 90 NumberOfNonLiveVariables, 654 ConjunctsInSsa, 154 ConjunctsInUnsatCore, 20 InterpolantComputations, 2 PerfectInterpolantSequences, 296/1110 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown