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-INT-LIM.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 22:10:05,078 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-07 22:10:05,080 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-07 22:10:05,099 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-07 22:10:05,100 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-07 22:10:05,101 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-07 22:10:05,103 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-07 22:10:05,105 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-07 22:10:05,108 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-07 22:10:05,109 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-07 22:10:05,110 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-07 22:10:05,113 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-07 22:10:05,115 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-07 22:10:05,116 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-07 22:10:05,119 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-07 22:10:05,126 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-07 22:10:05,127 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-07 22:10:05,130 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-07 22:10:05,133 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-07 22:10:05,138 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-07 22:10:05,139 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-07 22:10:05,140 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-07 22:10:05,143 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-07 22:10:05,144 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-07 22:10:05,144 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-07 22:10:05,145 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-07 22:10:05,146 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-07 22:10:05,147 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-07 22:10:05,147 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-07 22:10:05,148 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-07 22:10:05,149 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-07 22:10:05,149 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-07 22:10:05,149 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-07 22:10:05,151 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-07 22:10:05,153 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-07 22:10:05,153 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-07 22:10:05,154 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-INT-LIM.epf [2018-11-07 22:10:05,178 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-07 22:10:05,178 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-07 22:10:05,179 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-07 22:10:05,179 INFO L133 SettingsManager]: * User list type=DISABLED [2018-11-07 22:10:05,179 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-11-07 22:10:05,180 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-11-07 22:10:05,180 INFO L133 SettingsManager]: * Maximum recursion depth of evaluation operations=6 [2018-11-07 22:10:05,180 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-11-07 22:10:05,180 INFO L133 SettingsManager]: * Octagon Domain=false [2018-11-07 22:10:05,180 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-11-07 22:10:05,181 INFO L133 SettingsManager]: * Log string format=TERM [2018-11-07 22:10:05,181 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-11-07 22:10:05,181 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-11-07 22:10:05,182 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-07 22:10:05,182 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-07 22:10:05,182 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-07 22:10:05,182 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-07 22:10:05,182 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-07 22:10:05,183 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-07 22:10:05,183 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-07 22:10:05,183 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-07 22:10:05,183 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-07 22:10:05,183 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-07 22:10:05,184 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-07 22:10:05,184 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-07 22:10:05,184 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-07 22:10:05,184 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-07 22:10:05,184 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-07 22:10:05,184 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-07 22:10:05,185 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-11-07 22:10:05,185 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-07 22:10:05,185 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-07 22:10:05,185 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-07 22:10:05,185 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-07 22:10:05,186 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-11-07 22:10:05,233 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-07 22:10:05,253 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-07 22:10:05,257 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-07 22:10:05,259 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-07 22:10:05,259 INFO L276 PluginConnector]: CDTParser initialized [2018-11-07 22:10:05,260 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 22:10:05,325 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/815510f71/70a9cc12384c41278f30082ee1a37e33/FLAG91a1abe14 [2018-11-07 22:10:05,830 INFO L298 CDTParser]: Found 1 translation units. [2018-11-07 22:10:05,830 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 22:10:05,837 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/815510f71/70a9cc12384c41278f30082ee1a37e33/FLAG91a1abe14 [2018-11-07 22:10:05,852 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/815510f71/70a9cc12384c41278f30082ee1a37e33 [2018-11-07 22:10:05,863 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-07 22:10:05,865 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-07 22:10:05,866 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-07 22:10:05,866 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-07 22:10:05,870 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-07 22:10:05,871 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 10:10:05" (1/1) ... [2018-11-07 22:10:05,874 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@20bce090 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:05, skipping insertion in model container [2018-11-07 22:10:05,874 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 10:10:05" (1/1) ... [2018-11-07 22:10:05,884 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-07 22:10:05,906 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-07 22:10:06,097 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 22:10:06,101 INFO L189 MainTranslator]: Completed pre-run [2018-11-07 22:10:06,132 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 22:10:06,160 INFO L193 MainTranslator]: Completed translation [2018-11-07 22:10:06,160 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06 WrapperNode [2018-11-07 22:10:06,161 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-07 22:10:06,162 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-07 22:10:06,163 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-07 22:10:06,163 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-07 22:10:06,173 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,186 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,194 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-07 22:10:06,194 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-07 22:10:06,194 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-07 22:10:06,195 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-07 22:10:06,210 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,210 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,213 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,214 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,230 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,245 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,246 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (1/1) ... [2018-11-07 22:10:06,249 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-07 22:10:06,250 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-07 22:10:06,250 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-07 22:10:06,250 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-07 22:10:06,251 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (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 22:10:06,412 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2018-11-07 22:10:06,413 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-07 22:10:06,413 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-07 22:10:06,413 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-11-07 22:10:06,413 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-07 22:10:06,413 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-07 22:10:06,413 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-07 22:10:06,413 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-07 22:10:06,414 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2018-11-07 22:10:06,414 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-11-07 22:10:06,414 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-11-07 22:10:06,414 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-11-07 22:10:06,779 INFO L276 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-07 22:10:06,779 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 10:10:06 BoogieIcfgContainer [2018-11-07 22:10:06,780 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-07 22:10:06,780 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-07 22:10:06,780 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-07 22:10:06,783 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-07 22:10:06,783 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.11 10:10:05" (1/3) ... [2018-11-07 22:10:06,784 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c04f303 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 10:10:06, skipping insertion in model container [2018-11-07 22:10:06,784 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 10:10:06" (2/3) ... [2018-11-07 22:10:06,785 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c04f303 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 10:10:06, skipping insertion in model container [2018-11-07 22:10:06,785 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 10:10:06" (3/3) ... [2018-11-07 22:10:06,787 INFO L112 eAbstractionObserver]: Analyzing ICFG simple_array_index_value_true-unreach-call2_true-termination.i [2018-11-07 22:10:06,797 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-07 22:10:06,805 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-07 22:10:06,823 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-07 22:10:06,857 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-07 22:10:06,858 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-07 22:10:06,858 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-07 22:10:06,858 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-07 22:10:06,858 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-07 22:10:06,858 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-07 22:10:06,859 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-07 22:10:06,859 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-07 22:10:06,879 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states. [2018-11-07 22:10:06,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-11-07 22:10:06,885 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:10:06,886 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 22:10:06,888 INFO L423 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:10:06,893 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:06,894 INFO L82 PathProgramCache]: Analyzing trace with hash 1868031892, now seen corresponding path program 1 times [2018-11-07 22:10:06,897 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:10:06,953 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:06,954 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:10:06,954 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:06,954 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:10:06,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:07,039 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 22:10:07,041 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 22:10:07,041 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-07 22:10:07,042 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 22:10:07,046 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-07 22:10:07,060 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-07 22:10:07,061 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-07 22:10:07,063 INFO L87 Difference]: Start difference. First operand 30 states. Second operand 2 states. [2018-11-07 22:10:07,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:10:07,086 INFO L93 Difference]: Finished difference Result 49 states and 56 transitions. [2018-11-07 22:10:07,086 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-07 22:10:07,087 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 16 [2018-11-07 22:10:07,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:10:07,097 INFO L225 Difference]: With dead ends: 49 [2018-11-07 22:10:07,097 INFO L226 Difference]: Without dead ends: 24 [2018-11-07 22:10:07,100 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 22:10:07,120 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2018-11-07 22:10:07,135 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2018-11-07 22:10:07,136 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-11-07 22:10:07,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 25 transitions. [2018-11-07 22:10:07,139 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 25 transitions. Word has length 16 [2018-11-07 22:10:07,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:10:07,140 INFO L480 AbstractCegarLoop]: Abstraction has 24 states and 25 transitions. [2018-11-07 22:10:07,140 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-07 22:10:07,140 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 25 transitions. [2018-11-07 22:10:07,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-11-07 22:10:07,141 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:10:07,141 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 22:10:07,142 INFO L423 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:10:07,142 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:07,142 INFO L82 PathProgramCache]: Analyzing trace with hash 255747955, now seen corresponding path program 1 times [2018-11-07 22:10:07,142 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:10:07,143 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:07,143 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:10:07,144 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:07,144 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:10:07,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:07,236 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 22:10:07,236 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 22:10:07,236 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-07 22:10:07,237 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 22:10:07,238 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-11-07 22:10:07,239 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-11-07 22:10:07,239 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-07 22:10:07,239 INFO L87 Difference]: Start difference. First operand 24 states and 25 transitions. Second operand 3 states. [2018-11-07 22:10:07,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:10:07,346 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2018-11-07 22:10:07,346 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-07 22:10:07,346 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 17 [2018-11-07 22:10:07,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:10:07,349 INFO L225 Difference]: With dead ends: 47 [2018-11-07 22:10:07,349 INFO L226 Difference]: Without dead ends: 34 [2018-11-07 22:10:07,350 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 22:10:07,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-11-07 22:10:07,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2018-11-07 22:10:07,360 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-11-07 22:10:07,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2018-11-07 22:10:07,361 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 17 [2018-11-07 22:10:07,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:10:07,362 INFO L480 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2018-11-07 22:10:07,362 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-11-07 22:10:07,362 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2018-11-07 22:10:07,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-11-07 22:10:07,363 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:10:07,363 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 22:10:07,363 INFO L423 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:10:07,364 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:07,364 INFO L82 PathProgramCache]: Analyzing trace with hash -1253038918, now seen corresponding path program 1 times [2018-11-07 22:10:07,364 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:10:07,365 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:07,365 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:10:07,366 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:07,366 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:10:07,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:07,488 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 22:10:07,489 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:10:07,489 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:10:07,490 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 22 with the following transitions: [2018-11-07 22:10:07,492 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 22:10:07,530 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, IntervalDomain] [2018-11-07 22:10:07,530 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 22:10:07,666 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-07 22:10:07,868 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 22:10:07,873 INFO L272 AbstractInterpreter]: Visited 20 different actions 60 times. Merged at 5 different actions 33 times. Widened at 1 different actions 3 times. Found 6 fixpoints after 2 different actions. Largest state had 17 variables. [2018-11-07 22:10:07,929 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:07,931 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 22:10:07,933 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:10:07,933 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 22:10:07,949 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:10:07,950 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 22:10:07,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:07,988 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:10:08,156 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 22:10:08,162 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 22:10:08,163 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:08,177 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:08,202 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 22:10:08,202 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:17, output treesize:9 [2018-11-07 22:10:08,316 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 22:10:08,322 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 22:10:08,324 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 22:10:08,324 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:08,330 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:08,336 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 22:10:08,337 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:26, output treesize:9 [2018-11-07 22:10:08,518 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 22:10:08,518 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 22:10:08,732 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 22:10:08,828 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 22:10:08,830 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:08,835 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 22:10:08,890 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 22:10:08,890 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:13 [2018-11-07 22:10:10,877 WARN L179 SmtUtils]: Spent 1.85 s on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-11-07 22:10:10,904 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 22:10:10,932 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 22:10:10,932 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 9, 9] total 16 [2018-11-07 22:10:10,932 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 22:10:10,933 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-11-07 22:10:10,933 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-11-07 22:10:10,934 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=197, Unknown=0, NotChecked=0, Total=240 [2018-11-07 22:10:10,934 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand 10 states. [2018-11-07 22:10:11,700 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:10:11,701 INFO L93 Difference]: Finished difference Result 83 states and 91 transitions. [2018-11-07 22:10:11,702 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-11-07 22:10:11,703 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-11-07 22:10:11,703 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:10:11,705 INFO L225 Difference]: With dead ends: 83 [2018-11-07 22:10:11,705 INFO L226 Difference]: Without dead ends: 70 [2018-11-07 22:10:11,706 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=71, Invalid=309, Unknown=0, NotChecked=0, Total=380 [2018-11-07 22:10:11,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-11-07 22:10:11,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 43. [2018-11-07 22:10:11,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-11-07 22:10:11,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 45 transitions. [2018-11-07 22:10:11,717 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 45 transitions. Word has length 21 [2018-11-07 22:10:11,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:10:11,717 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 45 transitions. [2018-11-07 22:10:11,717 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-11-07 22:10:11,718 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 45 transitions. [2018-11-07 22:10:11,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-11-07 22:10:11,719 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:10:11,719 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 22:10:11,719 INFO L423 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:10:11,720 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:11,720 INFO L82 PathProgramCache]: Analyzing trace with hash 2321608, now seen corresponding path program 2 times [2018-11-07 22:10:11,720 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:10:11,721 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:11,722 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:10:11,722 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:11,722 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:10:11,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:12,002 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 22:10:12,002 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:10:12,002 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:10:12,003 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 22:10:12,003 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 22:10:12,003 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:10:12,003 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 22:10:12,018 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 22:10:12,018 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 22:10:12,046 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-11-07 22:10:12,046 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 22:10:12,051 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:10:12,127 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 22:10:12,130 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 22:10:12,131 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,135 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,144 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 22:10:12,144 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:17, output treesize:9 [2018-11-07 22:10:12,189 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 22:10:12,240 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 22:10:12,246 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-07 22:10:12,266 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,278 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 22:10:12,278 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:34, output treesize:27 [2018-11-07 22:10:12,344 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 22:10:12,371 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 22:10:12,378 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-07 22:10:12,393 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,411 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 22:10:12,411 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:34, output treesize:27 [2018-11-07 22:10:12,476 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 22:10:12,483 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 22:10:12,484 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 22:10:12,484 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,499 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,509 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 22:10:12,510 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:26, output treesize:9 [2018-11-07 22:10:12,585 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 22:10:12,585 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 22:10:12,873 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 22:10:12,894 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 22:10:12,896 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:12,901 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 22:10:12,910 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 22:10:12,910 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:13 [2018-11-07 22:10:14,791 WARN L179 SmtUtils]: Spent 1.82 s on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-11-07 22:10:14,803 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 22:10:14,824 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 22:10:14,824 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 10, 10] total 20 [2018-11-07 22:10:14,824 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 22:10:14,824 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-11-07 22:10:14,825 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-11-07 22:10:14,825 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=325, Unknown=0, NotChecked=0, Total=380 [2018-11-07 22:10:14,825 INFO L87 Difference]: Start difference. First operand 43 states and 45 transitions. Second operand 13 states. [2018-11-07 22:10:15,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:10:15,962 INFO L93 Difference]: Finished difference Result 90 states and 97 transitions. [2018-11-07 22:10:15,967 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-11-07 22:10:15,967 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 29 [2018-11-07 22:10:15,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:10:15,969 INFO L225 Difference]: With dead ends: 90 [2018-11-07 22:10:15,969 INFO L226 Difference]: Without dead ends: 68 [2018-11-07 22:10:15,970 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 22:10:15,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2018-11-07 22:10:15,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 46. [2018-11-07 22:10:15,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-11-07 22:10:15,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-11-07 22:10:15,980 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 29 [2018-11-07 22:10:15,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:10:15,980 INFO L480 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-11-07 22:10:15,980 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-11-07 22:10:15,980 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-11-07 22:10:15,982 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-11-07 22:10:15,982 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:10:15,982 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 22:10:15,982 INFO L423 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:10:15,982 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:15,982 INFO L82 PathProgramCache]: Analyzing trace with hash 41131456, now seen corresponding path program 1 times [2018-11-07 22:10:15,983 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:10:15,983 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:15,984 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 22:10:15,984 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:10:15,984 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:10:16,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:16,284 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 22:10:16,285 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:10:16,285 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:10:16,285 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 44 with the following transitions: [2018-11-07 22:10:16,285 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 22:10:16,289 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, IntervalDomain] [2018-11-07 22:10:16,290 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 22:10:16,311 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-11-07 22:10:16,573 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 22:10:16,573 INFO L272 AbstractInterpreter]: Visited 25 different actions 149 times. Merged at 11 different actions 75 times. Widened at 2 different actions 6 times. Found 7 fixpoints after 3 different actions. Largest state had 18 variables. [2018-11-07 22:10:16,604 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:10:16,605 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 22:10:16,605 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:10:16,605 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 22:10:16,618 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:10:16,618 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 22:10:16,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:10:16,659 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:10:16,952 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 22:10:16,956 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 22:10:16,957 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:16,982 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:17,003 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 22:10:17,004 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:47, output treesize:40 [2018-11-07 22:10:17,090 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 22:10:17,110 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 22:10:17,113 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 22:10:17,133 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:19,199 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 22:10:19,200 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:64, output treesize:57 [2018-11-07 22:10:19,393 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 22:10:19,412 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 22:10:19,415 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 22:10:19,433 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:21,486 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 22:10:21,487 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:64, output treesize:57 [2018-11-07 22:10:27,939 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 32 [2018-11-07 22:10:28,027 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 22:10:28,053 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 22:10:28,055 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 22:10:28,055 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:28,073 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:10:28,146 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 22:10:28,146 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:56, output treesize:33 [2018-11-07 22:10:28,563 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 22:10:28,564 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 22:10:31,070 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 22:10:31,125 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 22:10:31,126 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:10:31,133 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 22:10:31,138 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 22:10:31,138 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:13 [2018-11-07 22:10:32,188 WARN L179 SmtUtils]: Spent 945.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 11 [2018-11-07 22:10:33,110 WARN L179 SmtUtils]: Spent 825.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-11-07 22:10:33,235 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 22:10:33,255 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 22:10:33,256 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 14, 13] total 28 [2018-11-07 22:10:33,256 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 22:10:33,256 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-11-07 22:10:33,256 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-11-07 22:10:33,257 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=656, Unknown=4, NotChecked=0, Total=756 [2018-11-07 22:10:33,257 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 17 states. [2018-11-07 22:10:40,494 WARN L179 SmtUtils]: Spent 2.09 s on a formula simplification that was a NOOP. DAG size: 58 [2018-11-07 22:10:40,846 WARN L179 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 41 [2018-11-07 22:10:43,783 WARN L179 SmtUtils]: Spent 2.07 s on a formula simplification that was a NOOP. DAG size: 57 [2018-11-07 22:10:46,023 WARN L179 SmtUtils]: Spent 2.10 s on a formula simplification that was a NOOP. DAG size: 62 [2018-11-07 22:11:07,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:11:07,503 INFO L93 Difference]: Finished difference Result 105 states and 111 transitions. [2018-11-07 22:11:07,614 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-11-07 22:11:07,615 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 43 [2018-11-07 22:11:07,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:11:07,616 INFO L225 Difference]: With dead ends: 105 [2018-11-07 22:11:07,616 INFO L226 Difference]: Without dead ends: 84 [2018-11-07 22:11:07,618 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 59 SyntacticMatches, 12 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 20.1s TimeCoverageRelationStatistics Valid=181, Invalid=1221, Unknown=4, NotChecked=0, Total=1406 [2018-11-07 22:11:07,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2018-11-07 22:11:07,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 60. [2018-11-07 22:11:07,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-11-07 22:11:07,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 61 transitions. [2018-11-07 22:11:07,631 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 61 transitions. Word has length 43 [2018-11-07 22:11:07,631 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:11:07,631 INFO L480 AbstractCegarLoop]: Abstraction has 60 states and 61 transitions. [2018-11-07 22:11:07,631 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-11-07 22:11:07,632 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 61 transitions. [2018-11-07 22:11:07,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2018-11-07 22:11:07,633 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:11:07,634 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 22:11:07,634 INFO L423 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:11:07,634 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:11:07,634 INFO L82 PathProgramCache]: Analyzing trace with hash 115368056, now seen corresponding path program 2 times [2018-11-07 22:11:07,634 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:11:07,635 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:11:07,636 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:11:07,636 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:11:07,636 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:11:07,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:11:07,891 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 22:11:07,891 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:11:07,891 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:11:07,891 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 22:11:07,892 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 22:11:07,892 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:11:07,892 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 22:11:07,901 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 22:11:07,901 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 22:11:08,231 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-11-07 22:11:08,231 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 22:11:08,237 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:11:08,358 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 22:11:08,362 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 22:11:08,362 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:08,364 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:08,379 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 22:11:08,380 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-11-07 22:11:08,439 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 22:11:08,445 INFO L700 Elim1Store]: detected not equals via solver [2018-11-07 22:11:08,447 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 22:11:08,448 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:08,454 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:08,464 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 22:11:08,464 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:18 [2018-11-07 22:11:08,551 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 22:11:08,556 INFO L700 Elim1Store]: detected not equals via solver [2018-11-07 22:11:08,559 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 22:11:08,560 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:08,572 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:08,587 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 22:11:08,587 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:35 [2018-11-07 22:11:08,696 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 22:11:08,696 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 22:11:09,867 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 22:11:09,885 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 22:11:09,886 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:09,890 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:09,897 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 22:11:09,897 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:15 [2018-11-07 22:11:12,764 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 4 proven. 64 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-07 22:11:12,784 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 22:11:12,784 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 13, 18] total 35 [2018-11-07 22:11:12,784 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 22:11:12,785 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-07 22:11:12,785 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-07 22:11:12,786 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=237, Invalid=953, Unknown=0, NotChecked=0, Total=1190 [2018-11-07 22:11:12,787 INFO L87 Difference]: Start difference. First operand 60 states and 61 transitions. Second operand 19 states. [2018-11-07 22:11:13,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:11:13,597 INFO L93 Difference]: Finished difference Result 123 states and 129 transitions. [2018-11-07 22:11:13,598 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-11-07 22:11:13,598 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 57 [2018-11-07 22:11:13,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:11:13,600 INFO L225 Difference]: With dead ends: 123 [2018-11-07 22:11:13,601 INFO L226 Difference]: Without dead ends: 92 [2018-11-07 22:11:13,602 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 83 SyntacticMatches, 7 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 460 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=315, Invalid=1245, Unknown=0, NotChecked=0, Total=1560 [2018-11-07 22:11:13,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-11-07 22:11:13,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 64. [2018-11-07 22:11:13,613 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-11-07 22:11:13,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 65 transitions. [2018-11-07 22:11:13,614 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 65 transitions. Word has length 57 [2018-11-07 22:11:13,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:11:13,614 INFO L480 AbstractCegarLoop]: Abstraction has 64 states and 65 transitions. [2018-11-07 22:11:13,615 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-07 22:11:13,615 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 65 transitions. [2018-11-07 22:11:13,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2018-11-07 22:11:13,616 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:11:13,617 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 22:11:13,617 INFO L423 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:11:13,617 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:11:13,617 INFO L82 PathProgramCache]: Analyzing trace with hash -937620801, now seen corresponding path program 3 times [2018-11-07 22:11:13,617 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:11:13,618 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:11:13,618 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 22:11:13,618 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:11:13,619 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:11:13,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:11:13,852 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 22:11:13,852 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:11:13,853 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:11:13,853 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 22:11:13,853 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 22:11:13,853 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:11:13,853 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 22:11:13,865 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 22:11:13,865 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 22:11:13,904 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 22:11:13,904 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 22:11:13,908 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:11:14,051 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 22:11:14,053 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 22:11:14,053 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:14,056 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:14,072 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 22:11:14,072 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-11-07 22:11:14,169 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 22:11:14,188 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 22:11:14,190 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 22:11:14,205 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:14,237 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 22:11:14,237 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:11:14,318 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 22:11:14,337 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 22:11:14,338 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 22:11:14,355 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:14,380 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 22:11:14,381 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:11:14,512 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 22:11:14,538 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 22:11:14,539 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 22:11:14,559 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:14,583 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 22:11:14,584 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:11:15,511 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 22:11:15,517 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 22:11:15,518 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 22:11:15,518 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:15,525 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:15,539 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 22:11:15,539 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:55, output treesize:32 [2018-11-07 22:11:15,683 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 22:11:15,683 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 22:11:16,130 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 22:11:16,150 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 22:11:16,152 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:16,156 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 22:11:16,185 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 22:11:16,186 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:13 [2018-11-07 22:11:18,117 WARN L179 SmtUtils]: Spent 1.76 s on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-11-07 22:11:24,596 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 22:11:24,615 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 22:11:24,615 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 15, 15] total 33 [2018-11-07 22:11:24,615 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 22:11:24,616 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-11-07 22:11:24,616 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-11-07 22:11:24,617 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=939, Unknown=3, NotChecked=0, Total=1056 [2018-11-07 22:11:24,617 INFO L87 Difference]: Start difference. First operand 64 states and 65 transitions. Second operand 20 states. [2018-11-07 22:11:42,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:11:42,141 INFO L93 Difference]: Finished difference Result 137 states and 144 transitions. [2018-11-07 22:11:42,142 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-11-07 22:11:42,142 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 61 [2018-11-07 22:11:42,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:11:42,144 INFO L225 Difference]: With dead ends: 137 [2018-11-07 22:11:42,145 INFO L226 Difference]: Without dead ends: 106 [2018-11-07 22:11:42,146 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 86 SyntacticMatches, 16 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 445 ImplicationChecksByTransitivity, 14.2s TimeCoverageRelationStatistics Valid=217, Invalid=1759, Unknown=4, NotChecked=0, Total=1980 [2018-11-07 22:11:42,146 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2018-11-07 22:11:42,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 78. [2018-11-07 22:11:42,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2018-11-07 22:11:42,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 79 transitions. [2018-11-07 22:11:42,162 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 79 transitions. Word has length 61 [2018-11-07 22:11:42,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:11:42,162 INFO L480 AbstractCegarLoop]: Abstraction has 78 states and 79 transitions. [2018-11-07 22:11:42,162 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-11-07 22:11:42,162 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 79 transitions. [2018-11-07 22:11:42,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2018-11-07 22:11:42,164 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:11:42,164 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 22:11:42,165 INFO L423 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:11:42,165 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:11:42,165 INFO L82 PathProgramCache]: Analyzing trace with hash -723282185, now seen corresponding path program 4 times [2018-11-07 22:11:42,165 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:11:42,166 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:11:42,166 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 22:11:42,166 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:11:42,166 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:11:42,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:11:42,417 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 22:11:42,417 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:11:42,417 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:11:42,417 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 22:11:42,418 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 22:11:42,418 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:11:42,418 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 22:11:42,432 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:11:42,432 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 22:11:42,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:11:42,476 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:11:42,647 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 22:11:42,651 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 22:11:42,652 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:42,656 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:42,672 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 22:11:42,673 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-11-07 22:11:42,777 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 22:11:42,802 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 22:11:42,804 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 22:11:42,821 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:42,853 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 22:11:42,854 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:11:42,964 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 22:11:42,984 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 22:11:42,986 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 22:11:43,000 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:43,024 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 22:11:43,024 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:11:43,167 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 22:11:43,186 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 22:11:43,187 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 22:11:43,202 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:43,234 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 22:11:43,234 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:11:46,880 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 22:11:46,884 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 22:11:46,885 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 22:11:46,885 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:46,893 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:11:46,904 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 22:11:46,905 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:55, output treesize:32 [2018-11-07 22:11:47,067 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 4 proven. 113 refuted. 4 times theorem prover too weak. 25 trivial. 0 not checked. [2018-11-07 22:11:47,068 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 22:11:47,890 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 22:11:47,905 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 22:11:47,906 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:11:47,911 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-07 22:11:47,917 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 22:11:47,917 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:13 [2018-11-07 22:11:52,006 WARN L179 SmtUtils]: Spent 3.93 s on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-11-07 22:11:53,002 WARN L179 SmtUtils]: Spent 934.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-11-07 22:11:54,034 WARN L179 SmtUtils]: Spent 906.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-11-07 22:11:54,193 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 22:11:54,213 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 22:11:54,213 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 18, 17] total 39 [2018-11-07 22:11:54,213 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 22:11:54,213 INFO L459 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-11-07 22:11:54,214 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-11-07 22:11:54,214 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=145, Invalid=1336, Unknown=1, NotChecked=0, Total=1482 [2018-11-07 22:11:54,214 INFO L87 Difference]: Start difference. First operand 78 states and 79 transitions. Second operand 24 states. [2018-11-07 22:12:11,261 WARN L179 SmtUtils]: Spent 2.04 s on a formula simplification that was a NOOP. DAG size: 35 [2018-11-07 22:12:12,456 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 22:12:12,456 INFO L93 Difference]: Finished difference Result 161 states and 168 transitions. [2018-11-07 22:12:12,457 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-11-07 22:12:12,457 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 75 [2018-11-07 22:12:12,458 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 22:12:12,459 INFO L225 Difference]: With dead ends: 161 [2018-11-07 22:12:12,459 INFO L226 Difference]: Without dead ends: 120 [2018-11-07 22:12:12,461 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 107 SyntacticMatches, 17 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 645 ImplicationChecksByTransitivity, 15.5s TimeCoverageRelationStatistics Valid=260, Invalid=2289, Unknown=1, NotChecked=0, Total=2550 [2018-11-07 22:12:12,461 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-11-07 22:12:12,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 92. [2018-11-07 22:12:12,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2018-11-07 22:12:12,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 93 transitions. [2018-11-07 22:12:12,482 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 93 transitions. Word has length 75 [2018-11-07 22:12:12,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 22:12:12,483 INFO L480 AbstractCegarLoop]: Abstraction has 92 states and 93 transitions. [2018-11-07 22:12:12,483 INFO L481 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-11-07 22:12:12,483 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 93 transitions. [2018-11-07 22:12:12,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2018-11-07 22:12:12,484 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 22:12:12,484 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 22:12:12,485 INFO L423 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 22:12:12,485 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 22:12:12,485 INFO L82 PathProgramCache]: Analyzing trace with hash -1888574225, now seen corresponding path program 5 times [2018-11-07 22:12:12,485 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 22:12:12,486 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:12:12,486 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 22:12:12,486 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 22:12:12,486 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 22:12:12,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 22:12:13,120 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 22:12:13,120 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:12:13,120 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 22:12:13,120 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 22:12:13,121 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 22:12:13,121 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 22:12:13,121 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 22:12:13,129 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 22:12:13,129 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 22:13:26,018 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-11-07 22:13:26,019 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 22:13:26,054 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 22:13:26,250 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 22:13:26,263 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 22:13:26,263 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 22:13:26,265 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:13:26,321 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 22:13:26,322 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-11-07 22:13:26,418 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 22:13:26,433 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 22:13:26,434 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 22:13:26,575 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:13:26,725 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 22:13:26,726 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:13:27,442 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 22:13:27,616 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 22:13:27,617 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 22:13:27,769 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:13:27,925 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 22:13:27,926 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:63, output treesize:56 [2018-11-07 22:13:28,114 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 22:13:28,132 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 22:13:28,133 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 22:13:28,147 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 22:13:28,170 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 22:13:28,170 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:63, output treesize:56 [2018-11-07 22:13:31,428 WARN L179 SmtUtils]: Spent 2.14 s on a formula simplification that was a NOOP. DAG size: 41 Received shutdown request... [2018-11-07 22:14:45,750 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-07 22:14:45,951 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 22:14:45,952 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-07 22:14:45,957 WARN L205 ceAbstractionStarter]: Timeout [2018-11-07 22:14:45,957 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.11 10:14:45 BoogieIcfgContainer [2018-11-07 22:14:45,957 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-07 22:14:45,958 INFO L168 Benchmark]: Toolchain (without parser) took 280094.77 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 1.0 GB). Free memory was 1.4 GB in the beginning and 1.9 GB in the end (delta: -424.8 MB). Peak memory consumption was 575.5 MB. Max. memory is 7.1 GB. [2018-11-07 22:14:45,959 INFO L168 Benchmark]: CDTParser took 0.24 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 22:14:45,960 INFO L168 Benchmark]: CACSL2BoogieTranslator took 295.52 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 22:14:45,960 INFO L168 Benchmark]: Boogie Procedure Inliner took 32.45 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 22:14:45,960 INFO L168 Benchmark]: Boogie Preprocessor took 55.24 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 22:14:45,961 INFO L168 Benchmark]: RCFGBuilder took 529.81 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 764.4 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -810.1 MB). Peak memory consumption was 14.6 MB. Max. memory is 7.1 GB. [2018-11-07 22:14:45,961 INFO L168 Benchmark]: TraceAbstraction took 279177.28 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 235.9 MB). Free memory was 2.2 GB in the beginning and 1.9 GB in the end (delta: 374.7 MB). Peak memory consumption was 610.6 MB. Max. memory is 7.1 GB. [2018-11-07 22:14:45,964 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.24 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 295.52 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 32.45 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 55.24 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 529.81 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 764.4 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -810.1 MB). Peak memory consumption was 14.6 MB. Max. memory is 7.1 GB. * TraceAbstraction took 279177.28 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 235.9 MB). Free memory was 2.2 GB in the beginning and 1.9 GB in the end (delta: 374.7 MB). Peak memory consumption was 610.6 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 26 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 30 locations, 1 error locations. TIMEOUT Result, 279.1s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 73.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 278 SDtfs, 582 SDslu, 2078 SDs, 0 SdLazy, 3087 SolverSat, 280 SolverUnsat, 20 SolverUnknown, 0 SolverNotchecked, 54.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 681 GetRequests, 409 SyntacticMatches, 60 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 3 DeprecatedPredicates, 2063 ImplicationChecksByTransitivity, 60.2s 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, 0.7s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 165 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 50.5s InterpolantComputationTime, 605 NumberOfCodeBlocks, 605 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 871 ConstructedInterpolants, 150 QuantifiedInterpolants, 644401 SizeOfPredicates, 90 NumberOfNonLiveVariables, 654 ConjunctsInSsa, 154 ConjunctsInUnsatCore, 20 InterpolantComputations, 2 PerfectInterpolantSequences, 292/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