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-ext/tree_parent_ptr_true-valid-memsafety_false-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-21 00:38:54,758 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-21 00:38:54,792 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-21 00:38:54,808 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-21 00:38:54,809 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-21 00:38:54,810 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-21 00:38:54,811 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-21 00:38:54,813 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-21 00:38:54,815 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-21 00:38:54,816 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-21 00:38:54,816 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-21 00:38:54,817 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-21 00:38:54,818 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-21 00:38:54,819 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-21 00:38:54,820 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-21 00:38:54,822 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-21 00:38:54,825 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-21 00:38:54,826 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-21 00:38:54,828 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-21 00:38:54,829 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-21 00:38:54,831 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-21 00:38:54,832 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-21 00:38:54,832 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-21 00:38:54,833 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-21 00:38:54,833 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-21 00:38:54,835 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-21 00:38:54,835 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-21 00:38:54,836 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-21 00:38:54,836 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-21 00:38:54,836 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-21 00:38:54,837 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-21 00:38:54,837 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:38:54,847 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-21 00:38:54,847 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-21 00:38:54,848 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-21 00:38:54,848 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-21 00:38:54,848 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-21 00:38:54,849 INFO L133 SettingsManager]: * Deactivate Weak Equivalences=true [2018-01-21 00:38:54,849 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-21 00:38:54,849 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-21 00:38:54,850 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-21 00:38:54,850 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-21 00:38:54,850 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-21 00:38:54,850 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-21 00:38:54,850 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-21 00:38:54,851 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-21 00:38:54,851 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-21 00:38:54,851 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-21 00:38:54,851 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-21 00:38:54,851 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-21 00:38:54,852 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-21 00:38:54,852 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-21 00:38:54,852 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-21 00:38:54,852 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-21 00:38:54,852 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-21 00:38:54,852 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-21 00:38:54,853 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-21 00:38:54,853 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-21 00:38:54,853 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-21 00:38:54,853 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-21 00:38:54,853 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-21 00:38:54,854 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-21 00:38:54,854 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-21 00:38:54,854 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-21 00:38:54,854 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-21 00:38:54,854 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-21 00:38:54,855 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-21 00:38:54,855 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-21 00:38:54,855 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-21 00:38:54,856 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-21 00:38:54,856 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-21 00:38:54,891 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-21 00:38:54,903 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-21 00:38:54,907 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-21 00:38:54,909 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-21 00:38:54,909 INFO L276 PluginConnector]: CDTParser initialized [2018-01-21 00:38:54,910 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety-ext/tree_parent_ptr_true-valid-memsafety_false-termination.i [2018-01-21 00:38:55,067 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-21 00:38:55,071 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-21 00:38:55,072 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-21 00:38:55,072 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-21 00:38:55,077 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-21 00:38:55,078 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,080 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6350f34a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55, skipping insertion in model container [2018-01-21 00:38:55,080 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,095 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-21 00:38:55,132 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-21 00:38:55,254 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-21 00:38:55,279 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-21 00:38:55,289 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55 WrapperNode [2018-01-21 00:38:55,289 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-21 00:38:55,290 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-21 00:38:55,290 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-21 00:38:55,290 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-21 00:38:55,302 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,302 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,313 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,314 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,320 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,324 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,326 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (1/1) ... [2018-01-21 00:38:55,328 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-21 00:38:55,328 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-21 00:38:55,328 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-21 00:38:55,328 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-21 00:38:55,330 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (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:38:55,378 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-21 00:38:55,378 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-21 00:38:55,378 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-21 00:38:55,378 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-21 00:38:55,378 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-21 00:38:55,378 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-21 00:38:55,378 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-21 00:38:55,379 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-21 00:38:55,744 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-21 00:38:55,744 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.01 12:38:55 BoogieIcfgContainer [2018-01-21 00:38:55,745 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-21 00:38:55,746 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-21 00:38:55,746 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-21 00:38:55,748 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-21 00:38:55,748 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.01 12:38:55" (1/3) ... [2018-01-21 00:38:55,749 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@108b0005 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.01 12:38:55, skipping insertion in model container [2018-01-21 00:38:55,750 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 12:38:55" (2/3) ... [2018-01-21 00:38:55,750 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@108b0005 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.01 12:38:55, skipping insertion in model container [2018-01-21 00:38:55,750 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.01 12:38:55" (3/3) ... [2018-01-21 00:38:55,752 INFO L105 eAbstractionObserver]: Analyzing ICFG tree_parent_ptr_true-valid-memsafety_false-termination.i [2018-01-21 00:38:55,760 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-21 00:38:55,766 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-21 00:38:55,809 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 00:38:55,810 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 00:38:55,810 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 00:38:55,810 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 00:38:55,810 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 00:38:55,810 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 00:38:55,810 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 00:38:55,810 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-21 00:38:55,811 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 00:38:55,826 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states. [2018-01-21 00:38:55,831 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-21 00:38:55,831 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:55,832 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-21 00:38:55,832 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-21 00:38:55,835 INFO L82 PathProgramCache]: Analyzing trace with hash 185475, now seen corresponding path program 1 times [2018-01-21 00:38:55,837 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:55,881 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:55,881 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:55,881 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:55,881 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:55,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:38:55,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:38:55,939 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-21 00:38:55,946 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:38:55,952 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 00:38:55,952 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 00:38:55,952 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 00:38:55,952 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 00:38:55,952 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 00:38:55,953 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 00:38:55,953 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 00:38:55,953 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-21 00:38:55,953 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 00:38:55,956 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states. [2018-01-21 00:38:55,957 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-21 00:38:55,958 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:55,958 INFO L322 BasicCegarLoop]: trace histogram [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:38:55,958 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 00:38:55,958 INFO L82 PathProgramCache]: Analyzing trace with hash -1602735979, now seen corresponding path program 1 times [2018-01-21 00:38:55,958 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:55,959 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:55,959 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:55,960 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:55,960 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:55,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:38:55,992 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:38:56,034 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:38:56,036 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:38:56,036 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 00:38:56,037 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:38:56,039 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-21 00:38:56,132 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-21 00:38:56,132 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 00:38:56,135 INFO L87 Difference]: Start difference. First operand 92 states. Second operand 2 states. [2018-01-21 00:38:56,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:38:56,161 INFO L93 Difference]: Finished difference Result 173 states and 199 transitions. [2018-01-21 00:38:56,161 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-21 00:38:56,162 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 21 [2018-01-21 00:38:56,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:38:56,174 INFO L225 Difference]: With dead ends: 173 [2018-01-21 00:38:56,174 INFO L226 Difference]: Without dead ends: 89 [2018-01-21 00:38:56,177 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:38:56,194 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-01-21 00:38:56,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2018-01-21 00:38:56,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 89 states. [2018-01-21 00:38:56,211 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 99 transitions. [2018-01-21 00:38:56,213 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 99 transitions. Word has length 21 [2018-01-21 00:38:56,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:38:56,213 INFO L432 AbstractCegarLoop]: Abstraction has 89 states and 99 transitions. [2018-01-21 00:38:56,213 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-21 00:38:56,213 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 99 transitions. [2018-01-21 00:38:56,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-21 00:38:56,214 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:56,214 INFO L322 BasicCegarLoop]: trace histogram [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:38:56,214 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 00:38:56,214 INFO L82 PathProgramCache]: Analyzing trace with hash 553744969, now seen corresponding path program 1 times [2018-01-21 00:38:56,214 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:56,215 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,215 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:56,215 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,215 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:56,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:38:56,235 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:38:56,298 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:38:56,299 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:38:56,299 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-21 00:38:56,299 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:38:56,301 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-21 00:38:56,301 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-21 00:38:56,301 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-21 00:38:56,302 INFO L87 Difference]: Start difference. First operand 89 states and 99 transitions. Second operand 4 states. [2018-01-21 00:38:56,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:38:56,359 INFO L93 Difference]: Finished difference Result 98 states and 108 transitions. [2018-01-21 00:38:56,360 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-21 00:38:56,360 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 24 [2018-01-21 00:38:56,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:38:56,362 INFO L225 Difference]: With dead ends: 98 [2018-01-21 00:38:56,362 INFO L226 Difference]: Without dead ends: 93 [2018-01-21 00:38:56,363 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-21 00:38:56,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2018-01-21 00:38:56,370 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 91. [2018-01-21 00:38:56,370 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-01-21 00:38:56,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 101 transitions. [2018-01-21 00:38:56,372 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 101 transitions. Word has length 24 [2018-01-21 00:38:56,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:38:56,373 INFO L432 AbstractCegarLoop]: Abstraction has 91 states and 101 transitions. [2018-01-21 00:38:56,373 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-21 00:38:56,373 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 101 transitions. [2018-01-21 00:38:56,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-21 00:38:56,375 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:56,375 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:38:56,375 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 00:38:56,375 INFO L82 PathProgramCache]: Analyzing trace with hash -1841085354, now seen corresponding path program 1 times [2018-01-21 00:38:56,376 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:56,376 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,377 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:56,377 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,377 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:56,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:38:56,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 00:38:56,461 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-21 00:38:56,471 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:38:56,478 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:38:56,479 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 00:38:56,495 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 00:38:56,495 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 00:38:56,495 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 00:38:56,495 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 00:38:56,495 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 00:38:56,495 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 00:38:56,495 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 00:38:56,495 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-21 00:38:56,495 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 00:38:56,498 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states. [2018-01-21 00:38:56,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-01-21 00:38:56,499 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:56,499 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:38:56,499 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-21 00:38:56,499 INFO L82 PathProgramCache]: Analyzing trace with hash 2000564629, now seen corresponding path program 1 times [2018-01-21 00:38:56,500 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:56,501 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,501 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:56,501 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,501 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:56,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:38:56,510 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:38:56,524 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:38:56,524 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:38:56,525 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 00:38:56,525 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:38:56,525 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-21 00:38:56,525 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-21 00:38:56,526 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 00:38:56,526 INFO L87 Difference]: Start difference. First operand 92 states. Second operand 2 states. [2018-01-21 00:38:56,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:38:56,534 INFO L93 Difference]: Finished difference Result 173 states and 199 transitions. [2018-01-21 00:38:56,534 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-21 00:38:56,534 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 19 [2018-01-21 00:38:56,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:38:56,536 INFO L225 Difference]: With dead ends: 173 [2018-01-21 00:38:56,536 INFO L226 Difference]: Without dead ends: 87 [2018-01-21 00:38:56,537 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:38:56,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-01-21 00:38:56,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2018-01-21 00:38:56,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-21 00:38:56,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 97 transitions. [2018-01-21 00:38:56,544 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 97 transitions. Word has length 19 [2018-01-21 00:38:56,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:38:56,544 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 97 transitions. [2018-01-21 00:38:56,545 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-21 00:38:56,545 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 97 transitions. [2018-01-21 00:38:56,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-01-21 00:38:56,546 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:56,546 INFO L322 BasicCegarLoop]: trace histogram [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:38:56,546 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-21 00:38:56,546 INFO L82 PathProgramCache]: Analyzing trace with hash -1791600567, now seen corresponding path program 1 times [2018-01-21 00:38:56,546 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:56,547 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,547 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:56,548 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,548 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:56,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:38:56,561 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:38:56,591 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:38:56,592 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:38:56,592 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-21 00:38:56,592 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:38:56,593 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-21 00:38:56,593 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-21 00:38:56,593 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-21 00:38:56,593 INFO L87 Difference]: Start difference. First operand 87 states and 97 transitions. Second operand 4 states. [2018-01-21 00:38:56,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:38:56,623 INFO L93 Difference]: Finished difference Result 94 states and 104 transitions. [2018-01-21 00:38:56,624 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-21 00:38:56,624 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 22 [2018-01-21 00:38:56,624 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:38:56,625 INFO L225 Difference]: With dead ends: 94 [2018-01-21 00:38:56,625 INFO L226 Difference]: Without dead ends: 91 [2018-01-21 00:38:56,625 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-21 00:38:56,625 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2018-01-21 00:38:56,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 89. [2018-01-21 00:38:56,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 89 states. [2018-01-21 00:38:56,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 99 transitions. [2018-01-21 00:38:56,630 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 99 transitions. Word has length 22 [2018-01-21 00:38:56,630 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:38:56,630 INFO L432 AbstractCegarLoop]: Abstraction has 89 states and 99 transitions. [2018-01-21 00:38:56,631 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-21 00:38:56,631 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 99 transitions. [2018-01-21 00:38:56,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-01-21 00:38:56,632 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:38:56,632 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:38:56,632 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-21 00:38:56,632 INFO L82 PathProgramCache]: Analyzing trace with hash -2138226282, now seen corresponding path program 1 times [2018-01-21 00:38:56,632 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:38:56,633 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,633 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:56,633 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:38:56,633 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:38:56,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:38:56,654 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:38:57,137 WARN L146 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 26 DAG size of output 18 [2018-01-21 00:38:57,492 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:38:57,493 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:38:57,493 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:38:57,494 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 35 with the following transitions: [2018-01-21 00:38:57,496 INFO L201 CegarAbsIntRunner]: [0], [1], [7], [8], [9], [10], [11], [15], [17], [20], [109], [110], [111], [112], [113], [117], [121], [123], [124], [125], [126], [127], [128], [129], [140], [142], [153], [155], [159], [161], [162], [163], [164] [2018-01-21 00:38:57,541 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 00:38:57,541 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-21 00:38:58,012 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-21 00:38:58,013 INFO L268 AbstractInterpreter]: Visited 33 different actions 70 times. Merged at 15 different actions 36 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 34 variables. [2018-01-21 00:38:58,022 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-21 00:38:58,022 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:38:58,022 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:38:58,033 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:58,033 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:38:58,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:38:58,072 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:38:58,242 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:38:58,245 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 10 treesize of output 9 [2018-01-21 00:38:58,246 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:38:58,248 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:38:58,270 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:38:58,270 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:43, output treesize:54 [2018-01-21 00:38:58,393 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 52 treesize of output 42 [2018-01-21 00:38:58,405 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 42 treesize of output 37 [2018-01-21 00:38:58,408 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:38:58,426 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:38:58,443 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:38:58,443 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:56, output treesize:69 [2018-01-21 00:38:58,670 WARN L1029 $PredicateComparison]: unable to prove that (exists ((v_prenex_3 Int) (main_~n~4.base Int)) (let ((.cse0 (store |c_old(#valid)| main_~n~4.base 1))) (let ((.cse1 (store .cse0 v_prenex_3 0))) (and (not (= v_prenex_3 0)) (not (= 0 main_~n~4.base)) (= 0 (select .cse0 v_prenex_3)) (= |c_#valid| (store .cse1 main_~n~4.base 0)) (= (select .cse1 main_~n~4.base) 1) (= 0 (select |c_old(#valid)| main_~n~4.base)))))) is different from true [2018-01-21 00:38:58,686 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 2 not checked. [2018-01-21 00:38:58,686 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:38:58,730 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:38:58,735 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 18 [2018-01-21 00:38:58,737 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:38:58,744 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:38:58,764 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:38:58,765 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 21 treesize of output 18 [2018-01-21 00:38:58,792 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:38:58,793 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-21 00:38:58,796 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:38:58,808 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:38:58,808 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:91, output treesize:42 [2018-01-21 00:38:59,025 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 40 treesize of output 36 [2018-01-21 00:38:59,059 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-01-21 00:38:59,061 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:38:59,066 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:38:59,068 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 40 treesize of output 36 [2018-01-21 00:38:59,085 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 22 [2018-01-21 00:38:59,086 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:38:59,088 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 23 [2018-01-21 00:38:59,088 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:38:59,107 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-21 00:38:59,144 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 17 treesize of output 15 [2018-01-21 00:38:59,152 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:38:59,153 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-21 00:38:59,158 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:38:59,175 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-21 00:38:59,175 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 2 variables, input treesize:123, output treesize:34 [2018-01-21 00:38:59,397 WARN L1007 $PredicateComparison]: unable to prove that (forall ((|v_main_#t~malloc0.base_3| Int) (|v_main_#t~malloc33.base_3| Int)) (let ((.cse0 (store |c_#valid| |v_main_#t~malloc0.base_3| 1))) (let ((.cse1 (store .cse0 |v_main_#t~malloc33.base_3| 0))) (or (not (= 0 (select .cse0 |v_main_#t~malloc33.base_3|))) (= |c_old(#valid)| (store .cse1 |v_main_#t~malloc0.base_3| 0)) (not (= 1 (select .cse1 |v_main_#t~malloc0.base_3|))) (not (= 0 (select |c_#valid| |v_main_#t~malloc0.base_3|))) (= 0 |v_main_#t~malloc0.base_3|) (= |v_main_#t~malloc33.base_3| 0))))) is different from false [2018-01-21 00:38:59,400 WARN L1007 $PredicateComparison]: unable to prove that (forall ((|v_main_#t~malloc0.base_3| Int) (|v_main_#t~malloc33.base_3| Int)) (let ((.cse0 (store |c_#valid| |v_main_#t~malloc0.base_3| 1))) (let ((.cse1 (store .cse0 |v_main_#t~malloc33.base_3| 0))) (or (not (= 0 (select .cse0 |v_main_#t~malloc33.base_3|))) (= |c_#valid| (store .cse1 |v_main_#t~malloc0.base_3| 0)) (not (= 1 (select .cse1 |v_main_#t~malloc0.base_3|))) (not (= 0 (select |c_#valid| |v_main_#t~malloc0.base_3|))) (= 0 |v_main_#t~malloc0.base_3|) (= |v_main_#t~malloc33.base_3| 0))))) is different from false [2018-01-21 00:38:59,412 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:38:59,432 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:38:59,432 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:38:59,436 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:38:59,436 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:39:11,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2018-01-21 00:39:11,498 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-01-21 00:39:11,498 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 32 [2018-01-21 00:39:11,498 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:39:11,499 INFO L409 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-01-21 00:39:11,499 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-01-21 00:39:11,499 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=851, Unknown=3, NotChecked=118, Total=1056 [2018-01-21 00:39:11,499 INFO L87 Difference]: Start difference. First operand 89 states and 99 transitions. Second operand 23 states. [2018-01-21 00:39:13,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:39:13,220 INFO L93 Difference]: Finished difference Result 169 states and 197 transitions. [2018-01-21 00:39:13,221 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-01-21 00:39:13,221 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 34 [2018-01-21 00:39:13,221 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:39:13,226 INFO L225 Difference]: With dead ends: 169 [2018-01-21 00:39:13,226 INFO L226 Difference]: Without dead ends: 166 [2018-01-21 00:39:13,227 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 50 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=241, Invalid=1740, Unknown=7, NotChecked=174, Total=2162 [2018-01-21 00:39:13,228 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2018-01-21 00:39:13,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 129. [2018-01-21 00:39:13,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 129 states. [2018-01-21 00:39:13,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 149 transitions. [2018-01-21 00:39:13,243 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 149 transitions. Word has length 34 [2018-01-21 00:39:13,243 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:39:13,243 INFO L432 AbstractCegarLoop]: Abstraction has 129 states and 149 transitions. [2018-01-21 00:39:13,243 INFO L433 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-01-21 00:39:13,243 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 149 transitions. [2018-01-21 00:39:13,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-21 00:39:13,245 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:39:13,245 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:39:13,245 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-21 00:39:13,245 INFO L82 PathProgramCache]: Analyzing trace with hash -232230565, now seen corresponding path program 1 times [2018-01-21 00:39:13,245 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:39:13,246 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:13,247 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:39:13,247 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:13,247 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:39:13,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:39:13,263 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:39:13,309 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:39:13,310 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:39:13,310 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-21 00:39:13,310 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:39:13,310 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-21 00:39:13,311 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-21 00:39:13,311 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-21 00:39:13,311 INFO L87 Difference]: Start difference. First operand 129 states and 149 transitions. Second operand 5 states. [2018-01-21 00:39:13,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:39:13,426 INFO L93 Difference]: Finished difference Result 184 states and 209 transitions. [2018-01-21 00:39:13,426 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-21 00:39:13,426 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 40 [2018-01-21 00:39:13,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:39:13,428 INFO L225 Difference]: With dead ends: 184 [2018-01-21 00:39:13,428 INFO L226 Difference]: Without dead ends: 181 [2018-01-21 00:39:13,429 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-01-21 00:39:13,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2018-01-21 00:39:13,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 129. [2018-01-21 00:39:13,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 129 states. [2018-01-21 00:39:13,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 149 transitions. [2018-01-21 00:39:13,443 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 149 transitions. Word has length 40 [2018-01-21 00:39:13,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:39:13,444 INFO L432 AbstractCegarLoop]: Abstraction has 129 states and 149 transitions. [2018-01-21 00:39:13,444 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-21 00:39:13,444 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 149 transitions. [2018-01-21 00:39:13,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-21 00:39:13,445 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:39:13,445 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 00:39:13,446 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-21 00:39:13,446 INFO L82 PathProgramCache]: Analyzing trace with hash 380991995, now seen corresponding path program 1 times [2018-01-21 00:39:13,446 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:39:13,447 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:13,447 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:39:13,447 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:13,447 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:39:13,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:39:13,460 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:39:13,519 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:39:13,519 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 00:39:13,520 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-21 00:39:13,520 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 00:39:13,520 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-21 00:39:13,520 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-21 00:39:13,520 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-21 00:39:13,521 INFO L87 Difference]: Start difference. First operand 129 states and 149 transitions. Second operand 5 states. [2018-01-21 00:39:13,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:39:13,577 INFO L93 Difference]: Finished difference Result 181 states and 206 transitions. [2018-01-21 00:39:13,578 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-21 00:39:13,578 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 40 [2018-01-21 00:39:13,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:39:13,579 INFO L225 Difference]: With dead ends: 181 [2018-01-21 00:39:13,579 INFO L226 Difference]: Without dead ends: 178 [2018-01-21 00:39:13,579 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 4 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:39:13,580 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2018-01-21 00:39:13,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 129. [2018-01-21 00:39:13,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 129 states. [2018-01-21 00:39:13,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 149 transitions. [2018-01-21 00:39:13,592 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 149 transitions. Word has length 40 [2018-01-21 00:39:13,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:39:13,592 INFO L432 AbstractCegarLoop]: Abstraction has 129 states and 149 transitions. [2018-01-21 00:39:13,592 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-21 00:39:13,592 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 149 transitions. [2018-01-21 00:39:13,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-01-21 00:39:13,594 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:39:13,594 INFO L322 BasicCegarLoop]: trace histogram [3, 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] [2018-01-21 00:39:13,594 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-21 00:39:13,595 INFO L82 PathProgramCache]: Analyzing trace with hash 423075683, now seen corresponding path program 2 times [2018-01-21 00:39:13,595 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:39:13,596 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:13,596 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:39:13,596 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:13,596 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:39:13,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:39:13,612 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:39:13,733 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:39:13,733 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:39:13,734 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:39:13,734 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-21 00:39:13,734 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:39:13,734 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:39:13,734 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:39:13,758 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-21 00:39:13,758 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-21 00:39:13,776 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:39:13,800 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:39:13,803 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-21 00:39:13,807 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:39:13,813 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:39:13,817 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:39:13,818 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,819 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,821 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,821 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-01-21 00:39:13,835 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 16 [2018-01-21 00:39:13,842 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:13,844 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:39:13,845 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,855 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,860 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:39:13,860 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:21, output treesize:7 [2018-01-21 00:39:13,864 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-01-21 00:39:13,867 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-21 00:39:13,867 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,869 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,871 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:13,871 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:15, output treesize:3 [2018-01-21 00:39:13,902 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:39:13,902 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:39:13,915 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:39:13,940 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:39:13,941 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:39:13,947 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-21 00:39:13,947 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-21 00:39:13,967 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:39:14,002 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-21 00:39:14,065 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-21 00:39:14,072 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:39:14,113 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:39:14,114 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:39:14,114 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,116 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,119 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,120 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-01-21 00:39:14,135 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 16 [2018-01-21 00:39:14,137 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:14,138 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 16 treesize of output 23 [2018-01-21 00:39:14,138 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,142 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,149 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:39:14,150 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-21 00:39:14,170 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 17 [2018-01-21 00:39:14,172 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 0 case distinctions, treesize of input 17 treesize of output 8 [2018-01-21 00:39:14,173 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,175 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:14,176 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:39:14,176 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:23, output treesize:3 [2018-01-21 00:39:14,184 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:39:14,184 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-21 00:39:14,215 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:39:14,217 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-21 00:39:14,217 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6, 6, 11, 6] total 16 [2018-01-21 00:39:14,218 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-21 00:39:14,218 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-21 00:39:14,218 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-21 00:39:14,218 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=200, Unknown=0, NotChecked=0, Total=240 [2018-01-21 00:39:14,219 INFO L87 Difference]: Start difference. First operand 129 states and 149 transitions. Second operand 9 states. [2018-01-21 00:39:14,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 00:39:14,404 INFO L93 Difference]: Finished difference Result 192 states and 219 transitions. [2018-01-21 00:39:14,404 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-21 00:39:14,404 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 46 [2018-01-21 00:39:14,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 00:39:14,406 INFO L225 Difference]: With dead ends: 192 [2018-01-21 00:39:14,406 INFO L226 Difference]: Without dead ends: 157 [2018-01-21 00:39:14,407 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 171 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2018-01-21 00:39:14,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2018-01-21 00:39:14,414 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 145. [2018-01-21 00:39:14,415 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 145 states. [2018-01-21 00:39:14,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 167 transitions. [2018-01-21 00:39:14,416 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 167 transitions. Word has length 46 [2018-01-21 00:39:14,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 00:39:14,416 INFO L432 AbstractCegarLoop]: Abstraction has 145 states and 167 transitions. [2018-01-21 00:39:14,416 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-21 00:39:14,416 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 167 transitions. [2018-01-21 00:39:14,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-01-21 00:39:14,417 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 00:39:14,417 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, 1, 1, 1, 1, 1] [2018-01-21 00:39:14,417 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-21 00:39:14,417 INFO L82 PathProgramCache]: Analyzing trace with hash -1822928984, now seen corresponding path program 1 times [2018-01-21 00:39:14,417 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 00:39:14,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:14,418 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-21 00:39:14,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 00:39:14,418 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 00:39:14,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:39:14,440 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 00:39:15,329 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 00:39:15,330 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:39:15,330 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 00:39:15,330 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 53 with the following transitions: [2018-01-21 00:39:15,330 INFO L201 CegarAbsIntRunner]: [0], [1], [7], [8], [9], [10], [11], [15], [17], [20], [109], [110], [111], [112], [113], [117], [121], [123], [124], [125], [126], [127], [128], [129], [132], [133], [134], [135], [136], [137], [138], [140], [142], [153], [155], [159], [161], [162], [163], [164] [2018-01-21 00:39:15,332 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 00:39:15,332 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-21 00:39:15,781 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-21 00:39:15,781 INFO L268 AbstractInterpreter]: Visited 40 different actions 79 times. Merged at 19 different actions 36 times. Never widened. Found 4 fixpoints after 2 different actions. Largest state had 38 variables. [2018-01-21 00:39:15,824 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-21 00:39:15,824 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 00:39:15,824 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:39:15,831 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 00:39:15,831 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 00:39:15,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 00:39:15,870 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 00:39:15,948 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:39:15,949 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:39:15,950 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:15,951 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:15,954 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:15,954 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-01-21 00:39:15,980 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 21 treesize of output 16 [2018-01-21 00:39:15,982 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:15,982 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:39:15,983 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:15,987 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:15,998 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:15,999 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:28, output treesize:24 [2018-01-21 00:39:16,031 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 26 treesize of output 19 [2018-01-21 00:39:16,033 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 19 treesize of output 22 [2018-01-21 00:39:16,033 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,037 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,043 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,044 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:26 [2018-01-21 00:39:16,162 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 41 [2018-01-21 00:39:16,164 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 34 treesize of output 33 [2018-01-21 00:39:16,165 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,191 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,197 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,197 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:40, output treesize:36 [2018-01-21 00:39:16,233 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,240 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 3 case distinctions, treesize of input 42 treesize of output 57 [2018-01-21 00:39:16,244 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,245 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 56 [2018-01-21 00:39:16,245 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,271 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,272 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,273 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,273 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,274 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:39:16,274 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 55 [2018-01-21 00:39:16,274 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,293 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:39:16,310 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:39:16,310 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:49, output treesize:98 [2018-01-21 00:39:16,515 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 66 treesize of output 65 [2018-01-21 00:39:16,516 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,537 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 39 treesize of output 38 [2018-01-21 00:39:16,538 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:16,563 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-21 00:39:16,563 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:106, output treesize:104 [2018-01-21 00:39:16,816 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,824 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 2 case distinctions, treesize of input 55 treesize of output 58 [2018-01-21 00:39:16,825 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2018-01-21 00:39:16,923 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:16,928 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 2 case distinctions, treesize of input 82 treesize of output 85 [2018-01-21 00:39:16,928 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-21 00:39:17,032 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:17,037 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 2 case distinctions, treesize of input 55 treesize of output 58 [2018-01-21 00:39:17,037 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-21 00:39:17,154 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:17,159 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 2 case distinctions, treesize of input 82 treesize of output 85 [2018-01-21 00:39:17,160 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-21 00:39:17,300 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 4 dim-1 vars, End of recursive call: 4 dim-0 vars, and 8 xjuncts. [2018-01-21 00:39:17,300 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 8 variables, input treesize:275, output treesize:521 [2018-01-21 00:39:17,541 WARN L143 SmtUtils]: Spent 112ms on a formula simplification that was a NOOP. DAG size: 122 [2018-01-21 00:39:17,758 WARN L143 SmtUtils]: Spent 105ms on a formula simplification that was a NOOP. DAG size: 122 [2018-01-21 00:39:17,775 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 76 treesize of output 73 [2018-01-21 00:39:17,778 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:39:17,778 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:17,792 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:19,335 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:39:19,338 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 71 treesize of output 61 [2018-01-21 00:39:19,344 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:19,348 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 68 [2018-01-21 00:39:19,348 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:19,369 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:20,471 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:20,474 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 76 treesize of output 77 [2018-01-21 00:39:20,477 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:39:20,477 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:20,492 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:21,548 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 103 treesize of output 100 [2018-01-21 00:39:21,551 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:39:21,551 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:21,572 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:22,511 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:22,513 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 72 treesize of output 77 [2018-01-21 00:39:22,516 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:39:22,516 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:22,530 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:23,360 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:23,363 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:23,365 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:23,379 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 6 case distinctions, treesize of input 99 treesize of output 111 [2018-01-21 00:39:23,388 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:23,397 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 1 stores, 5 select indices, 5 select index equivalence classes, 9 disjoint index pairs (out of 10 index pairs), introduced 1 new quantified variables, introduced 3 case distinctions, treesize of input 97 treesize of output 131 [2018-01-21 00:39:23,398 INFO L267 ElimStorePlain]: Start of recursive call 13: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:23,498 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 84 treesize of output 83 [2018-01-21 00:39:23,498 INFO L267 ElimStorePlain]: Start of recursive call 14: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:23,550 INFO L267 ElimStorePlain]: Start of recursive call 12: 2 dim-1 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-21 00:39:24,448 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 103 treesize of output 127 [2018-01-21 00:39:24,468 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 2 case distinctions, treesize of input 105 treesize of output 113 [2018-01-21 00:39:24,469 INFO L267 ElimStorePlain]: Start of recursive call 16: End of recursive call: and 2 xjuncts. [2018-01-21 00:39:24,555 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 104 treesize of output 103 [2018-01-21 00:39:24,555 INFO L267 ElimStorePlain]: Start of recursive call 17: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:24,619 INFO L267 ElimStorePlain]: Start of recursive call 15: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:39:25,486 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:25,490 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 98 treesize of output 103 [2018-01-21 00:39:25,493 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:39:25,493 INFO L267 ElimStorePlain]: Start of recursive call 19: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:25,511 INFO L267 ElimStorePlain]: Start of recursive call 18: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:26,184 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 71 treesize of output 60 [2018-01-21 00:39:26,186 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:26,189 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 52 [2018-01-21 00:39:26,189 INFO L267 ElimStorePlain]: Start of recursive call 21: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:26,204 INFO L267 ElimStorePlain]: Start of recursive call 20: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:26,696 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:26,697 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:26,698 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:26,699 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 98 treesize of output 96 [2018-01-21 00:39:26,704 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:26,711 INFO L477 Elim1Store]: Elim1 applied some 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 1 case distinctions, treesize of input 56 treesize of output 78 [2018-01-21 00:39:26,712 INFO L267 ElimStorePlain]: Start of recursive call 23: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:26,735 INFO L267 ElimStorePlain]: Start of recursive call 22: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:27,159 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:39:27,161 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 68 treesize of output 70 [2018-01-21 00:39:27,168 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 2 case distinctions, treesize of input 19 treesize of output 31 [2018-01-21 00:39:27,168 INFO L267 ElimStorePlain]: Start of recursive call 25: End of recursive call: and 2 xjuncts. [2018-01-21 00:39:27,183 INFO L267 ElimStorePlain]: Start of recursive call 24: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:39:27,590 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 68 treesize of output 65 [2018-01-21 00:39:27,592 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:39:27,592 INFO L267 ElimStorePlain]: Start of recursive call 27: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:27,603 INFO L267 ElimStorePlain]: Start of recursive call 26: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:27,958 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:27,959 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:27,960 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:27,961 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 98 treesize of output 96 [2018-01-21 00:39:27,967 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:27,972 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 58 [2018-01-21 00:39:27,973 INFO L267 ElimStorePlain]: Start of recursive call 29: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:27,993 INFO L267 ElimStorePlain]: Start of recursive call 28: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:28,298 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,299 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,301 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,314 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 103 treesize of output 117 [2018-01-21 00:39:28,317 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 112 treesize of output 111 [2018-01-21 00:39:28,318 INFO L267 ElimStorePlain]: Start of recursive call 31: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:28,395 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 0 case distinctions, treesize of input 85 treesize of output 91 [2018-01-21 00:39:28,396 INFO L267 ElimStorePlain]: Start of recursive call 32: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:28,443 INFO L267 ElimStorePlain]: Start of recursive call 30: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-21 00:39:28,445 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,446 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,447 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,449 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 101 treesize of output 103 [2018-01-21 00:39:28,454 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:28,463 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 39 treesize of output 64 [2018-01-21 00:39:28,464 INFO L267 ElimStorePlain]: Start of recursive call 34: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:28,493 INFO L267 ElimStorePlain]: Start of recursive call 33: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-21 00:39:28,813 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 91 treesize of output 88 [2018-01-21 00:39:28,815 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:39:28,815 INFO L267 ElimStorePlain]: Start of recursive call 36: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:28,830 INFO L267 ElimStorePlain]: Start of recursive call 35: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:29,106 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:29,106 INFO L682 Elim1Store]: detected equality via solver [2018-01-21 00:39:29,110 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 72 treesize of output 76 [2018-01-21 00:39:29,112 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:39:29,112 INFO L267 ElimStorePlain]: Start of recursive call 38: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:29,126 INFO L267 ElimStorePlain]: Start of recursive call 37: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:29,368 INFO L267 ElimStorePlain]: Start of recursive call 1: 20 dim-0 vars, 16 dim-2 vars, End of recursive call: 10 dim-0 vars, and 12 xjuncts. [2018-01-21 00:39:29,368 INFO L202 ElimStorePlain]: Needed 38 recursive calls to eliminate 36 variables, input treesize:697, output treesize:781 [2018-01-21 00:39:29,845 WARN L146 SmtUtils]: Spent 333ms on a formula simplification. DAG size of input: 195 DAG size of output 176 [2018-01-21 00:39:30,208 WARN L143 SmtUtils]: Spent 204ms on a formula simplification that was a NOOP. DAG size: 182 [2018-01-21 00:39:30,230 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 68 treesize of output 67 [2018-01-21 00:39:30,234 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:30,234 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 14 treesize of output 24 [2018-01-21 00:39:30,235 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-21 00:39:30,246 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-21 00:39:35,401 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:35,402 INFO L700 Elim1Store]: detected not equals via solver [2018-01-21 00:39:35,405 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 96 treesize of output 97 [2018-01-21 00:39:35,430 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 3 new quantified variables, introduced 7 case distinctions, treesize of input 27 treesize of output 57 [2018-01-21 00:39:35,432 INFO L267 ElimStorePlain]: Start of recursive call 5: 4 dim-0 vars, End of recursive call: 4 dim-0 vars, and 6 xjuncts. [2018-01-21 00:39:35,467 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. Received shutdown request... [2018-01-21 00:40:05,402 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-21 00:40:05,402 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-21 00:40:05,404 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.01 12:40:05 BoogieIcfgContainer [2018-01-21 00:40:05,405 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-21 00:40:05,406 INFO L168 Benchmark]: Toolchain (without parser) took 70338.08 ms. Allocated memory was 305.1 MB in the beginning and 659.6 MB in the end (delta: 354.4 MB). Free memory was 263.4 MB in the beginning and 534.1 MB in the end (delta: -270.6 MB). Peak memory consumption was 312.2 MB. Max. memory is 5.3 GB. [2018-01-21 00:40:05,406 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 305.1 MB. Free memory is still 269.4 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-21 00:40:05,407 INFO L168 Benchmark]: CACSL2BoogieTranslator took 217.20 ms. Allocated memory is still 305.1 MB. Free memory was 262.4 MB in the beginning and 251.4 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 5.3 GB. [2018-01-21 00:40:05,407 INFO L168 Benchmark]: Boogie Preprocessor took 37.65 ms. Allocated memory is still 305.1 MB. Free memory was 251.4 MB in the beginning and 249.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-21 00:40:05,407 INFO L168 Benchmark]: RCFGBuilder took 416.53 ms. Allocated memory is still 305.1 MB. Free memory was 249.4 MB in the beginning and 221.8 MB in the end (delta: 27.6 MB). Peak memory consumption was 27.6 MB. Max. memory is 5.3 GB. [2018-01-21 00:40:05,408 INFO L168 Benchmark]: TraceAbstraction took 69659.16 ms. Allocated memory was 305.1 MB in the beginning and 659.6 MB in the end (delta: 354.4 MB). Free memory was 220.8 MB in the beginning and 534.1 MB in the end (delta: -313.2 MB). Peak memory consumption was 269.6 MB. Max. memory is 5.3 GB. [2018-01-21 00:40:05,409 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.19 ms. Allocated memory is still 305.1 MB. Free memory is still 269.4 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 217.20 ms. Allocated memory is still 305.1 MB. Free memory was 262.4 MB in the beginning and 251.4 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 37.65 ms. Allocated memory is still 305.1 MB. Free memory was 251.4 MB in the beginning and 249.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 416.53 ms. Allocated memory is still 305.1 MB. Free memory was 249.4 MB in the beginning and 221.8 MB in the end (delta: 27.6 MB). Peak memory consumption was 27.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 69659.16 ms. Allocated memory was 305.1 MB in the beginning and 659.6 MB in the end (delta: 354.4 MB). Free memory was 220.8 MB in the beginning and 534.1 MB in the end (delta: -313.2 MB). Peak memory consumption was 269.6 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.analysis.abstractinterpretationv2: - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 32 LocStat_MAX_WEQGRAPH_SIZE : 0 LocStat_MAX_SIZEOF_WEQEDGELABEL : 0 LocStat_NO_SUPPORTING_EQUALITIES : 370 LocStat_NO_SUPPORTING_DISEQUALITIES : 109 LocStat_NO_DISJUNCTIONS : -64 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 37 TransStat_MAX_WEQGRAPH_SIZE : 0 TransStat_MAX_SIZEOF_WEQEDGELABEL : 0 TransStat_NO_SUPPORTING_EQUALITIES : 94 TransStat_NO_SUPPORTING_DISEQUALITIES : 15 TransStat_NO_DISJUNCTIONS : 44 TransStat_MAX_NO_DISJUNCTIONS : 4 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 0.742658 RENAME_VARIABLES(MILLISECONDS) : 0.903099 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 0.686817 PROJECTAWAY(MILLISECONDS) : 0.665136 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.001618 DISJOIN(MILLISECONDS) : 0.968660 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.951466 ADD_EQUALITY(MILLISECONDS) : 0.037196 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.050626 #CONJOIN_DISJUNCTIVE : 120 #RENAME_VARIABLES : 220 #UNFREEZE : 0 #CONJOIN : 229 #PROJECTAWAY : 156 #ADD_WEAK_EQUALITY : 27 #DISJOIN : 13 #RENAME_VARIABLES_DISJUNCTIVE : 191 #ADD_EQUALITY : 86 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 7 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 38 LocStat_MAX_WEQGRAPH_SIZE : 0 LocStat_MAX_SIZEOF_WEQEDGELABEL : 0 LocStat_NO_SUPPORTING_EQUALITIES : 429 LocStat_NO_SUPPORTING_DISEQUALITIES : 135 LocStat_NO_DISJUNCTIONS : -76 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 44 TransStat_MAX_WEQGRAPH_SIZE : 0 TransStat_MAX_SIZEOF_WEQEDGELABEL : 0 TransStat_NO_SUPPORTING_EQUALITIES : 108 TransStat_NO_SUPPORTING_DISEQUALITIES : 21 TransStat_NO_DISJUNCTIONS : 52 TransStat_MAX_NO_DISJUNCTIONS : 4 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 2.674323 RENAME_VARIABLES(MILLISECONDS) : 0.389407 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 0.545672 PROJECTAWAY(MILLISECONDS) : 0.304386 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.001117 DISJOIN(MILLISECONDS) : 0.692173 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.421317 ADD_EQUALITY(MILLISECONDS) : 0.023058 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.012942 #CONJOIN_DISJUNCTIVE : 143 #RENAME_VARIABLES : 267 #UNFREEZE : 0 #CONJOIN : 272 #PROJECTAWAY : 187 #ADD_WEAK_EQUALITY : 37 #DISJOIN : 14 #RENAME_VARIABLES_DISJUNCTIVE : 225 #ADD_EQUALITY : 104 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 10 * 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, 92 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=92occurred 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: [L630] EXPR, FCALL malloc(sizeof(*root)) VAL [malloc(sizeof(*root))={14:0}] [L630] struct TreeNode* root = malloc(sizeof(*root)), *n; VAL [malloc(sizeof(*root))={14:0}, root={14:0}] [L631] FCALL root->left = ((void *)0) VAL [malloc(sizeof(*root))={14:0}, root={14:0}] [L632] FCALL root->right = ((void *)0) VAL [malloc(sizeof(*root))={14:0}, root={14:0}] [L633] FCALL root->parent = ((void *)0) VAL [malloc(sizeof(*root))={14:0}, root={14:0}] [L634] COND FALSE !(__VERIFIER_nondet_int()) [L655] n = ((void *)0) VAL [malloc(sizeof(*root))={14:0}, n={0:0}, root={14:0}] [L656] EXPR, FCALL malloc(sizeof(*s)) VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}] [L656] struct StackItem* s = malloc(sizeof(*s)), *st; VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}, s={15:0}] [L657] FCALL s->next = ((void *)0) VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}, s={15:0}] [L658] FCALL s->node = root VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}, s={15:0}] [L659] COND TRUE s != ((void *)0) [L660] st = s VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}, s={15:0}, s={15:0}] [L661] EXPR, FCALL s->next VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}, s={15:0}, s={15:0}, s->next={0:0}] [L661] s = s->next [L662] EXPR, FCALL st->node VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={0:0}, root={14:0}, s={0:0}, s={15:0}, st->node={14:0}] [L662] n = st->node [L663] FCALL free(st) VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={14:0}, root={14:0}, s={15:0}, s={0:0}] [L664] FCALL n->left VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={14:0}, n->left={0:0}, root={14:0}, s={15:0}, s={0:0}] [L664] COND FALSE !(n->left) [L670] FCALL n->right VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={14:0}, n->right={0:0}, root={14:0}, s={0:0}, s={15:0}] [L670] COND FALSE !(n->right) [L676] FCALL free(n) VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={14:0}, root={14:0}, s={0:0}, s={15:0}] [L659] COND FALSE !(s != ((void *)0)) VAL [malloc(sizeof(*root))={14:0}, malloc(sizeof(*s))={15:0}, n={14:0}, root={14:0}, s={15:0}, s={0:0}] [L678] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 92 locations, 3 error locations. UNSAFE Result, 0.5s OverallTime, 3 OverallIterations, 2 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 196 SDtfs, 38 SDslu, 154 SDs, 0 SdLazy, 13 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 7 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=92occurred 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, 2 MinimizatonAttempts, 2 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.1s InterpolantComputationTime, 81 NumberOfCodeBlocks, 81 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 43 ConstructedInterpolants, 0 QuantifiedInterpolants, 1274 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 2 InterpolantComputations, 2 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 53 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 385. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 92 locations, 3 error locations. TIMEOUT Result, 68.9s OverallTime, 7 OverallIterations, 3 TraceHistogramMax, 2.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 592 SDtfs, 549 SDslu, 2458 SDs, 0 SdLazy, 1172 SolverSat, 22 SolverUnsat, 10 SolverUnknown, 0 SolverNotchecked, 0.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 311 GetRequests, 233 SyntacticMatches, 4 SemanticMatches, 74 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 198 ImplicationChecksByTransitivity, 2.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=145occurred in iteration=6, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 1.0s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 6 MinimizatonAttempts, 152 StatesRemovedByMinimization, 5 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 12.2s SatisfiabilityAnalysisTime, 2.7s InterpolantComputationTime, 361 NumberOfCodeBlocks, 361 NumberOfCodeBlocksAsserted, 12 NumberOfCheckSat, 441 ConstructedInterpolants, 21 QuantifiedInterpolants, 122808 SizeOfPredicates, 32 NumberOfNonLiveVariables, 474 ConjunctsInSsa, 66 ConjunctsInUnsatCore, 12 InterpolantComputations, 4 PerfectInterpolantSequences, 54/90 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/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-1-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-1-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-21_00-40-05-421.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_parent_ptr_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Taipan+AI_EQ_imprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-21_00-40-05-421.csv Completed graceful shutdown