/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/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 11:28:26,923 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 11:28:26,924 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 11:28:26,960 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 11:28:26,961 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 11:28:26,962 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 11:28:26,964 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 11:28:26,966 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 11:28:26,968 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 11:28:26,971 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 11:28:26,972 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 11:28:26,973 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 11:28:26,973 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 11:28:26,975 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 11:28:26,976 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 11:28:26,978 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 11:28:26,979 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 11:28:26,979 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 11:28:26,981 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 11:28:26,985 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 11:28:26,987 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 11:28:26,988 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 11:28:26,988 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 11:28:26,989 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 11:28:26,990 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 11:28:26,994 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 11:28:26,995 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 11:28:26,995 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 11:28:26,995 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 11:28:26,996 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 11:28:26,997 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 11:28:26,997 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 11:28:26,998 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 11:28:26,998 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 11:28:26,999 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 11:28:26,999 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 11:28:26,999 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 11:28:27,000 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 11:28:27,000 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 11:28:27,000 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 11:28:27,001 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 11:28:27,002 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 11:28:27,002 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-08 11:28:27,011 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 11:28:27,012 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 11:28:27,013 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 11:28:27,013 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 11:28:27,013 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 11:28:27,013 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 11:28:27,013 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 11:28:27,013 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 11:28:27,014 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 11:28:27,014 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 11:28:27,014 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 11:28:27,014 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 11:28:27,015 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 11:28:27,015 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-08 11:28:27,015 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 11:28:27,227 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 11:28:27,242 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 11:28:27,243 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 11:28:27,244 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 11:28:27,245 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 11:28:27,246 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound20.c [2022-04-08 11:28:27,308 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aae494f58/227dcda98f1c4d1d87c63b68f7778431/FLAG7f75221b0 [2022-04-08 11:28:27,667 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 11:28:27,667 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound20.c [2022-04-08 11:28:27,671 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aae494f58/227dcda98f1c4d1d87c63b68f7778431/FLAG7f75221b0 [2022-04-08 11:28:28,100 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aae494f58/227dcda98f1c4d1d87c63b68f7778431 [2022-04-08 11:28:28,102 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 11:28:28,103 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 11:28:28,103 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 11:28:28,104 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 11:28:28,105 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 11:28:28,106 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,107 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@467d1623 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28, skipping insertion in model container [2022-04-08 11:28:28,107 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,111 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 11:28:28,119 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 11:28:28,256 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/dijkstra-u_unwindbound20.c[525,538] [2022-04-08 11:28:28,315 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 11:28:28,321 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 11:28:28,335 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/dijkstra-u_unwindbound20.c[525,538] [2022-04-08 11:28:28,367 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 11:28:28,382 INFO L208 MainTranslator]: Completed translation [2022-04-08 11:28:28,382 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28 WrapperNode [2022-04-08 11:28:28,382 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 11:28:28,383 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 11:28:28,383 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 11:28:28,383 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 11:28:28,391 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,391 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,406 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,406 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,411 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,414 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,415 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,417 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 11:28:28,417 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 11:28:28,417 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 11:28:28,418 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 11:28:28,418 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (1/1) ... [2022-04-08 11:28:28,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 11:28:28,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:28:28,449 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 11:28:28,451 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 11:28:28,473 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 11:28:28,473 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 11:28:28,473 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 11:28:28,474 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 11:28:28,474 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 11:28:28,474 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 11:28:28,474 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 11:28:28,474 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 11:28:28,474 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 11:28:28,475 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 11:28:28,475 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-08 11:28:28,475 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 11:28:28,475 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 11:28:28,476 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 11:28:28,476 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 11:28:28,476 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 11:28:28,476 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 11:28:28,476 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 11:28:28,477 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 11:28:28,477 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 11:28:28,522 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 11:28:28,524 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 11:28:28,702 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 11:28:28,706 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 11:28:28,707 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-08 11:28:28,708 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 11:28:28 BoogieIcfgContainer [2022-04-08 11:28:28,708 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 11:28:28,709 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 11:28:28,709 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 11:28:28,718 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 11:28:28,718 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 11:28:28" (1/3) ... [2022-04-08 11:28:28,718 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@13845526 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 11:28:28, skipping insertion in model container [2022-04-08 11:28:28,718 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:28:28" (2/3) ... [2022-04-08 11:28:28,719 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@13845526 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 11:28:28, skipping insertion in model container [2022-04-08 11:28:28,719 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 11:28:28" (3/3) ... [2022-04-08 11:28:28,719 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_unwindbound20.c [2022-04-08 11:28:28,722 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 11:28:28,722 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 11:28:28,747 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 11:28:28,751 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 11:28:28,751 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 11:28:28,762 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 11:28:28,766 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-08 11:28:28,766 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:28:28,767 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:28:28,767 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:28:28,770 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:28:28,770 INFO L85 PathProgramCache]: Analyzing trace with hash -2024343623, now seen corresponding path program 1 times [2022-04-08 11:28:28,774 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:28,775 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [501880728] [2022-04-08 11:28:28,781 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:28:28,781 INFO L85 PathProgramCache]: Analyzing trace with hash -2024343623, now seen corresponding path program 2 times [2022-04-08 11:28:28,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:28:28,783 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [138064568] [2022-04-08 11:28:28,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:28:28,784 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:28:28,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:28,876 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:28:28,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:28,888 INFO L290 TraceCheckUtils]: 0: Hoare triple {51#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {42#true} is VALID [2022-04-08 11:28:28,889 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume true; {42#true} is VALID [2022-04-08 11:28:28,889 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {42#true} {42#true} #102#return; {42#true} is VALID [2022-04-08 11:28:28,889 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:28:28,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:28,895 INFO L290 TraceCheckUtils]: 0: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-08 11:28:28,895 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-08 11:28:28,896 INFO L290 TraceCheckUtils]: 2: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-08 11:28:28,896 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {43#false} {42#true} #82#return; {43#false} is VALID [2022-04-08 11:28:28,897 INFO L272 TraceCheckUtils]: 0: Hoare triple {42#true} call ULTIMATE.init(); {51#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:28:28,897 INFO L290 TraceCheckUtils]: 1: Hoare triple {51#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {42#true} is VALID [2022-04-08 11:28:28,897 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#true} assume true; {42#true} is VALID [2022-04-08 11:28:28,897 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#true} {42#true} #102#return; {42#true} is VALID [2022-04-08 11:28:28,897 INFO L272 TraceCheckUtils]: 4: Hoare triple {42#true} call #t~ret7 := main(); {42#true} is VALID [2022-04-08 11:28:28,898 INFO L290 TraceCheckUtils]: 5: Hoare triple {42#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {42#true} is VALID [2022-04-08 11:28:28,898 INFO L272 TraceCheckUtils]: 6: Hoare triple {42#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {42#true} is VALID [2022-04-08 11:28:28,898 INFO L290 TraceCheckUtils]: 7: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-08 11:28:28,898 INFO L290 TraceCheckUtils]: 8: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-08 11:28:28,899 INFO L290 TraceCheckUtils]: 9: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-08 11:28:28,899 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {43#false} {42#true} #82#return; {43#false} is VALID [2022-04-08 11:28:28,899 INFO L290 TraceCheckUtils]: 11: Hoare triple {43#false} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {43#false} is VALID [2022-04-08 11:28:28,899 INFO L290 TraceCheckUtils]: 12: Hoare triple {43#false} assume !true; {43#false} is VALID [2022-04-08 11:28:28,899 INFO L290 TraceCheckUtils]: 13: Hoare triple {43#false} assume !true; {43#false} is VALID [2022-04-08 11:28:28,900 INFO L272 TraceCheckUtils]: 14: Hoare triple {43#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {43#false} is VALID [2022-04-08 11:28:28,900 INFO L290 TraceCheckUtils]: 15: Hoare triple {43#false} ~cond := #in~cond; {43#false} is VALID [2022-04-08 11:28:28,900 INFO L290 TraceCheckUtils]: 16: Hoare triple {43#false} assume 0 == ~cond; {43#false} is VALID [2022-04-08 11:28:28,900 INFO L290 TraceCheckUtils]: 17: Hoare triple {43#false} assume !false; {43#false} is VALID [2022-04-08 11:28:28,900 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 11:28:28,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:28:28,901 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [138064568] [2022-04-08 11:28:28,901 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [138064568] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:28,902 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:28,902 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 11:28:28,903 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:28:28,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [501880728] [2022-04-08 11:28:28,904 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [501880728] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:28,904 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:28,904 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 11:28:28,904 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [932659411] [2022-04-08 11:28:28,904 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:28:28,907 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-08 11:28:28,908 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:28:28,910 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:28,927 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:28,927 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 11:28:28,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:28,939 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 11:28:28,939 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 11:28:28,941 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:34,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:34,146 INFO L93 Difference]: Finished difference Result 70 states and 111 transitions. [2022-04-08 11:28:34,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 11:28:34,146 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-08 11:28:34,147 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:28:34,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:34,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 111 transitions. [2022-04-08 11:28:34,163 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:34,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 111 transitions. [2022-04-08 11:28:34,174 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 111 transitions. [2022-04-08 11:28:34,302 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 111 edges. 111 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:34,311 INFO L225 Difference]: With dead ends: 70 [2022-04-08 11:28:34,311 INFO L226 Difference]: Without dead ends: 35 [2022-04-08 11:28:34,314 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 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 11:28:34,316 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-04-08 11:28:34,316 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 53 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-04-08 11:28:34,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-08 11:28:34,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2022-04-08 11:28:34,338 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:28:34,338 INFO L82 GeneralOperation]: Start isEquivalent. First operand 35 states. Second operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:34,339 INFO L74 IsIncluded]: Start isIncluded. First operand 35 states. Second operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:34,339 INFO L87 Difference]: Start difference. First operand 35 states. Second operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:34,343 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:34,343 INFO L93 Difference]: Finished difference Result 35 states and 47 transitions. [2022-04-08 11:28:34,343 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 47 transitions. [2022-04-08 11:28:34,344 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:34,344 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:34,344 INFO L74 IsIncluded]: Start isIncluded. First operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 35 states. [2022-04-08 11:28:34,345 INFO L87 Difference]: Start difference. First operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 35 states. [2022-04-08 11:28:34,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:34,347 INFO L93 Difference]: Finished difference Result 35 states and 47 transitions. [2022-04-08 11:28:34,347 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 47 transitions. [2022-04-08 11:28:34,348 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:34,348 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:34,348 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:28:34,348 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:28:34,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:34,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 46 transitions. [2022-04-08 11:28:34,352 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 46 transitions. Word has length 18 [2022-04-08 11:28:34,352 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:28:34,352 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 46 transitions. [2022-04-08 11:28:34,352 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:34,353 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 34 states and 46 transitions. [2022-04-08 11:28:34,394 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 46 edges. 46 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:34,394 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 46 transitions. [2022-04-08 11:28:34,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-08 11:28:34,395 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:28:34,395 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:28:34,395 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 11:28:34,395 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:28:34,396 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:28:34,396 INFO L85 PathProgramCache]: Analyzing trace with hash -96361696, now seen corresponding path program 1 times [2022-04-08 11:28:34,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:34,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1066757799] [2022-04-08 11:28:34,397 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:28:34,397 INFO L85 PathProgramCache]: Analyzing trace with hash -96361696, now seen corresponding path program 2 times [2022-04-08 11:28:34,397 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:28:34,397 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [622455105] [2022-04-08 11:28:34,397 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:28:34,397 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:28:34,417 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:28:34,417 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1780163459] [2022-04-08 11:28:34,417 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:28:34,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:34,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:28:34,419 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 11:28:34,420 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 11:28:34,463 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:28:34,463 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:28:34,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-08 11:28:34,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:34,474 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:28:34,586 INFO L272 TraceCheckUtils]: 0: Hoare triple {332#true} call ULTIMATE.init(); {332#true} is VALID [2022-04-08 11:28:34,586 INFO L290 TraceCheckUtils]: 1: Hoare triple {332#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,587 INFO L290 TraceCheckUtils]: 2: Hoare triple {340#(<= ~counter~0 0)} assume true; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,587 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {340#(<= ~counter~0 0)} {332#true} #102#return; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,588 INFO L272 TraceCheckUtils]: 4: Hoare triple {340#(<= ~counter~0 0)} call #t~ret7 := main(); {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,588 INFO L290 TraceCheckUtils]: 5: Hoare triple {340#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,589 INFO L272 TraceCheckUtils]: 6: Hoare triple {340#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,589 INFO L290 TraceCheckUtils]: 7: Hoare triple {340#(<= ~counter~0 0)} ~cond := #in~cond; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,590 INFO L290 TraceCheckUtils]: 8: Hoare triple {340#(<= ~counter~0 0)} assume !(0 == ~cond); {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,590 INFO L290 TraceCheckUtils]: 9: Hoare triple {340#(<= ~counter~0 0)} assume true; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,590 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {340#(<= ~counter~0 0)} {340#(<= ~counter~0 0)} #82#return; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,591 INFO L290 TraceCheckUtils]: 11: Hoare triple {340#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:34,591 INFO L290 TraceCheckUtils]: 12: Hoare triple {340#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {374#(<= |main_#t~post5| 0)} is VALID [2022-04-08 11:28:34,592 INFO L290 TraceCheckUtils]: 13: Hoare triple {374#(<= |main_#t~post5| 0)} assume !(#t~post5 < 20);havoc #t~post5; {333#false} is VALID [2022-04-08 11:28:34,592 INFO L290 TraceCheckUtils]: 14: Hoare triple {333#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {333#false} is VALID [2022-04-08 11:28:34,592 INFO L290 TraceCheckUtils]: 15: Hoare triple {333#false} assume !(#t~post6 < 20);havoc #t~post6; {333#false} is VALID [2022-04-08 11:28:34,592 INFO L272 TraceCheckUtils]: 16: Hoare triple {333#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {333#false} is VALID [2022-04-08 11:28:34,592 INFO L290 TraceCheckUtils]: 17: Hoare triple {333#false} ~cond := #in~cond; {333#false} is VALID [2022-04-08 11:28:34,593 INFO L290 TraceCheckUtils]: 18: Hoare triple {333#false} assume 0 == ~cond; {333#false} is VALID [2022-04-08 11:28:34,593 INFO L290 TraceCheckUtils]: 19: Hoare triple {333#false} assume !false; {333#false} is VALID [2022-04-08 11:28:34,593 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 11:28:34,593 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:28:34,593 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:28:34,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [622455105] [2022-04-08 11:28:34,594 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:28:34,594 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1780163459] [2022-04-08 11:28:34,594 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1780163459] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:34,594 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:34,594 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 11:28:34,595 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:28:34,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1066757799] [2022-04-08 11:28:34,595 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1066757799] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:34,595 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:34,595 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 11:28:34,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1264590675] [2022-04-08 11:28:34,595 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:28:34,596 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-08 11:28:34,596 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:28:34,596 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:34,611 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:34,611 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-08 11:28:34,611 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:34,612 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-08 11:28:34,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 11:28:34,612 INFO L87 Difference]: Start difference. First operand 34 states and 46 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:37,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:37,033 INFO L93 Difference]: Finished difference Result 55 states and 78 transitions. [2022-04-08 11:28:37,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-08 11:28:37,034 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-08 11:28:37,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:28:37,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:37,036 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 78 transitions. [2022-04-08 11:28:37,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:37,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 78 transitions. [2022-04-08 11:28:37,038 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 78 transitions. [2022-04-08 11:28:37,125 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 11:28:37,127 INFO L225 Difference]: With dead ends: 55 [2022-04-08 11:28:37,128 INFO L226 Difference]: Without dead ends: 36 [2022-04-08 11:28:37,128 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 11:28:37,129 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 11:28:37,130 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 119 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 11:28:37,131 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-08 11:28:37,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-04-08 11:28:37,157 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:28:37,157 INFO L82 GeneralOperation]: Start isEquivalent. First operand 36 states. Second operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:37,158 INFO L74 IsIncluded]: Start isIncluded. First operand 36 states. Second operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:37,158 INFO L87 Difference]: Start difference. First operand 36 states. Second operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:37,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:37,160 INFO L93 Difference]: Finished difference Result 36 states and 48 transitions. [2022-04-08 11:28:37,160 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 11:28:37,160 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:37,161 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:37,161 INFO L74 IsIncluded]: Start isIncluded. First operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 36 states. [2022-04-08 11:28:37,161 INFO L87 Difference]: Start difference. First operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 36 states. [2022-04-08 11:28:37,163 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:37,163 INFO L93 Difference]: Finished difference Result 36 states and 48 transitions. [2022-04-08 11:28:37,163 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 11:28:37,164 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:37,164 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:37,164 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:28:37,164 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:28:37,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:37,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 48 transitions. [2022-04-08 11:28:37,169 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 48 transitions. Word has length 20 [2022-04-08 11:28:37,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:28:37,170 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 48 transitions. [2022-04-08 11:28:37,170 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:37,170 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 36 states and 48 transitions. [2022-04-08 11:28:37,215 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 48 edges. 48 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:37,217 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 11:28:37,218 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-08 11:28:37,222 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:28:37,222 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:28:37,239 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 11:28:37,438 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:37,439 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:28:37,439 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:28:37,439 INFO L85 PathProgramCache]: Analyzing trace with hash 962099791, now seen corresponding path program 1 times [2022-04-08 11:28:37,439 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:37,439 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2110854901] [2022-04-08 11:28:37,440 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:28:37,440 INFO L85 PathProgramCache]: Analyzing trace with hash 962099791, now seen corresponding path program 2 times [2022-04-08 11:28:37,440 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:28:37,440 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1267299753] [2022-04-08 11:28:37,440 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:28:37,440 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:28:37,457 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:28:37,457 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [642814698] [2022-04-08 11:28:37,457 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:28:37,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:37,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:28:37,462 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 11:28:37,463 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 11:28:37,501 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:28:37,501 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:28:37,502 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 11:28:37,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:37,513 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:28:37,630 INFO L272 TraceCheckUtils]: 0: Hoare triple {649#true} call ULTIMATE.init(); {649#true} is VALID [2022-04-08 11:28:37,631 INFO L290 TraceCheckUtils]: 1: Hoare triple {649#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,631 INFO L290 TraceCheckUtils]: 2: Hoare triple {657#(<= ~counter~0 0)} assume true; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,632 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {657#(<= ~counter~0 0)} {649#true} #102#return; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,632 INFO L272 TraceCheckUtils]: 4: Hoare triple {657#(<= ~counter~0 0)} call #t~ret7 := main(); {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,632 INFO L290 TraceCheckUtils]: 5: Hoare triple {657#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,633 INFO L272 TraceCheckUtils]: 6: Hoare triple {657#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,633 INFO L290 TraceCheckUtils]: 7: Hoare triple {657#(<= ~counter~0 0)} ~cond := #in~cond; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,634 INFO L290 TraceCheckUtils]: 8: Hoare triple {657#(<= ~counter~0 0)} assume !(0 == ~cond); {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,634 INFO L290 TraceCheckUtils]: 9: Hoare triple {657#(<= ~counter~0 0)} assume true; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,634 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {657#(<= ~counter~0 0)} {657#(<= ~counter~0 0)} #82#return; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,635 INFO L290 TraceCheckUtils]: 11: Hoare triple {657#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:37,635 INFO L290 TraceCheckUtils]: 12: Hoare triple {657#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {691#(<= ~counter~0 1)} is VALID [2022-04-08 11:28:37,636 INFO L290 TraceCheckUtils]: 13: Hoare triple {691#(<= ~counter~0 1)} assume !!(#t~post5 < 20);havoc #t~post5; {691#(<= ~counter~0 1)} is VALID [2022-04-08 11:28:37,636 INFO L290 TraceCheckUtils]: 14: Hoare triple {691#(<= ~counter~0 1)} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {691#(<= ~counter~0 1)} is VALID [2022-04-08 11:28:37,636 INFO L290 TraceCheckUtils]: 15: Hoare triple {691#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {701#(<= |main_#t~post6| 1)} is VALID [2022-04-08 11:28:37,637 INFO L290 TraceCheckUtils]: 16: Hoare triple {701#(<= |main_#t~post6| 1)} assume !(#t~post6 < 20);havoc #t~post6; {650#false} is VALID [2022-04-08 11:28:37,637 INFO L272 TraceCheckUtils]: 17: Hoare triple {650#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {650#false} is VALID [2022-04-08 11:28:37,637 INFO L290 TraceCheckUtils]: 18: Hoare triple {650#false} ~cond := #in~cond; {650#false} is VALID [2022-04-08 11:28:37,637 INFO L290 TraceCheckUtils]: 19: Hoare triple {650#false} assume 0 == ~cond; {650#false} is VALID [2022-04-08 11:28:37,637 INFO L290 TraceCheckUtils]: 20: Hoare triple {650#false} assume !false; {650#false} is VALID [2022-04-08 11:28:37,637 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 11:28:37,637 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:28:37,638 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:28:37,638 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1267299753] [2022-04-08 11:28:37,638 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:28:37,638 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [642814698] [2022-04-08 11:28:37,638 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [642814698] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:37,638 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:37,638 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:28:37,638 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:28:37,638 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2110854901] [2022-04-08 11:28:37,638 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2110854901] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:37,638 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:37,638 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:28:37,639 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2101850525] [2022-04-08 11:28:37,639 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:28:37,639 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-04-08 11:28:37,639 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:28:37,639 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:37,652 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:37,652 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 11:28:37,653 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:37,653 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 11:28:37,653 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-08 11:28:37,653 INFO L87 Difference]: Start difference. First operand 36 states and 48 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:43,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:43,152 INFO L93 Difference]: Finished difference Result 49 states and 64 transitions. [2022-04-08 11:28:43,152 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 11:28:43,153 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-04-08 11:28:43,153 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:28:43,153 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:43,155 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-08 11:28:43,155 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:43,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-08 11:28:43,156 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 64 transitions. [2022-04-08 11:28:43,203 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 11:28:43,204 INFO L225 Difference]: With dead ends: 49 [2022-04-08 11:28:43,204 INFO L226 Difference]: Without dead ends: 40 [2022-04-08 11:28:43,205 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 17 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 11:28:43,206 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 11:28:43,206 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 149 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 11:28:43,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-08 11:28:43,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2022-04-08 11:28:43,220 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:28:43,221 INFO L82 GeneralOperation]: Start isEquivalent. First operand 40 states. Second operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:43,221 INFO L74 IsIncluded]: Start isIncluded. First operand 40 states. Second operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:43,222 INFO L87 Difference]: Start difference. First operand 40 states. Second operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:43,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:43,224 INFO L93 Difference]: Finished difference Result 40 states and 53 transitions. [2022-04-08 11:28:43,224 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 53 transitions. [2022-04-08 11:28:43,224 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:43,224 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:43,225 INFO L74 IsIncluded]: Start isIncluded. First operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 40 states. [2022-04-08 11:28:43,225 INFO L87 Difference]: Start difference. First operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 40 states. [2022-04-08 11:28:43,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:43,226 INFO L93 Difference]: Finished difference Result 40 states and 53 transitions. [2022-04-08 11:28:43,226 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 53 transitions. [2022-04-08 11:28:43,227 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:43,227 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:43,227 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:28:43,227 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:28:43,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:28:43,229 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2022-04-08 11:28:43,229 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 21 [2022-04-08 11:28:43,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:28:43,229 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2022-04-08 11:28:43,229 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:28:43,229 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 39 states and 52 transitions. [2022-04-08 11:28:43,278 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 52 edges. 52 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:43,278 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2022-04-08 11:28:43,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-08 11:28:43,279 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:28:43,279 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:28:43,295 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-08 11:28:43,494 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,SelfDestructingSolverStorable2 [2022-04-08 11:28:43,495 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:28:43,495 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:28:43,495 INFO L85 PathProgramCache]: Analyzing trace with hash 963589341, now seen corresponding path program 1 times [2022-04-08 11:28:43,495 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:43,495 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1485103873] [2022-04-08 11:28:43,496 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:28:43,496 INFO L85 PathProgramCache]: Analyzing trace with hash 963589341, now seen corresponding path program 2 times [2022-04-08 11:28:43,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:28:43,496 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [339481472] [2022-04-08 11:28:43,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:28:43,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:28:43,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:43,648 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:28:43,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:43,654 INFO L290 TraceCheckUtils]: 0: Hoare triple {985#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {972#true} is VALID [2022-04-08 11:28:43,654 INFO L290 TraceCheckUtils]: 1: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:28:43,654 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {972#true} {972#true} #102#return; {972#true} is VALID [2022-04-08 11:28:43,654 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:28:43,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:43,658 INFO L290 TraceCheckUtils]: 0: Hoare triple {972#true} ~cond := #in~cond; {972#true} is VALID [2022-04-08 11:28:43,658 INFO L290 TraceCheckUtils]: 1: Hoare triple {972#true} assume !(0 == ~cond); {972#true} is VALID [2022-04-08 11:28:43,658 INFO L290 TraceCheckUtils]: 2: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:28:43,658 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {972#true} {972#true} #82#return; {972#true} is VALID [2022-04-08 11:28:43,658 INFO L272 TraceCheckUtils]: 0: Hoare triple {972#true} call ULTIMATE.init(); {985#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:28:43,659 INFO L290 TraceCheckUtils]: 1: Hoare triple {985#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {972#true} is VALID [2022-04-08 11:28:43,659 INFO L290 TraceCheckUtils]: 2: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:28:43,659 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {972#true} {972#true} #102#return; {972#true} is VALID [2022-04-08 11:28:43,659 INFO L272 TraceCheckUtils]: 4: Hoare triple {972#true} call #t~ret7 := main(); {972#true} is VALID [2022-04-08 11:28:43,659 INFO L290 TraceCheckUtils]: 5: Hoare triple {972#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {972#true} is VALID [2022-04-08 11:28:43,659 INFO L272 TraceCheckUtils]: 6: Hoare triple {972#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {972#true} is VALID [2022-04-08 11:28:43,659 INFO L290 TraceCheckUtils]: 7: Hoare triple {972#true} ~cond := #in~cond; {972#true} is VALID [2022-04-08 11:28:43,659 INFO L290 TraceCheckUtils]: 8: Hoare triple {972#true} assume !(0 == ~cond); {972#true} is VALID [2022-04-08 11:28:43,659 INFO L290 TraceCheckUtils]: 9: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:28:43,660 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {972#true} {972#true} #82#return; {972#true} is VALID [2022-04-08 11:28:43,660 INFO L290 TraceCheckUtils]: 11: Hoare triple {972#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-08 11:28:43,660 INFO L290 TraceCheckUtils]: 12: Hoare triple {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-08 11:28:43,661 INFO L290 TraceCheckUtils]: 13: Hoare triple {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !!(#t~post5 < 20);havoc #t~post5; {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-08 11:28:43,661 INFO L290 TraceCheckUtils]: 14: Hoare triple {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-08 11:28:43,662 INFO L290 TraceCheckUtils]: 15: Hoare triple {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-08 11:28:43,662 INFO L290 TraceCheckUtils]: 16: Hoare triple {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} assume !!(#t~post6 < 20);havoc #t~post6; {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-08 11:28:43,663 INFO L272 TraceCheckUtils]: 17: Hoare triple {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {983#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 11:28:43,664 INFO L290 TraceCheckUtils]: 18: Hoare triple {983#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {984#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 11:28:43,664 INFO L290 TraceCheckUtils]: 19: Hoare triple {984#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {973#false} is VALID [2022-04-08 11:28:43,664 INFO L290 TraceCheckUtils]: 20: Hoare triple {973#false} assume !false; {973#false} is VALID [2022-04-08 11:28:43,664 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 11:28:43,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:28:43,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [339481472] [2022-04-08 11:28:43,665 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [339481472] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:43,665 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:43,665 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-08 11:28:43,665 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:28:43,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1485103873] [2022-04-08 11:28:43,665 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1485103873] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:43,665 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:43,665 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-08 11:28:43,665 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [99732733] [2022-04-08 11:28:43,665 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:28:43,666 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2022-04-08 11:28:43,666 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:28:43,666 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:43,679 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:43,680 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-08 11:28:43,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:43,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-08 11:28:43,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-08 11:28:43,680 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:50,623 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:28:52,799 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:28:55,226 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:28:57,227 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:28:59,230 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:29:01,407 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:29:05,307 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.84s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:29:10,879 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:29:12,880 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:29:14,884 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:29:16,893 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:29:16,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:16,980 INFO L93 Difference]: Finished difference Result 72 states and 104 transitions. [2022-04-08 11:29:16,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-08 11:29:16,980 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2022-04-08 11:29:16,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:29:16,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:16,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 104 transitions. [2022-04-08 11:29:16,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:16,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 104 transitions. [2022-04-08 11:29:16,984 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 104 transitions. [2022-04-08 11:29:17,134 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 104 edges. 104 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:17,135 INFO L225 Difference]: With dead ends: 72 [2022-04-08 11:29:17,136 INFO L226 Difference]: Without dead ends: 51 [2022-04-08 11:29:17,136 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-08 11:29:17,137 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 24 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 37 mSolverCounterUnsat, 11 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 29.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 11 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 30.0s IncrementalHoareTripleChecker+Time [2022-04-08 11:29:17,137 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 107 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 198 Invalid, 11 Unknown, 0 Unchecked, 30.0s Time] [2022-04-08 11:29:17,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-08 11:29:17,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-04-08 11:29:17,156 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:29:17,156 INFO L82 GeneralOperation]: Start isEquivalent. First operand 51 states. Second operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:29:17,158 INFO L74 IsIncluded]: Start isIncluded. First operand 51 states. Second operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:29:17,159 INFO L87 Difference]: Start difference. First operand 51 states. Second operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:29:17,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:17,164 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-04-08 11:29:17,164 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-08 11:29:17,179 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:17,180 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:17,180 INFO L74 IsIncluded]: Start isIncluded. First operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 51 states. [2022-04-08 11:29:17,180 INFO L87 Difference]: Start difference. First operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 51 states. [2022-04-08 11:29:17,185 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:17,185 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-04-08 11:29:17,185 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-08 11:29:17,186 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:17,186 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:17,186 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:29:17,186 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:29:17,187 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:29:17,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 69 transitions. [2022-04-08 11:29:17,189 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 69 transitions. Word has length 21 [2022-04-08 11:29:17,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:29:17,189 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 69 transitions. [2022-04-08 11:29:17,190 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:17,190 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 51 states and 69 transitions. [2022-04-08 11:29:17,343 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:17,344 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-08 11:29:17,344 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-08 11:29:17,344 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:29:17,344 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:29:17,344 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-08 11:29:17,344 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:29:17,345 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:29:17,345 INFO L85 PathProgramCache]: Analyzing trace with hash -1701877900, now seen corresponding path program 1 times [2022-04-08 11:29:17,345 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:17,345 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1468372285] [2022-04-08 11:29:17,360 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:29:17,360 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:29:17,360 INFO L85 PathProgramCache]: Analyzing trace with hash -1701877900, now seen corresponding path program 2 times [2022-04-08 11:29:17,360 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:29:17,360 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1608089866] [2022-04-08 11:29:17,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:29:17,360 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:29:17,369 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:29:17,369 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1205299960] [2022-04-08 11:29:17,370 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:29:17,370 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:17,370 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:29:17,370 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 11:29:17,371 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 11:29:17,406 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:29:17,406 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:29:17,407 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 11:29:17,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:17,413 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:29:17,504 INFO L272 TraceCheckUtils]: 0: Hoare triple {1346#true} call ULTIMATE.init(); {1346#true} is VALID [2022-04-08 11:29:17,504 INFO L290 TraceCheckUtils]: 1: Hoare triple {1346#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L290 TraceCheckUtils]: 2: Hoare triple {1346#true} assume true; {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1346#true} {1346#true} #102#return; {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L272 TraceCheckUtils]: 4: Hoare triple {1346#true} call #t~ret7 := main(); {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L290 TraceCheckUtils]: 5: Hoare triple {1346#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L272 TraceCheckUtils]: 6: Hoare triple {1346#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L290 TraceCheckUtils]: 7: Hoare triple {1346#true} ~cond := #in~cond; {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L290 TraceCheckUtils]: 8: Hoare triple {1346#true} assume !(0 == ~cond); {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L290 TraceCheckUtils]: 9: Hoare triple {1346#true} assume true; {1346#true} is VALID [2022-04-08 11:29:17,505 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1346#true} {1346#true} #82#return; {1346#true} is VALID [2022-04-08 11:29:17,506 INFO L290 TraceCheckUtils]: 11: Hoare triple {1346#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,506 INFO L290 TraceCheckUtils]: 12: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,507 INFO L290 TraceCheckUtils]: 13: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(#t~post5 < 20);havoc #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,507 INFO L290 TraceCheckUtils]: 14: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,507 INFO L290 TraceCheckUtils]: 15: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,508 INFO L290 TraceCheckUtils]: 16: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(#t~post5 < 20);havoc #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,508 INFO L290 TraceCheckUtils]: 17: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,509 INFO L290 TraceCheckUtils]: 18: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(#t~post6 < 20);havoc #t~post6; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:29:17,510 INFO L272 TraceCheckUtils]: 19: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {1409#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 11:29:17,510 INFO L290 TraceCheckUtils]: 20: Hoare triple {1409#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1413#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 11:29:17,510 INFO L290 TraceCheckUtils]: 21: Hoare triple {1413#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1347#false} is VALID [2022-04-08 11:29:17,510 INFO L290 TraceCheckUtils]: 22: Hoare triple {1347#false} assume !false; {1347#false} is VALID [2022-04-08 11:29:17,510 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-08 11:29:17,511 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:29:17,511 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:29:17,511 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1608089866] [2022-04-08 11:29:17,511 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:29:17,511 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1205299960] [2022-04-08 11:29:17,511 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1205299960] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:17,511 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:29:17,511 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:29:17,511 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:29:17,511 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1468372285] [2022-04-08 11:29:17,511 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1468372285] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:17,511 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:29:17,511 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:29:17,512 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1074069151] [2022-04-08 11:29:17,512 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:29:17,512 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:29:17,512 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:29:17,512 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:17,525 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 11:29:17,525 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 11:29:17,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:17,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 11:29:17,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 11:29:17,526 INFO L87 Difference]: Start difference. First operand 51 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:20,564 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:29:21,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:21,130 INFO L93 Difference]: Finished difference Result 73 states and 99 transitions. [2022-04-08 11:29:21,130 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 11:29:21,130 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:29:21,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:29:21,130 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:21,131 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 73 transitions. [2022-04-08 11:29:21,131 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:21,132 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 73 transitions. [2022-04-08 11:29:21,133 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 73 transitions. [2022-04-08 11:29:21,219 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 73 edges. 73 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:21,221 INFO L225 Difference]: With dead ends: 73 [2022-04-08 11:29:21,221 INFO L226 Difference]: Without dead ends: 52 [2022-04-08 11:29:21,221 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 19 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 11:29:21,222 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 8 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2022-04-08 11:29:21,222 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 157 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 50 Invalid, 1 Unknown, 0 Unchecked, 2.4s Time] [2022-04-08 11:29:21,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-08 11:29:21,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-04-08 11:29:21,253 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:29:21,253 INFO L82 GeneralOperation]: Start isEquivalent. First operand 52 states. Second operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:29:21,254 INFO L74 IsIncluded]: Start isIncluded. First operand 52 states. Second operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:29:21,254 INFO L87 Difference]: Start difference. First operand 52 states. Second operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:29:21,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:21,256 INFO L93 Difference]: Finished difference Result 52 states and 72 transitions. [2022-04-08 11:29:21,256 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-08 11:29:21,256 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:21,256 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:21,256 INFO L74 IsIncluded]: Start isIncluded. First operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 52 states. [2022-04-08 11:29:21,256 INFO L87 Difference]: Start difference. First operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 52 states. [2022-04-08 11:29:21,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:21,258 INFO L93 Difference]: Finished difference Result 52 states and 72 transitions. [2022-04-08 11:29:21,258 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-08 11:29:21,258 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:21,258 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:21,259 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:29:21,259 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:29:21,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:29:21,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 72 transitions. [2022-04-08 11:29:21,262 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 72 transitions. Word has length 23 [2022-04-08 11:29:21,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:29:21,262 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 72 transitions. [2022-04-08 11:29:21,263 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:21,263 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 52 states and 72 transitions. [2022-04-08 11:29:21,367 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 11:29:21,367 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-08 11:29:21,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-08 11:29:21,368 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:29:21,368 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:29:21,386 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 11:29:21,568 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:21,568 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:29:21,569 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:29:21,569 INFO L85 PathProgramCache]: Analyzing trace with hash -1700388350, now seen corresponding path program 1 times [2022-04-08 11:29:21,569 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:21,569 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1568353919] [2022-04-08 11:29:21,579 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:29:21,579 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:29:21,579 INFO L85 PathProgramCache]: Analyzing trace with hash -1700388350, now seen corresponding path program 2 times [2022-04-08 11:29:21,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:29:21,579 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1819353854] [2022-04-08 11:29:21,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:29:21,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:29:21,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:21,629 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:29:21,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:21,657 INFO L290 TraceCheckUtils]: 0: Hoare triple {1787#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,658 INFO L290 TraceCheckUtils]: 1: Hoare triple {1780#(<= ~counter~0 0)} assume true; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,659 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {1780#(<= ~counter~0 0)} {1775#true} #102#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,659 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:29:21,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:21,666 INFO L290 TraceCheckUtils]: 0: Hoare triple {1775#true} ~cond := #in~cond; {1775#true} is VALID [2022-04-08 11:29:21,666 INFO L290 TraceCheckUtils]: 1: Hoare triple {1775#true} assume !(0 == ~cond); {1775#true} is VALID [2022-04-08 11:29:21,666 INFO L290 TraceCheckUtils]: 2: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:29:21,667 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1775#true} {1780#(<= ~counter~0 0)} #82#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,667 INFO L272 TraceCheckUtils]: 0: Hoare triple {1775#true} call ULTIMATE.init(); {1787#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:29:21,668 INFO L290 TraceCheckUtils]: 1: Hoare triple {1787#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,668 INFO L290 TraceCheckUtils]: 2: Hoare triple {1780#(<= ~counter~0 0)} assume true; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,668 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1780#(<= ~counter~0 0)} {1775#true} #102#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,669 INFO L272 TraceCheckUtils]: 4: Hoare triple {1780#(<= ~counter~0 0)} call #t~ret7 := main(); {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,672 INFO L290 TraceCheckUtils]: 5: Hoare triple {1780#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,672 INFO L272 TraceCheckUtils]: 6: Hoare triple {1780#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1775#true} is VALID [2022-04-08 11:29:21,672 INFO L290 TraceCheckUtils]: 7: Hoare triple {1775#true} ~cond := #in~cond; {1775#true} is VALID [2022-04-08 11:29:21,672 INFO L290 TraceCheckUtils]: 8: Hoare triple {1775#true} assume !(0 == ~cond); {1775#true} is VALID [2022-04-08 11:29:21,672 INFO L290 TraceCheckUtils]: 9: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:29:21,673 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1775#true} {1780#(<= ~counter~0 0)} #82#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,673 INFO L290 TraceCheckUtils]: 11: Hoare triple {1780#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:21,674 INFO L290 TraceCheckUtils]: 12: Hoare triple {1780#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1785#(<= ~counter~0 1)} is VALID [2022-04-08 11:29:21,674 INFO L290 TraceCheckUtils]: 13: Hoare triple {1785#(<= ~counter~0 1)} assume !!(#t~post5 < 20);havoc #t~post5; {1785#(<= ~counter~0 1)} is VALID [2022-04-08 11:29:21,675 INFO L290 TraceCheckUtils]: 14: Hoare triple {1785#(<= ~counter~0 1)} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1785#(<= ~counter~0 1)} is VALID [2022-04-08 11:29:21,675 INFO L290 TraceCheckUtils]: 15: Hoare triple {1785#(<= ~counter~0 1)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1786#(<= |main_#t~post5| 1)} is VALID [2022-04-08 11:29:21,676 INFO L290 TraceCheckUtils]: 16: Hoare triple {1786#(<= |main_#t~post5| 1)} assume !(#t~post5 < 20);havoc #t~post5; {1776#false} is VALID [2022-04-08 11:29:21,676 INFO L290 TraceCheckUtils]: 17: Hoare triple {1776#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1776#false} is VALID [2022-04-08 11:29:21,676 INFO L290 TraceCheckUtils]: 18: Hoare triple {1776#false} assume !!(#t~post6 < 20);havoc #t~post6; {1776#false} is VALID [2022-04-08 11:29:21,676 INFO L272 TraceCheckUtils]: 19: Hoare triple {1776#false} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1776#false} is VALID [2022-04-08 11:29:21,676 INFO L290 TraceCheckUtils]: 20: Hoare triple {1776#false} ~cond := #in~cond; {1776#false} is VALID [2022-04-08 11:29:21,676 INFO L290 TraceCheckUtils]: 21: Hoare triple {1776#false} assume 0 == ~cond; {1776#false} is VALID [2022-04-08 11:29:21,676 INFO L290 TraceCheckUtils]: 22: Hoare triple {1776#false} assume !false; {1776#false} is VALID [2022-04-08 11:29:21,677 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:29:21,677 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:29:21,677 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1819353854] [2022-04-08 11:29:21,677 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1819353854] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-08 11:29:21,677 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2075476550] [2022-04-08 11:29:21,677 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:29:21,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:21,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:29:21,679 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 11:29:21,679 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 11:29:21,731 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:29:21,731 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:29:21,732 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-08 11:29:21,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:21,738 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:29:21,823 INFO L272 TraceCheckUtils]: 0: Hoare triple {1775#true} call ULTIMATE.init(); {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L290 TraceCheckUtils]: 1: Hoare triple {1775#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L290 TraceCheckUtils]: 2: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1775#true} {1775#true} #102#return; {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L272 TraceCheckUtils]: 4: Hoare triple {1775#true} call #t~ret7 := main(); {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L290 TraceCheckUtils]: 5: Hoare triple {1775#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L272 TraceCheckUtils]: 6: Hoare triple {1775#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L290 TraceCheckUtils]: 7: Hoare triple {1775#true} ~cond := #in~cond; {1775#true} is VALID [2022-04-08 11:29:21,824 INFO L290 TraceCheckUtils]: 8: Hoare triple {1775#true} assume !(0 == ~cond); {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L290 TraceCheckUtils]: 9: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1775#true} {1775#true} #82#return; {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L290 TraceCheckUtils]: 11: Hoare triple {1775#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L290 TraceCheckUtils]: 12: Hoare triple {1775#true} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L290 TraceCheckUtils]: 13: Hoare triple {1775#true} assume !!(#t~post5 < 20);havoc #t~post5; {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L290 TraceCheckUtils]: 14: Hoare triple {1775#true} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1775#true} is VALID [2022-04-08 11:29:21,825 INFO L290 TraceCheckUtils]: 15: Hoare triple {1775#true} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1836#(<= (+ |main_#t~post5| 1) ~counter~0)} is VALID [2022-04-08 11:29:21,826 INFO L290 TraceCheckUtils]: 16: Hoare triple {1836#(<= (+ |main_#t~post5| 1) ~counter~0)} assume !(#t~post5 < 20);havoc #t~post5; {1840#(<= 21 ~counter~0)} is VALID [2022-04-08 11:29:21,826 INFO L290 TraceCheckUtils]: 17: Hoare triple {1840#(<= 21 ~counter~0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1844#(<= 21 |main_#t~post6|)} is VALID [2022-04-08 11:29:21,827 INFO L290 TraceCheckUtils]: 18: Hoare triple {1844#(<= 21 |main_#t~post6|)} assume !!(#t~post6 < 20);havoc #t~post6; {1776#false} is VALID [2022-04-08 11:29:21,827 INFO L272 TraceCheckUtils]: 19: Hoare triple {1776#false} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1776#false} is VALID [2022-04-08 11:29:21,827 INFO L290 TraceCheckUtils]: 20: Hoare triple {1776#false} ~cond := #in~cond; {1776#false} is VALID [2022-04-08 11:29:21,827 INFO L290 TraceCheckUtils]: 21: Hoare triple {1776#false} assume 0 == ~cond; {1776#false} is VALID [2022-04-08 11:29:21,827 INFO L290 TraceCheckUtils]: 22: Hoare triple {1776#false} assume !false; {1776#false} is VALID [2022-04-08 11:29:21,827 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-08 11:29:21,827 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:29:21,828 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2075476550] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:21,828 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-08 11:29:21,828 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2022-04-08 11:29:21,828 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:29:21,828 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1568353919] [2022-04-08 11:29:21,828 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1568353919] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:21,828 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:29:21,828 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:29:21,828 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [702124879] [2022-04-08 11:29:21,828 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:29:21,829 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:29:21,829 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:29:21,829 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:21,845 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:21,845 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 11:29:21,845 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:21,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 11:29:21,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2022-04-08 11:29:21,845 INFO L87 Difference]: Start difference. First operand 52 states and 72 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:25,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:25,402 INFO L93 Difference]: Finished difference Result 98 states and 135 transitions. [2022-04-08 11:29:25,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 11:29:25,402 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:29:25,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:29:25,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:25,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 86 transitions. [2022-04-08 11:29:25,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:25,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 86 transitions. [2022-04-08 11:29:25,405 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 86 transitions. [2022-04-08 11:29:25,500 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 86 edges. 86 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:25,502 INFO L225 Difference]: With dead ends: 98 [2022-04-08 11:29:25,502 INFO L226 Difference]: Without dead ends: 64 [2022-04-08 11:29:25,503 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-08 11:29:25,503 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 8 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 11:29:25,504 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 170 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 11:29:25,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-08 11:29:25,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 62. [2022-04-08 11:29:25,543 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:29:25,543 INFO L82 GeneralOperation]: Start isEquivalent. First operand 64 states. Second operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:29:25,543 INFO L74 IsIncluded]: Start isIncluded. First operand 64 states. Second operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:29:25,544 INFO L87 Difference]: Start difference. First operand 64 states. Second operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:29:25,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:25,546 INFO L93 Difference]: Finished difference Result 64 states and 83 transitions. [2022-04-08 11:29:25,546 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 83 transitions. [2022-04-08 11:29:25,546 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:25,547 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:25,547 INFO L74 IsIncluded]: Start isIncluded. First operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Second operand 64 states. [2022-04-08 11:29:25,547 INFO L87 Difference]: Start difference. First operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Second operand 64 states. [2022-04-08 11:29:25,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:25,549 INFO L93 Difference]: Finished difference Result 64 states and 83 transitions. [2022-04-08 11:29:25,549 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 83 transitions. [2022-04-08 11:29:25,550 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:25,550 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:25,550 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:29:25,550 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:29:25,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:29:25,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 82 transitions. [2022-04-08 11:29:25,552 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 82 transitions. Word has length 23 [2022-04-08 11:29:25,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:29:25,552 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 82 transitions. [2022-04-08 11:29:25,553 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:25,553 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 62 states and 82 transitions. [2022-04-08 11:29:25,635 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 82 edges. 82 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:25,635 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 82 transitions. [2022-04-08 11:29:25,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-08 11:29:25,636 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:29:25,636 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:29:25,655 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 11:29:25,836 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:25,836 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:29:25,837 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:29:25,837 INFO L85 PathProgramCache]: Analyzing trace with hash -1562772727, now seen corresponding path program 1 times [2022-04-08 11:29:25,837 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:25,837 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1667316070] [2022-04-08 11:29:25,850 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:29:25,850 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:29:25,850 INFO L85 PathProgramCache]: Analyzing trace with hash -1562772727, now seen corresponding path program 2 times [2022-04-08 11:29:25,850 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:29:25,850 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1857147967] [2022-04-08 11:29:25,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:29:25,851 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:29:25,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:25,995 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:29:25,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:26,002 INFO L290 TraceCheckUtils]: 0: Hoare triple {2323#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2309#true} is VALID [2022-04-08 11:29:26,002 INFO L290 TraceCheckUtils]: 1: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:29:26,002 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {2309#true} {2309#true} #102#return; {2309#true} is VALID [2022-04-08 11:29:26,002 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:29:26,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:26,006 INFO L290 TraceCheckUtils]: 0: Hoare triple {2309#true} ~cond := #in~cond; {2309#true} is VALID [2022-04-08 11:29:26,006 INFO L290 TraceCheckUtils]: 1: Hoare triple {2309#true} assume !(0 == ~cond); {2309#true} is VALID [2022-04-08 11:29:26,006 INFO L290 TraceCheckUtils]: 2: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:29:26,006 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2309#true} {2309#true} #82#return; {2309#true} is VALID [2022-04-08 11:29:26,007 INFO L272 TraceCheckUtils]: 0: Hoare triple {2309#true} call ULTIMATE.init(); {2323#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:29:26,007 INFO L290 TraceCheckUtils]: 1: Hoare triple {2323#(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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2309#true} is VALID [2022-04-08 11:29:26,007 INFO L290 TraceCheckUtils]: 2: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:29:26,007 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2309#true} {2309#true} #102#return; {2309#true} is VALID [2022-04-08 11:29:26,007 INFO L272 TraceCheckUtils]: 4: Hoare triple {2309#true} call #t~ret7 := main(); {2309#true} is VALID [2022-04-08 11:29:26,007 INFO L290 TraceCheckUtils]: 5: Hoare triple {2309#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {2309#true} is VALID [2022-04-08 11:29:26,008 INFO L272 TraceCheckUtils]: 6: Hoare triple {2309#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2309#true} is VALID [2022-04-08 11:29:26,008 INFO L290 TraceCheckUtils]: 7: Hoare triple {2309#true} ~cond := #in~cond; {2309#true} is VALID [2022-04-08 11:29:26,008 INFO L290 TraceCheckUtils]: 8: Hoare triple {2309#true} assume !(0 == ~cond); {2309#true} is VALID [2022-04-08 11:29:26,008 INFO L290 TraceCheckUtils]: 9: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:29:26,008 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2309#true} {2309#true} #82#return; {2309#true} is VALID [2022-04-08 11:29:26,008 INFO L290 TraceCheckUtils]: 11: Hoare triple {2309#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} is VALID [2022-04-08 11:29:26,009 INFO L290 TraceCheckUtils]: 12: Hoare triple {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} is VALID [2022-04-08 11:29:26,009 INFO L290 TraceCheckUtils]: 13: Hoare triple {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} assume !!(#t~post5 < 20);havoc #t~post5; {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} is VALID [2022-04-08 11:29:26,010 INFO L290 TraceCheckUtils]: 14: Hoare triple {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,010 INFO L290 TraceCheckUtils]: 15: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,010 INFO L290 TraceCheckUtils]: 16: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(#t~post5 < 20);havoc #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,011 INFO L290 TraceCheckUtils]: 17: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:29:26,012 INFO L290 TraceCheckUtils]: 18: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:29:26,012 INFO L290 TraceCheckUtils]: 19: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} assume !!(#t~post6 < 20);havoc #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:29:26,013 INFO L272 TraceCheckUtils]: 20: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2321#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 11:29:26,013 INFO L290 TraceCheckUtils]: 21: Hoare triple {2321#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {2322#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 11:29:26,014 INFO L290 TraceCheckUtils]: 22: Hoare triple {2322#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {2310#false} is VALID [2022-04-08 11:29:26,014 INFO L290 TraceCheckUtils]: 23: Hoare triple {2310#false} assume !false; {2310#false} is VALID [2022-04-08 11:29:26,014 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:29:26,014 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:29:26,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1857147967] [2022-04-08 11:29:26,014 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1857147967] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-08 11:29:26,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [108154447] [2022-04-08 11:29:26,014 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:29:26,014 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:26,014 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:29:26,032 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 11:29:26,056 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 11:29:26,083 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:29:26,084 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:29:26,084 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 8 conjunts are in the unsatisfiable core [2022-04-08 11:29:26,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:26,091 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:29:26,811 INFO L272 TraceCheckUtils]: 0: Hoare triple {2309#true} call ULTIMATE.init(); {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L290 TraceCheckUtils]: 1: Hoare triple {2309#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L290 TraceCheckUtils]: 2: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2309#true} {2309#true} #102#return; {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L272 TraceCheckUtils]: 4: Hoare triple {2309#true} call #t~ret7 := main(); {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L290 TraceCheckUtils]: 5: Hoare triple {2309#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L272 TraceCheckUtils]: 6: Hoare triple {2309#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L290 TraceCheckUtils]: 7: Hoare triple {2309#true} ~cond := #in~cond; {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L290 TraceCheckUtils]: 8: Hoare triple {2309#true} assume !(0 == ~cond); {2309#true} is VALID [2022-04-08 11:29:26,811 INFO L290 TraceCheckUtils]: 9: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:29:26,812 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2309#true} {2309#true} #82#return; {2309#true} is VALID [2022-04-08 11:29:26,812 INFO L290 TraceCheckUtils]: 11: Hoare triple {2309#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,812 INFO L290 TraceCheckUtils]: 12: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,813 INFO L290 TraceCheckUtils]: 13: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(#t~post5 < 20);havoc #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,813 INFO L290 TraceCheckUtils]: 14: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,813 INFO L290 TraceCheckUtils]: 15: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,814 INFO L290 TraceCheckUtils]: 16: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(#t~post5 < 20);havoc #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:29:26,814 INFO L290 TraceCheckUtils]: 17: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:29:26,815 INFO L290 TraceCheckUtils]: 18: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:29:26,815 INFO L290 TraceCheckUtils]: 19: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} assume !!(#t~post6 < 20);havoc #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:29:26,816 INFO L272 TraceCheckUtils]: 20: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2387#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 11:29:26,817 INFO L290 TraceCheckUtils]: 21: Hoare triple {2387#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2391#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 11:29:26,817 INFO L290 TraceCheckUtils]: 22: Hoare triple {2391#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2310#false} is VALID [2022-04-08 11:29:26,817 INFO L290 TraceCheckUtils]: 23: Hoare triple {2310#false} assume !false; {2310#false} is VALID [2022-04-08 11:29:26,817 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-08 11:29:26,817 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:29:26,818 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [108154447] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:26,818 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-08 11:29:26,818 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 10 [2022-04-08 11:29:26,818 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:29:26,818 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1667316070] [2022-04-08 11:29:26,818 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1667316070] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:26,818 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:29:26,818 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 11:29:26,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1424537502] [2022-04-08 11:29:26,818 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:29:26,819 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-04-08 11:29:26,819 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:29:26,819 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:26,834 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 11:29:26,834 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-08 11:29:26,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:26,835 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-08 11:29:26,835 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-08 11:29:26,835 INFO L87 Difference]: Start difference. First operand 62 states and 82 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:34,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:34,417 INFO L93 Difference]: Finished difference Result 85 states and 114 transitions. [2022-04-08 11:29:34,417 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-08 11:29:34,417 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-04-08 11:29:34,417 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:29:34,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:34,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 95 transitions. [2022-04-08 11:29:34,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:34,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 95 transitions. [2022-04-08 11:29:34,420 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 95 transitions. [2022-04-08 11:29:34,783 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 95 edges. 95 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:34,785 INFO L225 Difference]: With dead ends: 85 [2022-04-08 11:29:34,785 INFO L226 Difference]: Without dead ends: 69 [2022-04-08 11:29:34,785 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-08 11:29:34,786 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 16 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 150 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2022-04-08 11:29:34,786 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 182 Invalid, 150 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2022-04-08 11:29:34,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-04-08 11:29:34,814 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2022-04-08 11:29:34,815 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:29:34,815 INFO L82 GeneralOperation]: Start isEquivalent. First operand 69 states. Second operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:29:34,815 INFO L74 IsIncluded]: Start isIncluded. First operand 69 states. Second operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:29:34,815 INFO L87 Difference]: Start difference. First operand 69 states. Second operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:29:34,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:34,817 INFO L93 Difference]: Finished difference Result 69 states and 92 transitions. [2022-04-08 11:29:34,818 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 92 transitions. [2022-04-08 11:29:34,818 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:34,818 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:34,818 INFO L74 IsIncluded]: Start isIncluded. First operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand 69 states. [2022-04-08 11:29:34,818 INFO L87 Difference]: Start difference. First operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand 69 states. [2022-04-08 11:29:34,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:34,820 INFO L93 Difference]: Finished difference Result 69 states and 92 transitions. [2022-04-08 11:29:34,820 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 92 transitions. [2022-04-08 11:29:34,821 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:34,821 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:34,821 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:29:34,821 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:29:34,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:29:34,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 92 transitions. [2022-04-08 11:29:34,823 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 92 transitions. Word has length 24 [2022-04-08 11:29:34,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:29:34,823 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 92 transitions. [2022-04-08 11:29:34,823 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:29:34,823 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 69 states and 92 transitions. [2022-04-08 11:29:35,179 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 92 edges. 92 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:35,179 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 92 transitions. [2022-04-08 11:29:35,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-08 11:29:35,180 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:29:35,180 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:29:35,216 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 11:29:35,381 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:35,381 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:29:35,381 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:29:35,381 INFO L85 PathProgramCache]: Analyzing trace with hash 107903087, now seen corresponding path program 1 times [2022-04-08 11:29:35,381 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:35,381 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1823509468] [2022-04-08 11:29:35,388 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:29:35,388 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:29:35,388 INFO L85 PathProgramCache]: Analyzing trace with hash 107903087, now seen corresponding path program 2 times [2022-04-08 11:29:35,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:29:35,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1502615076] [2022-04-08 11:29:35,389 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:29:35,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:29:35,415 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:29:35,424 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [246526468] [2022-04-08 11:29:35,425 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:29:35,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:35,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:29:35,440 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 11:29:35,467 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 11:29:35,528 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 11:29:35,528 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:29:35,529 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-08 11:29:35,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:29:35,543 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:29:35,823 INFO L272 TraceCheckUtils]: 0: Hoare triple {2847#true} call ULTIMATE.init(); {2847#true} is VALID [2022-04-08 11:29:35,823 INFO L290 TraceCheckUtils]: 1: Hoare triple {2847#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,824 INFO L290 TraceCheckUtils]: 2: Hoare triple {2855#(<= ~counter~0 0)} assume true; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,824 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2855#(<= ~counter~0 0)} {2847#true} #102#return; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,824 INFO L272 TraceCheckUtils]: 4: Hoare triple {2855#(<= ~counter~0 0)} call #t~ret7 := main(); {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,825 INFO L290 TraceCheckUtils]: 5: Hoare triple {2855#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,825 INFO L272 TraceCheckUtils]: 6: Hoare triple {2855#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,826 INFO L290 TraceCheckUtils]: 7: Hoare triple {2855#(<= ~counter~0 0)} ~cond := #in~cond; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,826 INFO L290 TraceCheckUtils]: 8: Hoare triple {2855#(<= ~counter~0 0)} assume !(0 == ~cond); {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,826 INFO L290 TraceCheckUtils]: 9: Hoare triple {2855#(<= ~counter~0 0)} assume true; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,827 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2855#(<= ~counter~0 0)} {2855#(<= ~counter~0 0)} #82#return; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,827 INFO L290 TraceCheckUtils]: 11: Hoare triple {2855#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:29:35,827 INFO L290 TraceCheckUtils]: 12: Hoare triple {2855#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2889#(<= ~counter~0 1)} is VALID [2022-04-08 11:29:35,828 INFO L290 TraceCheckUtils]: 13: Hoare triple {2889#(<= ~counter~0 1)} assume !!(#t~post5 < 20);havoc #t~post5; {2889#(<= ~counter~0 1)} is VALID [2022-04-08 11:29:35,828 INFO L290 TraceCheckUtils]: 14: Hoare triple {2889#(<= ~counter~0 1)} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {2889#(<= ~counter~0 1)} is VALID [2022-04-08 11:29:35,828 INFO L290 TraceCheckUtils]: 15: Hoare triple {2889#(<= ~counter~0 1)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2899#(<= ~counter~0 2)} is VALID [2022-04-08 11:29:35,829 INFO L290 TraceCheckUtils]: 16: Hoare triple {2899#(<= ~counter~0 2)} assume !!(#t~post5 < 20);havoc #t~post5; {2899#(<= ~counter~0 2)} is VALID [2022-04-08 11:29:35,829 INFO L290 TraceCheckUtils]: 17: Hoare triple {2899#(<= ~counter~0 2)} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {2899#(<= ~counter~0 2)} is VALID [2022-04-08 11:29:35,830 INFO L290 TraceCheckUtils]: 18: Hoare triple {2899#(<= ~counter~0 2)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,830 INFO L290 TraceCheckUtils]: 19: Hoare triple {2909#(<= ~counter~0 3)} assume !!(#t~post6 < 20);havoc #t~post6; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,831 INFO L272 TraceCheckUtils]: 20: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,831 INFO L290 TraceCheckUtils]: 21: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,831 INFO L290 TraceCheckUtils]: 22: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,832 INFO L290 TraceCheckUtils]: 23: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,832 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #84#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,833 INFO L272 TraceCheckUtils]: 25: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,833 INFO L290 TraceCheckUtils]: 26: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,833 INFO L290 TraceCheckUtils]: 27: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,834 INFO L290 TraceCheckUtils]: 28: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,834 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #86#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,835 INFO L272 TraceCheckUtils]: 30: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,836 INFO L290 TraceCheckUtils]: 31: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,836 INFO L290 TraceCheckUtils]: 32: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,836 INFO L290 TraceCheckUtils]: 33: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,837 INFO L284 TraceCheckUtils]: 34: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #88#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,838 INFO L272 TraceCheckUtils]: 35: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~n~0 - 4 * ~h~0 * ~n~0 * ~p~0 + 4 * (~n~0 * ~n~0) * ~q~0 - ~n~0 * ~q~0 * ~q~0 - ~h~0 * ~h~0 * ~r~0 + 4 * ~h~0 * ~p~0 * ~r~0 - 8 * ~n~0 * ~q~0 * ~r~0 + ~q~0 * ~q~0 * ~r~0 + 4 * ~q~0 * ~r~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,838 INFO L290 TraceCheckUtils]: 36: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,838 INFO L290 TraceCheckUtils]: 37: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,839 INFO L290 TraceCheckUtils]: 38: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,839 INFO L284 TraceCheckUtils]: 39: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #90#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,840 INFO L272 TraceCheckUtils]: 40: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~p~0 - 4 * ~h~0 * ~n~0 * ~q~0 + 4 * ~n~0 * ~p~0 * ~q~0 - ~p~0 * ~q~0 * ~q~0 + 4 * ~h~0 * ~q~0 * ~r~0 - 4 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,840 INFO L290 TraceCheckUtils]: 41: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,841 INFO L290 TraceCheckUtils]: 42: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,841 INFO L290 TraceCheckUtils]: 43: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,841 INFO L284 TraceCheckUtils]: 44: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #92#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,842 INFO L272 TraceCheckUtils]: 45: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~p~0 * ~p~0 - ~n~0 * ~q~0 + ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,842 INFO L290 TraceCheckUtils]: 46: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,842 INFO L290 TraceCheckUtils]: 47: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,843 INFO L290 TraceCheckUtils]: 48: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,843 INFO L284 TraceCheckUtils]: 49: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #94#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,844 INFO L290 TraceCheckUtils]: 50: Hoare triple {2909#(<= ~counter~0 3)} assume !!(1 != ~q~0 % 4294967296);~q~0 := (if ~q~0 % 4294967296 < 0 && 0 != ~q~0 % 4294967296 % 4 then 1 + ~q~0 % 4294967296 / 4 else ~q~0 % 4294967296 / 4);~h~0 := ~p~0 + ~q~0;~p~0 := (if ~p~0 % 4294967296 < 0 && 0 != ~p~0 % 4294967296 % 2 then 1 + ~p~0 % 4294967296 / 2 else ~p~0 % 4294967296 / 2); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,844 INFO L290 TraceCheckUtils]: 51: Hoare triple {2909#(<= ~counter~0 3)} assume ~r~0 % 4294967296 >= ~h~0 % 4294967296;~p~0 := ~p~0 + ~q~0;~r~0 := ~r~0 - ~h~0; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:29:35,844 INFO L290 TraceCheckUtils]: 52: Hoare triple {2909#(<= ~counter~0 3)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3012#(<= |main_#t~post6| 3)} is VALID [2022-04-08 11:29:35,845 INFO L290 TraceCheckUtils]: 53: Hoare triple {3012#(<= |main_#t~post6| 3)} assume !(#t~post6 < 20);havoc #t~post6; {2848#false} is VALID [2022-04-08 11:29:35,845 INFO L272 TraceCheckUtils]: 54: Hoare triple {2848#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {2848#false} is VALID [2022-04-08 11:29:35,845 INFO L290 TraceCheckUtils]: 55: Hoare triple {2848#false} ~cond := #in~cond; {2848#false} is VALID [2022-04-08 11:29:35,845 INFO L290 TraceCheckUtils]: 56: Hoare triple {2848#false} assume 0 == ~cond; {2848#false} is VALID [2022-04-08 11:29:35,845 INFO L290 TraceCheckUtils]: 57: Hoare triple {2848#false} assume !false; {2848#false} is VALID [2022-04-08 11:29:35,845 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-08 11:29:35,845 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 11:29:36,148 INFO L290 TraceCheckUtils]: 57: Hoare triple {2848#false} assume !false; {2848#false} is VALID [2022-04-08 11:29:36,148 INFO L290 TraceCheckUtils]: 56: Hoare triple {2848#false} assume 0 == ~cond; {2848#false} is VALID [2022-04-08 11:29:36,148 INFO L290 TraceCheckUtils]: 55: Hoare triple {2848#false} ~cond := #in~cond; {2848#false} is VALID [2022-04-08 11:29:36,148 INFO L272 TraceCheckUtils]: 54: Hoare triple {2848#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {2848#false} is VALID [2022-04-08 11:29:36,149 INFO L290 TraceCheckUtils]: 53: Hoare triple {3040#(< |main_#t~post6| 20)} assume !(#t~post6 < 20);havoc #t~post6; {2848#false} is VALID [2022-04-08 11:29:36,149 INFO L290 TraceCheckUtils]: 52: Hoare triple {3044#(< ~counter~0 20)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3040#(< |main_#t~post6| 20)} is VALID [2022-04-08 11:29:36,149 INFO L290 TraceCheckUtils]: 51: Hoare triple {3044#(< ~counter~0 20)} assume ~r~0 % 4294967296 >= ~h~0 % 4294967296;~p~0 := ~p~0 + ~q~0;~r~0 := ~r~0 - ~h~0; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,149 INFO L290 TraceCheckUtils]: 50: Hoare triple {3044#(< ~counter~0 20)} assume !!(1 != ~q~0 % 4294967296);~q~0 := (if ~q~0 % 4294967296 < 0 && 0 != ~q~0 % 4294967296 % 4 then 1 + ~q~0 % 4294967296 / 4 else ~q~0 % 4294967296 / 4);~h~0 := ~p~0 + ~q~0;~p~0 := (if ~p~0 % 4294967296 < 0 && 0 != ~p~0 % 4294967296 % 2 then 1 + ~p~0 % 4294967296 / 2 else ~p~0 % 4294967296 / 2); {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,150 INFO L284 TraceCheckUtils]: 49: Hoare quadruple {2847#true} {3044#(< ~counter~0 20)} #94#return; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,150 INFO L290 TraceCheckUtils]: 48: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,150 INFO L290 TraceCheckUtils]: 47: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,150 INFO L290 TraceCheckUtils]: 46: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,150 INFO L272 TraceCheckUtils]: 45: Hoare triple {3044#(< ~counter~0 20)} call __VERIFIER_assert((if 0 == (~p~0 * ~p~0 - ~n~0 * ~q~0 + ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,151 INFO L284 TraceCheckUtils]: 44: Hoare quadruple {2847#true} {3044#(< ~counter~0 20)} #92#return; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,151 INFO L290 TraceCheckUtils]: 43: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,151 INFO L290 TraceCheckUtils]: 42: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,151 INFO L290 TraceCheckUtils]: 41: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,152 INFO L272 TraceCheckUtils]: 40: Hoare triple {3044#(< ~counter~0 20)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~p~0 - 4 * ~h~0 * ~n~0 * ~q~0 + 4 * ~n~0 * ~p~0 * ~q~0 - ~p~0 * ~q~0 * ~q~0 + 4 * ~h~0 * ~q~0 * ~r~0 - 4 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,152 INFO L284 TraceCheckUtils]: 39: Hoare quadruple {2847#true} {3044#(< ~counter~0 20)} #90#return; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,152 INFO L290 TraceCheckUtils]: 38: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,153 INFO L290 TraceCheckUtils]: 37: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,153 INFO L290 TraceCheckUtils]: 36: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,154 INFO L272 TraceCheckUtils]: 35: Hoare triple {3044#(< ~counter~0 20)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~n~0 - 4 * ~h~0 * ~n~0 * ~p~0 + 4 * (~n~0 * ~n~0) * ~q~0 - ~n~0 * ~q~0 * ~q~0 - ~h~0 * ~h~0 * ~r~0 + 4 * ~h~0 * ~p~0 * ~r~0 - 8 * ~n~0 * ~q~0 * ~r~0 + ~q~0 * ~q~0 * ~r~0 + 4 * ~q~0 * ~r~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,155 INFO L284 TraceCheckUtils]: 34: Hoare quadruple {2847#true} {3044#(< ~counter~0 20)} #88#return; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,155 INFO L290 TraceCheckUtils]: 33: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,155 INFO L290 TraceCheckUtils]: 32: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,155 INFO L290 TraceCheckUtils]: 31: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,155 INFO L272 TraceCheckUtils]: 30: Hoare triple {3044#(< ~counter~0 20)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,156 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {2847#true} {3044#(< ~counter~0 20)} #86#return; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,156 INFO L290 TraceCheckUtils]: 28: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,156 INFO L290 TraceCheckUtils]: 27: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,156 INFO L290 TraceCheckUtils]: 26: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,156 INFO L272 TraceCheckUtils]: 25: Hoare triple {3044#(< ~counter~0 20)} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,156 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {2847#true} {3044#(< ~counter~0 20)} #84#return; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,156 INFO L290 TraceCheckUtils]: 23: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,156 INFO L290 TraceCheckUtils]: 22: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,157 INFO L290 TraceCheckUtils]: 21: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,157 INFO L272 TraceCheckUtils]: 20: Hoare triple {3044#(< ~counter~0 20)} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,157 INFO L290 TraceCheckUtils]: 19: Hoare triple {3044#(< ~counter~0 20)} assume !!(#t~post6 < 20);havoc #t~post6; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,157 INFO L290 TraceCheckUtils]: 18: Hoare triple {3147#(< ~counter~0 19)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3044#(< ~counter~0 20)} is VALID [2022-04-08 11:29:36,158 INFO L290 TraceCheckUtils]: 17: Hoare triple {3147#(< ~counter~0 19)} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {3147#(< ~counter~0 19)} is VALID [2022-04-08 11:29:36,158 INFO L290 TraceCheckUtils]: 16: Hoare triple {3147#(< ~counter~0 19)} assume !!(#t~post5 < 20);havoc #t~post5; {3147#(< ~counter~0 19)} is VALID [2022-04-08 11:29:36,158 INFO L290 TraceCheckUtils]: 15: Hoare triple {3157#(< ~counter~0 18)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3147#(< ~counter~0 19)} is VALID [2022-04-08 11:29:36,158 INFO L290 TraceCheckUtils]: 14: Hoare triple {3157#(< ~counter~0 18)} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {3157#(< ~counter~0 18)} is VALID [2022-04-08 11:29:36,159 INFO L290 TraceCheckUtils]: 13: Hoare triple {3157#(< ~counter~0 18)} assume !!(#t~post5 < 20);havoc #t~post5; {3157#(< ~counter~0 18)} is VALID [2022-04-08 11:29:36,159 INFO L290 TraceCheckUtils]: 12: Hoare triple {3167#(< ~counter~0 17)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3157#(< ~counter~0 18)} is VALID [2022-04-08 11:29:36,159 INFO L290 TraceCheckUtils]: 11: Hoare triple {3167#(< ~counter~0 17)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,160 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2847#true} {3167#(< ~counter~0 17)} #82#return; {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,160 INFO L290 TraceCheckUtils]: 9: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:29:36,160 INFO L290 TraceCheckUtils]: 8: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:29:36,160 INFO L290 TraceCheckUtils]: 7: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:29:36,160 INFO L272 TraceCheckUtils]: 6: Hoare triple {3167#(< ~counter~0 17)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:29:36,160 INFO L290 TraceCheckUtils]: 5: Hoare triple {3167#(< ~counter~0 17)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,161 INFO L272 TraceCheckUtils]: 4: Hoare triple {3167#(< ~counter~0 17)} call #t~ret7 := main(); {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,161 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3167#(< ~counter~0 17)} {2847#true} #102#return; {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,161 INFO L290 TraceCheckUtils]: 2: Hoare triple {3167#(< ~counter~0 17)} assume true; {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,162 INFO L290 TraceCheckUtils]: 1: Hoare triple {2847#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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3167#(< ~counter~0 17)} is VALID [2022-04-08 11:29:36,162 INFO L272 TraceCheckUtils]: 0: Hoare triple {2847#true} call ULTIMATE.init(); {2847#true} is VALID [2022-04-08 11:29:36,162 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-08 11:29:36,162 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:29:36,162 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1502615076] [2022-04-08 11:29:36,162 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:29:36,162 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [246526468] [2022-04-08 11:29:36,163 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [246526468] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 11:29:36,163 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 11:29:36,163 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-04-08 11:29:36,163 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:29:36,163 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1823509468] [2022-04-08 11:29:36,163 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1823509468] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:29:36,163 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:29:36,163 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-08 11:29:36,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1121136468] [2022-04-08 11:29:36,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:29:36,164 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 58 [2022-04-08 11:29:36,164 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:29:36,164 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:29:36,213 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 43 edges. 43 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:36,213 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-08 11:29:36,214 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:36,215 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-08 11:29:36,215 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2022-04-08 11:29:36,215 INFO L87 Difference]: Start difference. First operand 69 states and 92 transitions. Second operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:29:50,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:50,976 INFO L93 Difference]: Finished difference Result 114 states and 146 transitions. [2022-04-08 11:29:50,976 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-08 11:29:50,976 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 58 [2022-04-08 11:29:50,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:29:50,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:29:50,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-08 11:29:50,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:29:50,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-08 11:29:50,979 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 90 transitions. [2022-04-08 11:29:51,045 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 90 edges. 90 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:51,047 INFO L225 Difference]: With dead ends: 114 [2022-04-08 11:29:51,047 INFO L226 Difference]: Without dead ends: 104 [2022-04-08 11:29:51,047 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=97, Unknown=0, NotChecked=0, Total=156 [2022-04-08 11:29:51,048 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 21 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2022-04-08 11:29:51,048 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 157 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2022-04-08 11:29:51,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-04-08 11:29:51,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 98. [2022-04-08 11:29:51,116 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:29:51,116 INFO L82 GeneralOperation]: Start isEquivalent. First operand 104 states. Second operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:29:51,124 INFO L74 IsIncluded]: Start isIncluded. First operand 104 states. Second operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:29:51,127 INFO L87 Difference]: Start difference. First operand 104 states. Second operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:29:51,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:51,138 INFO L93 Difference]: Finished difference Result 104 states and 133 transitions. [2022-04-08 11:29:51,138 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 133 transitions. [2022-04-08 11:29:51,155 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:51,155 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:51,155 INFO L74 IsIncluded]: Start isIncluded. First operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand 104 states. [2022-04-08 11:29:51,156 INFO L87 Difference]: Start difference. First operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand 104 states. [2022-04-08 11:29:51,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:29:51,158 INFO L93 Difference]: Finished difference Result 104 states and 133 transitions. [2022-04-08 11:29:51,158 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 133 transitions. [2022-04-08 11:29:51,159 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:29:51,159 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:29:51,159 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:29:51,159 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:29:51,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:29:51,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 126 transitions. [2022-04-08 11:29:51,161 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 126 transitions. Word has length 58 [2022-04-08 11:29:51,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:29:51,163 INFO L478 AbstractCegarLoop]: Abstraction has 98 states and 126 transitions. [2022-04-08 11:29:51,163 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:29:51,163 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 98 states and 126 transitions. [2022-04-08 11:29:51,601 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 126 edges. 126 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:29:51,602 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 126 transitions. [2022-04-08 11:29:51,602 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-08 11:29:51,602 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:29:51,602 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:29:51,608 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-04-08 11:29:51,809 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:51,810 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:29:51,810 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:29:51,810 INFO L85 PathProgramCache]: Analyzing trace with hash 109392637, now seen corresponding path program 1 times [2022-04-08 11:29:51,810 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:29:51,810 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2136882981] [2022-04-08 11:29:51,816 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:29:51,816 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:29:51,816 INFO L85 PathProgramCache]: Analyzing trace with hash 109392637, now seen corresponding path program 2 times [2022-04-08 11:29:51,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:29:51,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [485801779] [2022-04-08 11:29:51,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:29:51,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:29:51,836 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:29:51,837 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1455933044] [2022-04-08 11:29:51,837 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:29:51,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:29:51,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:29:51,856 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:29:51,870 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process