java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf -i ../../../trunk/examples/svcomp/loop-lit/mcmillan2006_true-unreach-call_true-termination.c.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-df4b876 [2018-11-07 05:07:21,230 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-07 05:07:21,233 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-07 05:07:21,245 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-07 05:07:21,246 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-07 05:07:21,247 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-07 05:07:21,248 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-07 05:07:21,250 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-07 05:07:21,251 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-07 05:07:21,252 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-07 05:07:21,253 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-07 05:07:21,253 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-07 05:07:21,254 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-07 05:07:21,255 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-07 05:07:21,257 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-07 05:07:21,257 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-07 05:07:21,258 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-07 05:07:21,260 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-07 05:07:21,262 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-07 05:07:21,264 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-07 05:07:21,265 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-07 05:07:21,266 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-07 05:07:21,268 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-07 05:07:21,269 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-07 05:07:21,269 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-07 05:07:21,270 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-07 05:07:21,271 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-07 05:07:21,272 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-07 05:07:21,273 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-07 05:07:21,274 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-07 05:07:21,274 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-07 05:07:21,275 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-07 05:07:21,275 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-07 05:07:21,275 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-07 05:07:21,277 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-07 05:07:21,280 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-07 05:07:21,280 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf [2018-11-07 05:07:21,295 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-07 05:07:21,296 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-07 05:07:21,296 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-07 05:07:21,297 INFO L133 SettingsManager]: * User list type=DISABLED [2018-11-07 05:07:21,297 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-11-07 05:07:21,297 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-11-07 05:07:21,297 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-11-07 05:07:21,297 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-11-07 05:07:21,298 INFO L133 SettingsManager]: * Log string format=TERM [2018-11-07 05:07:21,298 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-11-07 05:07:21,298 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-11-07 05:07:21,298 INFO L133 SettingsManager]: * Interval Domain=false [2018-11-07 05:07:21,299 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-07 05:07:21,299 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-07 05:07:21,299 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-07 05:07:21,299 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-07 05:07:21,300 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-07 05:07:21,300 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-07 05:07:21,300 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-07 05:07:21,301 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-07 05:07:21,302 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-07 05:07:21,302 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-07 05:07:21,302 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-07 05:07:21,302 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-07 05:07:21,302 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-07 05:07:21,303 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-07 05:07:21,303 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-07 05:07:21,303 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-07 05:07:21,303 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-11-07 05:07:21,304 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-07 05:07:21,304 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-07 05:07:21,304 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-07 05:07:21,304 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-07 05:07:21,304 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-11-07 05:07:21,361 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-07 05:07:21,380 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-07 05:07:21,385 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-07 05:07:21,386 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-07 05:07:21,387 INFO L276 PluginConnector]: CDTParser initialized [2018-11-07 05:07:21,387 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/loop-lit/mcmillan2006_true-unreach-call_true-termination.c.i [2018-11-07 05:07:21,452 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/07a73f724/622a4441c9e24b3f92a8795ec27225ec/FLAG8dc23d0b2 [2018-11-07 05:07:21,873 INFO L298 CDTParser]: Found 1 translation units. [2018-11-07 05:07:21,874 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loop-lit/mcmillan2006_true-unreach-call_true-termination.c.i [2018-11-07 05:07:21,880 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/07a73f724/622a4441c9e24b3f92a8795ec27225ec/FLAG8dc23d0b2 [2018-11-07 05:07:21,895 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/07a73f724/622a4441c9e24b3f92a8795ec27225ec [2018-11-07 05:07:21,907 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-07 05:07:21,909 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-07 05:07:21,911 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-07 05:07:21,911 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-07 05:07:21,917 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-07 05:07:21,918 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 05:07:21" (1/1) ... [2018-11-07 05:07:21,921 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4da35e62 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:21, skipping insertion in model container [2018-11-07 05:07:21,921 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.11 05:07:21" (1/1) ... [2018-11-07 05:07:21,932 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-07 05:07:21,957 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-07 05:07:22,209 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 05:07:22,224 INFO L189 MainTranslator]: Completed pre-run [2018-11-07 05:07:22,245 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-07 05:07:22,265 INFO L193 MainTranslator]: Completed translation [2018-11-07 05:07:22,266 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22 WrapperNode [2018-11-07 05:07:22,266 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-07 05:07:22,267 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-07 05:07:22,267 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-07 05:07:22,268 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-07 05:07:22,277 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,290 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,297 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-07 05:07:22,298 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-07 05:07:22,298 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-07 05:07:22,298 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-07 05:07:22,306 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,306 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,307 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,308 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,313 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,320 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,321 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... [2018-11-07 05:07:22,329 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-07 05:07:22,330 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-07 05:07:22,330 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-07 05:07:22,330 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-07 05:07:22,333 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-07 05:07:22,458 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-07 05:07:22,458 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-07 05:07:22,459 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2018-11-07 05:07:22,459 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-07 05:07:22,459 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-07 05:07:22,459 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-11-07 05:07:22,459 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-07 05:07:22,459 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-07 05:07:22,460 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2018-11-07 05:07:22,460 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-11-07 05:07:22,460 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-11-07 05:07:22,845 INFO L276 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-07 05:07:22,846 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 05:07:22 BoogieIcfgContainer [2018-11-07 05:07:22,846 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-07 05:07:22,847 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-07 05:07:22,847 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-07 05:07:22,850 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-07 05:07:22,850 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.11 05:07:21" (1/3) ... [2018-11-07 05:07:22,851 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2bc426f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 05:07:22, skipping insertion in model container [2018-11-07 05:07:22,851 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.11 05:07:22" (2/3) ... [2018-11-07 05:07:22,851 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2bc426f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.11 05:07:22, skipping insertion in model container [2018-11-07 05:07:22,852 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.11 05:07:22" (3/3) ... [2018-11-07 05:07:22,853 INFO L112 eAbstractionObserver]: Analyzing ICFG mcmillan2006_true-unreach-call_true-termination.c.i [2018-11-07 05:07:22,863 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-07 05:07:22,871 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-07 05:07:22,886 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-07 05:07:22,921 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-07 05:07:22,921 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-07 05:07:22,922 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-07 05:07:22,922 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-07 05:07:22,922 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-07 05:07:22,922 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-07 05:07:22,922 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-07 05:07:22,922 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-07 05:07:22,941 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states. [2018-11-07 05:07:22,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-11-07 05:07:22,948 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:22,949 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:22,951 INFO L423 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:22,957 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:22,957 INFO L82 PathProgramCache]: Analyzing trace with hash 849314513, now seen corresponding path program 1 times [2018-11-07 05:07:22,960 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:23,015 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:23,015 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:23,015 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:23,015 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:23,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:23,108 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:23,110 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 05:07:23,111 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-07 05:07:23,111 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:07:23,115 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-07 05:07:23,127 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-07 05:07:23,128 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-07 05:07:23,130 INFO L87 Difference]: Start difference. First operand 31 states. Second operand 2 states. [2018-11-07 05:07:23,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:23,152 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2018-11-07 05:07:23,153 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-07 05:07:23,154 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 18 [2018-11-07 05:07:23,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:23,162 INFO L225 Difference]: With dead ends: 49 [2018-11-07 05:07:23,162 INFO L226 Difference]: Without dead ends: 26 [2018-11-07 05:07:23,166 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-07 05:07:23,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2018-11-07 05:07:23,204 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-11-07 05:07:23,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-11-07 05:07:23,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2018-11-07 05:07:23,211 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 18 [2018-11-07 05:07:23,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:23,211 INFO L480 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2018-11-07 05:07:23,212 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-07 05:07:23,212 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2018-11-07 05:07:23,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-11-07 05:07:23,215 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:23,215 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:23,215 INFO L423 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:23,215 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:23,216 INFO L82 PathProgramCache]: Analyzing trace with hash -1258796197, now seen corresponding path program 1 times [2018-11-07 05:07:23,216 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:23,218 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:23,218 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:23,218 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:23,218 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:23,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:23,528 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:23,529 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-07 05:07:23,529 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-11-07 05:07:23,529 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-07 05:07:23,531 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-07 05:07:23,531 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-07 05:07:23,532 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-11-07 05:07:23,532 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand 5 states. [2018-11-07 05:07:23,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:23,698 INFO L93 Difference]: Finished difference Result 45 states and 47 transitions. [2018-11-07 05:07:23,700 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-07 05:07:23,700 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 19 [2018-11-07 05:07:23,700 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:23,701 INFO L225 Difference]: With dead ends: 45 [2018-11-07 05:07:23,701 INFO L226 Difference]: Without dead ends: 30 [2018-11-07 05:07:23,702 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-11-07 05:07:23,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-11-07 05:07:23,707 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 28. [2018-11-07 05:07:23,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 28 states. [2018-11-07 05:07:23,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 29 transitions. [2018-11-07 05:07:23,709 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 29 transitions. Word has length 19 [2018-11-07 05:07:23,709 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:23,710 INFO L480 AbstractCegarLoop]: Abstraction has 28 states and 29 transitions. [2018-11-07 05:07:23,710 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-07 05:07:23,710 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 29 transitions. [2018-11-07 05:07:23,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-11-07 05:07:23,711 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:23,711 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, 1, 1] [2018-11-07 05:07:23,711 INFO L423 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:23,712 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:23,712 INFO L82 PathProgramCache]: Analyzing trace with hash 11668962, now seen corresponding path program 1 times [2018-11-07 05:07:23,712 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:23,713 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:23,714 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:23,714 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:23,714 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:23,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:24,255 WARN L179 SmtUtils]: Spent 167.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 14 [2018-11-07 05:07:24,400 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:24,401 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:24,401 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:07:24,402 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 24 with the following transitions: [2018-11-07 05:07:24,404 INFO L202 CegarAbsIntRunner]: [0], [1], [5], [9], [10], [11], [15], [18], [20], [21], [23], [27], [31], [36], [37], [47], [50], [52], [58], [59], [60], [62] [2018-11-07 05:07:24,453 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-11-07 05:07:24,453 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 05:07:24,958 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 05:07:24,961 INFO L272 AbstractInterpreter]: Visited 22 different actions 95 times. Merged at 9 different actions 52 times. Widened at 2 different actions 4 times. Found 1 fixpoints after 1 different actions. Largest state had 20 variables. [2018-11-07 05:07:24,976 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:24,977 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 05:07:24,977 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:24,977 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:07:24,988 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:24,988 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:07:25,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:25,034 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:25,182 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-11-07 05:07:25,200 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-11-07 05:07:25,200 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,207 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,213 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,213 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-11-07 05:07:25,324 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 15 treesize of output 11 [2018-11-07 05:07:25,336 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-07 05:07:25,337 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,339 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,341 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,342 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:15, output treesize:3 [2018-11-07 05:07:25,379 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:25,380 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:07:25,646 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 14 treesize of output 12 [2018-11-07 05:07:25,857 WARN L179 SmtUtils]: Spent 207.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 10 [2018-11-07 05:07:25,875 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2018-11-07 05:07:25,875 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,888 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,899 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:25,899 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:14, output treesize:5 [2018-11-07 05:07:25,930 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:25,960 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:07:25,961 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8, 8] total 16 [2018-11-07 05:07:25,961 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:07:25,961 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-11-07 05:07:25,962 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-11-07 05:07:25,963 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=197, Unknown=0, NotChecked=0, Total=240 [2018-11-07 05:07:25,963 INFO L87 Difference]: Start difference. First operand 28 states and 29 transitions. Second operand 13 states. [2018-11-07 05:07:26,330 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:26,331 INFO L93 Difference]: Finished difference Result 42 states and 43 transitions. [2018-11-07 05:07:26,333 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-11-07 05:07:26,333 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 23 [2018-11-07 05:07:26,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:26,334 INFO L225 Difference]: With dead ends: 42 [2018-11-07 05:07:26,334 INFO L226 Difference]: Without dead ends: 40 [2018-11-07 05:07:26,335 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 37 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2018-11-07 05:07:26,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-11-07 05:07:26,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 36. [2018-11-07 05:07:26,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-11-07 05:07:26,344 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2018-11-07 05:07:26,344 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 23 [2018-11-07 05:07:26,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:26,344 INFO L480 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2018-11-07 05:07:26,344 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-11-07 05:07:26,345 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2018-11-07 05:07:26,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-11-07 05:07:26,346 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:26,346 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:26,346 INFO L423 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:26,347 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:26,347 INFO L82 PathProgramCache]: Analyzing trace with hash 1730228756, now seen corresponding path program 1 times [2018-11-07 05:07:26,347 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:26,348 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:26,348 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:26,348 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:26,349 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:26,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:26,465 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:26,465 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:26,465 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:07:26,466 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 34 with the following transitions: [2018-11-07 05:07:26,466 INFO L202 CegarAbsIntRunner]: [0], [1], [5], [9], [10], [11], [15], [18], [20], [21], [23], [27], [31], [36], [37], [39], [41], [47], [50], [52], [55], [57], [58], [59], [60], [62], [63] [2018-11-07 05:07:26,469 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-11-07 05:07:26,469 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-07 05:07:26,869 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-07 05:07:26,869 INFO L272 AbstractInterpreter]: Visited 27 different actions 163 times. Merged at 12 different actions 82 times. Widened at 3 different actions 8 times. Found 7 fixpoints after 4 different actions. Largest state had 21 variables. [2018-11-07 05:07:26,900 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:26,901 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-07 05:07:26,901 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:26,901 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:07:26,910 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:26,910 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:07:26,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:26,929 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:27,005 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:27,006 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:07:27,145 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:27,165 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:07:27,166 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2018-11-07 05:07:27,166 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:07:27,166 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-11-07 05:07:27,167 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-11-07 05:07:27,167 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2018-11-07 05:07:27,167 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 10 states. [2018-11-07 05:07:27,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:27,325 INFO L93 Difference]: Finished difference Result 63 states and 66 transitions. [2018-11-07 05:07:27,326 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-11-07 05:07:27,326 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 33 [2018-11-07 05:07:27,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:27,329 INFO L225 Difference]: With dead ends: 63 [2018-11-07 05:07:27,329 INFO L226 Difference]: Without dead ends: 42 [2018-11-07 05:07:27,330 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 60 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2018-11-07 05:07:27,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2018-11-07 05:07:27,339 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 40. [2018-11-07 05:07:27,339 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2018-11-07 05:07:27,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 41 transitions. [2018-11-07 05:07:27,341 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 41 transitions. Word has length 33 [2018-11-07 05:07:27,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:27,341 INFO L480 AbstractCegarLoop]: Abstraction has 40 states and 41 transitions. [2018-11-07 05:07:27,341 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-11-07 05:07:27,342 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 41 transitions. [2018-11-07 05:07:27,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-11-07 05:07:27,343 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:27,343 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:27,343 INFO L423 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:27,344 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:27,344 INFO L82 PathProgramCache]: Analyzing trace with hash -464225189, now seen corresponding path program 2 times [2018-11-07 05:07:27,344 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:27,345 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:27,345 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:27,345 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:27,345 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:27,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:27,590 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 1 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:27,591 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:27,591 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:07:27,591 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:07:27,591 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:07:27,592 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:27,592 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:07:27,608 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:07:27,608 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:07:27,657 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-11-07 05:07:27,657 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:07:27,660 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:27,735 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 15 treesize of output 12 [2018-11-07 05:07:27,738 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 12 treesize of output 11 [2018-11-07 05:07:27,738 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:27,740 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:27,750 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:27,750 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-07 05:07:28,366 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-07 05:07:28,370 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:07:28,371 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-07 05:07:28,372 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:28,376 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:28,385 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:28,386 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-07 05:07:28,549 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:28,549 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:07:28,845 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-07 05:07:28,859 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-07 05:07:28,860 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:28,862 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:28,868 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:28,869 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-07 05:07:28,893 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-07 05:07:28,913 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:07:28,913 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 14, 13] total 28 [2018-11-07 05:07:28,913 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:07:28,914 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-11-07 05:07:28,914 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-11-07 05:07:28,915 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=654, Unknown=0, NotChecked=0, Total=756 [2018-11-07 05:07:28,915 INFO L87 Difference]: Start difference. First operand 40 states and 41 transitions. Second operand 23 states. [2018-11-07 05:07:34,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:34,071 INFO L93 Difference]: Finished difference Result 75 states and 79 transitions. [2018-11-07 05:07:34,071 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-11-07 05:07:34,071 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 37 [2018-11-07 05:07:34,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:34,073 INFO L225 Difference]: With dead ends: 75 [2018-11-07 05:07:34,074 INFO L226 Difference]: Without dead ends: 58 [2018-11-07 05:07:34,075 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 54 SyntacticMatches, 8 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 468 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=246, Invalid=1646, Unknown=0, NotChecked=0, Total=1892 [2018-11-07 05:07:34,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-11-07 05:07:34,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 54. [2018-11-07 05:07:34,084 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-11-07 05:07:34,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 55 transitions. [2018-11-07 05:07:34,086 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 55 transitions. Word has length 37 [2018-11-07 05:07:34,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:34,086 INFO L480 AbstractCegarLoop]: Abstraction has 54 states and 55 transitions. [2018-11-07 05:07:34,086 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-11-07 05:07:34,087 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 55 transitions. [2018-11-07 05:07:34,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-11-07 05:07:34,088 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:34,088 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:34,089 INFO L423 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:34,089 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:34,089 INFO L82 PathProgramCache]: Analyzing trace with hash -1917919404, now seen corresponding path program 3 times [2018-11-07 05:07:34,089 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:34,090 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:34,090 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:07:34,090 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:34,091 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:34,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:34,479 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 3 proven. 36 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-11-07 05:07:34,479 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:34,479 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:07:34,479 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:07:34,479 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:07:34,480 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:34,480 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:07:34,508 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:07:34,508 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:07:34,527 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:07:34,528 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:07:34,532 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:34,570 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 15 treesize of output 12 [2018-11-07 05:07:34,573 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 12 treesize of output 11 [2018-11-07 05:07:34,573 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:34,576 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:34,586 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:07:34,586 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 [2018-11-07 05:07:41,736 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-07 05:07:41,750 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:07:41,751 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-07 05:07:41,751 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:41,756 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:41,757 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:41,758 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:23, output treesize:3 [2018-11-07 05:07:41,803 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-07 05:07:41,803 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:07:43,927 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 18 [2018-11-07 05:07:43,941 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-07 05:07:43,942 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:43,945 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:43,946 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:43,947 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:5 [2018-11-07 05:07:43,977 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 4 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-07 05:07:43,998 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:07:43,998 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 12] total 20 [2018-11-07 05:07:43,998 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:07:44,000 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-07 05:07:44,000 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-07 05:07:44,000 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=325, Unknown=3, NotChecked=0, Total=380 [2018-11-07 05:07:44,001 INFO L87 Difference]: Start difference. First operand 54 states and 55 transitions. Second operand 19 states. [2018-11-07 05:07:48,642 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:48,643 INFO L93 Difference]: Finished difference Result 70 states and 71 transitions. [2018-11-07 05:07:48,643 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-11-07 05:07:48,643 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 51 [2018-11-07 05:07:48,644 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:48,645 INFO L225 Difference]: With dead ends: 70 [2018-11-07 05:07:48,645 INFO L226 Difference]: Without dead ends: 68 [2018-11-07 05:07:48,646 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 87 SyntacticMatches, 14 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 169 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=108, Invalid=645, Unknown=3, NotChecked=0, Total=756 [2018-11-07 05:07:48,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2018-11-07 05:07:48,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 64. [2018-11-07 05:07:48,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-11-07 05:07:48,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 65 transitions. [2018-11-07 05:07:48,655 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 65 transitions. Word has length 51 [2018-11-07 05:07:48,655 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:48,655 INFO L480 AbstractCegarLoop]: Abstraction has 64 states and 65 transitions. [2018-11-07 05:07:48,655 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-07 05:07:48,655 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 65 transitions. [2018-11-07 05:07:48,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2018-11-07 05:07:48,657 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:48,657 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:48,658 INFO L423 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:48,658 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:48,658 INFO L82 PathProgramCache]: Analyzing trace with hash -320578298, now seen corresponding path program 4 times [2018-11-07 05:07:48,658 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:48,659 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:48,659 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:07:48,659 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:48,659 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:48,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:48,898 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 22 proven. 32 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-07 05:07:48,898 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:48,898 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:07:48,899 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:07:48,899 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:07:48,899 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:48,899 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:07:48,913 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:48,913 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:07:48,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:48,935 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:49,034 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 36 proven. 18 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-07 05:07:49,035 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:07:49,173 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 36 proven. 18 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-07 05:07:49,194 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:07:49,194 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2018-11-07 05:07:49,194 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:07:49,194 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-11-07 05:07:49,195 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-11-07 05:07:49,195 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=202, Unknown=0, NotChecked=0, Total=272 [2018-11-07 05:07:49,195 INFO L87 Difference]: Start difference. First operand 64 states and 65 transitions. Second operand 16 states. [2018-11-07 05:07:49,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:07:49,514 INFO L93 Difference]: Finished difference Result 103 states and 108 transitions. [2018-11-07 05:07:49,515 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-11-07 05:07:49,515 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 61 [2018-11-07 05:07:49,515 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:07:49,516 INFO L225 Difference]: With dead ends: 103 [2018-11-07 05:07:49,516 INFO L226 Difference]: Without dead ends: 70 [2018-11-07 05:07:49,517 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 110 SyntacticMatches, 7 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=118, Invalid=344, Unknown=0, NotChecked=0, Total=462 [2018-11-07 05:07:49,517 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-11-07 05:07:49,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2018-11-07 05:07:49,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 68 states. [2018-11-07 05:07:49,526 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 69 transitions. [2018-11-07 05:07:49,526 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 69 transitions. Word has length 61 [2018-11-07 05:07:49,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:07:49,527 INFO L480 AbstractCegarLoop]: Abstraction has 68 states and 69 transitions. [2018-11-07 05:07:49,527 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-11-07 05:07:49,527 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 69 transitions. [2018-11-07 05:07:49,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-11-07 05:07:49,528 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:07:49,528 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:07:49,529 INFO L423 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:07:49,529 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:07:49,529 INFO L82 PathProgramCache]: Analyzing trace with hash -53672243, now seen corresponding path program 5 times [2018-11-07 05:07:49,529 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:07:49,530 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:49,530 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:07:49,530 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:07:49,531 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:07:49,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:07:50,226 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 5 proven. 69 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-11-07 05:07:50,226 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:50,227 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:07:50,227 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:07:50,227 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:07:50,227 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:07:50,227 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:07:50,236 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:07:50,236 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:07:50,271 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-11-07 05:07:50,271 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:07:50,276 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:07:50,375 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 15 treesize of output 12 [2018-11-07 05:07:50,376 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 12 treesize of output 11 [2018-11-07 05:07:50,377 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:50,378 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:50,382 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:50,382 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-07 05:07:51,321 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-07 05:07:51,323 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:07:51,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 05:07:51,324 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:51,326 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:51,334 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:51,334 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-07 05:07:51,394 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 24 proven. 44 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-07 05:07:51,395 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:07:51,731 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-07 05:07:51,745 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-07 05:07:51,746 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:07:51,747 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:51,754 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:07:51,754 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-07 05:07:51,828 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 24 proven. 44 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-07 05:07:51,847 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:07:51,848 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 18, 17] total 38 [2018-11-07 05:07:51,848 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:07:51,848 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-11-07 05:07:51,849 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-11-07 05:07:51,850 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=1241, Unknown=0, NotChecked=0, Total=1406 [2018-11-07 05:07:51,850 INFO L87 Difference]: Start difference. First operand 68 states and 69 transitions. Second operand 31 states. [2018-11-07 05:07:53,603 WARN L179 SmtUtils]: Spent 144.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2018-11-07 05:08:04,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:08:04,420 INFO L93 Difference]: Finished difference Result 119 states and 124 transitions. [2018-11-07 05:08:04,420 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-11-07 05:08:04,420 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 65 [2018-11-07 05:08:04,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:08:04,422 INFO L225 Difference]: With dead ends: 119 [2018-11-07 05:08:04,422 INFO L226 Difference]: Without dead ends: 86 [2018-11-07 05:08:04,425 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 99 SyntacticMatches, 14 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1087 ImplicationChecksByTransitivity, 9.5s TimeCoverageRelationStatistics Valid=502, Invalid=3920, Unknown=0, NotChecked=0, Total=4422 [2018-11-07 05:08:04,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-11-07 05:08:04,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 82. [2018-11-07 05:08:04,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2018-11-07 05:08:04,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 83 transitions. [2018-11-07 05:08:04,436 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 83 transitions. Word has length 65 [2018-11-07 05:08:04,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:08:04,436 INFO L480 AbstractCegarLoop]: Abstraction has 82 states and 83 transitions. [2018-11-07 05:08:04,436 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-11-07 05:08:04,437 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 83 transitions. [2018-11-07 05:08:04,438 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-11-07 05:08:04,438 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:08:04,438 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:08:04,438 INFO L423 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:08:04,439 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:08:04,439 INFO L82 PathProgramCache]: Analyzing trace with hash -1837972794, now seen corresponding path program 6 times [2018-11-07 05:08:04,439 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:08:04,440 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:08:04,440 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:08:04,440 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:08:04,440 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:08:04,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:08:04,878 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 7 proven. 112 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-11-07 05:08:04,878 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:08:04,878 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:08:04,879 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:08:04,879 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:08:04,879 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:08:04,879 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:08:04,888 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:08:04,888 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:08:04,921 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:08:04,922 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:08:04,925 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:08:04,953 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 15 treesize of output 12 [2018-11-07 05:08:04,955 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 12 treesize of output 11 [2018-11-07 05:08:04,956 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:08:04,958 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:04,966 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:08:04,967 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 [2018-11-07 05:08:36,004 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 21 treesize of output 17 [2018-11-07 05:08:36,005 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:08:36,006 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 17 treesize of output 13 [2018-11-07 05:08:36,006 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:08:36,009 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:36,010 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:36,011 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:3 [2018-11-07 05:08:36,076 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 0 proven. 110 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-07 05:08:36,076 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:08:38,184 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-07 05:08:38,197 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-07 05:08:38,197 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:08:38,205 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:38,206 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:38,206 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:5 [2018-11-07 05:08:38,240 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 8 proven. 102 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-07 05:08:38,261 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:08:38,261 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 16] total 26 [2018-11-07 05:08:38,261 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:08:38,261 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-11-07 05:08:38,262 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-11-07 05:08:38,262 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=575, Unknown=5, NotChecked=0, Total=650 [2018-11-07 05:08:38,262 INFO L87 Difference]: Start difference. First operand 82 states and 83 transitions. Second operand 25 states. [2018-11-07 05:08:47,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:08:47,044 INFO L93 Difference]: Finished difference Result 98 states and 99 transitions. [2018-11-07 05:08:47,044 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-11-07 05:08:47,044 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 79 [2018-11-07 05:08:47,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:08:47,046 INFO L225 Difference]: With dead ends: 98 [2018-11-07 05:08:47,046 INFO L226 Difference]: Without dead ends: 96 [2018-11-07 05:08:47,047 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 135 SyntacticMatches, 20 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 299 ImplicationChecksByTransitivity, 33.7s TimeCoverageRelationStatistics Valid=142, Invalid=1113, Unknown=5, NotChecked=0, Total=1260 [2018-11-07 05:08:47,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-11-07 05:08:47,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 92. [2018-11-07 05:08:47,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2018-11-07 05:08:47,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 93 transitions. [2018-11-07 05:08:47,059 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 93 transitions. Word has length 79 [2018-11-07 05:08:47,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:08:47,059 INFO L480 AbstractCegarLoop]: Abstraction has 92 states and 93 transitions. [2018-11-07 05:08:47,059 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-11-07 05:08:47,060 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 93 transitions. [2018-11-07 05:08:47,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2018-11-07 05:08:47,061 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:08:47,061 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:08:47,061 INFO L423 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:08:47,061 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:08:47,062 INFO L82 PathProgramCache]: Analyzing trace with hash 843061752, now seen corresponding path program 7 times [2018-11-07 05:08:47,062 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:08:47,063 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:08:47,063 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:08:47,063 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:08:47,063 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:08:47,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:08:47,258 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 64 proven. 76 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-07 05:08:47,258 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:08:47,259 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:08:47,259 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:08:47,259 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:08:47,259 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:08:47,259 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:08:47,269 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:08:47,270 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:08:47,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:08:47,308 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:08:47,607 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 90 proven. 50 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-07 05:08:47,608 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:08:47,707 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 90 proven. 50 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-07 05:08:47,727 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:08:47,727 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2018-11-07 05:08:47,728 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:08:47,728 INFO L459 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-11-07 05:08:47,728 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-11-07 05:08:47,729 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=382, Unknown=0, NotChecked=0, Total=506 [2018-11-07 05:08:47,729 INFO L87 Difference]: Start difference. First operand 92 states and 93 transitions. Second operand 22 states. [2018-11-07 05:08:48,013 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:08:48,014 INFO L93 Difference]: Finished difference Result 143 states and 150 transitions. [2018-11-07 05:08:48,015 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-11-07 05:08:48,015 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 89 [2018-11-07 05:08:48,015 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:08:48,017 INFO L225 Difference]: With dead ends: 143 [2018-11-07 05:08:48,018 INFO L226 Difference]: Without dead ends: 98 [2018-11-07 05:08:48,019 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 160 SyntacticMatches, 11 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 321 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=211, Invalid=659, Unknown=0, NotChecked=0, Total=870 [2018-11-07 05:08:48,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-11-07 05:08:48,028 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 96. [2018-11-07 05:08:48,029 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-11-07 05:08:48,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 97 transitions. [2018-11-07 05:08:48,030 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 97 transitions. Word has length 89 [2018-11-07 05:08:48,030 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:08:48,030 INFO L480 AbstractCegarLoop]: Abstraction has 96 states and 97 transitions. [2018-11-07 05:08:48,030 INFO L481 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-11-07 05:08:48,031 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 97 transitions. [2018-11-07 05:08:48,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2018-11-07 05:08:48,032 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:08:48,032 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:08:48,033 INFO L423 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:08:48,033 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:08:48,033 INFO L82 PathProgramCache]: Analyzing trace with hash -1323572417, now seen corresponding path program 8 times [2018-11-07 05:08:48,033 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:08:48,034 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:08:48,034 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:08:48,034 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:08:48,034 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:08:48,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:08:48,438 INFO L134 CoverageAnalysis]: Checked inductivity of 202 backedges. 9 proven. 165 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-11-07 05:08:48,438 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:08:48,438 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:08:48,438 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:08:48,439 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:08:48,439 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:08:48,439 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 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:08:48,453 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:08:48,454 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:08:48,493 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-11-07 05:08:48,494 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:08:48,499 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:08:48,611 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 15 treesize of output 12 [2018-11-07 05:08:48,621 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 12 treesize of output 11 [2018-11-07 05:08:48,621 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:08:48,623 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:48,627 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:48,627 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-07 05:08:49,911 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-07 05:08:49,914 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:08:49,915 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-07 05:08:49,915 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:08:49,919 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:49,927 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:49,928 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-07 05:08:50,013 INFO L134 CoverageAnalysis]: Checked inductivity of 202 backedges. 70 proven. 92 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-07 05:08:50,013 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:08:51,777 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-07 05:08:51,793 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-07 05:08:51,794 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:08:51,796 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:51,801 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:08:51,801 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-07 05:08:53,212 INFO L134 CoverageAnalysis]: Checked inductivity of 202 backedges. 70 proven. 92 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-07 05:08:53,232 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:08:53,232 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 22, 21] total 48 [2018-11-07 05:08:53,232 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:08:53,233 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-11-07 05:08:53,233 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-11-07 05:08:53,234 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=248, Invalid=2008, Unknown=0, NotChecked=0, Total=2256 [2018-11-07 05:08:53,234 INFO L87 Difference]: Start difference. First operand 96 states and 97 transitions. Second operand 39 states. [2018-11-07 05:09:01,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:09:01,255 INFO L93 Difference]: Finished difference Result 163 states and 169 transitions. [2018-11-07 05:09:01,255 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-11-07 05:09:01,255 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 93 [2018-11-07 05:09:01,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:09:01,256 INFO L225 Difference]: With dead ends: 163 [2018-11-07 05:09:01,256 INFO L226 Difference]: Without dead ends: 114 [2018-11-07 05:09:01,259 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 251 GetRequests, 142 SyntacticMatches, 20 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2034 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=795, Invalid=7395, Unknown=0, NotChecked=0, Total=8190 [2018-11-07 05:09:01,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2018-11-07 05:09:01,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 110. [2018-11-07 05:09:01,269 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 110 states. [2018-11-07 05:09:01,270 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 111 transitions. [2018-11-07 05:09:01,271 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 111 transitions. Word has length 93 [2018-11-07 05:09:01,271 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:09:01,271 INFO L480 AbstractCegarLoop]: Abstraction has 110 states and 111 transitions. [2018-11-07 05:09:01,271 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-11-07 05:09:01,271 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 111 transitions. [2018-11-07 05:09:01,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-11-07 05:09:01,273 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:09:01,273 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:09:01,273 INFO L423 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:09:01,273 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:09:01,273 INFO L82 PathProgramCache]: Analyzing trace with hash -570673096, now seen corresponding path program 9 times [2018-11-07 05:09:01,274 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:09:01,274 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:09:01,274 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:09:01,275 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:09:01,275 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:09:01,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:09:02,458 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 11 proven. 228 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-11-07 05:09:02,458 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:09:02,459 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:09:02,459 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:09:02,459 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:09:02,459 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:09:02,459 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 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:09:02,468 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:09:02,468 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:09:02,504 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:09:02,504 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:09:02,508 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:09:02,585 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 15 treesize of output 12 [2018-11-07 05:09:02,587 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 12 treesize of output 11 [2018-11-07 05:09:02,587 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:09:02,589 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:09:02,596 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:09:02,596 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 [2018-11-07 05:09:59,388 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 21 treesize of output 17 [2018-11-07 05:09:59,417 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:09:59,418 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 17 treesize of output 13 [2018-11-07 05:09:59,419 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:09:59,429 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:09:59,430 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:09:59,431 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:3 [2018-11-07 05:09:59,510 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 0 proven. 224 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-07 05:09:59,510 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:10:00,563 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-07 05:10:00,576 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-07 05:10:00,577 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:10:00,578 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:00,579 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:00,580 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:5 [2018-11-07 05:10:00,608 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 12 proven. 212 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-07 05:10:00,628 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:10:00,628 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 20] total 32 [2018-11-07 05:10:00,628 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:10:00,629 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-11-07 05:10:00,629 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-11-07 05:10:00,629 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=897, Unknown=7, NotChecked=0, Total=992 [2018-11-07 05:10:00,630 INFO L87 Difference]: Start difference. First operand 110 states and 111 transitions. Second operand 31 states. [2018-11-07 05:10:14,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:10:14,038 INFO L93 Difference]: Finished difference Result 126 states and 127 transitions. [2018-11-07 05:10:14,038 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-11-07 05:10:14,039 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 107 [2018-11-07 05:10:14,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:10:14,041 INFO L225 Difference]: With dead ends: 126 [2018-11-07 05:10:14,041 INFO L226 Difference]: Without dead ends: 124 [2018-11-07 05:10:14,042 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 251 GetRequests, 183 SyntacticMatches, 26 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 459 ImplicationChecksByTransitivity, 59.1s TimeCoverageRelationStatistics Valid=176, Invalid=1709, Unknown=7, NotChecked=0, Total=1892 [2018-11-07 05:10:14,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2018-11-07 05:10:14,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 120. [2018-11-07 05:10:14,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 120 states. [2018-11-07 05:10:14,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 121 transitions. [2018-11-07 05:10:14,054 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 121 transitions. Word has length 107 [2018-11-07 05:10:14,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:10:14,055 INFO L480 AbstractCegarLoop]: Abstraction has 120 states and 121 transitions. [2018-11-07 05:10:14,055 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-11-07 05:10:14,055 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 121 transitions. [2018-11-07 05:10:14,056 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2018-11-07 05:10:14,056 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:10:14,057 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:10:14,057 INFO L423 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:10:14,057 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:10:14,057 INFO L82 PathProgramCache]: Analyzing trace with hash 974317802, now seen corresponding path program 10 times [2018-11-07 05:10:14,057 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:10:14,058 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:10:14,058 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:10:14,058 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:10:14,058 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:10:14,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:10:14,286 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 130 proven. 136 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-07 05:10:14,286 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:10:14,286 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:10:14,286 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:10:14,286 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:10:14,286 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:10:14,287 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 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:10:14,295 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:10:14,295 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-07 05:10:14,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:10:14,330 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:10:14,515 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 168 proven. 98 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-07 05:10:14,515 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:10:14,645 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 168 proven. 98 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-07 05:10:14,666 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:10:14,666 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 29 [2018-11-07 05:10:14,667 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:10:14,667 INFO L459 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-11-07 05:10:14,667 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-11-07 05:10:14,668 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=194, Invalid=618, Unknown=0, NotChecked=0, Total=812 [2018-11-07 05:10:14,668 INFO L87 Difference]: Start difference. First operand 120 states and 121 transitions. Second operand 28 states. [2018-11-07 05:10:15,066 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:10:15,066 INFO L93 Difference]: Finished difference Result 183 states and 192 transitions. [2018-11-07 05:10:15,066 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-11-07 05:10:15,066 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 117 [2018-11-07 05:10:15,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:10:15,068 INFO L225 Difference]: With dead ends: 183 [2018-11-07 05:10:15,068 INFO L226 Difference]: Without dead ends: 126 [2018-11-07 05:10:15,069 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 261 GetRequests, 210 SyntacticMatches, 15 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 547 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=332, Invalid=1074, Unknown=0, NotChecked=0, Total=1406 [2018-11-07 05:10:15,069 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2018-11-07 05:10:15,079 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 124. [2018-11-07 05:10:15,079 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 124 states. [2018-11-07 05:10:15,080 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 125 transitions. [2018-11-07 05:10:15,080 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 125 transitions. Word has length 117 [2018-11-07 05:10:15,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:10:15,081 INFO L480 AbstractCegarLoop]: Abstraction has 124 states and 125 transitions. [2018-11-07 05:10:15,081 INFO L481 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-11-07 05:10:15,081 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 125 transitions. [2018-11-07 05:10:15,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2018-11-07 05:10:15,082 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:10:15,082 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:10:15,083 INFO L423 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:10:15,083 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:10:15,083 INFO L82 PathProgramCache]: Analyzing trace with hash 1644138929, now seen corresponding path program 11 times [2018-11-07 05:10:15,083 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:10:15,084 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:10:15,084 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-07 05:10:15,084 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:10:15,084 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:10:15,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:10:15,717 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 13 proven. 301 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-11-07 05:10:15,717 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:10:15,717 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:10:15,717 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:10:15,717 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:10:15,717 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:10:15,718 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 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:10:15,727 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-07 05:10:15,727 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-07 05:10:15,786 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-11-07 05:10:15,787 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:10:15,792 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:10:15,979 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 15 treesize of output 12 [2018-11-07 05:10:15,982 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 12 treesize of output 11 [2018-11-07 05:10:15,983 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:10:15,987 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:15,991 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:15,991 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-07 05:10:17,647 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-07 05:10:17,649 INFO L682 Elim1Store]: detected equality via solver [2018-11-07 05:10:17,650 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-07 05:10:17,650 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:10:17,677 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:17,684 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:17,684 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-07 05:10:17,804 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 140 proven. 156 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-07 05:10:17,805 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-07 05:10:18,909 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-07 05:10:18,924 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-07 05:10:18,924 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:10:18,927 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:18,932 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:18,933 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-07 05:10:19,124 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 140 proven. 156 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-07 05:10:19,144 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-07 05:10:19,145 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 26, 25] total 58 [2018-11-07 05:10:19,145 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-07 05:10:19,145 INFO L459 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-11-07 05:10:19,146 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-11-07 05:10:19,147 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=351, Invalid=2955, Unknown=0, NotChecked=0, Total=3306 [2018-11-07 05:10:19,147 INFO L87 Difference]: Start difference. First operand 124 states and 125 transitions. Second operand 47 states. [2018-11-07 05:10:33,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-07 05:10:33,442 INFO L93 Difference]: Finished difference Result 215 states and 220 transitions. [2018-11-07 05:10:33,442 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-11-07 05:10:33,442 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 121 [2018-11-07 05:10:33,442 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-07 05:10:33,443 INFO L225 Difference]: With dead ends: 215 [2018-11-07 05:10:33,443 INFO L226 Difference]: Without dead ends: 142 [2018-11-07 05:10:33,448 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 323 GetRequests, 186 SyntacticMatches, 26 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3155 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=1108, Invalid=11548, Unknown=0, NotChecked=0, Total=12656 [2018-11-07 05:10:33,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2018-11-07 05:10:33,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 138. [2018-11-07 05:10:33,460 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 138 states. [2018-11-07 05:10:33,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 139 transitions. [2018-11-07 05:10:33,461 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 139 transitions. Word has length 121 [2018-11-07 05:10:33,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-07 05:10:33,462 INFO L480 AbstractCegarLoop]: Abstraction has 138 states and 139 transitions. [2018-11-07 05:10:33,462 INFO L481 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-11-07 05:10:33,462 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 139 transitions. [2018-11-07 05:10:33,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2018-11-07 05:10:33,463 INFO L367 BasicCegarLoop]: Found error trace [2018-11-07 05:10:33,464 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-07 05:10:33,464 INFO L423 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-07 05:10:33,464 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-07 05:10:33,464 INFO L82 PathProgramCache]: Analyzing trace with hash 1791606698, now seen corresponding path program 12 times [2018-11-07 05:10:33,464 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-07 05:10:33,465 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:10:33,465 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-07 05:10:33,465 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-07 05:10:33,466 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-07 05:10:33,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-07 05:10:34,070 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 15 proven. 384 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2018-11-07 05:10:34,070 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:10:34,070 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-07 05:10:34,070 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-07 05:10:34,071 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-07 05:10:34,071 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-07 05:10:34,071 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 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:10:34,079 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-07 05:10:34,079 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-07 05:10:34,110 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-07 05:10:34,110 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-07 05:10:34,113 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-07 05:10:34,132 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 15 treesize of output 12 [2018-11-07 05:10:34,135 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 12 treesize of output 11 [2018-11-07 05:10:34,136 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-07 05:10:34,139 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-07 05:10:34,148 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-07 05:10:34,149 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 Received shutdown request... [2018-11-07 05:12:01,178 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-07 05:12:01,379 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-07 05:12:01,380 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-07 05:12:01,385 WARN L205 ceAbstractionStarter]: Timeout [2018-11-07 05:12:01,385 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.11 05:12:01 BoogieIcfgContainer [2018-11-07 05:12:01,385 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-07 05:12:01,386 INFO L168 Benchmark]: Toolchain (without parser) took 279478.99 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 966.3 MB). Free memory was 1.4 GB in the beginning and 2.0 GB in the end (delta: -593.2 MB). Peak memory consumption was 373.0 MB. Max. memory is 7.1 GB. [2018-11-07 05:12:01,387 INFO L168 Benchmark]: CDTParser took 0.20 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-07 05:12:01,387 INFO L168 Benchmark]: CACSL2BoogieTranslator took 355.82 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-11-07 05:12:01,388 INFO L168 Benchmark]: Boogie Procedure Inliner took 30.23 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-07 05:12:01,388 INFO L168 Benchmark]: Boogie Preprocessor took 32.10 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-07 05:12:01,388 INFO L168 Benchmark]: RCFGBuilder took 515.71 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 725.6 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -767.5 MB). Peak memory consumption was 14.6 MB. Max. memory is 7.1 GB. [2018-11-07 05:12:01,389 INFO L168 Benchmark]: TraceAbstraction took 278538.97 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 240.6 MB). Free memory was 2.2 GB in the beginning and 2.0 GB in the end (delta: 163.7 MB). Peak memory consumption was 404.4 MB. Max. memory is 7.1 GB. [2018-11-07 05:12:01,391 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.20 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 355.82 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 30.23 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 32.10 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 515.71 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 725.6 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -767.5 MB). Peak memory consumption was 14.6 MB. Max. memory is 7.1 GB. * TraceAbstraction took 278538.97 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 240.6 MB). Free memory was 2.2 GB in the beginning and 2.0 GB in the end (delta: 163.7 MB). Peak memory consumption was 404.4 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 6]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 6). Cancelled while BasicCegarLoop was analyzing trace of length 136 with TraceHistMax 10,while TraceCheckSpWp was constructing forward predicates,while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 32 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 31 locations, 1 error locations. TIMEOUT Result, 278.4s OverallTime, 15 OverallIterations, 10 TraceHistogramMax, 68.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 463 SDtfs, 853 SDslu, 4991 SDs, 0 SdLazy, 7525 SolverSat, 486 SolverUnsat, 23 SolverUnknown, 0 SolverNotchecked, 53.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2166 GetRequests, 1467 SyntacticMatches, 169 SemanticMatches, 530 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8816 ImplicationChecksByTransitivity, 129.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=138occurred in iteration=14, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 1.0s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 14 MinimizatonAttempts, 42 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 119.2s InterpolantComputationTime, 1789 NumberOfCodeBlocks, 1783 NumberOfCodeBlocksAsserted, 46 NumberOfCheckSat, 2627 ConstructedInterpolants, 344 QuantifiedInterpolants, 1616315 SizeOfPredicates, 104 NumberOfNonLiveVariables, 1702 ConjunctsInSsa, 236 ConjunctsInUnsatCore, 38 InterpolantComputations, 2 PerfectInterpolantSequences, 2382/5220 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown