java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -s ../../../trunk/examples/settings/ai/array-bench/reach_32bit_array_oct.epf -i ../../../trunk/examples/programs/heapseparator/speedup-poc-dd-3-limited.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.24-1de736e-m [2019-02-15 11:24:30,601 INFO L170 SettingsManager]: Resetting all preferences to default values... [2019-02-15 11:24:30,602 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2019-02-15 11:24:30,614 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-02-15 11:24:30,615 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-02-15 11:24:30,616 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-02-15 11:24:30,617 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-02-15 11:24:30,619 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2019-02-15 11:24:30,620 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-02-15 11:24:30,621 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-02-15 11:24:30,622 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-02-15 11:24:30,622 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-02-15 11:24:30,623 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-02-15 11:24:30,624 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-02-15 11:24:30,626 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-02-15 11:24:30,626 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-02-15 11:24:30,627 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-02-15 11:24:30,629 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-02-15 11:24:30,632 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2019-02-15 11:24:30,633 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-02-15 11:24:30,634 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-02-15 11:24:30,636 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-02-15 11:24:30,638 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-02-15 11:24:30,639 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-02-15 11:24:30,639 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-02-15 11:24:30,640 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-02-15 11:24:30,641 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-02-15 11:24:30,642 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-02-15 11:24:30,642 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2019-02-15 11:24:30,644 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-02-15 11:24:30,644 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2019-02-15 11:24:30,645 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-02-15 11:24:30,645 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-02-15 11:24:30,645 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2019-02-15 11:24:30,646 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2019-02-15 11:24:30,647 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2019-02-15 11:24:30,647 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/array-bench/reach_32bit_array_oct.epf [2019-02-15 11:24:30,672 INFO L110 SettingsManager]: Loading preferences was successful [2019-02-15 11:24:30,672 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2019-02-15 11:24:30,673 INFO L131 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2019-02-15 11:24:30,673 INFO L133 SettingsManager]: * Show backtranslation warnings=false [2019-02-15 11:24:30,673 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2019-02-15 11:24:30,674 INFO L133 SettingsManager]: * User list type=DISABLED [2019-02-15 11:24:30,674 INFO L133 SettingsManager]: * Inline calls to unimplemented procedures=true [2019-02-15 11:24:30,674 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2019-02-15 11:24:30,674 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2019-02-15 11:24:30,674 INFO L133 SettingsManager]: * Underlying domain=OctagonDomain [2019-02-15 11:24:30,675 INFO L133 SettingsManager]: * Abstract domain=ArrayDomain [2019-02-15 11:24:30,676 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2019-02-15 11:24:30,676 INFO L133 SettingsManager]: * Interval Domain=false [2019-02-15 11:24:30,677 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-02-15 11:24:30,678 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2019-02-15 11:24:30,678 INFO L133 SettingsManager]: * Use SBE=true [2019-02-15 11:24:30,678 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-02-15 11:24:30,678 INFO L133 SettingsManager]: * sizeof long=4 [2019-02-15 11:24:30,678 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2019-02-15 11:24:30,679 INFO L133 SettingsManager]: * sizeof POINTER=4 [2019-02-15 11:24:30,681 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2019-02-15 11:24:30,681 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-02-15 11:24:30,681 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-02-15 11:24:30,681 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-02-15 11:24:30,681 INFO L133 SettingsManager]: * sizeof long double=12 [2019-02-15 11:24:30,682 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2019-02-15 11:24:30,682 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-02-15 11:24:30,682 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-02-15 11:24:30,682 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-02-15 11:24:30,682 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2019-02-15 11:24:30,682 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-02-15 11:24:30,683 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-02-15 11:24:30,683 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-02-15 11:24:30,683 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-02-15 11:24:30,683 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2019-02-15 11:24:30,683 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2019-02-15 11:24:30,684 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2019-02-15 11:24:30,684 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-02-15 11:24:30,685 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2019-02-15 11:24:30,737 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-02-15 11:24:30,752 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-02-15 11:24:30,757 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-02-15 11:24:30,760 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2019-02-15 11:24:30,760 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2019-02-15 11:24:30,761 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/heapseparator/speedup-poc-dd-3-limited.bpl [2019-02-15 11:24:30,761 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/heapseparator/speedup-poc-dd-3-limited.bpl' [2019-02-15 11:24:30,805 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-02-15 11:24:30,807 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2019-02-15 11:24:30,808 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2019-02-15 11:24:30,808 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2019-02-15 11:24:30,808 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2019-02-15 11:24:30,827 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,840 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,869 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2019-02-15 11:24:30,870 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-02-15 11:24:30,870 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-02-15 11:24:30,870 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2019-02-15 11:24:30,883 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,883 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,884 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,885 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,888 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,895 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,896 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... [2019-02-15 11:24:30,898 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-02-15 11:24:30,899 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-02-15 11:24:30,899 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-02-15 11:24:30,899 INFO L276 PluginConnector]: RCFGBuilder initialized [2019-02-15 11:24:30,906 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-02-15 11:24:30,982 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-02-15 11:24:30,982 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-02-15 11:24:31,232 INFO L281 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-02-15 11:24:31,233 INFO L286 CfgBuilder]: Removed 9 assue(true) statements. [2019-02-15 11:24:31,234 INFO L202 PluginConnector]: Adding new model speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 11:24:31 BoogieIcfgContainer [2019-02-15 11:24:31,234 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-02-15 11:24:31,235 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-02-15 11:24:31,235 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-02-15 11:24:31,238 INFO L276 PluginConnector]: TraceAbstraction initialized [2019-02-15 11:24:31,239 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.02 11:24:30" (1/2) ... [2019-02-15 11:24:31,240 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@d76635b and model type speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 11:24:31, skipping insertion in model container [2019-02-15 11:24:31,240 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 11:24:31" (2/2) ... [2019-02-15 11:24:31,242 INFO L112 eAbstractionObserver]: Analyzing ICFG speedup-poc-dd-3-limited.bpl [2019-02-15 11:24:31,251 INFO L156 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-02-15 11:24:31,261 INFO L168 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2019-02-15 11:24:31,281 INFO L257 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2019-02-15 11:24:31,320 INFO L382 AbstractCegarLoop]: Interprodecural is true [2019-02-15 11:24:31,320 INFO L383 AbstractCegarLoop]: Hoare is true [2019-02-15 11:24:31,320 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-02-15 11:24:31,320 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-02-15 11:24:31,320 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-02-15 11:24:31,321 INFO L387 AbstractCegarLoop]: Difference is false [2019-02-15 11:24:31,321 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-02-15 11:24:31,321 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-02-15 11:24:31,338 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states. [2019-02-15 11:24:31,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2019-02-15 11:24:31,349 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:24:31,351 INFO L402 BasicCegarLoop]: trace histogram [1, 1] [2019-02-15 11:24:31,357 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:24:31,365 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:31,365 INFO L82 PathProgramCache]: Analyzing trace with hash 976, now seen corresponding path program 1 times [2019-02-15 11:24:31,368 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:24:31,409 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:31,410 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:24:31,410 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:31,410 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:24:31,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:24:31,531 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:24:31,533 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-02-15 11:24:31,534 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2019-02-15 11:24:31,534 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:24:31,539 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:24:31,554 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:24:31,555 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:31,566 INFO L87 Difference]: Start difference. First operand 9 states. Second operand 3 states. [2019-02-15 11:24:31,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:24:31,737 INFO L93 Difference]: Finished difference Result 17 states and 21 transitions. [2019-02-15 11:24:31,738 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:24:31,739 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 2 [2019-02-15 11:24:31,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:24:31,760 INFO L225 Difference]: With dead ends: 17 [2019-02-15 11:24:31,760 INFO L226 Difference]: Without dead ends: 12 [2019-02-15 11:24:31,764 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:31,782 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2019-02-15 11:24:31,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 8. [2019-02-15 11:24:31,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2019-02-15 11:24:31,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 13 transitions. [2019-02-15 11:24:31,802 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 13 transitions. Word has length 2 [2019-02-15 11:24:31,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:24:31,803 INFO L480 AbstractCegarLoop]: Abstraction has 8 states and 13 transitions. [2019-02-15 11:24:31,804 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:24:31,804 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 13 transitions. [2019-02-15 11:24:31,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2019-02-15 11:24:31,804 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:24:31,805 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1] [2019-02-15 11:24:31,805 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:24:31,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:31,806 INFO L82 PathProgramCache]: Analyzing trace with hash 30304, now seen corresponding path program 1 times [2019-02-15 11:24:31,806 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:24:31,807 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:31,807 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:24:31,807 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:31,808 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:24:31,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:24:31,886 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:24:31,886 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-02-15 11:24:31,886 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2019-02-15 11:24:31,887 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:24:31,888 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:24:31,889 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:24:31,889 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:31,890 INFO L87 Difference]: Start difference. First operand 8 states and 13 transitions. Second operand 3 states. [2019-02-15 11:24:31,972 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:24:31,973 INFO L93 Difference]: Finished difference Result 12 states and 16 transitions. [2019-02-15 11:24:31,973 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:24:31,974 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2019-02-15 11:24:31,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:24:31,974 INFO L225 Difference]: With dead ends: 12 [2019-02-15 11:24:31,975 INFO L226 Difference]: Without dead ends: 11 [2019-02-15 11:24:31,976 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:31,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2019-02-15 11:24:31,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 9. [2019-02-15 11:24:31,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2019-02-15 11:24:31,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 14 transitions. [2019-02-15 11:24:31,979 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 14 transitions. Word has length 3 [2019-02-15 11:24:31,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:24:31,980 INFO L480 AbstractCegarLoop]: Abstraction has 9 states and 14 transitions. [2019-02-15 11:24:31,980 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:24:31,980 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 14 transitions. [2019-02-15 11:24:31,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2019-02-15 11:24:31,981 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:24:31,981 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1] [2019-02-15 11:24:31,981 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:24:31,982 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:31,982 INFO L82 PathProgramCache]: Analyzing trace with hash 29992, now seen corresponding path program 1 times [2019-02-15 11:24:31,982 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:24:31,983 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:31,983 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:24:31,983 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:31,984 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:24:31,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:24:32,058 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:24:32,058 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:24:32,058 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:24:32,059 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 4 with the following transitions: [2019-02-15 11:24:32,061 INFO L207 CegarAbsIntRunner]: [0], [6], [15] [2019-02-15 11:24:32,111 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:24:32,111 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:24:39,542 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:24:39,544 INFO L272 AbstractInterpreter]: Visited 3 different actions 13 times. Merged at 1 different actions 5 times. Widened at 1 different actions 1 times. Found 1 fixpoints after 1 different actions. Largest state had 0 variables. [2019-02-15 11:24:39,550 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:39,551 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:24:39,852 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:24:39,994 INFO L420 sIntCurrentIteration]: We unified 2 AI predicates to 2 [2019-02-15 11:24:39,995 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:24:39,998 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:24:39,999 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [2] total 3 [2019-02-15 11:24:39,999 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:24:39,999 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:24:40,000 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:24:40,000 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:40,000 INFO L87 Difference]: Start difference. First operand 9 states and 14 transitions. Second operand 3 states. [2019-02-15 11:24:41,076 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:24:41,076 INFO L93 Difference]: Finished difference Result 15 states and 22 transitions. [2019-02-15 11:24:41,076 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:24:41,076 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2019-02-15 11:24:41,077 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:24:41,077 INFO L225 Difference]: With dead ends: 15 [2019-02-15 11:24:41,077 INFO L226 Difference]: Without dead ends: 9 [2019-02-15 11:24:41,078 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 0 SyntacticMatches, 1 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:41,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2019-02-15 11:24:41,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 8. [2019-02-15 11:24:41,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2019-02-15 11:24:41,081 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 12 transitions. [2019-02-15 11:24:41,081 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 12 transitions. Word has length 3 [2019-02-15 11:24:41,082 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:24:41,082 INFO L480 AbstractCegarLoop]: Abstraction has 8 states and 12 transitions. [2019-02-15 11:24:41,082 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:24:41,082 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 12 transitions. [2019-02-15 11:24:41,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2019-02-15 11:24:41,083 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:24:41,083 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1] [2019-02-15 11:24:41,083 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:24:41,084 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:41,084 INFO L82 PathProgramCache]: Analyzing trace with hash 30116, now seen corresponding path program 1 times [2019-02-15 11:24:41,084 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:24:41,085 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:41,085 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:24:41,086 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:41,086 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:24:41,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:24:41,306 WARN L181 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 13 [2019-02-15 11:24:41,319 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:24:41,320 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:24:41,320 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:24:41,320 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 4 with the following transitions: [2019-02-15 11:24:41,321 INFO L207 CegarAbsIntRunner]: [0], [10], [15] [2019-02-15 11:24:41,323 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:24:41,323 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:24:45,108 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:24:45,108 INFO L272 AbstractInterpreter]: Visited 3 different actions 13 times. Merged at 1 different actions 5 times. Widened at 1 different actions 1 times. Found 1 fixpoints after 1 different actions. Largest state had 0 variables. [2019-02-15 11:24:45,109 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:45,109 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:24:45,273 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:24:45,390 INFO L420 sIntCurrentIteration]: We unified 2 AI predicates to 2 [2019-02-15 11:24:45,390 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:24:45,390 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:24:45,390 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [2] total 3 [2019-02-15 11:24:45,390 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:24:45,391 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:24:45,391 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:24:45,391 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:45,392 INFO L87 Difference]: Start difference. First operand 8 states and 12 transitions. Second operand 3 states. [2019-02-15 11:24:46,208 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:24:46,208 INFO L93 Difference]: Finished difference Result 15 states and 23 transitions. [2019-02-15 11:24:46,208 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:24:46,208 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2019-02-15 11:24:46,209 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:24:46,209 INFO L225 Difference]: With dead ends: 15 [2019-02-15 11:24:46,209 INFO L226 Difference]: Without dead ends: 10 [2019-02-15 11:24:46,210 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 0 SyntacticMatches, 1 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:46,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2019-02-15 11:24:46,213 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2019-02-15 11:24:46,214 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2019-02-15 11:24:46,214 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 18 transitions. [2019-02-15 11:24:46,214 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 18 transitions. Word has length 3 [2019-02-15 11:24:46,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:24:46,215 INFO L480 AbstractCegarLoop]: Abstraction has 10 states and 18 transitions. [2019-02-15 11:24:46,215 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:24:46,215 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 18 transitions. [2019-02-15 11:24:46,215 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2019-02-15 11:24:46,215 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:24:46,215 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1] [2019-02-15 11:24:46,216 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:24:46,216 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:46,216 INFO L82 PathProgramCache]: Analyzing trace with hash 30178, now seen corresponding path program 1 times [2019-02-15 11:24:46,216 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:24:46,217 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:46,217 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:24:46,217 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:46,217 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:24:46,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:24:46,346 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:24:46,347 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:24:46,347 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:24:46,347 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 4 with the following transitions: [2019-02-15 11:24:46,347 INFO L207 CegarAbsIntRunner]: [0], [12], [15] [2019-02-15 11:24:46,349 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:24:46,349 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:24:49,996 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:24:49,997 INFO L272 AbstractInterpreter]: Visited 3 different actions 13 times. Merged at 1 different actions 5 times. Widened at 1 different actions 1 times. Found 1 fixpoints after 1 different actions. Largest state had 0 variables. [2019-02-15 11:24:49,997 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:49,997 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:24:50,177 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:24:50,237 INFO L420 sIntCurrentIteration]: We unified 2 AI predicates to 2 [2019-02-15 11:24:50,237 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:24:50,237 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:24:50,237 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [2] total 3 [2019-02-15 11:24:50,238 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:24:50,238 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:24:50,238 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:24:50,238 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:50,238 INFO L87 Difference]: Start difference. First operand 10 states and 18 transitions. Second operand 3 states. [2019-02-15 11:24:50,754 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:24:50,754 INFO L93 Difference]: Finished difference Result 16 states and 26 transitions. [2019-02-15 11:24:50,754 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:24:50,755 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2019-02-15 11:24:50,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:24:50,755 INFO L225 Difference]: With dead ends: 16 [2019-02-15 11:24:50,755 INFO L226 Difference]: Without dead ends: 11 [2019-02-15 11:24:50,756 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 0 SyntacticMatches, 1 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:24:50,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2019-02-15 11:24:50,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2019-02-15 11:24:50,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2019-02-15 11:24:50,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 21 transitions. [2019-02-15 11:24:50,761 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 21 transitions. Word has length 3 [2019-02-15 11:24:50,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:24:50,761 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 21 transitions. [2019-02-15 11:24:50,762 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:24:50,762 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 21 transitions. [2019-02-15 11:24:50,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2019-02-15 11:24:50,762 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:24:50,762 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2019-02-15 11:24:50,763 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:24:50,763 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:24:50,763 INFO L82 PathProgramCache]: Analyzing trace with hash 929612, now seen corresponding path program 1 times [2019-02-15 11:24:50,763 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:24:50,764 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:50,764 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:24:50,764 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:24:50,765 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:24:50,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:24:50,946 WARN L181 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 9 [2019-02-15 11:24:51,072 WARN L181 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 13 [2019-02-15 11:24:51,082 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:24:51,082 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:24:51,083 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:24:51,083 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 5 with the following transitions: [2019-02-15 11:24:51,083 INFO L207 CegarAbsIntRunner]: [0], [6], [10], [15] [2019-02-15 11:24:51,085 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:24:51,085 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:25:02,962 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:25:02,963 INFO L272 AbstractInterpreter]: Visited 4 different actions 31 times. Merged at 2 different actions 9 times. Widened at 2 different actions 5 times. Found 11 fixpoints after 2 different actions. Largest state had 0 variables. [2019-02-15 11:25:02,963 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:02,963 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:25:03,433 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:25:03,474 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_idx_203 Int) (v_idx_207 Int) (v_idx_205 Int) (v_idx_200 Int) (v_idx_197 Int)) (let ((.cse9 (+ c_ULTIMATE.start_main_p1 2)) (.cse0 (+ c_ULTIMATE.start_main_p1 1)) (.cse10 (+ c_ULTIMATE.start_main_p3 1)) (.cse8 (+ c_ULTIMATE.start_main_p2 1))) (and (let ((.cse3 (select |c_#memory_int| v_idx_205))) (let ((.cse4 (<= .cse3 0)) (.cse5 (<= (* 2 .cse3) 0)) (.cse6 (< v_idx_205 c_ULTIMATE.start_main_p2)) (.cse7 (<= .cse8 v_idx_205))) (let ((.cse1 (or (and .cse4 .cse5) .cse6 .cse7))) (or (and (<= .cse0 v_idx_203) .cse1) (let ((.cse2 (select |c_#memory_int| v_idx_203))) (and (<= 0 .cse2) (or (and (<= .cse3 .cse2) .cse4 .cse5) .cse6 .cse7) (<= 0 (* 2 .cse2)))) (and (< v_idx_203 c_ULTIMATE.start_main_p1) .cse1))))) (<= .cse9 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (or (< v_idx_200 c_ULTIMATE.start_malloc_ptr) (<= .cse10 v_idx_200) (= 1 (select |c_#valid| v_idx_200))) (<= .cse9 c_ULTIMATE.start_malloc_ptr) (<= .cse8 c_ULTIMATE.start_malloc_ptr) (or (= (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_197) 0) (<= .cse10 v_idx_197) (< v_idx_197 c_ULTIMATE.start_malloc_ptr)) (<= .cse0 c_ULTIMATE.start_main_p2) (or (<= .cse10 v_idx_207) (= (select |c_#memory_int| v_idx_207) 0) (< v_idx_207 c_ULTIMATE.start_malloc_ptr)) (<= .cse8 c_ULTIMATE.start_main_p3)))) is different from false [2019-02-15 11:25:03,512 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_idx_213 Int) (v_idx_218 Int) (v_idx_216 Int) (v_idx_210 Int) (v_idx_220 Int)) (let ((.cse0 (+ c_ULTIMATE.start_main_p1 2)) (.cse3 (+ c_ULTIMATE.start_main_p1 1)) (.cse1 (+ c_ULTIMATE.start_main_p3 1)) (.cse2 (+ c_ULTIMATE.start_main_p2 1))) (and (<= .cse0 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (or (< v_idx_220 c_ULTIMATE.start_malloc_ptr) (= 0 (select |c_#memory_int| v_idx_220)) (<= .cse1 v_idx_220)) (<= .cse0 c_ULTIMATE.start_malloc_ptr) (<= .cse2 c_ULTIMATE.start_malloc_ptr) (<= .cse3 c_ULTIMATE.start_main_p2) (let ((.cse8 (select |c_#memory_int| v_idx_216))) (let ((.cse6 (< v_idx_216 c_ULTIMATE.start_main_p1)) (.cse9 (<= 0 .cse8)) (.cse10 (<= 0 (* 2 .cse8))) (.cse7 (<= .cse3 v_idx_216))) (let ((.cse4 (or .cse6 (and .cse9 .cse10) .cse7))) (or (and (< v_idx_218 c_ULTIMATE.start_main_p2) .cse4) (let ((.cse5 (select |c_#memory_int| v_idx_218))) (and (<= (* 2 .cse5) 0) (or .cse6 .cse7 (and (<= .cse5 .cse8) .cse9 .cse10)) (<= .cse5 0))) (and (<= .cse2 v_idx_218) .cse4))))) (or (<= .cse1 v_idx_210) (< v_idx_210 c_ULTIMATE.start_malloc_ptr) (= (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_210) 0)) (or (< v_idx_213 c_ULTIMATE.start_malloc_ptr) (<= .cse1 v_idx_213) (= 1 (select |c_#valid| v_idx_213))) (<= .cse2 c_ULTIMATE.start_main_p3)))) is different from false [2019-02-15 11:25:03,566 INFO L420 sIntCurrentIteration]: We unified 3 AI predicates to 3 [2019-02-15 11:25:03,566 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:25:03,567 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:25:03,567 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 6 [2019-02-15 11:25:03,567 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:25:03,568 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2019-02-15 11:25:03,568 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2019-02-15 11:25:03,569 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=5, Unknown=2, NotChecked=6, Total=20 [2019-02-15 11:25:03,569 INFO L87 Difference]: Start difference. First operand 11 states and 21 transitions. Second operand 5 states. [2019-02-15 11:25:03,906 WARN L838 $PredicateComparison]: unable to prove that (and (forall ((v_idx_203 Int) (v_idx_207 Int) (v_idx_205 Int) (v_idx_200 Int) (v_idx_197 Int)) (let ((.cse9 (+ c_ULTIMATE.start_main_p1 2)) (.cse0 (+ c_ULTIMATE.start_main_p1 1)) (.cse10 (+ c_ULTIMATE.start_main_p3 1)) (.cse8 (+ c_ULTIMATE.start_main_p2 1))) (and (let ((.cse3 (select |c_#memory_int| v_idx_205))) (let ((.cse4 (<= .cse3 0)) (.cse5 (<= (* 2 .cse3) 0)) (.cse6 (< v_idx_205 c_ULTIMATE.start_main_p2)) (.cse7 (<= .cse8 v_idx_205))) (let ((.cse1 (or (and .cse4 .cse5) .cse6 .cse7))) (or (and (<= .cse0 v_idx_203) .cse1) (let ((.cse2 (select |c_#memory_int| v_idx_203))) (and (<= 0 .cse2) (or (and (<= .cse3 .cse2) .cse4 .cse5) .cse6 .cse7) (<= 0 (* 2 .cse2)))) (and (< v_idx_203 c_ULTIMATE.start_main_p1) .cse1))))) (<= .cse9 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (or (< v_idx_200 c_ULTIMATE.start_malloc_ptr) (<= .cse10 v_idx_200) (= 1 (select |c_#valid| v_idx_200))) (<= .cse9 c_ULTIMATE.start_malloc_ptr) (<= .cse8 c_ULTIMATE.start_malloc_ptr) (or (= (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_197) 0) (<= .cse10 v_idx_197) (< v_idx_197 c_ULTIMATE.start_malloc_ptr)) (<= .cse0 c_ULTIMATE.start_main_p2) (or (<= .cse10 v_idx_207) (= (select |c_#memory_int| v_idx_207) 0) (< v_idx_207 c_ULTIMATE.start_malloc_ptr)) (<= .cse8 c_ULTIMATE.start_main_p3)))) (forall ((v_idx_226 Int) (v_idx_223 Int) (v_idx_229 Int) (v_idx_233 Int) (v_idx_231 Int)) (let ((.cse11 (+ c_ULTIMATE.start_main_p1 2)) (.cse20 (+ c_ULTIMATE.start_main_p1 1)) (.cse21 (+ c_ULTIMATE.start_main_p3 1)) (.cse13 (+ c_ULTIMATE.start_main_p2 1))) (and (<= .cse11 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (let ((.cse15 (select |c_#memory_int| v_idx_229))) (let ((.cse16 (<= 0 .cse15)) (.cse17 (<= 0 (* 2 .cse15))) (.cse18 (< v_idx_229 c_ULTIMATE.start_main_p1)) (.cse19 (<= .cse20 v_idx_229))) (let ((.cse12 (or (and .cse16 .cse17) .cse18 .cse19))) (or (and .cse12 (< v_idx_231 c_ULTIMATE.start_main_p2)) (and (<= .cse13 v_idx_231) .cse12) (let ((.cse14 (select |c_#memory_int| v_idx_231))) (and (<= (* 2 .cse14) 0) (or (and (<= .cse14 .cse15) .cse16 .cse17) .cse18 .cse19) (<= .cse14 0))))))) (or (= 1 (select |c_#valid| v_idx_226)) (< v_idx_226 c_ULTIMATE.start_malloc_ptr) (<= .cse21 v_idx_226)) (or (= (select |c_#memory_int| v_idx_233) 0) (< v_idx_233 c_ULTIMATE.start_malloc_ptr) (<= .cse21 v_idx_233)) (<= .cse11 c_ULTIMATE.start_malloc_ptr) (<= .cse13 c_ULTIMATE.start_malloc_ptr) (<= .cse20 c_ULTIMATE.start_main_p2) (or (< v_idx_223 c_ULTIMATE.start_malloc_ptr) (= 0 (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_223)) (<= .cse21 v_idx_223)) (<= .cse13 c_ULTIMATE.start_main_p3)))) (forall ((v_idx_213 Int) (v_idx_218 Int) (v_idx_216 Int) (v_idx_210 Int) (v_idx_220 Int)) (let ((.cse22 (+ c_ULTIMATE.start_main_p1 2)) (.cse25 (+ c_ULTIMATE.start_main_p1 1)) (.cse23 (+ c_ULTIMATE.start_main_p3 1)) (.cse24 (+ c_ULTIMATE.start_main_p2 1))) (and (<= .cse22 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (or (< v_idx_220 c_ULTIMATE.start_malloc_ptr) (= 0 (select |c_#memory_int| v_idx_220)) (<= .cse23 v_idx_220)) (<= .cse22 c_ULTIMATE.start_malloc_ptr) (<= .cse24 c_ULTIMATE.start_malloc_ptr) (<= .cse25 c_ULTIMATE.start_main_p2) (let ((.cse30 (select |c_#memory_int| v_idx_216))) (let ((.cse28 (< v_idx_216 c_ULTIMATE.start_main_p1)) (.cse31 (<= 0 .cse30)) (.cse32 (<= 0 (* 2 .cse30))) (.cse29 (<= .cse25 v_idx_216))) (let ((.cse26 (or .cse28 (and .cse31 .cse32) .cse29))) (or (and (< v_idx_218 c_ULTIMATE.start_main_p2) .cse26) (let ((.cse27 (select |c_#memory_int| v_idx_218))) (and (<= (* 2 .cse27) 0) (or .cse28 .cse29 (and (<= .cse27 .cse30) .cse31 .cse32)) (<= .cse27 0))) (and (<= .cse24 v_idx_218) .cse26))))) (or (<= .cse23 v_idx_210) (< v_idx_210 c_ULTIMATE.start_malloc_ptr) (= (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_210) 0)) (or (< v_idx_213 c_ULTIMATE.start_malloc_ptr) (<= .cse23 v_idx_213) (= 1 (select |c_#valid| v_idx_213))) (<= .cse24 c_ULTIMATE.start_main_p3))))) is different from false [2019-02-15 11:25:07,198 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:25:07,199 INFO L93 Difference]: Finished difference Result 17 states and 29 transitions. [2019-02-15 11:25:07,199 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:25:07,199 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 4 [2019-02-15 11:25:07,199 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:25:07,199 INFO L225 Difference]: With dead ends: 17 [2019-02-15 11:25:07,199 INFO L226 Difference]: Without dead ends: 12 [2019-02-15 11:25:07,200 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=6, Unknown=3, NotChecked=12, Total=30 [2019-02-15 11:25:07,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2019-02-15 11:25:07,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 10. [2019-02-15 11:25:07,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2019-02-15 11:25:07,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 18 transitions. [2019-02-15 11:25:07,206 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 18 transitions. Word has length 4 [2019-02-15 11:25:07,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:25:07,207 INFO L480 AbstractCegarLoop]: Abstraction has 10 states and 18 transitions. [2019-02-15 11:25:07,207 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2019-02-15 11:25:07,207 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 18 transitions. [2019-02-15 11:25:07,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2019-02-15 11:25:07,207 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:25:07,207 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2019-02-15 11:25:07,207 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:25:07,208 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:07,208 INFO L82 PathProgramCache]: Analyzing trace with hash 929674, now seen corresponding path program 1 times [2019-02-15 11:25:07,208 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:25:07,209 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:25:07,209 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:25:07,209 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:25:07,209 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:25:07,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:25:07,302 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:25:07,302 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:25:07,303 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:25:07,303 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 5 with the following transitions: [2019-02-15 11:25:07,303 INFO L207 CegarAbsIntRunner]: [0], [6], [12], [15] [2019-02-15 11:25:07,304 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:25:07,304 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:25:17,748 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:25:17,748 INFO L272 AbstractInterpreter]: Visited 4 different actions 31 times. Merged at 2 different actions 9 times. Widened at 2 different actions 5 times. Found 11 fixpoints after 2 different actions. Largest state had 0 variables. [2019-02-15 11:25:17,748 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:17,748 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:25:17,995 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:25:18,150 INFO L420 sIntCurrentIteration]: We unified 3 AI predicates to 3 [2019-02-15 11:25:18,150 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:25:18,150 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:25:18,150 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [3] total 4 [2019-02-15 11:25:18,150 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:25:18,151 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:25:18,151 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:25:18,151 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:25:18,151 INFO L87 Difference]: Start difference. First operand 10 states and 18 transitions. Second operand 3 states. [2019-02-15 11:25:18,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:25:18,707 INFO L93 Difference]: Finished difference Result 17 states and 29 transitions. [2019-02-15 11:25:18,707 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:25:18,708 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 4 [2019-02-15 11:25:18,708 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:25:18,708 INFO L225 Difference]: With dead ends: 17 [2019-02-15 11:25:18,708 INFO L226 Difference]: Without dead ends: 12 [2019-02-15 11:25:18,709 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 2 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:25:18,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2019-02-15 11:25:18,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 10. [2019-02-15 11:25:18,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2019-02-15 11:25:18,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 18 transitions. [2019-02-15 11:25:18,716 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 18 transitions. Word has length 4 [2019-02-15 11:25:18,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:25:18,716 INFO L480 AbstractCegarLoop]: Abstraction has 10 states and 18 transitions. [2019-02-15 11:25:18,717 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:25:18,717 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 18 transitions. [2019-02-15 11:25:18,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2019-02-15 11:25:18,717 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:25:18,717 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2019-02-15 11:25:18,717 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:25:18,717 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:18,718 INFO L82 PathProgramCache]: Analyzing trace with hash 933518, now seen corresponding path program 1 times [2019-02-15 11:25:18,718 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:25:18,718 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:25:18,719 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:25:18,719 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:25:18,719 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:25:18,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:25:19,043 WARN L181 SmtUtils]: Spent 297.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 17 [2019-02-15 11:25:19,069 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:25:19,070 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:25:19,070 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:25:19,070 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 5 with the following transitions: [2019-02-15 11:25:19,070 INFO L207 CegarAbsIntRunner]: [0], [10], [12], [15] [2019-02-15 11:25:19,072 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:25:19,072 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:25:28,050 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:25:28,051 INFO L272 AbstractInterpreter]: Visited 4 different actions 28 times. Merged at 2 different actions 8 times. Widened at 2 different actions 4 times. Found 10 fixpoints after 2 different actions. Largest state had 0 variables. [2019-02-15 11:25:28,051 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:28,051 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:25:28,299 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:25:28,448 INFO L420 sIntCurrentIteration]: We unified 3 AI predicates to 3 [2019-02-15 11:25:28,449 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:25:28,449 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:25:28,449 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [3] total 4 [2019-02-15 11:25:28,449 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:25:28,450 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-02-15 11:25:28,450 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-02-15 11:25:28,450 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:25:28,450 INFO L87 Difference]: Start difference. First operand 10 states and 18 transitions. Second operand 3 states. [2019-02-15 11:25:28,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:25:28,990 INFO L93 Difference]: Finished difference Result 17 states and 34 transitions. [2019-02-15 11:25:28,990 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:25:28,991 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 4 [2019-02-15 11:25:28,991 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:25:28,991 INFO L225 Difference]: With dead ends: 17 [2019-02-15 11:25:28,991 INFO L226 Difference]: Without dead ends: 15 [2019-02-15 11:25:28,992 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 2 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-02-15 11:25:28,992 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2019-02-15 11:25:29,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2019-02-15 11:25:29,004 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2019-02-15 11:25:29,004 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 32 transitions. [2019-02-15 11:25:29,005 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 32 transitions. Word has length 4 [2019-02-15 11:25:29,005 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:25:29,005 INFO L480 AbstractCegarLoop]: Abstraction has 15 states and 32 transitions. [2019-02-15 11:25:29,005 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-02-15 11:25:29,005 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 32 transitions. [2019-02-15 11:25:29,006 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2019-02-15 11:25:29,006 INFO L394 BasicCegarLoop]: Found error trace [2019-02-15 11:25:29,006 INFO L402 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2019-02-15 11:25:29,006 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr2ASSERT_VIOLATIONASSERT, ULTIMATE.startErr1ASSERT_VIOLATIONASSERT]=== [2019-02-15 11:25:29,006 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:29,007 INFO L82 PathProgramCache]: Analyzing trace with hash 28817894, now seen corresponding path program 1 times [2019-02-15 11:25:29,007 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2019-02-15 11:25:29,008 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:25:29,008 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-02-15 11:25:29,008 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2019-02-15 11:25:29,008 INFO L289 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2019-02-15 11:25:29,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-02-15 11:25:29,216 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-02-15 11:25:29,217 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2019-02-15 11:25:29,217 INFO L193 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2019-02-15 11:25:29,217 INFO L205 CegarAbsIntRunner]: Running AI on error trace of length 6 with the following transitions: [2019-02-15 11:25:29,218 INFO L207 CegarAbsIntRunner]: [0], [6], [10], [12], [15] [2019-02-15 11:25:29,219 INFO L148 AbstractInterpreter]: Using domain ArrayDomain [2019-02-15 11:25:29,219 INFO L101 FixpointEngine]: Starting fixpoint engine with domain ArrayDomain (maxUnwinding=3, maxParallelStates=2) [2019-02-15 11:25:48,407 INFO L266 AbstractInterpreter]: Error location(s) were unreachable [2019-02-15 11:25:48,407 INFO L272 AbstractInterpreter]: Visited 5 different actions 57 times. Merged at 3 different actions 13 times. Widened at 3 different actions 9 times. Found 29 fixpoints after 3 different actions. Largest state had 0 variables. [2019-02-15 11:25:48,407 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-02-15 11:25:48,408 INFO L403 sIntCurrentIteration]: Generating AbsInt predicates [2019-02-15 11:25:48,868 INFO L418 sIntCurrentIteration]: Unifying AI predicates [2019-02-15 11:25:48,920 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_idx_454 Int) (v_idx_444 Int) (v_idx_447 Int) (v_idx_452 Int) (v_idx_450 Int)) (let ((.cse1 (+ c_ULTIMATE.start_main_p1 2)) (.cse0 (+ c_ULTIMATE.start_main_p3 1)) (.cse19 (+ c_ULTIMATE.start_main_p1 1)) (.cse2 (+ c_ULTIMATE.start_main_p2 1))) (and (or (< v_idx_447 c_ULTIMATE.start_malloc_ptr) (= (select |c_#valid| v_idx_447) 1) (<= .cse0 v_idx_447)) (<= .cse1 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (or (= 0 (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_444)) (< v_idx_444 c_ULTIMATE.start_malloc_ptr) (<= .cse0 v_idx_444)) (<= .cse1 c_ULTIMATE.start_malloc_ptr) (<= .cse2 c_ULTIMATE.start_malloc_ptr) (let ((.cse11 (select |c_#memory_int| v_idx_452)) (.cse16 (select |c_#memory_int| v_idx_450))) (let ((.cse15 (<= .cse2 v_idx_452)) (.cse14 (< v_idx_452 c_ULTIMATE.start_main_p2)) (.cse5 (<= .cse11 .cse16)) (.cse10 (<= (* 2 .cse11) 0)) (.cse12 (<= .cse11 0)) (.cse4 (< v_idx_450 c_ULTIMATE.start_main_p1)) (.cse9 (<= .cse19 v_idx_450)) (.cse6 (<= 0 .cse16)) (.cse8 (<= 0 (* 2 .cse16)))) (let ((.cse17 (let ((.cse18 (or .cse4 .cse9 (and .cse6 .cse8)))) (or (and .cse18 .cse15) (and .cse18 .cse14) (and (or .cse4 (and .cse5 .cse6 .cse8) .cse9) .cse10 .cse12))))) (or (let ((.cse3 (select |c_#memory_int| v_idx_454))) (and (<= 0 (* 2 .cse3)) (let ((.cse7 (<= 0 (+ .cse3 .cse16)))) (let ((.cse13 (or .cse4 .cse9 (and .cse6 .cse7 .cse8)))) (or (and (or .cse4 (and .cse5 .cse6 .cse7 .cse8) .cse9) .cse10 (<= .cse11 .cse3) .cse12) (and .cse13 .cse14) (and .cse13 .cse15)))) (<= 0 .cse3))) (and (< v_idx_454 c_ULTIMATE.start_malloc_ptr) .cse17) (and (<= .cse0 v_idx_454) .cse17))))) (<= .cse19 c_ULTIMATE.start_main_p2) (<= .cse2 c_ULTIMATE.start_main_p3)))) is different from false [2019-02-15 11:25:49,025 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_idx_478 Int) (v_idx_476 Int) (v_idx_470 Int) (v_idx_480 Int) (v_idx_473 Int)) (let ((.cse0 (+ c_ULTIMATE.start_main_p1 2)) (.cse18 (+ c_ULTIMATE.start_main_p3 1)) (.cse19 (+ c_ULTIMATE.start_main_p1 1)) (.cse16 (+ c_ULTIMATE.start_main_p2 1))) (and (<= .cse0 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (let ((.cse15 (select |c_#memory_int| v_idx_480)) (.cse4 (select |c_#memory_int| v_idx_476))) (let ((.cse3 (<= 0 (* 2 .cse4))) (.cse5 (<= 0 .cse4)) (.cse10 (<= 0 (+ .cse15 .cse4))) (.cse14 (<= .cse19 v_idx_476)) (.cse13 (< v_idx_476 c_ULTIMATE.start_main_p1)) (.cse6 (<= .cse18 v_idx_480)) (.cse11 (< v_idx_480 c_ULTIMATE.start_malloc_ptr)) (.cse8 (<= 0 .cse15)) (.cse9 (<= 0 (* 2 .cse15)))) (let ((.cse1 (let ((.cse17 (or .cse6 .cse11 (and .cse8 .cse9)))) (or (and .cse3 .cse5 (or .cse6 .cse11 (and .cse8 .cse9 .cse10))) (and .cse17 .cse14) (and .cse13 .cse17))))) (or (and .cse1 (< v_idx_478 c_ULTIMATE.start_main_p2)) (let ((.cse2 (select |c_#memory_int| v_idx_478))) (and (<= (* 2 .cse2) 0) (let ((.cse7 (<= .cse2 .cse15))) (let ((.cse12 (or .cse6 (and .cse7 .cse8 .cse9) .cse11))) (or (and .cse3 (<= .cse2 .cse4) .cse5 (or .cse6 (and .cse7 .cse8 .cse9 .cse10) .cse11)) (and .cse12 .cse13) (and .cse12 .cse14)))) (<= .cse2 0))) (and .cse1 (<= .cse16 v_idx_478)))))) (or (<= .cse18 v_idx_470) (< v_idx_470 c_ULTIMATE.start_malloc_ptr) (= (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_470) 0)) (<= .cse0 c_ULTIMATE.start_malloc_ptr) (<= .cse16 c_ULTIMATE.start_malloc_ptr) (or (<= .cse18 v_idx_473) (< v_idx_473 c_ULTIMATE.start_malloc_ptr) (= 1 (select |c_#valid| v_idx_473))) (<= .cse19 c_ULTIMATE.start_main_p2) (<= .cse16 c_ULTIMATE.start_main_p3)))) is different from false [2019-02-15 11:25:49,083 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_idx_489 Int) (v_idx_493 Int) (v_idx_491 Int) (v_idx_486 Int) (v_idx_483 Int)) (let ((.cse0 (+ c_ULTIMATE.start_main_p1 2)) (.cse3 (+ c_ULTIMATE.start_main_p1 1)) (.cse1 (+ c_ULTIMATE.start_main_p3 1)) (.cse19 (+ c_ULTIMATE.start_main_p2 1))) (and (<= .cse0 c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_malloc_ptr c_ULTIMATE.start_main_p3) (<= c_ULTIMATE.start_main_p3 c_ULTIMATE.start_malloc_ptr) (or (<= .cse1 v_idx_483) (= 0 (select |c_ULTIMATE.start_malloc_old_#valid| v_idx_483)) (< v_idx_483 c_ULTIMATE.start_malloc_ptr)) (let ((.cse17 (select |c_#memory_int| v_idx_491)) (.cse13 (select |c_#memory_int| v_idx_493))) (let ((.cse16 (< v_idx_493 c_ULTIMATE.start_malloc_ptr)) (.cse8 (<= .cse17 .cse13)) (.cse5 (<= 0 (* 2 .cse13))) (.cse6 (<= 0 .cse13)) (.cse14 (<= .cse1 v_idx_493)) (.cse7 (<= .cse19 v_idx_491)) (.cse9 (<= (* 2 .cse17) 0)) (.cse11 (<= .cse17 0)) (.cse12 (< v_idx_491 c_ULTIMATE.start_main_p2))) (let ((.cse2 (let ((.cse18 (or .cse7 (and .cse9 .cse11) .cse12))) (or (and .cse18 .cse16) (and (or .cse7 (and .cse8 .cse9 .cse11) .cse12) .cse5 .cse6) (and .cse14 .cse18))))) (or (and .cse2 (<= .cse3 v_idx_489)) (let ((.cse4 (select |c_#memory_int| v_idx_489))) (and (<= 0 (* 2 .cse4)) (let ((.cse10 (<= .cse17 .cse4))) (let ((.cse15 (or .cse7 (and .cse9 .cse10 .cse11) .cse12))) (or (and .cse5 .cse6 (or .cse7 (and .cse8 .cse9 .cse10 .cse11) .cse12) (<= 0 (+ .cse13 .cse4))) (and .cse14 .cse15) (and .cse16 .cse15)))) (<= 0 .cse4))) (and .cse2 (< v_idx_489 c_ULTIMATE.start_main_p1)))))) (<= .cse0 c_ULTIMATE.start_malloc_ptr) (<= .cse19 c_ULTIMATE.start_malloc_ptr) (<= .cse3 c_ULTIMATE.start_main_p2) (or (= 1 (select |c_#valid| v_idx_486)) (< v_idx_486 c_ULTIMATE.start_malloc_ptr) (<= .cse1 v_idx_486)) (<= .cse19 c_ULTIMATE.start_main_p3)))) is different from false [2019-02-15 11:25:49,088 INFO L420 sIntCurrentIteration]: We unified 4 AI predicates to 4 [2019-02-15 11:25:49,088 INFO L429 sIntCurrentIteration]: Finished generation of AbsInt predicates [2019-02-15 11:25:49,089 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-02-15 11:25:49,089 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 8 [2019-02-15 11:25:49,089 INFO L257 anRefinementStrategy]: Using the first perfect interpolant sequence [2019-02-15 11:25:49,089 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2019-02-15 11:25:49,089 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2019-02-15 11:25:49,089 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=6, Unknown=3, NotChecked=12, Total=30 [2019-02-15 11:25:49,090 INFO L87 Difference]: Start difference. First operand 15 states and 32 transitions. Second operand 6 states. [2019-02-15 11:25:51,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-02-15 11:25:51,104 INFO L93 Difference]: Finished difference Result 15 states and 32 transitions. [2019-02-15 11:25:51,105 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-02-15 11:25:51,105 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 5 [2019-02-15 11:25:51,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-02-15 11:25:51,105 INFO L225 Difference]: With dead ends: 15 [2019-02-15 11:25:51,105 INFO L226 Difference]: Without dead ends: 0 [2019-02-15 11:25:51,106 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 0 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=9, Invalid=6, Unknown=3, NotChecked=12, Total=30 [2019-02-15 11:25:51,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2019-02-15 11:25:51,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2019-02-15 11:25:51,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2019-02-15 11:25:51,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2019-02-15 11:25:51,106 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 5 [2019-02-15 11:25:51,106 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-02-15 11:25:51,106 INFO L480 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2019-02-15 11:25:51,106 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2019-02-15 11:25:51,107 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2019-02-15 11:25:51,107 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2019-02-15 11:25:51,110 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2019-02-15 11:25:51,187 INFO L448 ceAbstractionStarter]: For program point ULTIMATE.startEXIT(lines 7 9) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L444 ceAbstractionStarter]: At program point L31-1(lines 28 36) the Hoare annotation is: (forall ((v_idx_467 Int) (v_idx_457 Int) (v_idx_465 Int) (v_idx_460 Int) (v_idx_463 Int)) (let ((.cse0 (+ ULTIMATE.start_main_p1 2)) (.cse18 (+ ULTIMATE.start_main_p1 1)) (.cse19 (+ ULTIMATE.start_main_p3 1)) (.cse15 (+ ULTIMATE.start_main_p2 1))) (and (<= .cse0 ULTIMATE.start_main_p3) (<= ULTIMATE.start_malloc_ptr ULTIMATE.start_main_p3) (<= ULTIMATE.start_main_p3 ULTIMATE.start_malloc_ptr) (let ((.cse14 (select |#memory_int| v_idx_463)) (.cse11 (select |#memory_int| v_idx_467))) (let ((.cse1 (<= .cse19 v_idx_467)) (.cse9 (<= 0 (* 2 .cse11))) (.cse8 (<= 0 (+ .cse14 .cse11))) (.cse12 (<= 0 .cse11)) (.cse13 (< v_idx_467 ULTIMATE.start_malloc_ptr)) (.cse3 (<= .cse18 v_idx_463)) (.cse5 (<= 0 (* 2 .cse14))) (.cse7 (<= 0 .cse14)) (.cse4 (< v_idx_463 ULTIMATE.start_main_p1))) (let ((.cse16 (let ((.cse17 (or .cse3 (and .cse5 .cse7) .cse4))) (or (and .cse1 .cse17) (and .cse9 (or (and .cse5 .cse7 .cse8) .cse3 .cse4) .cse12) (and .cse13 .cse17))))) (or (let ((.cse10 (select |#memory_int| v_idx_465))) (and (let ((.cse6 (<= .cse10 .cse14))) (let ((.cse2 (or .cse3 .cse4 (and .cse5 .cse6 .cse7)))) (or (and .cse1 .cse2) (and (or .cse3 .cse4 (and .cse5 .cse6 .cse7 .cse8)) .cse9 (<= .cse10 .cse11) .cse12) (and .cse13 .cse2)))) (<= (* 2 .cse10) 0) (<= .cse10 0))) (and (<= .cse15 v_idx_465) .cse16) (and .cse16 (< v_idx_465 ULTIMATE.start_main_p2)))))) (or (= (select |#valid| v_idx_460) 1) (<= .cse19 v_idx_460) (< v_idx_460 ULTIMATE.start_malloc_ptr)) (<= .cse0 ULTIMATE.start_malloc_ptr) (<= .cse15 ULTIMATE.start_malloc_ptr) (<= .cse18 ULTIMATE.start_main_p2) (or (< v_idx_457 ULTIMATE.start_malloc_ptr) (= (select |ULTIMATE.start_malloc_old_#valid| v_idx_457) 0) (<= .cse19 v_idx_457)) (<= .cse15 ULTIMATE.start_main_p3)))) [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point ULTIMATE.startENTRY(lines 7 9) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point ULTIMATE.startErr2ASSERT_VIOLATIONASSERT(line 40) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point ULTIMATE.startErr0ASSERT_VIOLATIONASSERT(line 38) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point L14(lines 7 42) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point ULTIMATE.startErr1ASSERT_VIOLATIONASSERT(line 39) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point L40(line 40) no Hoare annotation was computed. [2019-02-15 11:25:51,188 INFO L448 ceAbstractionStarter]: For program point L39(line 39) no Hoare annotation was computed. [2019-02-15 11:25:51,204 INFO L202 PluginConnector]: Adding new model speedup-poc-dd-3-limited.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.02 11:25:51 BoogieIcfgContainer [2019-02-15 11:25:51,204 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2019-02-15 11:25:51,205 INFO L168 Benchmark]: Toolchain (without parser) took 80398.98 ms. Allocated memory was 133.7 MB in the beginning and 2.7 GB in the end (delta: 2.6 GB). Free memory was 109.1 MB in the beginning and 750.9 MB in the end (delta: -641.9 MB). Peak memory consumption was 2.0 GB. Max. memory is 7.1 GB. [2019-02-15 11:25:51,206 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.22 ms. Allocated memory is still 133.7 MB. Free memory is still 110.3 MB. There was no memory consumed. Max. memory is 7.1 GB. [2019-02-15 11:25:51,207 INFO L168 Benchmark]: Boogie Procedure Inliner took 61.54 ms. Allocated memory is still 133.7 MB. Free memory was 108.9 MB in the beginning and 106.8 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 7.1 GB. [2019-02-15 11:25:51,207 INFO L168 Benchmark]: Boogie Preprocessor took 28.82 ms. Allocated memory is still 133.7 MB. Free memory was 106.8 MB in the beginning and 105.5 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 7.1 GB. [2019-02-15 11:25:51,208 INFO L168 Benchmark]: RCFGBuilder took 335.33 ms. Allocated memory is still 133.7 MB. Free memory was 105.5 MB in the beginning and 96.2 MB in the end (delta: 9.3 MB). Peak memory consumption was 9.3 MB. Max. memory is 7.1 GB. [2019-02-15 11:25:51,209 INFO L168 Benchmark]: TraceAbstraction took 79968.81 ms. Allocated memory was 133.7 MB in the beginning and 2.7 GB in the end (delta: 2.6 GB). Free memory was 95.8 MB in the beginning and 750.9 MB in the end (delta: -655.2 MB). Peak memory consumption was 1.9 GB. Max. memory is 7.1 GB. [2019-02-15 11:25:51,214 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.22 ms. Allocated memory is still 133.7 MB. Free memory is still 110.3 MB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 61.54 ms. Allocated memory is still 133.7 MB. Free memory was 108.9 MB in the beginning and 106.8 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 28.82 ms. Allocated memory is still 133.7 MB. Free memory was 106.8 MB in the beginning and 105.5 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 7.1 GB. * RCFGBuilder took 335.33 ms. Allocated memory is still 133.7 MB. Free memory was 105.5 MB in the beginning and 96.2 MB in the end (delta: 9.3 MB). Peak memory consumption was 9.3 MB. Max. memory is 7.1 GB. * TraceAbstraction took 79968.81 ms. Allocated memory was 133.7 MB in the beginning and 2.7 GB in the end (delta: 2.6 GB). Free memory was 95.8 MB in the beginning and 750.9 MB in the end (delta: -655.2 MB). Peak memory consumption was 1.9 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - PositiveResult [Line: 38]: assertion always holds For all program executions holds that assertion always holds at this location - PositiveResult [Line: 40]: assertion always holds For all program executions holds that assertion always holds at this location - PositiveResult [Line: 39]: assertion always holds For all program executions holds that assertion always holds at this location - AllSpecificationsHoldResult: All specifications hold 3 specifications checked. All of them hold - InvariantResult [Line: 28]: Loop Invariant Derived loop invariant: (forall v_idx_467 : int, v_idx_457 : int, v_idx_465 : int, v_idx_460 : int, v_idx_463 : int :: ((((((((p1 + 2 <= p3 && ptr <= p3) && p3 <= ptr) && (((((((p3 + 1 <= v_idx_467 && ((p1 + 1 <= v_idx_463 || v_idx_463 < p1) || ((0 <= 2 * #memory_int[v_idx_463] && #memory_int[v_idx_465] <= #memory_int[v_idx_463]) && 0 <= #memory_int[v_idx_463]))) || (((((p1 + 1 <= v_idx_463 || v_idx_463 < p1) || (((0 <= 2 * #memory_int[v_idx_463] && #memory_int[v_idx_465] <= #memory_int[v_idx_463]) && 0 <= #memory_int[v_idx_463]) && 0 <= #memory_int[v_idx_463] + #memory_int[v_idx_467])) && 0 <= 2 * #memory_int[v_idx_467]) && #memory_int[v_idx_465] <= #memory_int[v_idx_467]) && 0 <= #memory_int[v_idx_467])) || (v_idx_467 < ptr && ((p1 + 1 <= v_idx_463 || v_idx_463 < p1) || ((0 <= 2 * #memory_int[v_idx_463] && #memory_int[v_idx_465] <= #memory_int[v_idx_463]) && 0 <= #memory_int[v_idx_463])))) && 2 * #memory_int[v_idx_465] <= 0) && #memory_int[v_idx_465] <= 0) || (p2 + 1 <= v_idx_465 && (((p3 + 1 <= v_idx_467 && ((p1 + 1 <= v_idx_463 || (0 <= 2 * #memory_int[v_idx_463] && 0 <= #memory_int[v_idx_463])) || v_idx_463 < p1)) || ((0 <= 2 * #memory_int[v_idx_467] && ((((0 <= 2 * #memory_int[v_idx_463] && 0 <= #memory_int[v_idx_463]) && 0 <= #memory_int[v_idx_463] + #memory_int[v_idx_467]) || p1 + 1 <= v_idx_463) || v_idx_463 < p1)) && 0 <= #memory_int[v_idx_467])) || (v_idx_467 < ptr && ((p1 + 1 <= v_idx_463 || (0 <= 2 * #memory_int[v_idx_463] && 0 <= #memory_int[v_idx_463])) || v_idx_463 < p1))))) || ((((p3 + 1 <= v_idx_467 && ((p1 + 1 <= v_idx_463 || (0 <= 2 * #memory_int[v_idx_463] && 0 <= #memory_int[v_idx_463])) || v_idx_463 < p1)) || ((0 <= 2 * #memory_int[v_idx_467] && ((((0 <= 2 * #memory_int[v_idx_463] && 0 <= #memory_int[v_idx_463]) && 0 <= #memory_int[v_idx_463] + #memory_int[v_idx_467]) || p1 + 1 <= v_idx_463) || v_idx_463 < p1)) && 0 <= #memory_int[v_idx_467])) || (v_idx_467 < ptr && ((p1 + 1 <= v_idx_463 || (0 <= 2 * #memory_int[v_idx_463] && 0 <= #memory_int[v_idx_463])) || v_idx_463 < p1))) && v_idx_465 < p2))) && ((#valid[v_idx_460] == 1 || p3 + 1 <= v_idx_460) || v_idx_460 < ptr)) && p1 + 2 <= ptr) && p2 + 1 <= ptr) && p1 + 1 <= p2) && ((v_idx_457 < ptr || old(malloc_old_#valid)[v_idx_457] == 0) || p3 + 1 <= v_idx_457)) && p2 + 1 <= p3) - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 9 locations, 3 error locations. SAFE Result, 79.8s OverallTime, 9 OverallIterations, 1 TraceHistogramMax, 9.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 31 SDtfs, 19 SDslu, 1 SDs, 0 SdLazy, 50 SolverSat, 43 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 6.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 23 GetRequests, 0 SyntacticMatches, 8 SemanticMatches, 15 ConstructedPredicates, 6 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 65.4s AbstIntTime, 7 AbstIntIterations, 7 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 9 MinimizatonAttempts, 11 StatesRemovedByMinimization, 5 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 1 LocationsWithAnnotation, 1 PreInvPairs, 8 NumberOfFragments, 410 HoareAnnotationTreeSize, 1 FomulaSimplifications, 14722 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 1 FomulaSimplificationsInter, 0 FormulaSimplificationTreeSizeReductionInter, 0.0s HoareSimplificationTimeInter, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 1.4s InterpolantComputationTime, 31 NumberOfCodeBlocks, 31 NumberOfCodeBlocksAsserted, 9 NumberOfCheckSat, 22 ConstructedInterpolants, 0 QuantifiedInterpolants, 682 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 9 InterpolantComputations, 2 PerfectInterpolantSequences, 0/18 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be correct! Received shutdown request...