/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 06:40:19,600 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 06:40:19,602 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 06:40:19,656 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 06:40:19,657 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 06:40:19,659 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 06:40:19,662 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 06:40:19,668 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 06:40:19,670 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 06:40:19,673 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 06:40:19,673 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 06:40:19,674 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 06:40:19,675 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 06:40:19,675 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 06:40:19,676 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 06:40:19,677 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 06:40:19,677 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 06:40:19,678 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 06:40:19,679 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 06:40:19,681 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 06:40:19,682 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 06:40:19,689 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 06:40:19,690 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 06:40:19,693 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 06:40:19,694 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 06:40:19,703 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 06:40:19,703 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 06:40:19,704 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 06:40:19,704 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 06:40:19,705 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 06:40:19,705 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 06:40:19,706 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 06:40:19,706 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 06:40:19,707 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 06:40:19,707 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 06:40:19,708 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 06:40:19,708 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 06:40:19,709 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 06:40:19,709 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 06:40:19,709 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 06:40:19,710 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 06:40:19,715 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 06:40:19,715 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-08 06:40:19,725 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 06:40:19,725 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 06:40:19,727 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 06:40:19,727 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-08 06:40:19,727 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 06:40:19,727 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-08 06:40:19,727 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 06:40:19,727 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 06:40:19,728 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 06:40:19,728 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 06:40:19,728 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 06:40:19,729 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 06:40:19,729 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 06:40:19,730 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 06:40:19,730 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 06:40:19,730 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 06:40:19,730 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 06:40:19,730 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 06:40:19,730 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-08 06:40:19,730 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-08 06:40:19,948 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 06:40:19,979 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 06:40:19,981 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 06:40:19,982 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 06:40:19,983 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 06:40:19,984 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound2.c [2022-04-08 06:40:20,046 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69d4ded3d/fc4de2711676499097caca3a7e1c9e43/FLAGabbaff6bb [2022-04-08 06:40:20,465 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 06:40:20,465 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound2.c [2022-04-08 06:40:20,471 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69d4ded3d/fc4de2711676499097caca3a7e1c9e43/FLAGabbaff6bb [2022-04-08 06:40:20,867 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69d4ded3d/fc4de2711676499097caca3a7e1c9e43 [2022-04-08 06:40:20,869 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 06:40:20,871 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 06:40:20,872 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 06:40:20,872 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 06:40:20,876 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 06:40:20,877 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 06:40:20" (1/1) ... [2022-04-08 06:40:20,878 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@111b8f23 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:20, skipping insertion in model container [2022-04-08 06:40:20,879 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 06:40:20" (1/1) ... [2022-04-08 06:40:20,885 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 06:40:20,899 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 06:40:21,100 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound2.c[526,539] [2022-04-08 06:40:21,129 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 06:40:21,136 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 06:40:21,152 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound2.c[526,539] [2022-04-08 06:40:21,171 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 06:40:21,183 INFO L208 MainTranslator]: Completed translation [2022-04-08 06:40:21,184 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21 WrapperNode [2022-04-08 06:40:21,185 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 06:40:21,185 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 06:40:21,186 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 06:40:21,186 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 06:40:21,195 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,195 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,203 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,203 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,218 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,225 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,233 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,236 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 06:40:21,237 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 06:40:21,237 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 06:40:21,237 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 06:40:21,240 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (1/1) ... [2022-04-08 06:40:21,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 06:40:21,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:21,269 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-08 06:40:21,300 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-08 06:40:21,316 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 06:40:21,316 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 06:40:21,316 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 06:40:21,317 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 06:40:21,317 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 06:40:21,317 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 06:40:21,317 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 06:40:21,317 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 06:40:21,317 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 06:40:21,318 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 06:40:21,318 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-08 06:40:21,319 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 06:40:21,319 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 06:40:21,319 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 06:40:21,319 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 06:40:21,320 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 06:40:21,320 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 06:40:21,320 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 06:40:21,320 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 06:40:21,320 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 06:40:21,381 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 06:40:21,382 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 06:40:21,567 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 06:40:21,573 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 06:40:21,573 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-08 06:40:21,575 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 06:40:21 BoogieIcfgContainer [2022-04-08 06:40:21,575 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 06:40:21,576 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 06:40:21,576 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 06:40:21,594 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 06:40:21,595 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 06:40:20" (1/3) ... [2022-04-08 06:40:21,595 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7768fc90 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 06:40:21, skipping insertion in model container [2022-04-08 06:40:21,596 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:40:21" (2/3) ... [2022-04-08 06:40:21,596 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7768fc90 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 06:40:21, skipping insertion in model container [2022-04-08 06:40:21,596 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 06:40:21" (3/3) ... [2022-04-08 06:40:21,597 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound2.c [2022-04-08 06:40:21,601 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 06:40:21,602 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 06:40:21,669 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 06:40:21,677 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-08 06:40:21,677 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 06:40:21,705 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 06:40:21,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-08 06:40:21,712 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:21,712 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:21,714 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:21,719 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:21,719 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 1 times [2022-04-08 06:40:21,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:21,728 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [95844734] [2022-04-08 06:40:21,739 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:21,740 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 2 times [2022-04-08 06:40:21,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:21,743 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303177358] [2022-04-08 06:40:21,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:21,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:21,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:21,939 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 06:40:21,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:21,965 INFO L290 TraceCheckUtils]: 0: Hoare triple {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-08 06:40:21,965 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-08 06:40:21,966 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #92#return; {34#true} is VALID [2022-04-08 06:40:21,970 INFO L272 TraceCheckUtils]: 0: Hoare triple {34#true} call ULTIMATE.init(); {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 06:40:21,971 INFO L290 TraceCheckUtils]: 1: Hoare triple {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-08 06:40:21,971 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-08 06:40:21,972 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #92#return; {34#true} is VALID [2022-04-08 06:40:21,972 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret7 := main(); {34#true} is VALID [2022-04-08 06:40:21,972 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {34#true} is VALID [2022-04-08 06:40:21,973 INFO L290 TraceCheckUtils]: 6: Hoare triple {34#true} assume !true; {35#false} is VALID [2022-04-08 06:40:21,973 INFO L290 TraceCheckUtils]: 7: Hoare triple {35#false} assume !true; {35#false} is VALID [2022-04-08 06:40:21,974 INFO L272 TraceCheckUtils]: 8: Hoare triple {35#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {35#false} is VALID [2022-04-08 06:40:21,975 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-08 06:40:21,975 INFO L290 TraceCheckUtils]: 10: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-08 06:40:21,975 INFO L290 TraceCheckUtils]: 11: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-08 06:40:21,976 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 06:40:21,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:21,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1303177358] [2022-04-08 06:40:21,978 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1303177358] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:21,978 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:21,978 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 06:40:21,985 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:21,986 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [95844734] [2022-04-08 06:40:21,987 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [95844734] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:21,987 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:21,987 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 06:40:21,987 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [644229688] [2022-04-08 06:40:21,988 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:21,994 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-08 06:40:21,996 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:22,000 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:22,033 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 12 edges. 12 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:22,033 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 06:40:22,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:22,056 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 06:40:22,057 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 06:40:22,061 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:22,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:22,279 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-04-08 06:40:22,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 06:40:22,279 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-08 06:40:22,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:22,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:22,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 91 transitions. [2022-04-08 06:40:22,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:22,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 91 transitions. [2022-04-08 06:40:22,318 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 91 transitions. [2022-04-08 06:40:22,436 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 91 edges. 91 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:22,454 INFO L225 Difference]: With dead ends: 57 [2022-04-08 06:40:22,454 INFO L226 Difference]: Without dead ends: 27 [2022-04-08 06:40:22,458 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 06:40:22,463 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:22,464 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 06:40:22,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-08 06:40:22,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-08 06:40:22,512 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:22,513 INFO L82 GeneralOperation]: Start isEquivalent. First operand 27 states. Second operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:22,513 INFO L74 IsIncluded]: Start isIncluded. First operand 27 states. Second operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:22,514 INFO L87 Difference]: Start difference. First operand 27 states. Second operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:22,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:22,519 INFO L93 Difference]: Finished difference Result 27 states and 37 transitions. [2022-04-08 06:40:22,519 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2022-04-08 06:40:22,520 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:22,520 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:22,521 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 27 states. [2022-04-08 06:40:22,521 INFO L87 Difference]: Start difference. First operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 27 states. [2022-04-08 06:40:22,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:22,541 INFO L93 Difference]: Finished difference Result 27 states and 37 transitions. [2022-04-08 06:40:22,541 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2022-04-08 06:40:22,542 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:22,542 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:22,542 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:22,542 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:22,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:22,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-04-08 06:40:22,547 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-04-08 06:40:22,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:22,547 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-04-08 06:40:22,547 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:22,548 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 36 transitions. [2022-04-08 06:40:22,617 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 36 edges. 36 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:22,621 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-04-08 06:40:22,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-08 06:40:22,621 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:22,621 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:22,622 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 06:40:22,622 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:22,623 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:22,623 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 1 times [2022-04-08 06:40:22,623 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:22,623 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1158784865] [2022-04-08 06:40:22,624 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:22,624 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 2 times [2022-04-08 06:40:22,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:22,624 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [133134397] [2022-04-08 06:40:22,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:22,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:22,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:22,749 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 06:40:22,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:22,768 INFO L290 TraceCheckUtils]: 0: Hoare triple {270#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {262#true} is VALID [2022-04-08 06:40:22,769 INFO L290 TraceCheckUtils]: 1: Hoare triple {262#true} assume true; {262#true} is VALID [2022-04-08 06:40:22,769 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {262#true} {262#true} #92#return; {262#true} is VALID [2022-04-08 06:40:22,770 INFO L272 TraceCheckUtils]: 0: Hoare triple {262#true} call ULTIMATE.init(); {270#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 06:40:22,770 INFO L290 TraceCheckUtils]: 1: Hoare triple {270#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {262#true} is VALID [2022-04-08 06:40:22,770 INFO L290 TraceCheckUtils]: 2: Hoare triple {262#true} assume true; {262#true} is VALID [2022-04-08 06:40:22,770 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {262#true} {262#true} #92#return; {262#true} is VALID [2022-04-08 06:40:22,770 INFO L272 TraceCheckUtils]: 4: Hoare triple {262#true} call #t~ret7 := main(); {262#true} is VALID [2022-04-08 06:40:22,773 INFO L290 TraceCheckUtils]: 5: Hoare triple {262#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {267#(= main_~q~0 0)} is VALID [2022-04-08 06:40:22,774 INFO L290 TraceCheckUtils]: 6: Hoare triple {267#(= main_~q~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {267#(= main_~q~0 0)} is VALID [2022-04-08 06:40:22,775 INFO L290 TraceCheckUtils]: 7: Hoare triple {267#(= main_~q~0 0)} assume !!(#t~post5 < 2);havoc #t~post5; {267#(= main_~q~0 0)} is VALID [2022-04-08 06:40:22,776 INFO L272 TraceCheckUtils]: 8: Hoare triple {267#(= main_~q~0 0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {268#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:40:22,776 INFO L290 TraceCheckUtils]: 9: Hoare triple {268#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {269#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 06:40:22,777 INFO L290 TraceCheckUtils]: 10: Hoare triple {269#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {263#false} is VALID [2022-04-08 06:40:22,777 INFO L290 TraceCheckUtils]: 11: Hoare triple {263#false} assume !false; {263#false} is VALID [2022-04-08 06:40:22,777 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 06:40:22,778 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:22,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [133134397] [2022-04-08 06:40:22,778 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [133134397] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:22,778 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:22,778 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 06:40:22,778 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:22,779 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1158784865] [2022-04-08 06:40:22,779 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1158784865] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:22,779 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:22,779 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 06:40:22,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1059499068] [2022-04-08 06:40:22,779 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:22,780 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-08 06:40:22,780 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:22,781 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:22,793 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 12 edges. 12 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:22,794 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-08 06:40:22,794 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:22,794 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-08 06:40:22,795 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:40:22,795 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:23,206 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-04-08 06:40:23,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-08 06:40:23,207 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-08 06:40:23,208 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:23,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-08 06:40:23,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-08 06:40:23,228 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 56 transitions. [2022-04-08 06:40:23,285 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:23,287 INFO L225 Difference]: With dead ends: 41 [2022-04-08 06:40:23,287 INFO L226 Difference]: Without dead ends: 39 [2022-04-08 06:40:23,288 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-08 06:40:23,289 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:23,290 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 85 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 06:40:23,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-08 06:40:23,297 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-04-08 06:40:23,297 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:23,297 INFO L82 GeneralOperation]: Start isEquivalent. First operand 39 states. Second operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,298 INFO L74 IsIncluded]: Start isIncluded. First operand 39 states. Second operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,298 INFO L87 Difference]: Start difference. First operand 39 states. Second operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:23,301 INFO L93 Difference]: Finished difference Result 39 states and 54 transitions. [2022-04-08 06:40:23,301 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 54 transitions. [2022-04-08 06:40:23,302 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:23,302 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:23,303 INFO L74 IsIncluded]: Start isIncluded. First operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 39 states. [2022-04-08 06:40:23,303 INFO L87 Difference]: Start difference. First operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 39 states. [2022-04-08 06:40:23,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:23,306 INFO L93 Difference]: Finished difference Result 39 states and 54 transitions. [2022-04-08 06:40:23,306 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 54 transitions. [2022-04-08 06:40:23,306 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:23,307 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:23,307 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:23,307 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:23,307 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-08 06:40:23,309 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-04-08 06:40:23,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:23,309 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-08 06:40:23,310 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,310 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 30 states and 39 transitions. [2022-04-08 06:40:23,362 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 39 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:23,362 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-08 06:40:23,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-04-08 06:40:23,363 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:23,363 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:23,363 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-08 06:40:23,363 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:23,364 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:23,364 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 1 times [2022-04-08 06:40:23,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:23,364 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [817714859] [2022-04-08 06:40:23,365 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:23,365 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 2 times [2022-04-08 06:40:23,365 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:23,365 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1863538129] [2022-04-08 06:40:23,365 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:23,366 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:23,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:23,412 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 06:40:23,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:23,425 INFO L290 TraceCheckUtils]: 0: Hoare triple {508#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,425 INFO L290 TraceCheckUtils]: 1: Hoare triple {506#(<= ~counter~0 0)} assume true; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,426 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {506#(<= ~counter~0 0)} {501#true} #92#return; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,427 INFO L272 TraceCheckUtils]: 0: Hoare triple {501#true} call ULTIMATE.init(); {508#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 06:40:23,428 INFO L290 TraceCheckUtils]: 1: Hoare triple {508#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,428 INFO L290 TraceCheckUtils]: 2: Hoare triple {506#(<= ~counter~0 0)} assume true; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,429 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {506#(<= ~counter~0 0)} {501#true} #92#return; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,429 INFO L272 TraceCheckUtils]: 4: Hoare triple {506#(<= ~counter~0 0)} call #t~ret7 := main(); {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,430 INFO L290 TraceCheckUtils]: 5: Hoare triple {506#(<= ~counter~0 0)} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {506#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:23,430 INFO L290 TraceCheckUtils]: 6: Hoare triple {506#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {507#(<= |main_#t~post5| 0)} is VALID [2022-04-08 06:40:23,431 INFO L290 TraceCheckUtils]: 7: Hoare triple {507#(<= |main_#t~post5| 0)} assume !(#t~post5 < 2);havoc #t~post5; {502#false} is VALID [2022-04-08 06:40:23,431 INFO L290 TraceCheckUtils]: 8: Hoare triple {502#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {502#false} is VALID [2022-04-08 06:40:23,431 INFO L290 TraceCheckUtils]: 9: Hoare triple {502#false} assume !(#t~post6 < 2);havoc #t~post6; {502#false} is VALID [2022-04-08 06:40:23,431 INFO L272 TraceCheckUtils]: 10: Hoare triple {502#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {502#false} is VALID [2022-04-08 06:40:23,432 INFO L290 TraceCheckUtils]: 11: Hoare triple {502#false} ~cond := #in~cond; {502#false} is VALID [2022-04-08 06:40:23,432 INFO L290 TraceCheckUtils]: 12: Hoare triple {502#false} assume 0 == ~cond; {502#false} is VALID [2022-04-08 06:40:23,432 INFO L290 TraceCheckUtils]: 13: Hoare triple {502#false} assume !false; {502#false} is VALID [2022-04-08 06:40:23,432 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 06:40:23,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:23,433 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1863538129] [2022-04-08 06:40:23,433 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1863538129] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:23,433 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:23,433 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 06:40:23,434 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:23,434 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [817714859] [2022-04-08 06:40:23,435 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [817714859] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:23,435 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:23,435 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 06:40:23,435 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1641263198] [2022-04-08 06:40:23,435 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:23,436 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-08 06:40:23,436 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:23,436 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,458 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 14 edges. 14 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:23,459 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:40:23,459 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:23,459 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:40:23,459 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:40:23,460 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:23,661 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-04-08 06:40:23,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-08 06:40:23,662 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-08 06:40:23,662 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:23,662 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 58 transitions. [2022-04-08 06:40:23,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 58 transitions. [2022-04-08 06:40:23,666 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 58 transitions. [2022-04-08 06:40:23,731 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 58 edges. 58 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:23,732 INFO L225 Difference]: With dead ends: 46 [2022-04-08 06:40:23,732 INFO L226 Difference]: Without dead ends: 32 [2022-04-08 06:40:23,733 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:40:23,734 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:23,734 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 06:40:23,735 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-08 06:40:23,744 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-08 06:40:23,744 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:23,745 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,745 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,745 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,747 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:23,748 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-08 06:40:23,748 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-08 06:40:23,748 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:23,748 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:23,749 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 32 states. [2022-04-08 06:40:23,749 INFO L87 Difference]: Start difference. First operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 32 states. [2022-04-08 06:40:23,751 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:23,751 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-08 06:40:23,751 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-08 06:40:23,752 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:23,752 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:23,752 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:23,752 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:23,753 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:23,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-08 06:40:23,754 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-04-08 06:40:23,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:23,755 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-08 06:40:23,755 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 06:40:23,755 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 41 transitions. [2022-04-08 06:40:23,794 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 41 edges. 41 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:23,795 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-08 06:40:23,795 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-08 06:40:23,795 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:23,795 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:23,796 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-08 06:40:23,796 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:23,796 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:23,796 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 1 times [2022-04-08 06:40:23,797 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:23,797 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [685982050] [2022-04-08 06:40:23,797 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:23,797 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 2 times [2022-04-08 06:40:23,798 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:23,798 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484198821] [2022-04-08 06:40:23,798 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:23,798 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:23,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:23,849 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 06:40:23,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:23,856 INFO L290 TraceCheckUtils]: 0: Hoare triple {745#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {733#true} is VALID [2022-04-08 06:40:23,857 INFO L290 TraceCheckUtils]: 1: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-08 06:40:23,857 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {733#true} {733#true} #92#return; {733#true} is VALID [2022-04-08 06:40:23,857 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-04-08 06:40:23,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:23,863 INFO L290 TraceCheckUtils]: 0: Hoare triple {733#true} ~cond := #in~cond; {733#true} is VALID [2022-04-08 06:40:23,864 INFO L290 TraceCheckUtils]: 1: Hoare triple {733#true} assume !(0 == ~cond); {733#true} is VALID [2022-04-08 06:40:23,864 INFO L290 TraceCheckUtils]: 2: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-08 06:40:23,865 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {733#true} {738#(= main_~A~0 main_~r~0)} #78#return; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-08 06:40:23,865 INFO L272 TraceCheckUtils]: 0: Hoare triple {733#true} call ULTIMATE.init(); {745#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 06:40:23,866 INFO L290 TraceCheckUtils]: 1: Hoare triple {745#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {733#true} is VALID [2022-04-08 06:40:23,866 INFO L290 TraceCheckUtils]: 2: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-08 06:40:23,866 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {733#true} {733#true} #92#return; {733#true} is VALID [2022-04-08 06:40:23,866 INFO L272 TraceCheckUtils]: 4: Hoare triple {733#true} call #t~ret7 := main(); {733#true} is VALID [2022-04-08 06:40:23,867 INFO L290 TraceCheckUtils]: 5: Hoare triple {733#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-08 06:40:23,867 INFO L290 TraceCheckUtils]: 6: Hoare triple {738#(= main_~A~0 main_~r~0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-08 06:40:23,868 INFO L290 TraceCheckUtils]: 7: Hoare triple {738#(= main_~A~0 main_~r~0)} assume !!(#t~post5 < 2);havoc #t~post5; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-08 06:40:23,868 INFO L272 TraceCheckUtils]: 8: Hoare triple {738#(= main_~A~0 main_~r~0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {733#true} is VALID [2022-04-08 06:40:23,868 INFO L290 TraceCheckUtils]: 9: Hoare triple {733#true} ~cond := #in~cond; {733#true} is VALID [2022-04-08 06:40:23,868 INFO L290 TraceCheckUtils]: 10: Hoare triple {733#true} assume !(0 == ~cond); {733#true} is VALID [2022-04-08 06:40:23,868 INFO L290 TraceCheckUtils]: 11: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-08 06:40:23,869 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {733#true} {738#(= main_~A~0 main_~r~0)} #78#return; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-08 06:40:23,870 INFO L272 TraceCheckUtils]: 13: Hoare triple {738#(= main_~A~0 main_~r~0)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {743#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:40:23,870 INFO L290 TraceCheckUtils]: 14: Hoare triple {743#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {744#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 06:40:23,871 INFO L290 TraceCheckUtils]: 15: Hoare triple {744#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {734#false} is VALID [2022-04-08 06:40:23,871 INFO L290 TraceCheckUtils]: 16: Hoare triple {734#false} assume !false; {734#false} is VALID [2022-04-08 06:40:23,871 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 06:40:23,871 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:23,872 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484198821] [2022-04-08 06:40:23,872 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1484198821] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:23,872 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:23,872 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 06:40:23,872 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:23,872 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [685982050] [2022-04-08 06:40:23,872 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [685982050] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:23,873 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:23,873 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 06:40:23,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [304707992] [2022-04-08 06:40:23,873 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:23,873 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-08 06:40:23,874 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:23,874 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 06:40:23,888 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:23,888 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-08 06:40:23,888 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:23,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-08 06:40:23,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:40:23,889 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 06:40:24,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:24,226 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-08 06:40:24,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-08 06:40:24,227 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-08 06:40:24,228 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:24,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 06:40:24,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-08 06:40:24,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 06:40:24,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-08 06:40:24,234 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 56 transitions. [2022-04-08 06:40:24,280 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:24,283 INFO L225 Difference]: With dead ends: 46 [2022-04-08 06:40:24,283 INFO L226 Difference]: Without dead ends: 44 [2022-04-08 06:40:24,285 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-08 06:40:24,287 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:24,288 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 78 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 06:40:24,289 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-08 06:40:24,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-04-08 06:40:24,307 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:24,308 INFO L82 GeneralOperation]: Start isEquivalent. First operand 44 states. Second operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:24,308 INFO L74 IsIncluded]: Start isIncluded. First operand 44 states. Second operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:24,310 INFO L87 Difference]: Start difference. First operand 44 states. Second operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:24,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:24,313 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-08 06:40:24,313 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2022-04-08 06:40:24,313 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:24,314 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:24,314 INFO L74 IsIncluded]: Start isIncluded. First operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 44 states. [2022-04-08 06:40:24,314 INFO L87 Difference]: Start difference. First operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 44 states. [2022-04-08 06:40:24,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:24,317 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-08 06:40:24,317 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2022-04-08 06:40:24,317 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:24,317 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:24,317 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:24,318 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:24,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:40:24,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-04-08 06:40:24,320 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-04-08 06:40:24,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:24,320 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-04-08 06:40:24,320 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 06:40:24,320 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 36 states and 44 transitions. [2022-04-08 06:40:24,357 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:24,357 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-04-08 06:40:24,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-08 06:40:24,358 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:24,358 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:24,358 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-08 06:40:24,358 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:24,359 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:24,359 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 1 times [2022-04-08 06:40:24,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:24,359 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1594600865] [2022-04-08 06:40:24,360 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:24,360 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 2 times [2022-04-08 06:40:24,360 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:24,360 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154872619] [2022-04-08 06:40:24,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:24,361 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:24,372 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:40:24,373 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1052028750] [2022-04-08 06:40:24,373 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:40:24,373 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:24,373 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:24,375 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:40:24,397 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-08 06:40:24,429 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:40:24,430 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:40:24,432 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-08 06:40:24,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:24,460 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:40:24,677 INFO L272 TraceCheckUtils]: 0: Hoare triple {1008#true} call ULTIMATE.init(); {1008#true} is VALID [2022-04-08 06:40:24,677 INFO L290 TraceCheckUtils]: 1: Hoare triple {1008#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1008#true} is VALID [2022-04-08 06:40:24,677 INFO L290 TraceCheckUtils]: 2: Hoare triple {1008#true} assume true; {1008#true} is VALID [2022-04-08 06:40:24,678 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1008#true} {1008#true} #92#return; {1008#true} is VALID [2022-04-08 06:40:24,678 INFO L272 TraceCheckUtils]: 4: Hoare triple {1008#true} call #t~ret7 := main(); {1008#true} is VALID [2022-04-08 06:40:24,678 INFO L290 TraceCheckUtils]: 5: Hoare triple {1008#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:24,679 INFO L290 TraceCheckUtils]: 6: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:24,683 INFO L290 TraceCheckUtils]: 7: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !!(#t~post5 < 2);havoc #t~post5; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:24,684 INFO L272 TraceCheckUtils]: 8: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1008#true} is VALID [2022-04-08 06:40:24,684 INFO L290 TraceCheckUtils]: 9: Hoare triple {1008#true} ~cond := #in~cond; {1008#true} is VALID [2022-04-08 06:40:24,684 INFO L290 TraceCheckUtils]: 10: Hoare triple {1008#true} assume !(0 == ~cond); {1008#true} is VALID [2022-04-08 06:40:24,684 INFO L290 TraceCheckUtils]: 11: Hoare triple {1008#true} assume true; {1008#true} is VALID [2022-04-08 06:40:24,685 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1008#true} {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #78#return; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:24,685 INFO L272 TraceCheckUtils]: 13: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {1008#true} is VALID [2022-04-08 06:40:24,685 INFO L290 TraceCheckUtils]: 14: Hoare triple {1008#true} ~cond := #in~cond; {1008#true} is VALID [2022-04-08 06:40:24,685 INFO L290 TraceCheckUtils]: 15: Hoare triple {1008#true} assume !(0 == ~cond); {1008#true} is VALID [2022-04-08 06:40:24,685 INFO L290 TraceCheckUtils]: 16: Hoare triple {1008#true} assume true; {1008#true} is VALID [2022-04-08 06:40:24,686 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1008#true} {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #80#return; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:24,687 INFO L272 TraceCheckUtils]: 18: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {1068#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:40:24,687 INFO L290 TraceCheckUtils]: 19: Hoare triple {1068#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1072#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:40:24,688 INFO L290 TraceCheckUtils]: 20: Hoare triple {1072#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1009#false} is VALID [2022-04-08 06:40:24,688 INFO L290 TraceCheckUtils]: 21: Hoare triple {1009#false} assume !false; {1009#false} is VALID [2022-04-08 06:40:24,688 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-08 06:40:24,689 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 06:40:24,689 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:24,689 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [154872619] [2022-04-08 06:40:24,689 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:40:24,689 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1052028750] [2022-04-08 06:40:24,689 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1052028750] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:24,689 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:24,689 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:24,690 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:24,690 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1594600865] [2022-04-08 06:40:24,690 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1594600865] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:24,690 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:24,690 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:24,691 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [238187997] [2022-04-08 06:40:24,691 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:24,691 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-08 06:40:24,696 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:24,696 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 06:40:24,711 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 19 edges. 19 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:24,711 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:40:24,713 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:24,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:40:24,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:40:24,715 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 06:40:24,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:24,891 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-08 06:40:24,891 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 06:40:24,892 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-08 06:40:24,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:24,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 06:40:24,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 81 transitions. [2022-04-08 06:40:24,894 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 06:40:24,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 81 transitions. [2022-04-08 06:40:24,896 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 81 transitions. [2022-04-08 06:40:24,958 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 81 edges. 81 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:24,960 INFO L225 Difference]: With dead ends: 65 [2022-04-08 06:40:24,960 INFO L226 Difference]: Without dead ends: 50 [2022-04-08 06:40:24,961 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:40:24,961 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:24,961 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 06:40:24,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-08 06:40:24,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-08 06:40:24,983 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:24,984 INFO L82 GeneralOperation]: Start isEquivalent. First operand 50 states. Second operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:24,984 INFO L74 IsIncluded]: Start isIncluded. First operand 50 states. Second operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:24,984 INFO L87 Difference]: Start difference. First operand 50 states. Second operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:24,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:24,987 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-04-08 06:40:24,987 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-08 06:40:24,987 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:24,987 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:24,988 INFO L74 IsIncluded]: Start isIncluded. First operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 50 states. [2022-04-08 06:40:24,988 INFO L87 Difference]: Start difference. First operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 50 states. [2022-04-08 06:40:24,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:24,991 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-04-08 06:40:24,991 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-08 06:40:24,991 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:24,991 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:24,991 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:24,991 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:24,992 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:24,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-04-08 06:40:24,994 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-04-08 06:40:24,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:24,994 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-04-08 06:40:24,994 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 06:40:24,994 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 50 states and 64 transitions. [2022-04-08 06:40:25,050 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:25,051 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-08 06:40:25,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-08 06:40:25,052 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:25,052 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:25,080 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-08 06:40:25,265 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:25,265 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:25,266 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:25,266 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 1 times [2022-04-08 06:40:25,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:25,266 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2146163359] [2022-04-08 06:40:25,267 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:25,267 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 2 times [2022-04-08 06:40:25,267 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:25,267 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [525438108] [2022-04-08 06:40:25,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:25,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:25,283 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:40:25,283 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [196449071] [2022-04-08 06:40:25,283 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:40:25,283 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:25,284 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:25,296 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:40:25,312 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-08 06:40:25,373 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:40:25,374 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:40:25,375 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 06:40:25,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:25,386 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:40:25,603 INFO L272 TraceCheckUtils]: 0: Hoare triple {1410#true} call ULTIMATE.init(); {1410#true} is VALID [2022-04-08 06:40:25,604 INFO L290 TraceCheckUtils]: 1: Hoare triple {1410#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1418#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:25,605 INFO L290 TraceCheckUtils]: 2: Hoare triple {1418#(<= ~counter~0 0)} assume true; {1418#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:25,605 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1418#(<= ~counter~0 0)} {1410#true} #92#return; {1418#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:25,606 INFO L272 TraceCheckUtils]: 4: Hoare triple {1418#(<= ~counter~0 0)} call #t~ret7 := main(); {1418#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:25,606 INFO L290 TraceCheckUtils]: 5: Hoare triple {1418#(<= ~counter~0 0)} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1418#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:25,607 INFO L290 TraceCheckUtils]: 6: Hoare triple {1418#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,607 INFO L290 TraceCheckUtils]: 7: Hoare triple {1434#(<= ~counter~0 1)} assume !!(#t~post5 < 2);havoc #t~post5; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,610 INFO L272 TraceCheckUtils]: 8: Hoare triple {1434#(<= ~counter~0 1)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,610 INFO L290 TraceCheckUtils]: 9: Hoare triple {1434#(<= ~counter~0 1)} ~cond := #in~cond; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,611 INFO L290 TraceCheckUtils]: 10: Hoare triple {1434#(<= ~counter~0 1)} assume !(0 == ~cond); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,611 INFO L290 TraceCheckUtils]: 11: Hoare triple {1434#(<= ~counter~0 1)} assume true; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,612 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1434#(<= ~counter~0 1)} {1434#(<= ~counter~0 1)} #78#return; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,613 INFO L272 TraceCheckUtils]: 13: Hoare triple {1434#(<= ~counter~0 1)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,613 INFO L290 TraceCheckUtils]: 14: Hoare triple {1434#(<= ~counter~0 1)} ~cond := #in~cond; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,613 INFO L290 TraceCheckUtils]: 15: Hoare triple {1434#(<= ~counter~0 1)} assume !(0 == ~cond); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,614 INFO L290 TraceCheckUtils]: 16: Hoare triple {1434#(<= ~counter~0 1)} assume true; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,614 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1434#(<= ~counter~0 1)} {1434#(<= ~counter~0 1)} #80#return; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,615 INFO L272 TraceCheckUtils]: 18: Hoare triple {1434#(<= ~counter~0 1)} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,616 INFO L290 TraceCheckUtils]: 19: Hoare triple {1434#(<= ~counter~0 1)} ~cond := #in~cond; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,616 INFO L290 TraceCheckUtils]: 20: Hoare triple {1434#(<= ~counter~0 1)} assume !(0 == ~cond); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,617 INFO L290 TraceCheckUtils]: 21: Hoare triple {1434#(<= ~counter~0 1)} assume true; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,618 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1434#(<= ~counter~0 1)} {1434#(<= ~counter~0 1)} #82#return; {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,618 INFO L290 TraceCheckUtils]: 23: Hoare triple {1434#(<= ~counter~0 1)} assume !(~r~0 >= ~d~0); {1434#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:25,620 INFO L290 TraceCheckUtils]: 24: Hoare triple {1434#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1489#(<= |main_#t~post6| 1)} is VALID [2022-04-08 06:40:25,621 INFO L290 TraceCheckUtils]: 25: Hoare triple {1489#(<= |main_#t~post6| 1)} assume !(#t~post6 < 2);havoc #t~post6; {1411#false} is VALID [2022-04-08 06:40:25,629 INFO L272 TraceCheckUtils]: 26: Hoare triple {1411#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {1411#false} is VALID [2022-04-08 06:40:25,630 INFO L290 TraceCheckUtils]: 27: Hoare triple {1411#false} ~cond := #in~cond; {1411#false} is VALID [2022-04-08 06:40:25,630 INFO L290 TraceCheckUtils]: 28: Hoare triple {1411#false} assume 0 == ~cond; {1411#false} is VALID [2022-04-08 06:40:25,630 INFO L290 TraceCheckUtils]: 29: Hoare triple {1411#false} assume !false; {1411#false} is VALID [2022-04-08 06:40:25,630 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 06:40:25,631 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 06:40:25,631 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:25,631 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [525438108] [2022-04-08 06:40:25,631 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:40:25,631 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [196449071] [2022-04-08 06:40:25,631 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [196449071] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:25,631 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:25,632 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:25,632 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:25,632 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2146163359] [2022-04-08 06:40:25,632 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2146163359] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:25,632 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:25,632 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:25,632 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1135971555] [2022-04-08 06:40:25,632 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:25,633 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-08 06:40:25,633 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:25,633 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:25,653 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 24 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:25,654 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:40:25,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:25,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:40:25,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:40:25,656 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:25,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:25,798 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-04-08 06:40:25,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 06:40:25,798 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-08 06:40:25,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:25,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:25,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 59 transitions. [2022-04-08 06:40:25,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:25,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 59 transitions. [2022-04-08 06:40:25,801 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 59 transitions. [2022-04-08 06:40:25,841 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 59 edges. 59 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:25,843 INFO L225 Difference]: With dead ends: 70 [2022-04-08 06:40:25,843 INFO L226 Difference]: Without dead ends: 63 [2022-04-08 06:40:25,844 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:40:25,844 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:25,845 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 105 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 06:40:25,845 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-08 06:40:25,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-04-08 06:40:25,872 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:25,872 INFO L82 GeneralOperation]: Start isEquivalent. First operand 63 states. Second operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:25,873 INFO L74 IsIncluded]: Start isIncluded. First operand 63 states. Second operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:25,873 INFO L87 Difference]: Start difference. First operand 63 states. Second operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:25,875 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:25,875 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2022-04-08 06:40:25,875 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2022-04-08 06:40:25,876 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:25,876 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:25,876 INFO L74 IsIncluded]: Start isIncluded. First operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 63 states. [2022-04-08 06:40:25,876 INFO L87 Difference]: Start difference. First operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 63 states. [2022-04-08 06:40:25,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:25,878 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2022-04-08 06:40:25,879 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2022-04-08 06:40:25,879 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:25,879 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:25,879 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:25,879 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:25,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 06:40:25,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-04-08 06:40:25,882 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-04-08 06:40:25,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:25,882 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-04-08 06:40:25,882 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:25,882 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 62 states and 72 transitions. [2022-04-08 06:40:25,978 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 72 edges. 72 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:25,979 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-04-08 06:40:25,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-08 06:40:25,979 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:25,979 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:26,008 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-08 06:40:26,195 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-04-08 06:40:26,196 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:26,196 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:26,196 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 1 times [2022-04-08 06:40:26,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:26,196 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2090508752] [2022-04-08 06:40:26,197 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:40:26,197 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 2 times [2022-04-08 06:40:26,197 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:26,197 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2063089340] [2022-04-08 06:40:26,197 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:26,198 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:26,209 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:40:26,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [560700247] [2022-04-08 06:40:26,209 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:40:26,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:26,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:26,211 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:40:26,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-08 06:40:26,261 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:40:26,261 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:40:26,262 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 06:40:26,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:26,279 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:40:26,428 INFO L272 TraceCheckUtils]: 0: Hoare triple {1894#true} call ULTIMATE.init(); {1894#true} is VALID [2022-04-08 06:40:26,428 INFO L290 TraceCheckUtils]: 1: Hoare triple {1894#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1894#true} is VALID [2022-04-08 06:40:26,428 INFO L290 TraceCheckUtils]: 2: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-08 06:40:26,428 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1894#true} {1894#true} #92#return; {1894#true} is VALID [2022-04-08 06:40:26,428 INFO L272 TraceCheckUtils]: 4: Hoare triple {1894#true} call #t~ret7 := main(); {1894#true} is VALID [2022-04-08 06:40:26,429 INFO L290 TraceCheckUtils]: 5: Hoare triple {1894#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,430 INFO L290 TraceCheckUtils]: 6: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,430 INFO L290 TraceCheckUtils]: 7: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} assume !!(#t~post5 < 2);havoc #t~post5; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,430 INFO L272 TraceCheckUtils]: 8: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1894#true} is VALID [2022-04-08 06:40:26,430 INFO L290 TraceCheckUtils]: 9: Hoare triple {1894#true} ~cond := #in~cond; {1894#true} is VALID [2022-04-08 06:40:26,430 INFO L290 TraceCheckUtils]: 10: Hoare triple {1894#true} assume !(0 == ~cond); {1894#true} is VALID [2022-04-08 06:40:26,431 INFO L290 TraceCheckUtils]: 11: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-08 06:40:26,431 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1894#true} {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #78#return; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,431 INFO L272 TraceCheckUtils]: 13: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {1894#true} is VALID [2022-04-08 06:40:26,432 INFO L290 TraceCheckUtils]: 14: Hoare triple {1894#true} ~cond := #in~cond; {1894#true} is VALID [2022-04-08 06:40:26,432 INFO L290 TraceCheckUtils]: 15: Hoare triple {1894#true} assume !(0 == ~cond); {1894#true} is VALID [2022-04-08 06:40:26,432 INFO L290 TraceCheckUtils]: 16: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-08 06:40:26,432 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1894#true} {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #80#return; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,433 INFO L272 TraceCheckUtils]: 18: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {1894#true} is VALID [2022-04-08 06:40:26,433 INFO L290 TraceCheckUtils]: 19: Hoare triple {1894#true} ~cond := #in~cond; {1894#true} is VALID [2022-04-08 06:40:26,433 INFO L290 TraceCheckUtils]: 20: Hoare triple {1894#true} assume !(0 == ~cond); {1894#true} is VALID [2022-04-08 06:40:26,433 INFO L290 TraceCheckUtils]: 21: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-08 06:40:26,434 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1894#true} {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #82#return; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,434 INFO L290 TraceCheckUtils]: 23: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} assume !(~r~0 >= ~d~0); {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,435 INFO L290 TraceCheckUtils]: 24: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,435 INFO L290 TraceCheckUtils]: 25: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} assume !!(#t~post6 < 2);havoc #t~post6; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-08 06:40:26,436 INFO L272 TraceCheckUtils]: 26: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~A~0 == ~q~0 * ~B~0 + ~r~0 then 1 else 0)); {1978#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:40:26,436 INFO L290 TraceCheckUtils]: 27: Hoare triple {1978#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1982#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:40:26,437 INFO L290 TraceCheckUtils]: 28: Hoare triple {1982#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1895#false} is VALID [2022-04-08 06:40:26,437 INFO L290 TraceCheckUtils]: 29: Hoare triple {1895#false} assume !false; {1895#false} is VALID [2022-04-08 06:40:26,437 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 06:40:26,437 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 06:40:26,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:26,437 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2063089340] [2022-04-08 06:40:26,438 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:40:26,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [560700247] [2022-04-08 06:40:26,438 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [560700247] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:26,438 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:26,438 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:26,438 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:26,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2090508752] [2022-04-08 06:40:26,438 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2090508752] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:26,439 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:26,439 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:26,439 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [500646948] [2022-04-08 06:40:26,439 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:26,439 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-08 06:40:26,439 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:26,440 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:26,456 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 24 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:26,457 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:40:26,457 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:26,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:40:26,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:40:26,458 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:26,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:26,664 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-04-08 06:40:26,664 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 06:40:26,665 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-08 06:40:26,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:26,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:26,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 55 transitions. [2022-04-08 06:40:26,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:26,669 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 55 transitions. [2022-04-08 06:40:26,669 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 55 transitions. [2022-04-08 06:40:26,715 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 55 edges. 55 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:26,718 INFO L225 Difference]: With dead ends: 76 [2022-04-08 06:40:26,719 INFO L226 Difference]: Without dead ends: 64 [2022-04-08 06:40:26,719 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:40:26,720 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:26,720 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 95 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 06:40:26,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-08 06:40:26,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-04-08 06:40:26,768 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:26,769 INFO L82 GeneralOperation]: Start isEquivalent. First operand 64 states. Second operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:26,769 INFO L74 IsIncluded]: Start isIncluded. First operand 64 states. Second operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:26,769 INFO L87 Difference]: Start difference. First operand 64 states. Second operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:26,772 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:26,772 INFO L93 Difference]: Finished difference Result 64 states and 77 transitions. [2022-04-08 06:40:26,772 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-04-08 06:40:26,772 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:26,772 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:26,773 INFO L74 IsIncluded]: Start isIncluded. First operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 64 states. [2022-04-08 06:40:26,773 INFO L87 Difference]: Start difference. First operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 64 states. [2022-04-08 06:40:26,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:26,775 INFO L93 Difference]: Finished difference Result 64 states and 77 transitions. [2022-04-08 06:40:26,775 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-04-08 06:40:26,775 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:26,776 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:26,776 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:26,776 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:26,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:26,778 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-04-08 06:40:26,778 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-04-08 06:40:26,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:26,778 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-04-08 06:40:26,779 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:26,779 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 63 states and 76 transitions. [2022-04-08 06:40:26,848 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 76 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:26,849 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-04-08 06:40:26,849 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-08 06:40:26,850 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:26,850 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:26,869 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-08 06:40:27,059 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:27,060 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:27,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:27,060 INFO L85 PathProgramCache]: Analyzing trace with hash -1255015940, now seen corresponding path program 1 times [2022-04-08 06:40:27,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:27,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1624120574] [2022-04-08 06:40:29,285 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 3 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-08 06:40:29,286 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-04-08 06:40:29,286 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 06:40:29,286 INFO L85 PathProgramCache]: Analyzing trace with hash -1255015940, now seen corresponding path program 2 times [2022-04-08 06:40:29,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:29,286 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [428278383] [2022-04-08 06:40:29,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:29,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:29,303 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:40:29,304 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2019149284] [2022-04-08 06:40:29,304 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:40:29,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:29,304 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:29,305 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:40:29,332 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-08 06:40:29,356 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:40:29,357 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:40:29,357 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 06:40:29,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:29,375 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:40:29,566 INFO L272 TraceCheckUtils]: 0: Hoare triple {2396#true} call ULTIMATE.init(); {2396#true} is VALID [2022-04-08 06:40:29,567 INFO L290 TraceCheckUtils]: 1: Hoare triple {2396#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,568 INFO L290 TraceCheckUtils]: 2: Hoare triple {2404#(<= ~counter~0 0)} assume true; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,568 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2404#(<= ~counter~0 0)} {2396#true} #92#return; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,569 INFO L272 TraceCheckUtils]: 4: Hoare triple {2404#(<= ~counter~0 0)} call #t~ret7 := main(); {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,569 INFO L290 TraceCheckUtils]: 5: Hoare triple {2404#(<= ~counter~0 0)} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,570 INFO L290 TraceCheckUtils]: 6: Hoare triple {2404#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,570 INFO L290 TraceCheckUtils]: 7: Hoare triple {2420#(<= ~counter~0 1)} assume !!(#t~post5 < 2);havoc #t~post5; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,570 INFO L272 TraceCheckUtils]: 8: Hoare triple {2420#(<= ~counter~0 1)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,571 INFO L290 TraceCheckUtils]: 9: Hoare triple {2420#(<= ~counter~0 1)} ~cond := #in~cond; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,571 INFO L290 TraceCheckUtils]: 10: Hoare triple {2420#(<= ~counter~0 1)} assume !(0 == ~cond); {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,572 INFO L290 TraceCheckUtils]: 11: Hoare triple {2420#(<= ~counter~0 1)} assume true; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,572 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {2420#(<= ~counter~0 1)} {2420#(<= ~counter~0 1)} #78#return; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,573 INFO L272 TraceCheckUtils]: 13: Hoare triple {2420#(<= ~counter~0 1)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,573 INFO L290 TraceCheckUtils]: 14: Hoare triple {2420#(<= ~counter~0 1)} ~cond := #in~cond; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,573 INFO L290 TraceCheckUtils]: 15: Hoare triple {2420#(<= ~counter~0 1)} assume !(0 == ~cond); {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,574 INFO L290 TraceCheckUtils]: 16: Hoare triple {2420#(<= ~counter~0 1)} assume true; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,574 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {2420#(<= ~counter~0 1)} {2420#(<= ~counter~0 1)} #80#return; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,575 INFO L272 TraceCheckUtils]: 18: Hoare triple {2420#(<= ~counter~0 1)} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,575 INFO L290 TraceCheckUtils]: 19: Hoare triple {2420#(<= ~counter~0 1)} ~cond := #in~cond; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,575 INFO L290 TraceCheckUtils]: 20: Hoare triple {2420#(<= ~counter~0 1)} assume !(0 == ~cond); {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,576 INFO L290 TraceCheckUtils]: 21: Hoare triple {2420#(<= ~counter~0 1)} assume true; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,576 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {2420#(<= ~counter~0 1)} {2420#(<= ~counter~0 1)} #82#return; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,577 INFO L290 TraceCheckUtils]: 23: Hoare triple {2420#(<= ~counter~0 1)} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,577 INFO L290 TraceCheckUtils]: 24: Hoare triple {2420#(<= ~counter~0 1)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2475#(<= |main_#t~post5| 1)} is VALID [2022-04-08 06:40:29,578 INFO L290 TraceCheckUtils]: 25: Hoare triple {2475#(<= |main_#t~post5| 1)} assume !(#t~post5 < 2);havoc #t~post5; {2397#false} is VALID [2022-04-08 06:40:29,578 INFO L290 TraceCheckUtils]: 26: Hoare triple {2397#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2397#false} is VALID [2022-04-08 06:40:29,578 INFO L290 TraceCheckUtils]: 27: Hoare triple {2397#false} assume !(#t~post6 < 2);havoc #t~post6; {2397#false} is VALID [2022-04-08 06:40:29,578 INFO L272 TraceCheckUtils]: 28: Hoare triple {2397#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {2397#false} is VALID [2022-04-08 06:40:29,578 INFO L290 TraceCheckUtils]: 29: Hoare triple {2397#false} ~cond := #in~cond; {2397#false} is VALID [2022-04-08 06:40:29,578 INFO L290 TraceCheckUtils]: 30: Hoare triple {2397#false} assume !(0 == ~cond); {2397#false} is VALID [2022-04-08 06:40:29,579 INFO L290 TraceCheckUtils]: 31: Hoare triple {2397#false} assume true; {2397#false} is VALID [2022-04-08 06:40:29,579 INFO L284 TraceCheckUtils]: 32: Hoare quadruple {2397#false} {2397#false} #88#return; {2397#false} is VALID [2022-04-08 06:40:29,579 INFO L272 TraceCheckUtils]: 33: Hoare triple {2397#false} call __VERIFIER_assert((if ~B~0 == ~d~0 then 1 else 0)); {2397#false} is VALID [2022-04-08 06:40:29,579 INFO L290 TraceCheckUtils]: 34: Hoare triple {2397#false} ~cond := #in~cond; {2397#false} is VALID [2022-04-08 06:40:29,579 INFO L290 TraceCheckUtils]: 35: Hoare triple {2397#false} assume 0 == ~cond; {2397#false} is VALID [2022-04-08 06:40:29,579 INFO L290 TraceCheckUtils]: 36: Hoare triple {2397#false} assume !false; {2397#false} is VALID [2022-04-08 06:40:29,580 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-04-08 06:40:29,580 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 06:40:29,760 INFO L290 TraceCheckUtils]: 36: Hoare triple {2397#false} assume !false; {2397#false} is VALID [2022-04-08 06:40:29,761 INFO L290 TraceCheckUtils]: 35: Hoare triple {2397#false} assume 0 == ~cond; {2397#false} is VALID [2022-04-08 06:40:29,761 INFO L290 TraceCheckUtils]: 34: Hoare triple {2397#false} ~cond := #in~cond; {2397#false} is VALID [2022-04-08 06:40:29,761 INFO L272 TraceCheckUtils]: 33: Hoare triple {2397#false} call __VERIFIER_assert((if ~B~0 == ~d~0 then 1 else 0)); {2397#false} is VALID [2022-04-08 06:40:29,761 INFO L284 TraceCheckUtils]: 32: Hoare quadruple {2396#true} {2397#false} #88#return; {2397#false} is VALID [2022-04-08 06:40:29,761 INFO L290 TraceCheckUtils]: 31: Hoare triple {2396#true} assume true; {2396#true} is VALID [2022-04-08 06:40:29,762 INFO L290 TraceCheckUtils]: 30: Hoare triple {2396#true} assume !(0 == ~cond); {2396#true} is VALID [2022-04-08 06:40:29,762 INFO L290 TraceCheckUtils]: 29: Hoare triple {2396#true} ~cond := #in~cond; {2396#true} is VALID [2022-04-08 06:40:29,762 INFO L272 TraceCheckUtils]: 28: Hoare triple {2397#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {2396#true} is VALID [2022-04-08 06:40:29,762 INFO L290 TraceCheckUtils]: 27: Hoare triple {2397#false} assume !(#t~post6 < 2);havoc #t~post6; {2397#false} is VALID [2022-04-08 06:40:29,762 INFO L290 TraceCheckUtils]: 26: Hoare triple {2397#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2397#false} is VALID [2022-04-08 06:40:29,768 INFO L290 TraceCheckUtils]: 25: Hoare triple {2475#(<= |main_#t~post5| 1)} assume !(#t~post5 < 2);havoc #t~post5; {2397#false} is VALID [2022-04-08 06:40:29,768 INFO L290 TraceCheckUtils]: 24: Hoare triple {2420#(<= ~counter~0 1)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2475#(<= |main_#t~post5| 1)} is VALID [2022-04-08 06:40:29,769 INFO L290 TraceCheckUtils]: 23: Hoare triple {2420#(<= ~counter~0 1)} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,769 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {2396#true} {2420#(<= ~counter~0 1)} #82#return; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,769 INFO L290 TraceCheckUtils]: 21: Hoare triple {2396#true} assume true; {2396#true} is VALID [2022-04-08 06:40:29,770 INFO L290 TraceCheckUtils]: 20: Hoare triple {2396#true} assume !(0 == ~cond); {2396#true} is VALID [2022-04-08 06:40:29,770 INFO L290 TraceCheckUtils]: 19: Hoare triple {2396#true} ~cond := #in~cond; {2396#true} is VALID [2022-04-08 06:40:29,770 INFO L272 TraceCheckUtils]: 18: Hoare triple {2420#(<= ~counter~0 1)} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {2396#true} is VALID [2022-04-08 06:40:29,772 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {2396#true} {2420#(<= ~counter~0 1)} #80#return; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,772 INFO L290 TraceCheckUtils]: 16: Hoare triple {2396#true} assume true; {2396#true} is VALID [2022-04-08 06:40:29,772 INFO L290 TraceCheckUtils]: 15: Hoare triple {2396#true} assume !(0 == ~cond); {2396#true} is VALID [2022-04-08 06:40:29,772 INFO L290 TraceCheckUtils]: 14: Hoare triple {2396#true} ~cond := #in~cond; {2396#true} is VALID [2022-04-08 06:40:29,772 INFO L272 TraceCheckUtils]: 13: Hoare triple {2420#(<= ~counter~0 1)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {2396#true} is VALID [2022-04-08 06:40:29,773 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {2396#true} {2420#(<= ~counter~0 1)} #78#return; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,773 INFO L290 TraceCheckUtils]: 11: Hoare triple {2396#true} assume true; {2396#true} is VALID [2022-04-08 06:40:29,773 INFO L290 TraceCheckUtils]: 10: Hoare triple {2396#true} assume !(0 == ~cond); {2396#true} is VALID [2022-04-08 06:40:29,773 INFO L290 TraceCheckUtils]: 9: Hoare triple {2396#true} ~cond := #in~cond; {2396#true} is VALID [2022-04-08 06:40:29,774 INFO L272 TraceCheckUtils]: 8: Hoare triple {2420#(<= ~counter~0 1)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {2396#true} is VALID [2022-04-08 06:40:29,774 INFO L290 TraceCheckUtils]: 7: Hoare triple {2420#(<= ~counter~0 1)} assume !!(#t~post5 < 2);havoc #t~post5; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,775 INFO L290 TraceCheckUtils]: 6: Hoare triple {2404#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2420#(<= ~counter~0 1)} is VALID [2022-04-08 06:40:29,775 INFO L290 TraceCheckUtils]: 5: Hoare triple {2404#(<= ~counter~0 0)} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,775 INFO L272 TraceCheckUtils]: 4: Hoare triple {2404#(<= ~counter~0 0)} call #t~ret7 := main(); {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,776 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2404#(<= ~counter~0 0)} {2396#true} #92#return; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,776 INFO L290 TraceCheckUtils]: 2: Hoare triple {2404#(<= ~counter~0 0)} assume true; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,777 INFO L290 TraceCheckUtils]: 1: Hoare triple {2396#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2404#(<= ~counter~0 0)} is VALID [2022-04-08 06:40:29,777 INFO L272 TraceCheckUtils]: 0: Hoare triple {2396#true} call ULTIMATE.init(); {2396#true} is VALID [2022-04-08 06:40:29,777 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-08 06:40:29,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:29,777 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [428278383] [2022-04-08 06:40:29,778 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:40:29,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2019149284] [2022-04-08 06:40:29,778 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2019149284] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 06:40:29,779 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 06:40:29,779 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2022-04-08 06:40:29,779 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:29,779 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1624120574] [2022-04-08 06:40:29,779 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1624120574] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:29,779 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:29,780 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:29,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1522300501] [2022-04-08 06:40:29,780 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:29,780 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 37 [2022-04-08 06:40:29,780 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:29,780 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 06:40:29,801 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:29,801 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:40:29,801 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:29,802 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:40:29,802 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:40:29,802 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 06:40:29,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:29,968 INFO L93 Difference]: Finished difference Result 90 states and 114 transitions. [2022-04-08 06:40:29,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-08 06:40:29,969 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 37 [2022-04-08 06:40:29,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:29,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 06:40:29,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 70 transitions. [2022-04-08 06:40:29,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 06:40:29,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 70 transitions. [2022-04-08 06:40:29,972 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 70 transitions. [2022-04-08 06:40:30,032 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 70 edges. 70 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:30,034 INFO L225 Difference]: With dead ends: 90 [2022-04-08 06:40:30,034 INFO L226 Difference]: Without dead ends: 65 [2022-04-08 06:40:30,038 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:40:30,038 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 2 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:30,038 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 126 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 06:40:30,039 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-04-08 06:40:30,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2022-04-08 06:40:30,083 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:30,083 INFO L82 GeneralOperation]: Start isEquivalent. First operand 65 states. Second operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:30,083 INFO L74 IsIncluded]: Start isIncluded. First operand 65 states. Second operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:30,084 INFO L87 Difference]: Start difference. First operand 65 states. Second operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:30,088 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:30,088 INFO L93 Difference]: Finished difference Result 65 states and 78 transitions. [2022-04-08 06:40:30,088 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 78 transitions. [2022-04-08 06:40:30,088 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:30,089 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:30,089 INFO L74 IsIncluded]: Start isIncluded. First operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 65 states. [2022-04-08 06:40:30,089 INFO L87 Difference]: Start difference. First operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 65 states. [2022-04-08 06:40:30,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:30,091 INFO L93 Difference]: Finished difference Result 65 states and 78 transitions. [2022-04-08 06:40:30,091 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 78 transitions. [2022-04-08 06:40:30,092 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:30,092 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:30,092 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:30,092 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:30,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-08 06:40:30,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 78 transitions. [2022-04-08 06:40:30,094 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 78 transitions. Word has length 37 [2022-04-08 06:40:30,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:30,095 INFO L478 AbstractCegarLoop]: Abstraction has 65 states and 78 transitions. [2022-04-08 06:40:30,095 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 06:40:30,095 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 65 states and 78 transitions. [2022-04-08 06:40:30,168 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 78 edges. 78 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:30,168 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 78 transitions. [2022-04-08 06:40:30,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-08 06:40:30,169 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:30,169 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:30,207 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-08 06:40:30,397 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:30,398 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:30,398 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:30,398 INFO L85 PathProgramCache]: Analyzing trace with hash -1057559728, now seen corresponding path program 1 times [2022-04-08 06:40:30,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:30,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [509184440] [2022-04-08 06:40:34,535 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 3 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-08 06:40:34,535 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-04-08 06:40:34,536 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 06:40:34,536 INFO L85 PathProgramCache]: Analyzing trace with hash -1057559728, now seen corresponding path program 2 times [2022-04-08 06:40:34,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:34,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [549883575] [2022-04-08 06:40:34,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:34,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:34,546 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:40:34,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [630412582] [2022-04-08 06:40:34,546 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:40:34,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:34,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:34,559 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:40:34,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-08 06:40:34,616 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:40:34,616 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:40:34,617 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-08 06:40:34,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:40:34,630 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:40:34,860 INFO L272 TraceCheckUtils]: 0: Hoare triple {3064#true} call ULTIMATE.init(); {3064#true} is VALID [2022-04-08 06:40:34,860 INFO L290 TraceCheckUtils]: 1: Hoare triple {3064#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3064#true} is VALID [2022-04-08 06:40:34,861 INFO L290 TraceCheckUtils]: 2: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:34,861 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3064#true} {3064#true} #92#return; {3064#true} is VALID [2022-04-08 06:40:34,861 INFO L272 TraceCheckUtils]: 4: Hoare triple {3064#true} call #t~ret7 := main(); {3064#true} is VALID [2022-04-08 06:40:34,862 INFO L290 TraceCheckUtils]: 5: Hoare triple {3064#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:34,862 INFO L290 TraceCheckUtils]: 6: Hoare triple {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:34,863 INFO L290 TraceCheckUtils]: 7: Hoare triple {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !!(#t~post5 < 2);havoc #t~post5; {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:34,863 INFO L272 TraceCheckUtils]: 8: Hoare triple {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:34,863 INFO L290 TraceCheckUtils]: 9: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:34,863 INFO L290 TraceCheckUtils]: 10: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:34,863 INFO L290 TraceCheckUtils]: 11: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:34,864 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {3064#true} {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #78#return; {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:34,864 INFO L272 TraceCheckUtils]: 13: Hoare triple {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:34,864 INFO L290 TraceCheckUtils]: 14: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:34,864 INFO L290 TraceCheckUtils]: 15: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:34,864 INFO L290 TraceCheckUtils]: 16: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:34,865 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {3064#true} {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #80#return; {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:34,865 INFO L272 TraceCheckUtils]: 18: Hoare triple {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:34,865 INFO L290 TraceCheckUtils]: 19: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:34,866 INFO L290 TraceCheckUtils]: 20: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:34,866 INFO L290 TraceCheckUtils]: 21: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:34,866 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {3064#true} {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #82#return; {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-08 06:40:34,867 INFO L290 TraceCheckUtils]: 23: Hoare triple {3084#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} is VALID [2022-04-08 06:40:34,868 INFO L290 TraceCheckUtils]: 24: Hoare triple {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} is VALID [2022-04-08 06:40:34,868 INFO L290 TraceCheckUtils]: 25: Hoare triple {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} assume !!(#t~post5 < 2);havoc #t~post5; {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} is VALID [2022-04-08 06:40:34,868 INFO L272 TraceCheckUtils]: 26: Hoare triple {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:34,868 INFO L290 TraceCheckUtils]: 27: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:34,868 INFO L290 TraceCheckUtils]: 28: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:34,869 INFO L290 TraceCheckUtils]: 29: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:34,869 INFO L284 TraceCheckUtils]: 30: Hoare quadruple {3064#true} {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} #78#return; {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} is VALID [2022-04-08 06:40:34,869 INFO L272 TraceCheckUtils]: 31: Hoare triple {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:34,870 INFO L290 TraceCheckUtils]: 32: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:34,870 INFO L290 TraceCheckUtils]: 33: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:34,870 INFO L290 TraceCheckUtils]: 34: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:34,870 INFO L284 TraceCheckUtils]: 35: Hoare quadruple {3064#true} {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} #80#return; {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} is VALID [2022-04-08 06:40:34,871 INFO L272 TraceCheckUtils]: 36: Hoare triple {3139#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) (= main_~B~0 1))} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {3179#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:40:34,872 INFO L290 TraceCheckUtils]: 37: Hoare triple {3179#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {3183#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:40:34,872 INFO L290 TraceCheckUtils]: 38: Hoare triple {3183#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {3065#false} is VALID [2022-04-08 06:40:34,872 INFO L290 TraceCheckUtils]: 39: Hoare triple {3065#false} assume !false; {3065#false} is VALID [2022-04-08 06:40:34,872 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-08 06:40:34,873 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 06:40:35,046 INFO L290 TraceCheckUtils]: 39: Hoare triple {3065#false} assume !false; {3065#false} is VALID [2022-04-08 06:40:35,047 INFO L290 TraceCheckUtils]: 38: Hoare triple {3183#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {3065#false} is VALID [2022-04-08 06:40:35,047 INFO L290 TraceCheckUtils]: 37: Hoare triple {3179#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {3183#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:40:35,048 INFO L272 TraceCheckUtils]: 36: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {3179#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:40:35,049 INFO L284 TraceCheckUtils]: 35: Hoare quadruple {3064#true} {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #80#return; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,049 INFO L290 TraceCheckUtils]: 34: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:35,049 INFO L290 TraceCheckUtils]: 33: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:35,049 INFO L290 TraceCheckUtils]: 32: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:35,050 INFO L272 TraceCheckUtils]: 31: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:35,050 INFO L284 TraceCheckUtils]: 30: Hoare quadruple {3064#true} {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #78#return; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,050 INFO L290 TraceCheckUtils]: 29: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:35,051 INFO L290 TraceCheckUtils]: 28: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:35,051 INFO L290 TraceCheckUtils]: 27: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:35,051 INFO L272 TraceCheckUtils]: 26: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:35,051 INFO L290 TraceCheckUtils]: 25: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} assume !!(#t~post5 < 2);havoc #t~post5; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,052 INFO L290 TraceCheckUtils]: 24: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,055 INFO L290 TraceCheckUtils]: 23: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,056 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {3064#true} {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #82#return; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,057 INFO L290 TraceCheckUtils]: 21: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:35,057 INFO L290 TraceCheckUtils]: 20: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:35,057 INFO L290 TraceCheckUtils]: 19: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:35,057 INFO L272 TraceCheckUtils]: 18: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:35,058 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {3064#true} {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #80#return; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,058 INFO L290 TraceCheckUtils]: 16: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:35,058 INFO L290 TraceCheckUtils]: 15: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:35,058 INFO L290 TraceCheckUtils]: 14: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:35,058 INFO L272 TraceCheckUtils]: 13: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:35,059 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {3064#true} {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #78#return; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,059 INFO L290 TraceCheckUtils]: 11: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:35,059 INFO L290 TraceCheckUtils]: 10: Hoare triple {3064#true} assume !(0 == ~cond); {3064#true} is VALID [2022-04-08 06:40:35,059 INFO L290 TraceCheckUtils]: 9: Hoare triple {3064#true} ~cond := #in~cond; {3064#true} is VALID [2022-04-08 06:40:35,059 INFO L272 TraceCheckUtils]: 8: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3064#true} is VALID [2022-04-08 06:40:35,060 INFO L290 TraceCheckUtils]: 7: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} assume !!(#t~post5 < 2);havoc #t~post5; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,060 INFO L290 TraceCheckUtils]: 6: Hoare triple {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,061 INFO L290 TraceCheckUtils]: 5: Hoare triple {3064#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {3199#(= (* main_~B~0 main_~p~0) main_~d~0)} is VALID [2022-04-08 06:40:35,061 INFO L272 TraceCheckUtils]: 4: Hoare triple {3064#true} call #t~ret7 := main(); {3064#true} is VALID [2022-04-08 06:40:35,061 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3064#true} {3064#true} #92#return; {3064#true} is VALID [2022-04-08 06:40:35,061 INFO L290 TraceCheckUtils]: 2: Hoare triple {3064#true} assume true; {3064#true} is VALID [2022-04-08 06:40:35,062 INFO L290 TraceCheckUtils]: 1: Hoare triple {3064#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3064#true} is VALID [2022-04-08 06:40:35,062 INFO L272 TraceCheckUtils]: 0: Hoare triple {3064#true} call ULTIMATE.init(); {3064#true} is VALID [2022-04-08 06:40:35,062 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-08 06:40:35,062 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:40:35,062 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [549883575] [2022-04-08 06:40:35,062 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:40:35,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [630412582] [2022-04-08 06:40:35,063 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [630412582] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-08 06:40:35,063 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-08 06:40:35,063 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-08 06:40:35,063 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:40:35,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [509184440] [2022-04-08 06:40:35,063 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [509184440] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:40:35,063 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:40:35,064 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:40:35,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1308214515] [2022-04-08 06:40:35,064 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:40:35,064 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-04-08 06:40:35,065 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:40:35,065 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:35,092 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:35,092 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:40:35,092 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:35,093 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:40:35,093 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-08 06:40:35,093 INFO L87 Difference]: Start difference. First operand 65 states and 78 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:37,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:37,089 INFO L93 Difference]: Finished difference Result 78 states and 95 transitions. [2022-04-08 06:40:37,089 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 06:40:37,089 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-04-08 06:40:37,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:40:37,090 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:37,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 53 transitions. [2022-04-08 06:40:37,091 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:37,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 53 transitions. [2022-04-08 06:40:37,092 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 53 transitions. [2022-04-08 06:40:37,156 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 53 edges. 53 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:37,160 INFO L225 Difference]: With dead ends: 78 [2022-04-08 06:40:37,160 INFO L226 Difference]: Without dead ends: 76 [2022-04-08 06:40:37,160 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-08 06:40:37,163 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 06:40:37,163 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 06:40:37,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-04-08 06:40:37,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2022-04-08 06:40:37,217 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:40:37,217 INFO L82 GeneralOperation]: Start isEquivalent. First operand 76 states. Second operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-08 06:40:37,218 INFO L74 IsIncluded]: Start isIncluded. First operand 76 states. Second operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-08 06:40:37,218 INFO L87 Difference]: Start difference. First operand 76 states. Second operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-08 06:40:37,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:37,221 INFO L93 Difference]: Finished difference Result 76 states and 93 transitions. [2022-04-08 06:40:37,221 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 93 transitions. [2022-04-08 06:40:37,221 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:37,222 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:37,222 INFO L74 IsIncluded]: Start isIncluded. First operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) Second operand 76 states. [2022-04-08 06:40:37,222 INFO L87 Difference]: Start difference. First operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) Second operand 76 states. [2022-04-08 06:40:37,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:40:37,224 INFO L93 Difference]: Finished difference Result 76 states and 93 transitions. [2022-04-08 06:40:37,224 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 93 transitions. [2022-04-08 06:40:37,224 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:40:37,224 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:40:37,225 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:40:37,225 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:40:37,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-08 06:40:37,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 88 transitions. [2022-04-08 06:40:37,228 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 88 transitions. Word has length 40 [2022-04-08 06:40:37,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:40:37,228 INFO L478 AbstractCegarLoop]: Abstraction has 73 states and 88 transitions. [2022-04-08 06:40:37,228 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:40:37,228 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 73 states and 88 transitions. [2022-04-08 06:40:37,322 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 88 edges. 88 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:40:37,322 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 88 transitions. [2022-04-08 06:40:37,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-04-08 06:40:37,326 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:40:37,326 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:40:37,345 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-08 06:40:37,535 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:37,535 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:40:37,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:40:37,536 INFO L85 PathProgramCache]: Analyzing trace with hash 529029787, now seen corresponding path program 1 times [2022-04-08 06:40:37,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:40:37,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1847739536] [2022-04-08 06:40:41,674 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 3 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-08 06:40:41,674 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because UNSUPPORTED_EIGENVALUES [2022-04-08 06:40:41,674 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 06:40:41,674 INFO L85 PathProgramCache]: Analyzing trace with hash 529029787, now seen corresponding path program 2 times [2022-04-08 06:40:41,674 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:40:41,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1024014017] [2022-04-08 06:40:41,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:40:41,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:40:41,686 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:40:41,686 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [603187373] [2022-04-08 06:40:41,686 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:40:41,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:41,686 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:40:41,697 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:40:41,708 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-08 06:40:41,749 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:40:41,749 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-04-08 06:40:41,749 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-08 06:40:41,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-08 06:40:41,793 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-08 06:40:41,793 INFO L130 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found a feasible trace [2022-04-08 06:40:41,794 INFO L618 BasicCegarLoop]: Counterexample is feasible [2022-04-08 06:40:41,796 INFO L788 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-08 06:40:41,834 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-08 06:40:42,013 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:40:42,016 INFO L719 BasicCegarLoop]: Path program histogram: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] [2022-04-08 06:40:42,019 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-08 06:40:42,031 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-08 06:40:42,031 WARN L170 areAnnotationChecker]: ULTIMATE.initENTRY has no Hoare annotation [2022-04-08 06:40:42,031 WARN L170 areAnnotationChecker]: ULTIMATE.startENTRY has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: ULTIMATE.startENTRY has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: assume_abort_if_notENTRY has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: mainENTRY has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: __VERIFIER_assertENTRY has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L-1 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L-1 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L34-3 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L34-3 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L15 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L15 has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: ULTIMATE.initEXIT has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-08 06:40:42,032 WARN L170 areAnnotationChecker]: L12-2 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L52-2 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L52-2 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L34-1 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L34-1 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L16 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L16 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L15-2 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L44-2 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L44-2 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L44 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L44 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L35 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: L35 has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,033 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L58 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L58 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L45 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L45 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L35-1 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L35-1 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L36 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L36 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L37 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L37 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L45-1 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L45-1 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L46 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L46 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L59 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L52 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: L52 has no Hoare annotation [2022-04-08 06:40:42,034 WARN L170 areAnnotationChecker]: mainFINAL has no Hoare annotation [2022-04-08 06:40:42,035 WARN L170 areAnnotationChecker]: mainEXIT has no Hoare annotation [2022-04-08 06:40:42,035 INFO L163 areAnnotationChecker]: CFG has 0 edges. 0 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-08 06:40:42,036 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 08.04 06:40:42 BoogieIcfgContainer [2022-04-08 06:40:42,036 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-08 06:40:42,037 INFO L158 Benchmark]: Toolchain (without parser) took 21166.43ms. Allocated memory was 168.8MB in the beginning and 244.3MB in the end (delta: 75.5MB). Free memory was 117.1MB in the beginning and 171.2MB in the end (delta: -54.1MB). Peak memory consumption was 22.2MB. Max. memory is 8.0GB. [2022-04-08 06:40:42,037 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 168.8MB. Free memory is still 133.7MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-08 06:40:42,038 INFO L158 Benchmark]: CACSL2BoogieTranslator took 312.86ms. Allocated memory was 168.8MB in the beginning and 203.4MB in the end (delta: 34.6MB). Free memory was 116.9MB in the beginning and 179.5MB in the end (delta: -62.6MB). Peak memory consumption was 13.3MB. Max. memory is 8.0GB. [2022-04-08 06:40:42,038 INFO L158 Benchmark]: Boogie Preprocessor took 50.43ms. Allocated memory is still 203.4MB. Free memory was 179.5MB in the beginning and 178.1MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-08 06:40:42,038 INFO L158 Benchmark]: RCFGBuilder took 338.12ms. Allocated memory is still 203.4MB. Free memory was 178.1MB in the beginning and 166.0MB in the end (delta: 12.1MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-08 06:40:42,038 INFO L158 Benchmark]: TraceAbstraction took 20459.95ms. Allocated memory was 203.4MB in the beginning and 244.3MB in the end (delta: 40.9MB). Free memory was 165.5MB in the beginning and 171.2MB in the end (delta: -5.7MB). Peak memory consumption was 35.1MB. Max. memory is 8.0GB. [2022-04-08 06:40:42,039 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.15ms. Allocated memory is still 168.8MB. Free memory is still 133.7MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 312.86ms. Allocated memory was 168.8MB in the beginning and 203.4MB in the end (delta: 34.6MB). Free memory was 116.9MB in the beginning and 179.5MB in the end (delta: -62.6MB). Peak memory consumption was 13.3MB. Max. memory is 8.0GB. * Boogie Preprocessor took 50.43ms. Allocated memory is still 203.4MB. Free memory was 179.5MB in the beginning and 178.1MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 338.12ms. Allocated memory is still 203.4MB. Free memory was 178.1MB in the beginning and 166.0MB in the end (delta: 12.1MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 20459.95ms. Allocated memory was 203.4MB in the beginning and 244.3MB in the end (delta: 40.9MB). Free memory was 165.5MB in the beginning and 171.2MB in the end (delta: -5.7MB). Peak memory consumption was 35.1MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; [L24] int A, B; [L25] int r, d, p, q; [L26] A = __VERIFIER_nondet_int() [L27] B = 1 [L29] r = A [L30] d = B [L31] p = 1 [L32] q = 0 [L34] EXPR counter++ [L34] COND TRUE counter++<2 [L35] CALL __VERIFIER_assert(q == 0) [L15] COND FALSE !(!(cond)) [L35] RET __VERIFIER_assert(q == 0) [L36] CALL __VERIFIER_assert(r == A) [L15] COND FALSE !(!(cond)) [L36] RET __VERIFIER_assert(r == A) [L37] CALL __VERIFIER_assert(d == B * p) [L15] COND FALSE !(!(cond)) [L37] RET __VERIFIER_assert(d == B * p) [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p [L34] EXPR counter++ [L34] COND TRUE counter++<2 [L35] CALL __VERIFIER_assert(q == 0) [L15] COND FALSE !(!(cond)) [L35] RET __VERIFIER_assert(q == 0) [L36] CALL __VERIFIER_assert(r == A) [L15] COND FALSE !(!(cond)) [L36] RET __VERIFIER_assert(r == A) [L37] CALL __VERIFIER_assert(d == B * p) [L15] COND FALSE !(!(cond)) [L37] RET __VERIFIER_assert(d == B * p) [L38] COND TRUE !(r >= d) [L44] EXPR counter++ [L44] COND FALSE !(counter++<2) [L58] CALL __VERIFIER_assert(A == d*q + r) [L15] COND FALSE !(!(cond)) [L58] RET __VERIFIER_assert(A == d*q + r) [L59] CALL __VERIFIER_assert(B == d) [L15] COND TRUE !(cond) [L17] reach_error() - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 38 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 20.3s, OverallIterations: 10, TraceHistogramMax: 8, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 4.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 113 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 92 mSDsluCounter, 830 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 514 mSDsCounter, 55 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 420 IncrementalHoareTripleChecker+Invalid, 475 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 55 mSolverCounterUnsat, 316 mSDtfsCounter, 420 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 270 GetRequests, 225 SyntacticMatches, 3 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=73occurred in iteration=9, InterpolantAutomatonStates: 51, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 9 MinimizatonAttempts, 23 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: No data available, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-04-08 06:40:42,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...