java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf -i ../../../trunk/examples/svcomp/memsafety/test-0504_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-21 00:37:12,165 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-21 00:37:12,167 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-21 00:37:12,182 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-21 00:37:12,182 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-21 00:37:12,183 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-21 00:37:12,184 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-21 00:37:12,186 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-21 00:37:12,188 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-21 00:37:12,189 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-21 00:37:12,190 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-21 00:37:12,190 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-21 00:37:12,191 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-21 00:37:12,193 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-21 00:37:12,194 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-21 00:37:12,196 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-21 00:37:12,198 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-21 00:37:12,200 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-21 00:37:12,202 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-21 00:37:12,203 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-21 00:37:12,206 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-21 00:37:12,206 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-21 00:37:12,206 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-21 00:37:12,207 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-21 00:37:12,208 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-21 00:37:12,209 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-21 00:37:12,210 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-21 00:37:12,210 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-21 00:37:12,211 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-21 00:37:12,211 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-21 00:37:12,211 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-21 00:37:12,212 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf [2018-01-21 00:37:12,221 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-21 00:37:12,221 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-21 00:37:12,222 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-21 00:37:12,222 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-21 00:37:12,222 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-21 00:37:12,222 INFO L133 SettingsManager]: * Deactivate Weak Equivalences=true [2018-01-21 00:37:12,222 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-21 00:37:12,222 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-21 00:37:12,223 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-21 00:37:12,223 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-21 00:37:12,223 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-21 00:37:12,223 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-21 00:37:12,223 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-21 00:37:12,223 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-21 00:37:12,223 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-21 00:37:12,224 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-21 00:37:12,224 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-21 00:37:12,224 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-21 00:37:12,224 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-21 00:37:12,224 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-21 00:37:12,224 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-21 00:37:12,224 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-21 00:37:12,225 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-21 00:37:12,225 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-21 00:37:12,225 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-21 00:37:12,225 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-21 00:37:12,225 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-21 00:37:12,226 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-21 00:37:12,226 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-21 00:37:12,227 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-21 00:37:12,227 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-21 00:37:12,228 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-21 00:37:12,259 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-21 00:37:12,270 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-21 00:37:12,273 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-21 00:37:12,274 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-21 00:37:12,274 INFO L276 PluginConnector]: CDTParser initialized [2018-01-21 00:37:12,275 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety/test-0504_true-valid-memsafety.i [2018-01-21 00:37:12,431 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-21 00:37:12,435 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-21 00:37:12,436 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-21 00:37:12,436 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-21 00:37:12,441 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-21 00:37:12,442 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,444 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@726f39e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12, skipping insertion in model container [2018-01-21 00:37:12,445 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,458 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-21 00:37:12,495 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-21 00:37:12,617 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-21 00:37:12,638 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-21 00:37:12,647 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12 WrapperNode [2018-01-21 00:37:12,647 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-21 00:37:12,648 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-21 00:37:12,648 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-21 00:37:12,648 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-21 00:37:12,665 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,665 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,674 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,675 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,680 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,684 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,686 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... [2018-01-21 00:37:12,688 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-21 00:37:12,689 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-21 00:37:12,689 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-21 00:37:12,689 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-21 00:37:12,690 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (1/1) ... No working directory specified, using /storage/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-01-21 00:37:12,735 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-21 00:37:12,736 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-21 00:37:12,736 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-21 00:37:12,736 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-21 00:37:12,736 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-21 00:37:12,736 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-21 00:37:12,736 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-21 00:37:12,737 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-21 00:37:12,737 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-21 00:37:12,737 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-21 00:37:12,737 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-21 00:37:12,737 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-21 00:37:12,737 INFO L128 BoogieDeclarations]: Found specification of procedure abort [2018-01-21 00:37:12,738 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-21 00:37:12,738 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-21 00:37:12,738 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-21 00:37:12,738 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-21 00:37:13,018 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-21 00:37:13,019 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.01 12:37:13 BoogieIcfgContainer [2018-01-21 00:37:13,019 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-21 00:37:13,019 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-21 00:37:13,019 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-21 00:37:13,021 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-21 00:37:13,021 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.01 12:37:12" (1/3) ... [2018-01-21 00:37:13,022 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c7a3518 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.01 12:37:13, skipping insertion in model container [2018-01-21 00:37:13,023 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:37:12" (2/3) ... [2018-01-21 00:37:13,023 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c7a3518 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.01 12:37:13, skipping insertion in model container [2018-01-21 00:37:13,023 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.01 12:37:13" (3/3) ... [2018-01-21 00:37:13,025 INFO L105 eAbstractionObserver]: Analyzing ICFG test-0504_true-valid-memsafety.i [2018-01-21 00:37:13,035 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-21 00:37:13,043 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-21 00:37:13,087 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 00:37:13,087 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 00:37:13,087 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 00:37:13,087 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 00:37:13,087 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 00:37:13,088 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 00:37:13,088 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 00:37:13,088 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-21 00:37:13,088 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 00:37:13,102 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-01-21 00:37:13,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-21 00:37:13,107 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,108 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-21 00:37:13,108 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-21 00:37:13,112 INFO L82 PathProgramCache]: Analyzing trace with hash 141778, now seen corresponding path program 1 times [2018-01-21 00:37:13,113 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,160 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,160 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,161 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,161 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:37:13,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:37:13,215 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-21 00:37:13,221 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:37:13,228 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 00:37:13,228 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 00:37:13,228 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 00:37:13,228 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 00:37:13,228 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 00:37:13,228 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 00:37:13,229 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 00:37:13,229 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-21 00:37:13,229 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 00:37:13,231 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-01-21 00:37:13,232 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-01-21 00:37:13,232 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,232 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,232 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 00:37:13,233 INFO L82 PathProgramCache]: Analyzing trace with hash 1069227820, now seen corresponding path program 1 times [2018-01-21 00:37:13,233 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,234 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,234 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,234 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,235 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:13,253 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:13,282 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:13,283 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:37:13,284 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 00:37:13,284 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:37:13,286 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-21 00:37:13,297 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-21 00:37:13,298 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 00:37:13,300 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 2 states. [2018-01-21 00:37:13,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:13,392 INFO L93 Difference]: Finished difference Result 109 states and 129 transitions. [2018-01-21 00:37:13,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-21 00:37:13,394 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 12 [2018-01-21 00:37:13,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:13,405 INFO L225 Difference]: With dead ends: 109 [2018-01-21 00:37:13,406 INFO L226 Difference]: Without dead ends: 55 [2018-01-21 00:37:13,409 INFO L525 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-01-21 00:37:13,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-21 00:37:13,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-21 00:37:13,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-21 00:37:13,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 59 transitions. [2018-01-21 00:37:13,446 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 59 transitions. Word has length 12 [2018-01-21 00:37:13,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:13,446 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 59 transitions. [2018-01-21 00:37:13,446 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-21 00:37:13,447 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 59 transitions. [2018-01-21 00:37:13,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-21 00:37:13,447 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,448 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,448 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 00:37:13,448 INFO L82 PathProgramCache]: Analyzing trace with hash 764024314, now seen corresponding path program 1 times [2018-01-21 00:37:13,448 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,449 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,450 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,450 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,450 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:37:13,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:37:13,482 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-21 00:37:13,487 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:37:13,488 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:37:13,489 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:37:13,498 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 00:37:13,498 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 00:37:13,498 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 00:37:13,498 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 00:37:13,498 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 00:37:13,499 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 00:37:13,499 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 00:37:13,499 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-21 00:37:13,499 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 00:37:13,501 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-01-21 00:37:13,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-01-21 00:37:13,502 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,502 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,502 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:13,502 INFO L82 PathProgramCache]: Analyzing trace with hash -1951957839, now seen corresponding path program 1 times [2018-01-21 00:37:13,503 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,504 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,504 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,504 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,504 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:13,513 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:13,523 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:13,524 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:37:13,524 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 00:37:13,524 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:37:13,524 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-21 00:37:13,525 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-21 00:37:13,525 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 00:37:13,525 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 2 states. [2018-01-21 00:37:13,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:13,533 INFO L93 Difference]: Finished difference Result 109 states and 129 transitions. [2018-01-21 00:37:13,533 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-21 00:37:13,533 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 10 [2018-01-21 00:37:13,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:13,535 INFO L225 Difference]: With dead ends: 109 [2018-01-21 00:37:13,535 INFO L226 Difference]: Without dead ends: 53 [2018-01-21 00:37:13,536 INFO L525 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-01-21 00:37:13,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-01-21 00:37:13,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-01-21 00:37:13,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-21 00:37:13,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 57 transitions. [2018-01-21 00:37:13,542 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 57 transitions. Word has length 10 [2018-01-21 00:37:13,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:13,543 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 57 transitions. [2018-01-21 00:37:13,543 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-21 00:37:13,543 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 57 transitions. [2018-01-21 00:37:13,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-21 00:37:13,544 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,544 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,544 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:13,544 INFO L82 PathProgramCache]: Analyzing trace with hash -691941633, now seen corresponding path program 1 times [2018-01-21 00:37:13,544 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,545 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,546 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,546 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,546 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:13,558 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:13,598 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:13,598 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:37:13,598 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 00:37:13,598 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:37:13,599 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-21 00:37:13,599 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-21 00:37:13,599 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-21 00:37:13,599 INFO L87 Difference]: Start difference. First operand 53 states and 57 transitions. Second operand 3 states. [2018-01-21 00:37:13,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:13,650 INFO L93 Difference]: Finished difference Result 72 states and 78 transitions. [2018-01-21 00:37:13,650 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-21 00:37:13,650 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-21 00:37:13,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:13,652 INFO L225 Difference]: With dead ends: 72 [2018-01-21 00:37:13,652 INFO L226 Difference]: Without dead ends: 69 [2018-01-21 00:37:13,653 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-21 00:37:13,653 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2018-01-21 00:37:13,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 58. [2018-01-21 00:37:13,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-21 00:37:13,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 63 transitions. [2018-01-21 00:37:13,660 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 63 transitions. Word has length 13 [2018-01-21 00:37:13,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:13,660 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 63 transitions. [2018-01-21 00:37:13,660 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-21 00:37:13,660 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 63 transitions. [2018-01-21 00:37:13,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-01-21 00:37:13,661 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,661 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,661 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:13,662 INFO L82 PathProgramCache]: Analyzing trace with hash 1939646148, now seen corresponding path program 1 times [2018-01-21 00:37:13,662 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,662 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,663 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,663 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,663 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:13,674 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:13,710 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:13,710 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:37:13,710 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-21 00:37:13,711 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:37:13,711 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-21 00:37:13,711 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-21 00:37:13,711 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-21 00:37:13,712 INFO L87 Difference]: Start difference. First operand 58 states and 63 transitions. Second operand 3 states. [2018-01-21 00:37:13,738 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:13,738 INFO L93 Difference]: Finished difference Result 131 states and 142 transitions. [2018-01-21 00:37:13,738 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-21 00:37:13,739 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 22 [2018-01-21 00:37:13,739 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:13,739 INFO L225 Difference]: With dead ends: 131 [2018-01-21 00:37:13,740 INFO L226 Difference]: Without dead ends: 82 [2018-01-21 00:37:13,740 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-21 00:37:13,740 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-01-21 00:37:13,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2018-01-21 00:37:13,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2018-01-21 00:37:13,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 87 transitions. [2018-01-21 00:37:13,746 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 87 transitions. Word has length 22 [2018-01-21 00:37:13,746 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:13,746 INFO L432 AbstractCegarLoop]: Abstraction has 82 states and 87 transitions. [2018-01-21 00:37:13,746 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-21 00:37:13,746 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 87 transitions. [2018-01-21 00:37:13,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-21 00:37:13,747 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,747 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,747 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:13,747 INFO L82 PathProgramCache]: Analyzing trace with hash 1620764504, now seen corresponding path program 1 times [2018-01-21 00:37:13,747 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,748 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,749 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,749 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,749 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:13,772 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:13,840 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:13,840 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:37:13,840 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-21 00:37:13,841 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:37:13,841 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-21 00:37:13,841 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-21 00:37:13,841 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-21 00:37:13,842 INFO L87 Difference]: Start difference. First operand 82 states and 87 transitions. Second operand 5 states. [2018-01-21 00:37:13,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:13,947 INFO L93 Difference]: Finished difference Result 133 states and 143 transitions. [2018-01-21 00:37:13,948 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-21 00:37:13,948 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 29 [2018-01-21 00:37:13,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:13,949 INFO L225 Difference]: With dead ends: 133 [2018-01-21 00:37:13,949 INFO L226 Difference]: Without dead ends: 86 [2018-01-21 00:37:13,950 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-21 00:37:13,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-01-21 00:37:13,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 84. [2018-01-21 00:37:13,956 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 84 states. [2018-01-21 00:37:13,957 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 88 transitions. [2018-01-21 00:37:13,958 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 88 transitions. Word has length 29 [2018-01-21 00:37:13,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:13,958 INFO L432 AbstractCegarLoop]: Abstraction has 84 states and 88 transitions. [2018-01-21 00:37:13,958 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-21 00:37:13,958 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 88 transitions. [2018-01-21 00:37:13,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-01-21 00:37:13,960 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:13,960 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:13,960 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:13,960 INFO L82 PathProgramCache]: Analyzing trace with hash -1106845045, now seen corresponding path program 1 times [2018-01-21 00:37:13,960 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:13,961 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,962 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:13,962 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:13,962 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:13,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:13,987 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:14,182 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:14,182 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:14,183 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:37:14,184 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 39 with the following transitions: [2018-01-21 00:37:14,186 INFO L201 CegarAbsIntRunner]: [0], [4], [6], [9], [11], [12], [13], [18], [20], [21], [22], [23], [24], [25], [29], [31], [34], [60], [72], [76], [78], [79], [80], [81], [82], [86], [90], [99], [103], [105], [106], [107], [113], [114], [115] [2018-01-21 00:37:14,237 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 00:37:14,238 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-21 00:37:14,816 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-21 00:37:14,818 INFO L268 AbstractInterpreter]: Visited 35 different actions 79 times. Merged at 29 different actions 41 times. Never widened. Found 3 fixpoints after 3 different actions. Largest state had 35 variables. [2018-01-21 00:37:14,852 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-21 00:37:14,852 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:14,852 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/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-01-21 00:37:14,861 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:14,861 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:14,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:14,901 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:15,047 WARN L1029 $PredicateComparison]: unable to prove that (exists ((main_~x~10.base Int)) (and (= (select |c_old(#valid)| main_~x~10.base) 0) (= |c_#valid| (store |c_old(#valid)| main_~x~10.base 0)) (not (= main_~x~10.base 0)))) is different from true [2018-01-21 00:37:15,061 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 2 not checked. [2018-01-21 00:37:15,061 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:15,270 WARN L1007 $PredicateComparison]: unable to prove that (forall ((|v_main_#t~malloc1.base_4| Int)) (or (= 0 |v_main_#t~malloc1.base_4|) (= |c_old(#valid)| (store |c_#valid| |v_main_#t~malloc1.base_4| 0)) (not (= 0 (select |c_#valid| |v_main_#t~malloc1.base_4|))))) is different from false [2018-01-21 00:37:15,291 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2018-01-21 00:37:15,313 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:15,313 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 3 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-21 00:37:15,317 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:15,317 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:15,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:15,364 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:15,794 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:15,794 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:15,847 WARN L1007 $PredicateComparison]: unable to prove that (forall ((|v_main_#t~malloc1.base_5| Int)) (or (not (= 0 (select |c_#valid| |v_main_#t~malloc1.base_5|))) (= 0 |v_main_#t~malloc1.base_5|) (= (store |c_#valid| |v_main_#t~malloc1.base_5| 0) |c_old(#valid)|))) is different from false [2018-01-21 00:37:15,870 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2018-01-21 00:37:15,872 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-21 00:37:15,872 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 8, 9, 7] total 24 [2018-01-21 00:37:15,872 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:37:15,872 INFO L409 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-01-21 00:37:15,873 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-01-21 00:37:15,873 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=390, Unknown=8, NotChecked=126, Total=600 [2018-01-21 00:37:15,873 INFO L87 Difference]: Start difference. First operand 84 states and 88 transitions. Second operand 13 states. [2018-01-21 00:37:16,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:16,317 INFO L93 Difference]: Finished difference Result 120 states and 128 transitions. [2018-01-21 00:37:16,317 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-21 00:37:16,317 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 38 [2018-01-21 00:37:16,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:16,320 INFO L225 Difference]: With dead ends: 120 [2018-01-21 00:37:16,320 INFO L226 Difference]: Without dead ends: 117 [2018-01-21 00:37:16,321 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 131 SyntacticMatches, 5 SemanticMatches, 30 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=150, Invalid=666, Unknown=8, NotChecked=168, Total=992 [2018-01-21 00:37:16,322 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2018-01-21 00:37:16,330 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 100. [2018-01-21 00:37:16,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-21 00:37:16,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 107 transitions. [2018-01-21 00:37:16,331 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 107 transitions. Word has length 38 [2018-01-21 00:37:16,332 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:16,332 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 107 transitions. [2018-01-21 00:37:16,332 INFO L433 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-01-21 00:37:16,332 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 107 transitions. [2018-01-21 00:37:16,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-01-21 00:37:16,334 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:16,334 INFO L322 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:16,334 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:16,334 INFO L82 PathProgramCache]: Analyzing trace with hash -159189785, now seen corresponding path program 1 times [2018-01-21 00:37:16,335 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:16,336 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:16,336 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:16,336 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:16,336 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:16,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:16,354 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:16,543 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:16,543 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:37:16,544 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2018-01-21 00:37:16,544 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:37:16,544 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-21 00:37:16,544 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-21 00:37:16,544 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2018-01-21 00:37:16,545 INFO L87 Difference]: Start difference. First operand 100 states and 107 transitions. Second operand 10 states. [2018-01-21 00:37:16,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:16,784 INFO L93 Difference]: Finished difference Result 178 states and 190 transitions. [2018-01-21 00:37:16,785 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-21 00:37:16,785 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 43 [2018-01-21 00:37:16,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:16,786 INFO L225 Difference]: With dead ends: 178 [2018-01-21 00:37:16,786 INFO L226 Difference]: Without dead ends: 160 [2018-01-21 00:37:16,786 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 6 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=106, Invalid=274, Unknown=0, NotChecked=0, Total=380 [2018-01-21 00:37:16,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2018-01-21 00:37:16,793 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 100. [2018-01-21 00:37:16,793 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-21 00:37:16,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 106 transitions. [2018-01-21 00:37:16,794 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 106 transitions. Word has length 43 [2018-01-21 00:37:16,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:16,794 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 106 transitions. [2018-01-21 00:37:16,794 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-21 00:37:16,794 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 106 transitions. [2018-01-21 00:37:16,795 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-21 00:37:16,795 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:16,795 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 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, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:16,795 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:16,795 INFO L82 PathProgramCache]: Analyzing trace with hash -175714120, now seen corresponding path program 2 times [2018-01-21 00:37:16,796 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:16,796 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:16,796 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:16,796 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:16,796 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:16,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:16,813 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:17,005 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:17,006 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:17,006 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:37:17,006 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-21 00:37:17,006 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-21 00:37:17,008 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:17,008 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-21 00:37:17,018 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-21 00:37:17,018 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-21 00:37:17,028 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:37:17,038 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:37:17,040 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-21 00:37:17,044 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:17,074 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 13 treesize of output 10 [2018-01-21 00:37:17,076 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 10 treesize of output 9 [2018-01-21 00:37:17,076 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,078 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,088 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,089 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:17, output treesize:13 [2018-01-21 00:37:17,109 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 23 [2018-01-21 00:37:17,123 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,125 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 27 [2018-01-21 00:37:17,125 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,131 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,135 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,135 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:31, output treesize:22 [2018-01-21 00:37:17,151 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 23 [2018-01-21 00:37:17,153 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,154 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,155 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,156 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 46 [2018-01-21 00:37:17,157 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,168 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,173 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,173 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:33, output treesize:29 [2018-01-21 00:37:17,207 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 39 treesize of output 30 [2018-01-21 00:37:17,214 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,215 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,216 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,216 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,217 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,218 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:17,222 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 77 [2018-01-21 00:37:17,223 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,303 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,336 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,337 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:42, output treesize:38 [2018-01-21 00:37:17,370 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 44 treesize of output 33 [2018-01-21 00:37:17,381 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 29 [2018-01-21 00:37:17,381 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,386 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,392 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,392 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:44, output treesize:29 [2018-01-21 00:37:17,453 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 38 treesize of output 28 [2018-01-21 00:37:17,478 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 6 disjoint index pairs (out of 10 index pairs), introduced 0 new quantified variables, introduced 4 case distinctions, treesize of input 28 treesize of output 41 [2018-01-21 00:37:17,479 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 4 xjuncts. [2018-01-21 00:37:17,497 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,512 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,512 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:38, output treesize:55 [2018-01-21 00:37:17,558 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:17,558 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:17,648 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:17,649 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:17,651 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:17,651 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:28, output treesize:12 [2018-01-21 00:37:17,735 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 30 treesize of output 28 [2018-01-21 00:37:17,737 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 32 [2018-01-21 00:37:17,739 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,740 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 42 [2018-01-21 00:37:17,743 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,743 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,744 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,745 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 55 [2018-01-21 00:37:17,748 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,748 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,748 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,749 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,749 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,749 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,752 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 77 [2018-01-21 00:37:17,768 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,768 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,768 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,769 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,769 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,769 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,772 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 41 [2018-01-21 00:37:17,773 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:17,778 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,778 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,779 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,779 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,779 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,779 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:17,789 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 9 disjoint index pairs (out of 10 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 68 [2018-01-21 00:37:17,790 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:17,817 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 4 xjuncts. [2018-01-21 00:37:17,840 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,858 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,877 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,903 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,920 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:17,921 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 3 variables, input treesize:30, output treesize:56 [2018-01-21 00:37:17,969 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:17,991 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:17,991 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 5 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-21 00:37:17,994 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-21 00:37:17,994 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-21 00:37:18,006 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:37:18,022 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:37:18,102 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-21 00:37:18,110 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:18,126 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 13 treesize of output 10 [2018-01-21 00:37:18,128 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 10 treesize of output 9 [2018-01-21 00:37:18,128 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,133 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,144 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,144 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:17, output treesize:13 [2018-01-21 00:37:18,170 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 23 [2018-01-21 00:37:18,177 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,178 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 27 [2018-01-21 00:37:18,179 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,183 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,188 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,189 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:31, output treesize:22 [2018-01-21 00:37:18,193 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 23 [2018-01-21 00:37:18,196 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,197 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,198 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,200 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 46 [2018-01-21 00:37:18,201 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,208 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,213 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,214 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:33, output treesize:29 [2018-01-21 00:37:18,217 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 39 treesize of output 30 [2018-01-21 00:37:18,219 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,220 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,221 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,221 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,222 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,222 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,225 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 77 [2018-01-21 00:37:18,226 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,235 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,242 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,243 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:42, output treesize:38 [2018-01-21 00:37:18,247 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 54 treesize of output 43 [2018-01-21 00:37:18,259 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,263 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,264 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,271 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,272 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,280 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,284 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,294 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,295 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,296 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:18,303 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 107 [2018-01-21 00:37:18,303 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,316 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,322 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,322 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:57, output treesize:38 [2018-01-21 00:37:18,350 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 36 treesize of output 26 [2018-01-21 00:37:18,368 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 3 [2018-01-21 00:37:18,368 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,370 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,371 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:18,371 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:3 [2018-01-21 00:37:18,382 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:18,382 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:18,446 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:18,449 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:18,453 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:18,453 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:14 [2018-01-21 00:37:18,560 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:18,562 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-21 00:37:18,562 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 15, 15, 12, 7] total 31 [2018-01-21 00:37:18,563 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:37:18,563 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-21 00:37:18,563 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-21 00:37:18,564 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=808, Unknown=0, NotChecked=0, Total=930 [2018-01-21 00:37:18,564 INFO L87 Difference]: Start difference. First operand 100 states and 106 transitions. Second operand 17 states. [2018-01-21 00:37:19,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:19,202 INFO L93 Difference]: Finished difference Result 161 states and 171 transitions. [2018-01-21 00:37:19,202 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-21 00:37:19,203 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 47 [2018-01-21 00:37:19,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:19,204 INFO L225 Difference]: With dead ends: 161 [2018-01-21 00:37:19,204 INFO L226 Difference]: Without dead ends: 125 [2018-01-21 00:37:19,205 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 158 SyntacticMatches, 16 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 647 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=587, Invalid=2065, Unknown=0, NotChecked=0, Total=2652 [2018-01-21 00:37:19,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2018-01-21 00:37:19,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 91. [2018-01-21 00:37:19,215 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-01-21 00:37:19,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 96 transitions. [2018-01-21 00:37:19,216 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 96 transitions. Word has length 47 [2018-01-21 00:37:19,216 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:19,216 INFO L432 AbstractCegarLoop]: Abstraction has 91 states and 96 transitions. [2018-01-21 00:37:19,216 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-21 00:37:19,216 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 96 transitions. [2018-01-21 00:37:19,218 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-21 00:37:19,218 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:19,218 INFO L322 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:19,218 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:19,218 INFO L82 PathProgramCache]: Analyzing trace with hash 716995032, now seen corresponding path program 1 times [2018-01-21 00:37:19,219 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:19,219 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:19,220 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-21 00:37:19,220 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:19,220 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:19,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:19,239 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:19,343 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:19,344 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:19,344 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:37:19,344 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 55 with the following transitions: [2018-01-21 00:37:19,344 INFO L201 CegarAbsIntRunner]: [0], [4], [6], [9], [11], [12], [13], [18], [20], [21], [22], [23], [24], [25], [29], [31], [34], [36], [37], [38], [43], [45], [46], [47], [48], [49], [50], [51], [52], [53], [54], [60], [72], [76], [78], [79], [80], [81], [82], [86], [90], [99], [103], [105], [106], [107], [113], [114], [115] [2018-01-21 00:37:19,346 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 00:37:19,347 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-21 00:37:19,958 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-21 00:37:19,959 INFO L268 AbstractInterpreter]: Visited 49 different actions 192 times. Merged at 43 different actions 134 times. Widened at 1 different actions 1 times. Found 10 fixpoints after 5 different actions. Largest state had 41 variables. [2018-01-21 00:37:19,967 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-21 00:37:19,967 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:19,967 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-21 00:37:19,977 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:19,977 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:20,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:20,012 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:20,019 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 6 treesize of output 5 [2018-01-21 00:37:20,019 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,023 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,023 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-21 00:37:20,053 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:20,054 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:20,054 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-21 00:37:20,054 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,057 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,057 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:8 [2018-01-21 00:37:20,084 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 8 [2018-01-21 00:37:20,092 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-21 00:37:20,092 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,104 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,143 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,144 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:8 [2018-01-21 00:37:20,211 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 16 treesize of output 12 [2018-01-21 00:37:20,222 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 13 [2018-01-21 00:37:20,223 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:20,226 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:20,229 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:20,229 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:16, output treesize:9 [2018-01-21 00:37:20,270 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:20,270 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:20,311 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 11 treesize of output 9 [2018-01-21 00:37:20,319 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 10 treesize of output 3 [2018-01-21 00:37:20,319 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,324 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:20,326 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:20,327 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:8 [2018-01-21 00:37:20,467 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:20,502 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:20,502 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 7 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-21 00:37:20,506 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:20,506 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:20,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:20,562 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:20,566 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 6 treesize of output 5 [2018-01-21 00:37:20,566 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,570 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,570 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-21 00:37:20,580 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:20,587 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:20,588 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-21 00:37:20,588 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,591 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,591 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:8 [2018-01-21 00:37:20,596 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 8 [2018-01-21 00:37:20,597 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-21 00:37:20,597 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,599 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,602 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,602 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:12 [2018-01-21 00:37:20,651 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 16 treesize of output 12 [2018-01-21 00:37:20,652 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-21 00:37:20,652 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,653 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,654 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:20,654 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:16, output treesize:4 [2018-01-21 00:37:20,657 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:20,657 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:20,727 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:20,728 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-21 00:37:20,729 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 12, 11, 11] total 28 [2018-01-21 00:37:20,729 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:37:20,729 INFO L409 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-01-21 00:37:20,730 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-01-21 00:37:20,730 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=681, Unknown=0, NotChecked=0, Total=756 [2018-01-21 00:37:20,730 INFO L87 Difference]: Start difference. First operand 91 states and 96 transitions. Second operand 21 states. [2018-01-21 00:37:21,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:21,404 INFO L93 Difference]: Finished difference Result 225 states and 240 transitions. [2018-01-21 00:37:21,404 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-21 00:37:21,405 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 54 [2018-01-21 00:37:21,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:21,406 INFO L225 Difference]: With dead ends: 225 [2018-01-21 00:37:21,406 INFO L226 Difference]: Without dead ends: 210 [2018-01-21 00:37:21,407 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 242 GetRequests, 199 SyntacticMatches, 3 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=320, Invalid=1402, Unknown=0, NotChecked=0, Total=1722 [2018-01-21 00:37:21,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 210 states. [2018-01-21 00:37:21,415 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 210 to 102. [2018-01-21 00:37:21,415 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 102 states. [2018-01-21 00:37:21,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 108 transitions. [2018-01-21 00:37:21,416 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 108 transitions. Word has length 54 [2018-01-21 00:37:21,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:21,416 INFO L432 AbstractCegarLoop]: Abstraction has 102 states and 108 transitions. [2018-01-21 00:37:21,416 INFO L433 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-01-21 00:37:21,416 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 108 transitions. [2018-01-21 00:37:21,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2018-01-21 00:37:21,417 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:21,417 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1] [2018-01-21 00:37:21,417 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:21,417 INFO L82 PathProgramCache]: Analyzing trace with hash -2069250024, now seen corresponding path program 1 times [2018-01-21 00:37:21,417 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:21,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:21,418 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:21,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:21,418 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:21,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:21,443 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:21,862 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 7 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:21,862 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:21,862 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:37:21,863 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 58 with the following transitions: [2018-01-21 00:37:21,863 INFO L201 CegarAbsIntRunner]: [0], [4], [6], [9], [11], [12], [13], [18], [20], [21], [22], [23], [24], [25], [29], [31], [34], [60], [62], [63], [64], [65], [72], [76], [78], [79], [80], [81], [82], [86], [90], [99], [103], [105], [106], [107], [113], [114], [115] [2018-01-21 00:37:21,864 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 00:37:21,865 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-21 00:37:22,185 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-21 00:37:22,185 INFO L268 AbstractInterpreter]: Visited 39 different actions 126 times. Merged at 33 different actions 79 times. Never widened. Found 8 fixpoints after 5 different actions. Largest state had 35 variables. [2018-01-21 00:37:22,190 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-21 00:37:22,190 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:22,190 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/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-01-21 00:37:22,210 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:22,210 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:22,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:22,240 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:22,243 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 6 treesize of output 5 [2018-01-21 00:37:22,244 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,247 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,247 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-21 00:37:22,277 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:22,278 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:22,279 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-21 00:37:22,279 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,284 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,285 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:20, output treesize:14 [2018-01-21 00:37:22,343 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 8 [2018-01-21 00:37:22,345 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 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-01-21 00:37:22,345 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,346 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,351 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,351 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:26, output treesize:22 [2018-01-21 00:37:22,375 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 32 [2018-01-21 00:37:22,377 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-01-21 00:37:22,377 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,380 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,384 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,384 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:36, output treesize:28 [2018-01-21 00:37:22,438 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 30 [2018-01-21 00:37:22,443 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 20 treesize of output 19 [2018-01-21 00:37:22,443 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:22,449 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 5 treesize of output 1 [2018-01-21 00:37:22,449 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,453 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:22,457 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:22,457 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:37, output treesize:11 [2018-01-21 00:37:22,507 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 7 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:22,507 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:22,576 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 30 [2018-01-21 00:37:22,590 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 11 treesize of output 10 [2018-01-21 00:37:22,590 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,610 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 25 treesize of output 23 [2018-01-21 00:37:22,611 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 8 treesize of output 1 [2018-01-21 00:37:22,611 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,615 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,622 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 22 treesize of output 26 [2018-01-21 00:37:22,625 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 15 treesize of output 7 [2018-01-21 00:37:22,625 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,636 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 1 case distinctions, treesize of input 18 treesize of output 14 [2018-01-21 00:37:22,637 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:22,644 INFO L267 ElimStorePlain]: Start of recursive call 6: 2 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:22,649 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 28 [2018-01-21 00:37:22,651 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 17 treesize of output 9 [2018-01-21 00:37:22,651 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:22,662 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 1 case distinctions, treesize of input 20 treesize of output 16 [2018-01-21 00:37:22,663 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:22,671 INFO L267 ElimStorePlain]: Start of recursive call 9: 2 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:22,690 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, 1 dim-2 vars, End of recursive call: and 7 xjuncts. [2018-01-21 00:37:22,707 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 6 xjuncts. [2018-01-21 00:37:22,707 INFO L202 ElimStorePlain]: Needed 11 recursive calls to eliminate 1 variables, input treesize:38, output treesize:54 [2018-01-21 00:37:22,951 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 7 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:22,972 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:22,972 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 9 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-21 00:37:22,975 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:22,975 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:35,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2018-01-21 00:37:35,078 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-01-21 00:37:35,078 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 14, 14] total 29 [2018-01-21 00:37:35,078 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:37:35,078 INFO L409 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-01-21 00:37:35,078 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-01-21 00:37:35,079 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=719, Unknown=0, NotChecked=0, Total=812 [2018-01-21 00:37:35,079 INFO L87 Difference]: Start difference. First operand 102 states and 108 transitions. Second operand 20 states. [2018-01-21 00:37:35,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:35,888 INFO L93 Difference]: Finished difference Result 173 states and 184 transitions. [2018-01-21 00:37:35,888 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-01-21 00:37:35,888 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 57 [2018-01-21 00:37:35,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:35,889 INFO L225 Difference]: With dead ends: 173 [2018-01-21 00:37:35,889 INFO L226 Difference]: Without dead ends: 170 [2018-01-21 00:37:35,890 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 95 SyntacticMatches, 7 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 183 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=315, Invalid=1325, Unknown=0, NotChecked=0, Total=1640 [2018-01-21 00:37:35,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2018-01-21 00:37:35,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 146. [2018-01-21 00:37:35,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 146 states. [2018-01-21 00:37:35,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 155 transitions. [2018-01-21 00:37:35,899 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 155 transitions. Word has length 57 [2018-01-21 00:37:35,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:35,899 INFO L432 AbstractCegarLoop]: Abstraction has 146 states and 155 transitions. [2018-01-21 00:37:35,899 INFO L433 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-01-21 00:37:35,899 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 155 transitions. [2018-01-21 00:37:35,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-21 00:37:35,900 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:35,900 INFO L322 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:35,900 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:35,900 INFO L82 PathProgramCache]: Analyzing trace with hash 1645798842, now seen corresponding path program 1 times [2018-01-21 00:37:35,901 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:35,901 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:35,901 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:35,901 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:35,902 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:35,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:35,922 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:36,372 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:36,372 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:36,372 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:37:36,372 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 60 with the following transitions: [2018-01-21 00:37:36,373 INFO L201 CegarAbsIntRunner]: [0], [4], [6], [9], [11], [12], [13], [18], [20], [21], [22], [23], [24], [25], [29], [31], [34], [36], [37], [38], [43], [45], [46], [47], [48], [49], [50], [51], [52], [53], [54], [60], [72], [76], [78], [79], [80], [81], [82], [86], [90], [92], [93], [94], [95], [99], [103], [105], [106], [107], [113], [114], [115] [2018-01-21 00:37:36,375 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 00:37:36,375 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-21 00:37:37,170 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-21 00:37:37,170 INFO L268 AbstractInterpreter]: Visited 53 different actions 231 times. Merged at 47 different actions 164 times. Widened at 2 different actions 2 times. Found 16 fixpoints after 8 different actions. Largest state had 45 variables. [2018-01-21 00:37:37,176 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-21 00:37:37,176 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:37,176 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/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-01-21 00:37:37,182 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:37,182 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:37,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:37,219 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:37,430 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 8 [2018-01-21 00:37:37,445 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-21 00:37:37,446 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:37,460 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:37,511 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:37,511 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:43 [2018-01-21 00:37:37,934 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 33 [2018-01-21 00:37:37,941 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 30 [2018-01-21 00:37:37,942 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-21 00:37:37,955 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-21 00:37:37,971 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-21 00:37:37,971 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:50, output treesize:67 [2018-01-21 00:37:38,483 WARN L1029 $PredicateComparison]: unable to prove that (exists ((v_prenex_7 Int) (main_~x~10.base Int)) (let ((.cse0 (store |c_old(#valid)| main_~x~10.base 1))) (and (= (select |c_old(#valid)| main_~x~10.base) 0) (not (= v_prenex_7 0)) (= |c_#valid| (store (store .cse0 v_prenex_7 0) main_~x~10.base 0)) (not (= main_~x~10.base 0)) (= 0 (select .cse0 v_prenex_7))))) is different from true [2018-01-21 00:37:38,499 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 2 times theorem prover too weak. 0 trivial. 2 not checked. [2018-01-21 00:37:38,499 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:38,532 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 22 [2018-01-21 00:37:38,536 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 10 treesize of output 14 [2018-01-21 00:37:38,536 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:38,539 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:38,550 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:38,550 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:51, output treesize:45 [2018-01-21 00:37:38,814 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 27 treesize of output 23 [2018-01-21 00:37:38,828 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-01-21 00:37:38,829 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:38,839 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-21 00:37:38,861 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 22 treesize of output 18 [2018-01-21 00:37:38,872 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 14 treesize of output 12 [2018-01-21 00:37:38,873 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:38,874 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2018-01-21 00:37:38,874 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:38,881 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:38,908 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 13 [2018-01-21 00:37:38,915 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-01-21 00:37:38,915 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:38,919 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:38,932 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-2 vars, End of recursive call: and 4 xjuncts. [2018-01-21 00:37:38,933 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 3 variables, input treesize:65, output treesize:33 [2018-01-21 00:37:39,475 WARN L1007 $PredicateComparison]: unable to prove that (forall ((|v_main_#t~malloc8.base_15| Int) (|v_main_#t~malloc1.base_19| Int)) (let ((.cse0 (store |c_#valid| |v_main_#t~malloc1.base_19| 1))) (or (not (= (select .cse0 |v_main_#t~malloc8.base_15|) 0)) (= 0 |v_main_#t~malloc8.base_15|) (not (= 0 (select |c_#valid| |v_main_#t~malloc1.base_19|))) (= 0 |v_main_#t~malloc1.base_19|) (= |c_old(#valid)| (store (store .cse0 |v_main_#t~malloc8.base_15| 0) |v_main_#t~malloc1.base_19| 0)) (= |v_main_#t~malloc1.base_19| |v_main_#t~malloc8.base_15|)))) is different from false [2018-01-21 00:37:39,481 WARN L1007 $PredicateComparison]: unable to prove that (forall ((|v_main_#t~malloc8.base_15| Int) (|v_main_#t~malloc1.base_19| Int)) (let ((.cse0 (store |c_#valid| |v_main_#t~malloc1.base_19| 1))) (or (not (= (select .cse0 |v_main_#t~malloc8.base_15|) 0)) (= 0 |v_main_#t~malloc8.base_15|) (= |c_#valid| (store (store .cse0 |v_main_#t~malloc8.base_15| 0) |v_main_#t~malloc1.base_19| 0)) (not (= 0 (select |c_#valid| |v_main_#t~malloc1.base_19|))) (= 0 |v_main_#t~malloc1.base_19|) (= |v_main_#t~malloc1.base_19| |v_main_#t~malloc8.base_15|)))) is different from false [2018-01-21 00:37:39,502 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2018-01-21 00:37:39,523 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:39,523 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 11 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-21 00:37:39,528 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:39,528 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:37:39,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:39,592 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:39,887 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 8 [2018-01-21 00:37:39,889 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-21 00:37:39,889 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:39,891 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:39,900 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:39,900 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:50, output treesize:51 [2018-01-21 00:37:40,070 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 33 [2018-01-21 00:37:40,072 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 22 [2018-01-21 00:37:40,072 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:40,076 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:40,082 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:40,082 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:55, output treesize:36 [2018-01-21 00:37:40,382 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:40,382 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:40,397 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 14 [2018-01-21 00:37:40,402 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 10 treesize of output 14 [2018-01-21 00:37:40,403 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:40,404 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:40,408 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:40,408 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:25, output treesize:18 [2018-01-21 00:37:41,089 WARN L1007 $PredicateComparison]: unable to prove that (forall ((v_prenex_17 Int) (|v_main_#t~malloc1.base_20| Int)) (let ((.cse0 (store |c_#valid| |v_main_#t~malloc1.base_20| 1))) (or (= 0 v_prenex_17) (not (= 0 (select |c_#valid| |v_main_#t~malloc1.base_20|))) (not (= 0 (select .cse0 v_prenex_17))) (= (store (store .cse0 v_prenex_17 0) |v_main_#t~malloc1.base_20| 0) |c_old(#valid)|) (= 0 |v_main_#t~malloc1.base_20|)))) is different from false [2018-01-21 00:37:41,095 WARN L1007 $PredicateComparison]: unable to prove that (forall ((v_prenex_17 Int) (|v_main_#t~malloc1.base_20| Int)) (let ((.cse0 (store |c_#valid| |v_main_#t~malloc1.base_20| 1))) (or (= 0 v_prenex_17) (not (= 0 (select |c_#valid| |v_main_#t~malloc1.base_20|))) (not (= 0 (select .cse0 v_prenex_17))) (= 0 |v_main_#t~malloc1.base_20|) (= |c_#valid| (store (store .cse0 v_prenex_17 0) |v_main_#t~malloc1.base_20| 0))))) is different from false [2018-01-21 00:37:41,134 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2018-01-21 00:37:41,136 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-21 00:37:41,136 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16, 16, 16, 14] total 67 [2018-01-21 00:37:41,136 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:37:41,136 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-01-21 00:37:41,137 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-01-21 00:37:41,138 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=235, Invalid=3906, Unknown=31, NotChecked=384, Total=4556 [2018-01-21 00:37:41,138 INFO L87 Difference]: Start difference. First operand 146 states and 155 transitions. Second operand 28 states. [2018-01-21 00:37:42,820 WARN L146 SmtUtils]: Spent 134ms on a formula simplification. DAG size of input: 100 DAG size of output 46 [2018-01-21 00:37:43,208 WARN L146 SmtUtils]: Spent 106ms on a formula simplification. DAG size of input: 101 DAG size of output 38 [2018-01-21 00:37:43,425 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 99 DAG size of output 41 [2018-01-21 00:37:43,697 WARN L146 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 127 DAG size of output 44 [2018-01-21 00:37:44,131 WARN L146 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 85 DAG size of output 63 [2018-01-21 00:37:44,399 WARN L146 SmtUtils]: Spent 143ms on a formula simplification. DAG size of input: 93 DAG size of output 68 [2018-01-21 00:37:44,616 WARN L146 SmtUtils]: Spent 128ms on a formula simplification. DAG size of input: 71 DAG size of output 49 [2018-01-21 00:37:44,958 WARN L146 SmtUtils]: Spent 180ms on a formula simplification. DAG size of input: 83 DAG size of output 75 [2018-01-21 00:37:45,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:37:45,364 INFO L93 Difference]: Finished difference Result 201 states and 214 transitions. [2018-01-21 00:37:45,364 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-21 00:37:45,364 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 59 [2018-01-21 00:37:45,365 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:37:45,365 INFO L225 Difference]: With dead ends: 201 [2018-01-21 00:37:45,366 INFO L226 Difference]: Without dead ends: 198 [2018-01-21 00:37:45,367 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 272 GetRequests, 179 SyntacticMatches, 6 SemanticMatches, 87 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 1395 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=571, Invalid=6714, Unknown=37, NotChecked=510, Total=7832 [2018-01-21 00:37:45,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2018-01-21 00:37:45,376 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 179. [2018-01-21 00:37:45,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 179 states. [2018-01-21 00:37:45,377 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 179 states to 179 states and 191 transitions. [2018-01-21 00:37:45,377 INFO L78 Accepts]: Start accepts. Automaton has 179 states and 191 transitions. Word has length 59 [2018-01-21 00:37:45,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:37:45,377 INFO L432 AbstractCegarLoop]: Abstraction has 179 states and 191 transitions. [2018-01-21 00:37:45,377 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-01-21 00:37:45,378 INFO L276 IsEmpty]: Start isEmpty. Operand 179 states and 191 transitions. [2018-01-21 00:37:45,379 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-01-21 00:37:45,379 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:37:45,379 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:37:45,379 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-21 00:37:45,379 INFO L82 PathProgramCache]: Analyzing trace with hash 2087622424, now seen corresponding path program 2 times [2018-01-21 00:37:45,379 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:37:45,380 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:45,380 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:37:45,380 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:37:45,380 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:37:45,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:37:45,392 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:37:45,782 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:45,782 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:45,782 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:37:45,782 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-21 00:37:45,783 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-21 00:37:45,783 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:37:45,783 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/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-01-21 00:37:45,793 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-21 00:37:45,793 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-21 00:37:45,804 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:37:45,829 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:37:45,842 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-21 00:37:45,845 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:37:45,886 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-01-21 00:37:45,888 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-01-21 00:37:45,888 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,889 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,892 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,893 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2018-01-21 00:37:45,898 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 26 treesize of output 21 [2018-01-21 00:37:45,904 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:45,904 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-21 00:37:45,905 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,914 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,918 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,918 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:20 [2018-01-21 00:37:45,942 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 36 treesize of output 29 [2018-01-21 00:37:45,944 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:45,944 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:45,945 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:45,947 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-21 00:37:45,947 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,952 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,956 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:45,956 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:39, output treesize:20 [2018-01-21 00:37:46,039 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 32 treesize of output 40 [2018-01-21 00:37:46,042 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 33 treesize of output 32 [2018-01-21 00:37:46,042 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,060 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,065 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,066 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:38, output treesize:34 [2018-01-21 00:37:46,114 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:46,127 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 49 treesize of output 52 [2018-01-21 00:37:46,130 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,132 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 38 [2018-01-21 00:37:46,133 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,149 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,160 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 4 case distinctions, treesize of input 32 treesize of output 61 [2018-01-21 00:37:46,161 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 4 xjuncts. [2018-01-21 00:37:46,187 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:46,207 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 3 xjuncts. [2018-01-21 00:37:46,207 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:55, output treesize:116 [2018-01-21 00:37:46,265 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 47 treesize of output 49 [2018-01-21 00:37:46,267 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,267 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 53 [2018-01-21 00:37:46,268 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,285 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:46,328 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 47 treesize of output 49 [2018-01-21 00:37:46,330 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,330 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 53 [2018-01-21 00:37:46,331 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,348 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:46,390 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 60 treesize of output 58 [2018-01-21 00:37:46,392 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,393 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 66 [2018-01-21 00:37:46,393 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,407 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,431 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 3 dim-2 vars, End of recursive call: 1 dim-0 vars, and 3 xjuncts. [2018-01-21 00:37:46,431 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:155, output treesize:143 [2018-01-21 00:37:46,498 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 66 treesize of output 66 [2018-01-21 00:37:46,504 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 55 [2018-01-21 00:37:46,504 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,541 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:37:46,548 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 36 [2018-01-21 00:37:46,549 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:46,569 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:46,614 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 57 [2018-01-21 00:37:46,618 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 42 [2018-01-21 00:37:46,619 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,635 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,672 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 57 [2018-01-21 00:37:46,675 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 42 [2018-01-21 00:37:46,676 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,708 INFO L267 ElimStorePlain]: Start of recursive call 7: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,729 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 3 dim-2 vars, End of recursive call: 1 dim-0 vars, and 3 xjuncts. [2018-01-21 00:37:46,729 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 4 variables, input treesize:173, output treesize:128 [2018-01-21 00:37:46,790 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 78 treesize of output 57 [2018-01-21 00:37:46,792 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,793 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,794 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:37:46,794 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 69 treesize of output 106 [2018-01-21 00:37:46,794 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,811 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:46,824 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-21 00:37:46,858 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 38 [2018-01-21 00:37:46,860 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 33 [2018-01-21 00:37:46,861 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,864 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,885 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 38 [2018-01-21 00:37:46,890 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 45 [2018-01-21 00:37:46,890 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,893 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:37:46,901 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 3 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:37:46,901 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 4 variables, input treesize:185, output treesize:73 [2018-01-21 00:37:47,083 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 2 case distinctions, treesize of input 53 treesize of output 55 [2018-01-21 00:37:47,114 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 39 [2018-01-21 00:37:47,114 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,138 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 18 [2018-01-21 00:37:47,138 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,159 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 24 treesize of output 19 [2018-01-21 00:37:47,159 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,179 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 9 [2018-01-21 00:37:47,180 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,198 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 29 treesize of output 30 [2018-01-21 00:37:47,199 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:47,217 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 22 treesize of output 32 [2018-01-21 00:37:47,218 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 4 xjuncts. [2018-01-21 00:37:47,227 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 27 [2018-01-21 00:37:47,228 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 4 xjuncts. [2018-01-21 00:37:47,256 INFO L267 ElimStorePlain]: Start of recursive call 2: 8 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:47,287 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 3 case distinctions, treesize of input 49 treesize of output 57 [2018-01-21 00:37:47,292 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 18 [2018-01-21 00:37:47,292 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,340 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 25 [2018-01-21 00:37:47,340 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,383 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 43 treesize of output 38 [2018-01-21 00:37:47,383 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,439 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 18 treesize of output 17 [2018-01-21 00:37:47,439 INFO L267 ElimStorePlain]: Start of recursive call 14: End of recursive call: and 2 xjuncts. [2018-01-21 00:37:47,485 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 14 treesize of output 9 [2018-01-21 00:37:47,486 INFO L267 ElimStorePlain]: Start of recursive call 15: End of recursive call: and 1 xjuncts. [2018-01-21 00:37:47,565 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 19 treesize of output 41 [2018-01-21 00:37:47,567 INFO L267 ElimStorePlain]: Start of recursive call 16: End of recursive call: and 11 xjuncts. [2018-01-21 00:37:47,596 INFO L267 ElimStorePlain]: Start of recursive call 10: 12 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:47,613 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:37:47,613 INFO L202 ElimStorePlain]: Needed 16 recursive calls to eliminate 4 variables, input treesize:213, output treesize:22 [2018-01-21 00:37:47,746 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:37:47,746 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:37:48,127 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:48,128 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:37:48,133 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-21 00:37:48,133 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:43, output treesize:77 [2018-01-21 00:37:50,507 WARN L143 SmtUtils]: Spent 2028ms on a formula simplification that was a NOOP. DAG size: 50 [2018-01-21 00:38:08,904 WARN L143 SmtUtils]: Spent 6150ms on a formula simplification that was a NOOP. DAG size: 57 Received shutdown request... [2018-01-21 00:38:11,057 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-21 00:38:11,058 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-21 00:38:11,059 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.01 12:38:11 BoogieIcfgContainer [2018-01-21 00:38:11,059 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-21 00:38:11,060 INFO L168 Benchmark]: Toolchain (without parser) took 58628.08 ms. Allocated memory was 301.5 MB in the beginning and 837.8 MB in the end (delta: 536.3 MB). Free memory was 259.8 MB in the beginning and 374.5 MB in the end (delta: -114.7 MB). Peak memory consumption was 421.7 MB. Max. memory is 5.3 GB. [2018-01-21 00:38:11,060 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 301.5 MB. Free memory is still 265.8 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-21 00:38:11,061 INFO L168 Benchmark]: CACSL2BoogieTranslator took 212.03 ms. Allocated memory is still 301.5 MB. Free memory was 258.8 MB in the beginning and 247.7 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 5.3 GB. [2018-01-21 00:38:11,061 INFO L168 Benchmark]: Boogie Preprocessor took 40.08 ms. Allocated memory is still 301.5 MB. Free memory was 247.7 MB in the beginning and 246.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. [2018-01-21 00:38:11,061 INFO L168 Benchmark]: RCFGBuilder took 330.22 ms. Allocated memory is still 301.5 MB. Free memory was 246.7 MB in the beginning and 224.1 MB in the end (delta: 22.7 MB). Peak memory consumption was 22.7 MB. Max. memory is 5.3 GB. [2018-01-21 00:38:11,062 INFO L168 Benchmark]: TraceAbstraction took 58040.07 ms. Allocated memory was 301.5 MB in the beginning and 837.8 MB in the end (delta: 536.3 MB). Free memory was 224.1 MB in the beginning and 374.5 MB in the end (delta: -150.4 MB). Peak memory consumption was 385.9 MB. Max. memory is 5.3 GB. [2018-01-21 00:38:11,063 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.15 ms. Allocated memory is still 301.5 MB. Free memory is still 265.8 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 212.03 ms. Allocated memory is still 301.5 MB. Free memory was 258.8 MB in the beginning and 247.7 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 40.08 ms. Allocated memory is still 301.5 MB. Free memory was 247.7 MB in the beginning and 246.7 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. * RCFGBuilder took 330.22 ms. Allocated memory is still 301.5 MB. Free memory was 246.7 MB in the beginning and 224.1 MB in the end (delta: 22.7 MB). Peak memory consumption was 22.7 MB. Max. memory is 5.3 GB. * TraceAbstraction took 58040.07 ms. Allocated memory was 301.5 MB in the beginning and 837.8 MB in the end (delta: 536.3 MB). Free memory was 224.1 MB in the beginning and 374.5 MB in the end (delta: -150.4 MB). Peak memory consumption was 385.9 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.analysis.abstractinterpretationv2: - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 33 LocStat_MAX_WEQGRAPH_SIZE : 0 LocStat_MAX_SIZEOF_WEQEDGELABEL : 0 LocStat_NO_SUPPORTING_EQUALITIES : 280 LocStat_NO_SUPPORTING_DISEQUALITIES : 42 LocStat_NO_DISJUNCTIONS : -66 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 39 TransStat_MAX_WEQGRAPH_SIZE : 0 TransStat_MAX_SIZEOF_WEQEDGELABEL : 0 TransStat_NO_SUPPORTING_EQUALITIES : 80 TransStat_NO_SUPPORTING_DISEQUALITIES : 12 TransStat_NO_DISJUNCTIONS : 44 TransStat_MAX_NO_DISJUNCTIONS : 4 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 2.286058 RENAME_VARIABLES(MILLISECONDS) : 0.869034 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 0.518070 PROJECTAWAY(MILLISECONDS) : 0.354506 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.001688 DISJOIN(MILLISECONDS) : 0.847262 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.914338 ADD_EQUALITY(MILLISECONDS) : 0.018958 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.034240 #CONJOIN_DISJUNCTIVE : 138 #RENAME_VARIABLES : 254 #UNFREEZE : 0 #CONJOIN : 231 #PROJECTAWAY : 163 #ADD_WEAK_EQUALITY : 34 #DISJOIN : 23 #RENAME_VARIABLES_DISJUNCTIVE : 233 #ADD_EQUALITY : 91 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 8 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 46 LocStat_MAX_WEQGRAPH_SIZE : 0 LocStat_MAX_SIZEOF_WEQEDGELABEL : 0 LocStat_NO_SUPPORTING_EQUALITIES : 449 LocStat_NO_SUPPORTING_DISEQUALITIES : 76 LocStat_NO_DISJUNCTIONS : -92 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 53 TransStat_MAX_WEQGRAPH_SIZE : 0 TransStat_MAX_SIZEOF_WEQEDGELABEL : 0 TransStat_NO_SUPPORTING_EQUALITIES : 101 TransStat_NO_SUPPORTING_DISEQUALITIES : 19 TransStat_NO_DISJUNCTIONS : 59 TransStat_MAX_NO_DISJUNCTIONS : 4 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 0.420814 RENAME_VARIABLES(MILLISECONDS) : 0.345790 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 0.396119 PROJECTAWAY(MILLISECONDS) : 0.162612 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.001095 DISJOIN(MILLISECONDS) : 0.797344 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.370826 ADD_EQUALITY(MILLISECONDS) : 0.012449 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.012920 #CONJOIN_DISJUNCTIVE : 313 #RENAME_VARIABLES : 594 #UNFREEZE : 0 #CONJOIN : 439 #PROJECTAWAY : 343 #ADD_WEAK_EQUALITY : 66 #DISJOIN : 15 #RENAME_VARIABLES_DISJUNCTIVE : 563 #ADD_EQUALITY : 133 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 12 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 36 LocStat_MAX_WEQGRAPH_SIZE : 0 LocStat_MAX_SIZEOF_WEQEDGELABEL : 0 LocStat_NO_SUPPORTING_EQUALITIES : 293 LocStat_NO_SUPPORTING_DISEQUALITIES : 41 LocStat_NO_DISJUNCTIONS : -72 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 43 TransStat_MAX_WEQGRAPH_SIZE : 0 TransStat_MAX_SIZEOF_WEQEDGELABEL : 0 TransStat_NO_SUPPORTING_EQUALITIES : 86 TransStat_NO_SUPPORTING_DISEQUALITIES : 14 TransStat_NO_DISJUNCTIONS : 49 TransStat_MAX_NO_DISJUNCTIONS : 4 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 0.286870 RENAME_VARIABLES(MILLISECONDS) : 0.213691 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 0.264043 PROJECTAWAY(MILLISECONDS) : 0.139474 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.000857 DISJOIN(MILLISECONDS) : 0.822459 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.237280 ADD_EQUALITY(MILLISECONDS) : 0.009802 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.014579 #CONJOIN_DISJUNCTIVE : 211 #RENAME_VARIABLES : 403 #UNFREEZE : 0 #CONJOIN : 321 #PROJECTAWAY : 235 #ADD_WEAK_EQUALITY : 46 #DISJOIN : 10 #RENAME_VARIABLES_DISJUNCTIVE : 373 #ADD_EQUALITY : 105 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 10 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 49 LocStat_MAX_WEQGRAPH_SIZE : 0 LocStat_MAX_SIZEOF_WEQEDGELABEL : 0 LocStat_NO_SUPPORTING_EQUALITIES : 463 LocStat_NO_SUPPORTING_DISEQUALITIES : 76 LocStat_NO_DISJUNCTIONS : -98 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 57 TransStat_MAX_WEQGRAPH_SIZE : 0 TransStat_MAX_SIZEOF_WEQEDGELABEL : 0 TransStat_NO_SUPPORTING_EQUALITIES : 123 TransStat_NO_SUPPORTING_DISEQUALITIES : 23 TransStat_NO_DISJUNCTIONS : 67 TransStat_MAX_NO_DISJUNCTIONS : 4 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 0.246478 RENAME_VARIABLES(MILLISECONDS) : 0.203915 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 0.231260 PROJECTAWAY(MILLISECONDS) : 0.120474 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.002029 DISJOIN(MILLISECONDS) : 0.671687 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.224612 ADD_EQUALITY(MILLISECONDS) : 0.019588 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.014052 #CONJOIN_DISJUNCTIVE : 380 #RENAME_VARIABLES : 766 #UNFREEZE : 0 #CONJOIN : 578 #PROJECTAWAY : 448 #ADD_WEAK_EQUALITY : 67 #DISJOIN : 31 #RENAME_VARIABLES_DISJUNCTIVE : 689 #ADD_EQUALITY : 145 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 15 * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 3 procedures, 58 locations, 3 error locations. UNSAFE Result, 0.1s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=58occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 3 NumberOfCodeBlocks, 3 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 0 ConstructedInterpolants, 0 QuantifiedInterpolants, 0 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 0 InterpolantComputations, 0 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: [L631] struct T2* first = ((void *)0); [L632] struct T2* last = ((void *)0); VAL [first={0:0}, last={0:0}] [L633] COND FALSE !(__VERIFIER_nondet_int()) [L663] COND FALSE !(\read(*first)) VAL [first={0:0}, last={0:0}] [L674] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 58 locations, 3 error locations. UNSAFE Result, 0.2s OverallTime, 2 OverallIterations, 1 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 62 SDtfs, 0 SDslu, 0 SDs, 0 SdLazy, 0 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=58occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 1 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 27 NumberOfCodeBlocks, 27 NumberOfCodeBlocksAsserted, 2 NumberOfCheckSat, 11 ConstructedInterpolants, 0 QuantifiedInterpolants, 121 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 1 InterpolantComputations, 1 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 620]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 620). Cancelled while BasicCegarLoop was analyzing trace of length 65 with TraceHistMax 3, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 55 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 58 locations, 3 error locations. TIMEOUT Result, 57.5s OverallTime, 11 OverallIterations, 3 TraceHistogramMax, 7.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 557 SDtfs, 2102 SDslu, 3340 SDs, 0 SdLazy, 3340 SolverSat, 251 SolverUnsat, 12 SolverUnknown, 0 SolverNotchecked, 2.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1086 GetRequests, 776 SyntacticMatches, 39 SemanticMatches, 271 ConstructedPredicates, 6 IntricatePredicates, 0 DeprecatedPredicates, 2665 ImplicationChecksByTransitivity, 10.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=179occurred in iteration=10, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 2.4s AbstIntTime, 4 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 10 MinimizatonAttempts, 275 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 12.5s SatisfiabilityAnalysisTime, 9.1s InterpolantComputationTime, 882 NumberOfCodeBlocks, 882 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 1250 ConstructedInterpolants, 104 QuantifiedInterpolants, 912316 SizeOfPredicates, 115 NumberOfNonLiveVariables, 1557 ConjunctsInSsa, 259 ConjunctsInUnsatCore, 28 InterpolantComputations, 5 PerfectInterpolantSequences, 100/279 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate proved your program to be incorrect! Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-1-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-1-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-2-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-2-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-3-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-3-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-21_00-38-11-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0504_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-21_00-38-11-074.csv Completed graceful shutdown