/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-u_valuebound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 09:34:40,376 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 09:34:40,378 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 09:34:40,428 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 09:34:40,429 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 09:34:40,431 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 09:34:40,434 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 09:34:40,437 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 09:34:40,439 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 09:34:40,443 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 09:34:40,444 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 09:34:40,446 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 09:34:40,446 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 09:34:40,448 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 09:34:40,450 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 09:34:40,453 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 09:34:40,453 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 09:34:40,454 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 09:34:40,457 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 09:34:40,462 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 09:34:40,464 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 09:34:40,466 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 09:34:40,467 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 09:34:40,468 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 09:34:40,469 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 09:34:40,475 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 09:34:40,476 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 09:34:40,476 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 09:34:40,477 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 09:34:40,477 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 09:34:40,479 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 09:34:40,479 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 09:34:40,481 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 09:34:40,482 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 09:34:40,482 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 09:34:40,483 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 09:34:40,483 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 09:34:40,484 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 09:34:40,484 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 09:34:40,484 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 09:34:40,485 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 09:34:40,487 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 09:34:40,487 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-15 09:34:40,499 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 09:34:40,500 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 09:34:40,502 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 09:34:40,502 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-15 09:34:40,502 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 09:34:40,502 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-15 09:34:40,502 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 09:34:40,503 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 09:34:40,503 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 09:34:40,504 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 09:34:40,504 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-15 09:34:40,504 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 09:34:40,504 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 09:34:40,504 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 09:34:40,504 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 09:34:40,505 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 09:34:40,505 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 09:34:40,506 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 09:34:40,506 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-15 09:34:40,506 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-15 09:34:40,758 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 09:34:40,776 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 09:34:40,779 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 09:34:40,780 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 09:34:40,780 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 09:34:40,782 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-u_valuebound5.c [2022-04-15 09:34:40,853 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f15d0b0d0/913a0018e3c8462fa849565642767e34/FLAG48954ebc5 [2022-04-15 09:34:41,353 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 09:34:41,354 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_valuebound5.c [2022-04-15 09:34:41,368 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f15d0b0d0/913a0018e3c8462fa849565642767e34/FLAG48954ebc5 [2022-04-15 09:34:41,828 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f15d0b0d0/913a0018e3c8462fa849565642767e34 [2022-04-15 09:34:41,831 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 09:34:41,832 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 09:34:41,835 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 09:34:41,836 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 09:34:41,839 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 09:34:41,840 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 09:34:41" (1/1) ... [2022-04-15 09:34:41,841 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1e23fbac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:41, skipping insertion in model container [2022-04-15 09:34:41,841 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 09:34:41" (1/1) ... [2022-04-15 09:34:41,847 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 09:34:41,859 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 09:34:42,017 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/hard-u_valuebound5.c[537,550] [2022-04-15 09:34:42,035 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 09:34:42,042 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 09:34:42,054 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/hard-u_valuebound5.c[537,550] [2022-04-15 09:34:42,063 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 09:34:42,075 INFO L208 MainTranslator]: Completed translation [2022-04-15 09:34:42,075 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42 WrapperNode [2022-04-15 09:34:42,075 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 09:34:42,076 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 09:34:42,076 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 09:34:42,077 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 09:34:42,086 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,086 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,092 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,092 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,098 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,102 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,103 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,106 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 09:34:42,106 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 09:34:42,107 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 09:34:42,107 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 09:34:42,108 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (1/1) ... [2022-04-15 09:34:42,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 09:34:42,136 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:34:42,157 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-15 09:34:42,165 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-15 09:34:42,209 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 09:34:42,209 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 09:34:42,209 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 09:34:42,209 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 09:34:42,209 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 09:34:42,209 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 09:34:42,210 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 09:34:42,210 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 09:34:42,210 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 09:34:42,211 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 09:34:42,211 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-15 09:34:42,212 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 09:34:42,212 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 09:34:42,212 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 09:34:42,213 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 09:34:42,213 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 09:34:42,213 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 09:34:42,213 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 09:34:42,213 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 09:34:42,213 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 09:34:42,275 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 09:34:42,277 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 09:34:42,522 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 09:34:42,528 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 09:34:42,528 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-15 09:34:42,530 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 09:34:42 BoogieIcfgContainer [2022-04-15 09:34:42,530 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 09:34:42,544 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 09:34:42,544 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 09:34:42,556 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 09:34:42,557 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 09:34:41" (1/3) ... [2022-04-15 09:34:42,557 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7ba989c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 09:34:42, skipping insertion in model container [2022-04-15 09:34:42,557 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:34:42" (2/3) ... [2022-04-15 09:34:42,558 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7ba989c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 09:34:42, skipping insertion in model container [2022-04-15 09:34:42,558 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 09:34:42" (3/3) ... [2022-04-15 09:34:42,560 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-u_valuebound5.c [2022-04-15 09:34:42,565 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 09:34:42,566 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 09:34:42,623 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 09:34:42,630 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-15 09:34:42,631 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 09:34:42,660 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 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-15 09:34:42,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-15 09:34:42,667 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:34:42,668 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:34:42,669 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:34:42,673 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:34:42,674 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 1 times [2022-04-15 09:34:42,683 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:42,684 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [192232665] [2022-04-15 09:34:42,695 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:34:42,696 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 2 times [2022-04-15 09:34:42,698 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:34:42,699 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [932830845] [2022-04-15 09:34:42,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:34:42,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:34:42,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:42,910 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 09:34:42,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:42,936 INFO L290 TraceCheckUtils]: 0: Hoare triple {58#(and (= |#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(9, 2);call #Ultimate.allocInit(12, 3); {41#true} is VALID [2022-04-15 09:34:42,936 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 09:34:42,936 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {41#true} {41#true} #101#return; {41#true} is VALID [2022-04-15 09:34:42,938 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 09:34:42,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:42,947 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 09:34:42,948 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 09:34:42,948 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 09:34:42,949 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-15 09:34:42,949 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-15 09:34:42,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:42,968 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 09:34:42,969 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 09:34:42,969 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 09:34:42,970 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-15 09:34:42,970 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-15 09:34:42,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:42,982 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 09:34:42,984 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 09:34:42,984 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 09:34:42,985 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {42#false} #85#return; {42#false} is VALID [2022-04-15 09:34:42,986 INFO L272 TraceCheckUtils]: 0: Hoare triple {41#true} call ULTIMATE.init(); {58#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 09:34:42,987 INFO L290 TraceCheckUtils]: 1: Hoare triple {58#(and (= |#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(9, 2);call #Ultimate.allocInit(12, 3); {41#true} is VALID [2022-04-15 09:34:42,987 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 09:34:42,987 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#true} {41#true} #101#return; {41#true} is VALID [2022-04-15 09:34:42,987 INFO L272 TraceCheckUtils]: 4: Hoare triple {41#true} call #t~ret6 := main(); {41#true} is VALID [2022-04-15 09:34:42,988 INFO L290 TraceCheckUtils]: 5: Hoare triple {41#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {41#true} is VALID [2022-04-15 09:34:42,988 INFO L272 TraceCheckUtils]: 6: Hoare triple {41#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {41#true} is VALID [2022-04-15 09:34:42,988 INFO L290 TraceCheckUtils]: 7: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 09:34:42,989 INFO L290 TraceCheckUtils]: 8: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 09:34:42,989 INFO L290 TraceCheckUtils]: 9: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 09:34:42,990 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-15 09:34:42,990 INFO L290 TraceCheckUtils]: 11: Hoare triple {42#false} ~B~0 := #t~nondet5;havoc #t~nondet5; {42#false} is VALID [2022-04-15 09:34:42,990 INFO L272 TraceCheckUtils]: 12: Hoare triple {42#false} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {41#true} is VALID [2022-04-15 09:34:42,990 INFO L290 TraceCheckUtils]: 13: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 09:34:42,991 INFO L290 TraceCheckUtils]: 14: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 09:34:42,992 INFO L290 TraceCheckUtils]: 15: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 09:34:42,992 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-15 09:34:42,992 INFO L272 TraceCheckUtils]: 17: Hoare triple {42#false} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {41#true} is VALID [2022-04-15 09:34:42,993 INFO L290 TraceCheckUtils]: 18: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 09:34:42,994 INFO L290 TraceCheckUtils]: 19: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 09:34:42,994 INFO L290 TraceCheckUtils]: 20: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 09:34:42,994 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {42#false} {42#false} #85#return; {42#false} is VALID [2022-04-15 09:34:42,995 INFO L290 TraceCheckUtils]: 22: Hoare triple {42#false} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {42#false} is VALID [2022-04-15 09:34:42,996 INFO L290 TraceCheckUtils]: 23: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-15 09:34:42,996 INFO L272 TraceCheckUtils]: 24: Hoare triple {42#false} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {42#false} is VALID [2022-04-15 09:34:42,996 INFO L290 TraceCheckUtils]: 25: Hoare triple {42#false} ~cond := #in~cond; {42#false} is VALID [2022-04-15 09:34:42,997 INFO L290 TraceCheckUtils]: 26: Hoare triple {42#false} assume 0 == ~cond; {42#false} is VALID [2022-04-15 09:34:42,997 INFO L290 TraceCheckUtils]: 27: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-15 09:34:42,998 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 09:34:42,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:34:42,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [932830845] [2022-04-15 09:34:42,999 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [932830845] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:43,000 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:43,000 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 09:34:43,005 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:34:43,006 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [192232665] [2022-04-15 09:34:43,006 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [192232665] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:43,006 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:43,006 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 09:34:43,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [441152540] [2022-04-15 09:34:43,008 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:34:43,014 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-15 09:34:43,017 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:34:43,021 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:34:43,061 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-15 09:34:43,061 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 09:34:43,061 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:43,089 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 09:34:43,090 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 09:34:43,093 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:34:43,344 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:43,345 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-04-15 09:34:43,345 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 09:34:43,346 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-15 09:34:43,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:34:43,348 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:34:43,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 110 transitions. [2022-04-15 09:34:43,367 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:34:43,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 110 transitions. [2022-04-15 09:34:43,381 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 110 transitions. [2022-04-15 09:34:43,518 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 110 edges. 110 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:43,529 INFO L225 Difference]: With dead ends: 69 [2022-04-15 09:34:43,529 INFO L226 Difference]: Without dead ends: 33 [2022-04-15 09:34:43,534 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 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-15 09:34:43,538 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 09:34:43,540 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 09:34:43,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-15 09:34:43,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-15 09:34:43,576 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:34:43,577 INFO L82 GeneralOperation]: Start isEquivalent. First operand 33 states. Second operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 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-15 09:34:43,578 INFO L74 IsIncluded]: Start isIncluded. First operand 33 states. Second operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 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-15 09:34:43,579 INFO L87 Difference]: Start difference. First operand 33 states. Second operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 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-15 09:34:43,583 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:43,583 INFO L93 Difference]: Finished difference Result 33 states and 43 transitions. [2022-04-15 09:34:43,583 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-15 09:34:43,584 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:43,584 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:43,585 INFO L74 IsIncluded]: Start isIncluded. First operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 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 33 states. [2022-04-15 09:34:43,585 INFO L87 Difference]: Start difference. First operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 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 33 states. [2022-04-15 09:34:43,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:43,589 INFO L93 Difference]: Finished difference Result 33 states and 43 transitions. [2022-04-15 09:34:43,589 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-15 09:34:43,589 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:43,590 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:43,590 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:34:43,590 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:34:43,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 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-15 09:34:43,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-04-15 09:34:43,594 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-04-15 09:34:43,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:34:43,595 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-04-15 09:34:43,595 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, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:34:43,595 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 43 transitions. [2022-04-15 09:34:43,658 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-15 09:34:43,658 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-15 09:34:43,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-15 09:34:43,659 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:34:43,659 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:34:43,672 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 09:34:43,672 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:34:43,673 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:34:43,673 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 1 times [2022-04-15 09:34:43,673 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:43,673 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1424063124] [2022-04-15 09:34:43,674 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:34:43,674 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 2 times [2022-04-15 09:34:43,674 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:34:43,674 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1918705812] [2022-04-15 09:34:43,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:34:43,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:34:43,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:43,805 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 09:34:43,808 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:43,819 INFO L290 TraceCheckUtils]: 0: Hoare triple {351#(and (= |#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(9, 2);call #Ultimate.allocInit(12, 3); {331#true} is VALID [2022-04-15 09:34:43,819 INFO L290 TraceCheckUtils]: 1: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,820 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {331#true} {331#true} #101#return; {331#true} is VALID [2022-04-15 09:34:43,820 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 09:34:43,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:43,827 INFO L290 TraceCheckUtils]: 0: Hoare triple {331#true} ~cond := #in~cond; {331#true} is VALID [2022-04-15 09:34:43,831 INFO L290 TraceCheckUtils]: 1: Hoare triple {331#true} assume !(0 == ~cond); {331#true} is VALID [2022-04-15 09:34:43,831 INFO L290 TraceCheckUtils]: 2: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,833 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {331#true} {331#true} #81#return; {331#true} is VALID [2022-04-15 09:34:43,833 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-15 09:34:43,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:43,842 INFO L290 TraceCheckUtils]: 0: Hoare triple {331#true} ~cond := #in~cond; {331#true} is VALID [2022-04-15 09:34:43,842 INFO L290 TraceCheckUtils]: 1: Hoare triple {331#true} assume !(0 == ~cond); {331#true} is VALID [2022-04-15 09:34:43,842 INFO L290 TraceCheckUtils]: 2: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,843 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {331#true} {331#true} #83#return; {331#true} is VALID [2022-04-15 09:34:43,844 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-15 09:34:43,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:43,855 INFO L290 TraceCheckUtils]: 0: Hoare triple {331#true} ~cond := #in~cond; {331#true} is VALID [2022-04-15 09:34:43,855 INFO L290 TraceCheckUtils]: 1: Hoare triple {331#true} assume !(0 == ~cond); {331#true} is VALID [2022-04-15 09:34:43,856 INFO L290 TraceCheckUtils]: 2: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,856 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {331#true} {331#true} #85#return; {331#true} is VALID [2022-04-15 09:34:43,857 INFO L272 TraceCheckUtils]: 0: Hoare triple {331#true} call ULTIMATE.init(); {351#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 09:34:43,857 INFO L290 TraceCheckUtils]: 1: Hoare triple {351#(and (= |#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(9, 2);call #Ultimate.allocInit(12, 3); {331#true} is VALID [2022-04-15 09:34:43,858 INFO L290 TraceCheckUtils]: 2: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,858 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {331#true} {331#true} #101#return; {331#true} is VALID [2022-04-15 09:34:43,858 INFO L272 TraceCheckUtils]: 4: Hoare triple {331#true} call #t~ret6 := main(); {331#true} is VALID [2022-04-15 09:34:43,858 INFO L290 TraceCheckUtils]: 5: Hoare triple {331#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {331#true} is VALID [2022-04-15 09:34:43,859 INFO L272 TraceCheckUtils]: 6: Hoare triple {331#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {331#true} is VALID [2022-04-15 09:34:43,859 INFO L290 TraceCheckUtils]: 7: Hoare triple {331#true} ~cond := #in~cond; {331#true} is VALID [2022-04-15 09:34:43,859 INFO L290 TraceCheckUtils]: 8: Hoare triple {331#true} assume !(0 == ~cond); {331#true} is VALID [2022-04-15 09:34:43,860 INFO L290 TraceCheckUtils]: 9: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,860 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {331#true} {331#true} #81#return; {331#true} is VALID [2022-04-15 09:34:43,861 INFO L290 TraceCheckUtils]: 11: Hoare triple {331#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {331#true} is VALID [2022-04-15 09:34:43,861 INFO L272 TraceCheckUtils]: 12: Hoare triple {331#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {331#true} is VALID [2022-04-15 09:34:43,861 INFO L290 TraceCheckUtils]: 13: Hoare triple {331#true} ~cond := #in~cond; {331#true} is VALID [2022-04-15 09:34:43,861 INFO L290 TraceCheckUtils]: 14: Hoare triple {331#true} assume !(0 == ~cond); {331#true} is VALID [2022-04-15 09:34:43,862 INFO L290 TraceCheckUtils]: 15: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,862 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {331#true} {331#true} #83#return; {331#true} is VALID [2022-04-15 09:34:43,862 INFO L272 TraceCheckUtils]: 17: Hoare triple {331#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {331#true} is VALID [2022-04-15 09:34:43,862 INFO L290 TraceCheckUtils]: 18: Hoare triple {331#true} ~cond := #in~cond; {331#true} is VALID [2022-04-15 09:34:43,863 INFO L290 TraceCheckUtils]: 19: Hoare triple {331#true} assume !(0 == ~cond); {331#true} is VALID [2022-04-15 09:34:43,863 INFO L290 TraceCheckUtils]: 20: Hoare triple {331#true} assume true; {331#true} is VALID [2022-04-15 09:34:43,863 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {331#true} {331#true} #85#return; {331#true} is VALID [2022-04-15 09:34:43,864 INFO L290 TraceCheckUtils]: 22: Hoare triple {331#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {348#(= main_~q~0 0)} is VALID [2022-04-15 09:34:43,864 INFO L290 TraceCheckUtils]: 23: Hoare triple {348#(= main_~q~0 0)} assume !false; {348#(= main_~q~0 0)} is VALID [2022-04-15 09:34:43,865 INFO L272 TraceCheckUtils]: 24: Hoare triple {348#(= main_~q~0 0)} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {349#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:34:43,866 INFO L290 TraceCheckUtils]: 25: Hoare triple {349#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {350#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 09:34:43,867 INFO L290 TraceCheckUtils]: 26: Hoare triple {350#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {332#false} is VALID [2022-04-15 09:34:43,867 INFO L290 TraceCheckUtils]: 27: Hoare triple {332#false} assume !false; {332#false} is VALID [2022-04-15 09:34:43,867 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 09:34:43,868 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:34:43,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1918705812] [2022-04-15 09:34:43,871 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1918705812] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:43,872 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:43,872 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 09:34:43,872 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:34:43,872 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1424063124] [2022-04-15 09:34:43,872 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1424063124] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:43,872 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:43,872 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 09:34:43,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1228375296] [2022-04-15 09:34:43,873 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:34:43,874 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-04-15 09:34:43,874 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:34:43,874 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:34:43,893 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-15 09:34:43,894 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 09:34:43,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:43,894 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 09:34:43,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 09:34:43,895 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:34:44,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:44,476 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-15 09:34:44,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-15 09:34:44,477 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-04-15 09:34:44,482 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:34:44,482 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:34:44,484 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 60 transitions. [2022-04-15 09:34:44,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:34:44,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 60 transitions. [2022-04-15 09:34:44,486 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 7 states and 60 transitions. [2022-04-15 09:34:44,554 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 60 edges. 60 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:44,556 INFO L225 Difference]: With dead ends: 46 [2022-04-15 09:34:44,556 INFO L226 Difference]: Without dead ends: 44 [2022-04-15 09:34:44,557 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-15 09:34:44,558 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-15 09:34:44,558 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-15 09:34:44,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-15 09:34:44,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-15 09:34:44,565 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:34:44,566 INFO L82 GeneralOperation]: Start isEquivalent. First operand 44 states. Second operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:44,566 INFO L74 IsIncluded]: Start isIncluded. First operand 44 states. Second operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:44,567 INFO L87 Difference]: Start difference. First operand 44 states. Second operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:44,569 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:44,570 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-15 09:34:44,570 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2022-04-15 09:34:44,570 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:44,570 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:44,587 INFO L74 IsIncluded]: Start isIncluded. First operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 44 states. [2022-04-15 09:34:44,592 INFO L87 Difference]: Start difference. First operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 44 states. [2022-04-15 09:34:44,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:44,595 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-15 09:34:44,595 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2022-04-15 09:34:44,596 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:44,596 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:44,596 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:34:44,596 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:34:44,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:44,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-04-15 09:34:44,598 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-04-15 09:34:44,598 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:34:44,599 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-04-15 09:34:44,599 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:34:44,599 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 37 states and 46 transitions. [2022-04-15 09:34:44,697 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-15 09:34:44,697 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-04-15 09:34:44,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-15 09:34:44,698 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:34:44,698 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:34:44,698 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 09:34:44,699 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:34:44,699 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:34:44,699 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 1 times [2022-04-15 09:34:44,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:44,699 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2108000983] [2022-04-15 09:34:44,700 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:34:44,700 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 2 times [2022-04-15 09:34:44,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:34:44,700 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [503687208] [2022-04-15 09:34:44,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:34:44,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:34:44,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:44,816 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 09:34:44,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:44,823 INFO L290 TraceCheckUtils]: 0: Hoare triple {640#(and (= |#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(9, 2);call #Ultimate.allocInit(12, 3); {616#true} is VALID [2022-04-15 09:34:44,823 INFO L290 TraceCheckUtils]: 1: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,824 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {616#true} {616#true} #101#return; {616#true} is VALID [2022-04-15 09:34:44,824 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 09:34:44,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:44,829 INFO L290 TraceCheckUtils]: 0: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,829 INFO L290 TraceCheckUtils]: 1: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,829 INFO L290 TraceCheckUtils]: 2: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,829 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {616#true} {616#true} #81#return; {616#true} is VALID [2022-04-15 09:34:44,830 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-15 09:34:44,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:44,834 INFO L290 TraceCheckUtils]: 0: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,835 INFO L290 TraceCheckUtils]: 1: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,835 INFO L290 TraceCheckUtils]: 2: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,835 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {616#true} {616#true} #83#return; {616#true} is VALID [2022-04-15 09:34:44,835 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-15 09:34:44,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:44,840 INFO L290 TraceCheckUtils]: 0: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,840 INFO L290 TraceCheckUtils]: 1: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,840 INFO L290 TraceCheckUtils]: 2: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,841 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {616#true} {616#true} #85#return; {616#true} is VALID [2022-04-15 09:34:44,841 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-04-15 09:34:44,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:44,847 INFO L290 TraceCheckUtils]: 0: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,848 INFO L290 TraceCheckUtils]: 1: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,848 INFO L290 TraceCheckUtils]: 2: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,849 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {616#true} {633#(= main_~A~0 main_~r~0)} #87#return; {633#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 09:34:44,850 INFO L272 TraceCheckUtils]: 0: Hoare triple {616#true} call ULTIMATE.init(); {640#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 09:34:44,850 INFO L290 TraceCheckUtils]: 1: Hoare triple {640#(and (= |#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(9, 2);call #Ultimate.allocInit(12, 3); {616#true} is VALID [2022-04-15 09:34:44,850 INFO L290 TraceCheckUtils]: 2: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,850 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {616#true} {616#true} #101#return; {616#true} is VALID [2022-04-15 09:34:44,850 INFO L272 TraceCheckUtils]: 4: Hoare triple {616#true} call #t~ret6 := main(); {616#true} is VALID [2022-04-15 09:34:44,850 INFO L290 TraceCheckUtils]: 5: Hoare triple {616#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {616#true} is VALID [2022-04-15 09:34:44,851 INFO L272 TraceCheckUtils]: 6: Hoare triple {616#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {616#true} is VALID [2022-04-15 09:34:44,851 INFO L290 TraceCheckUtils]: 7: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,851 INFO L290 TraceCheckUtils]: 8: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,851 INFO L290 TraceCheckUtils]: 9: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,851 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {616#true} {616#true} #81#return; {616#true} is VALID [2022-04-15 09:34:44,851 INFO L290 TraceCheckUtils]: 11: Hoare triple {616#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {616#true} is VALID [2022-04-15 09:34:44,852 INFO L272 TraceCheckUtils]: 12: Hoare triple {616#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {616#true} is VALID [2022-04-15 09:34:44,852 INFO L290 TraceCheckUtils]: 13: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,852 INFO L290 TraceCheckUtils]: 14: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,852 INFO L290 TraceCheckUtils]: 15: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,852 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {616#true} {616#true} #83#return; {616#true} is VALID [2022-04-15 09:34:44,852 INFO L272 TraceCheckUtils]: 17: Hoare triple {616#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {616#true} is VALID [2022-04-15 09:34:44,853 INFO L290 TraceCheckUtils]: 18: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,853 INFO L290 TraceCheckUtils]: 19: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,853 INFO L290 TraceCheckUtils]: 20: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,853 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {616#true} {616#true} #85#return; {616#true} is VALID [2022-04-15 09:34:44,854 INFO L290 TraceCheckUtils]: 22: Hoare triple {616#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {633#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 09:34:44,854 INFO L290 TraceCheckUtils]: 23: Hoare triple {633#(= main_~A~0 main_~r~0)} assume !false; {633#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 09:34:44,854 INFO L272 TraceCheckUtils]: 24: Hoare triple {633#(= main_~A~0 main_~r~0)} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {616#true} is VALID [2022-04-15 09:34:44,854 INFO L290 TraceCheckUtils]: 25: Hoare triple {616#true} ~cond := #in~cond; {616#true} is VALID [2022-04-15 09:34:44,855 INFO L290 TraceCheckUtils]: 26: Hoare triple {616#true} assume !(0 == ~cond); {616#true} is VALID [2022-04-15 09:34:44,855 INFO L290 TraceCheckUtils]: 27: Hoare triple {616#true} assume true; {616#true} is VALID [2022-04-15 09:34:44,862 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {616#true} {633#(= main_~A~0 main_~r~0)} #87#return; {633#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 09:34:44,863 INFO L272 TraceCheckUtils]: 29: Hoare triple {633#(= main_~A~0 main_~r~0)} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {638#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:34:44,863 INFO L290 TraceCheckUtils]: 30: Hoare triple {638#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {639#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 09:34:44,864 INFO L290 TraceCheckUtils]: 31: Hoare triple {639#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {617#false} is VALID [2022-04-15 09:34:44,864 INFO L290 TraceCheckUtils]: 32: Hoare triple {617#false} assume !false; {617#false} is VALID [2022-04-15 09:34:44,864 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 09:34:44,864 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:34:44,864 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [503687208] [2022-04-15 09:34:44,865 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [503687208] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:44,865 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:44,865 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 09:34:44,865 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:34:44,865 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2108000983] [2022-04-15 09:34:44,865 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2108000983] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:44,865 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:44,865 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 09:34:44,866 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [307741927] [2022-04-15 09:34:44,866 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:34:44,866 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-15 09:34:44,866 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:34:44,867 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:34:44,894 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 27 edges. 27 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:44,895 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 09:34:44,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:44,895 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 09:34:44,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 09:34:44,896 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:34:45,395 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:45,395 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-04-15 09:34:45,395 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-15 09:34:45,395 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-15 09:34:45,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:34:45,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:34:45,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 60 transitions. [2022-04-15 09:34:45,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:34:45,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 60 transitions. [2022-04-15 09:34:45,409 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 7 states and 60 transitions. [2022-04-15 09:34:45,496 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 60 edges. 60 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:45,498 INFO L225 Difference]: With dead ends: 50 [2022-04-15 09:34:45,498 INFO L226 Difference]: Without dead ends: 48 [2022-04-15 09:34:45,498 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-15 09:34:45,499 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-15 09:34:45,500 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-15 09:34:45,500 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-15 09:34:45,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-04-15 09:34:45,507 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:34:45,507 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:45,508 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:45,508 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:45,511 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:45,511 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-04-15 09:34:45,511 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 61 transitions. [2022-04-15 09:34:45,512 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:45,512 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:45,513 INFO L74 IsIncluded]: Start isIncluded. First operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 48 states. [2022-04-15 09:34:45,513 INFO L87 Difference]: Start difference. First operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 48 states. [2022-04-15 09:34:45,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:45,516 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-04-15 09:34:45,516 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 61 transitions. [2022-04-15 09:34:45,517 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:45,517 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:45,517 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:34:45,517 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:34:45,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 09:34:45,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-04-15 09:34:45,519 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-04-15 09:34:45,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:34:45,520 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-04-15 09:34:45,520 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:34:45,520 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 41 states and 49 transitions. [2022-04-15 09:34:45,571 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 49 edges. 49 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:45,571 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-04-15 09:34:45,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-04-15 09:34:45,572 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:34:45,572 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:34:45,573 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-15 09:34:45,573 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:34:45,573 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:34:45,573 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 1 times [2022-04-15 09:34:45,573 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:45,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [782102846] [2022-04-15 09:34:45,574 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:34:45,574 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 2 times [2022-04-15 09:34:45,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:34:45,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1873197409] [2022-04-15 09:34:45,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:34:45,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:34:45,592 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:34:45,592 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [434945205] [2022-04-15 09:34:45,592 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:34:45,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:34:45,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:34:45,595 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-15 09:34:45,618 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-15 09:34:45,657 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 09:34:45,658 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:34:45,660 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 09:34:45,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:45,684 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:34:45,942 INFO L272 TraceCheckUtils]: 0: Hoare triple {929#true} call ULTIMATE.init(); {929#true} is VALID [2022-04-15 09:34:45,942 INFO L290 TraceCheckUtils]: 1: Hoare triple {929#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(9, 2);call #Ultimate.allocInit(12, 3); {929#true} is VALID [2022-04-15 09:34:45,942 INFO L290 TraceCheckUtils]: 2: Hoare triple {929#true} assume true; {929#true} is VALID [2022-04-15 09:34:45,943 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {929#true} {929#true} #101#return; {929#true} is VALID [2022-04-15 09:34:45,943 INFO L272 TraceCheckUtils]: 4: Hoare triple {929#true} call #t~ret6 := main(); {929#true} is VALID [2022-04-15 09:34:45,943 INFO L290 TraceCheckUtils]: 5: Hoare triple {929#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {929#true} is VALID [2022-04-15 09:34:45,943 INFO L272 TraceCheckUtils]: 6: Hoare triple {929#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {929#true} is VALID [2022-04-15 09:34:45,943 INFO L290 TraceCheckUtils]: 7: Hoare triple {929#true} ~cond := #in~cond; {929#true} is VALID [2022-04-15 09:34:45,943 INFO L290 TraceCheckUtils]: 8: Hoare triple {929#true} assume !(0 == ~cond); {929#true} is VALID [2022-04-15 09:34:45,944 INFO L290 TraceCheckUtils]: 9: Hoare triple {929#true} assume true; {929#true} is VALID [2022-04-15 09:34:45,944 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {929#true} {929#true} #81#return; {929#true} is VALID [2022-04-15 09:34:45,944 INFO L290 TraceCheckUtils]: 11: Hoare triple {929#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {929#true} is VALID [2022-04-15 09:34:45,944 INFO L272 TraceCheckUtils]: 12: Hoare triple {929#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {929#true} is VALID [2022-04-15 09:34:45,944 INFO L290 TraceCheckUtils]: 13: Hoare triple {929#true} ~cond := #in~cond; {929#true} is VALID [2022-04-15 09:34:45,944 INFO L290 TraceCheckUtils]: 14: Hoare triple {929#true} assume !(0 == ~cond); {929#true} is VALID [2022-04-15 09:34:45,945 INFO L290 TraceCheckUtils]: 15: Hoare triple {929#true} assume true; {929#true} is VALID [2022-04-15 09:34:45,945 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {929#true} {929#true} #83#return; {929#true} is VALID [2022-04-15 09:34:45,945 INFO L272 TraceCheckUtils]: 17: Hoare triple {929#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {929#true} is VALID [2022-04-15 09:34:45,945 INFO L290 TraceCheckUtils]: 18: Hoare triple {929#true} ~cond := #in~cond; {929#true} is VALID [2022-04-15 09:34:45,945 INFO L290 TraceCheckUtils]: 19: Hoare triple {929#true} assume !(0 == ~cond); {929#true} is VALID [2022-04-15 09:34:45,945 INFO L290 TraceCheckUtils]: 20: Hoare triple {929#true} assume true; {929#true} is VALID [2022-04-15 09:34:45,945 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {929#true} {929#true} #85#return; {929#true} is VALID [2022-04-15 09:34:45,946 INFO L290 TraceCheckUtils]: 22: Hoare triple {929#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:45,947 INFO L290 TraceCheckUtils]: 23: Hoare triple {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !false; {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:45,947 INFO L272 TraceCheckUtils]: 24: Hoare triple {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {929#true} is VALID [2022-04-15 09:34:45,947 INFO L290 TraceCheckUtils]: 25: Hoare triple {929#true} ~cond := #in~cond; {929#true} is VALID [2022-04-15 09:34:45,947 INFO L290 TraceCheckUtils]: 26: Hoare triple {929#true} assume !(0 == ~cond); {929#true} is VALID [2022-04-15 09:34:45,947 INFO L290 TraceCheckUtils]: 27: Hoare triple {929#true} assume true; {929#true} is VALID [2022-04-15 09:34:45,952 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {929#true} {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} #87#return; {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:45,952 INFO L272 TraceCheckUtils]: 29: Hoare triple {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {929#true} is VALID [2022-04-15 09:34:45,952 INFO L290 TraceCheckUtils]: 30: Hoare triple {929#true} ~cond := #in~cond; {929#true} is VALID [2022-04-15 09:34:45,953 INFO L290 TraceCheckUtils]: 31: Hoare triple {929#true} assume !(0 == ~cond); {929#true} is VALID [2022-04-15 09:34:45,953 INFO L290 TraceCheckUtils]: 32: Hoare triple {929#true} assume true; {929#true} is VALID [2022-04-15 09:34:45,954 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {929#true} {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} #89#return; {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:45,954 INFO L272 TraceCheckUtils]: 34: Hoare triple {1000#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {1037#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:34:45,955 INFO L290 TraceCheckUtils]: 35: Hoare triple {1037#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1041#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:34:45,955 INFO L290 TraceCheckUtils]: 36: Hoare triple {1041#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {930#false} is VALID [2022-04-15 09:34:45,955 INFO L290 TraceCheckUtils]: 37: Hoare triple {930#false} assume !false; {930#false} is VALID [2022-04-15 09:34:45,956 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-15 09:34:45,956 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 09:34:45,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:34:45,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1873197409] [2022-04-15 09:34:45,956 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:34:45,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [434945205] [2022-04-15 09:34:45,957 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [434945205] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:45,957 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:45,957 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 09:34:45,957 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:34:45,957 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [782102846] [2022-04-15 09:34:45,958 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [782102846] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:45,958 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:45,958 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 09:34:45,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2082919818] [2022-04-15 09:34:45,958 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:34:45,958 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-04-15 09:34:45,967 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:34:45,968 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-15 09:34:45,994 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 29 edges. 29 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:45,994 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 09:34:45,994 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:45,995 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 09:34:45,995 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 09:34:45,995 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-15 09:34:48,162 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-15 09:34:48,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:48,418 INFO L93 Difference]: Finished difference Result 58 states and 73 transitions. [2022-04-15 09:34:48,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 09:34:48,418 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-04-15 09:34:48,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:34:48,419 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-15 09:34:48,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 09:34:48,421 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-15 09:34:48,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 09:34:48,423 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-15 09:34:48,493 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:48,495 INFO L225 Difference]: With dead ends: 58 [2022-04-15 09:34:48,495 INFO L226 Difference]: Without dead ends: 55 [2022-04-15 09:34:48,496 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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-15 09:34:48,497 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 8 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2022-04-15 09:34:48,497 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 142 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 49 Invalid, 1 Unknown, 0 Unchecked, 2.1s Time] [2022-04-15 09:34:48,498 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-15 09:34:48,510 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-15 09:34:48,510 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:34:48,510 INFO L82 GeneralOperation]: Start isEquivalent. First operand 55 states. Second operand has 55 states, 30 states have (on average 1.2) internal successors, (36), 32 states have internal predecessors, (36), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-15 09:34:48,511 INFO L74 IsIncluded]: Start isIncluded. First operand 55 states. Second operand has 55 states, 30 states have (on average 1.2) internal successors, (36), 32 states have internal predecessors, (36), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-15 09:34:48,511 INFO L87 Difference]: Start difference. First operand 55 states. Second operand has 55 states, 30 states have (on average 1.2) internal successors, (36), 32 states have internal predecessors, (36), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-15 09:34:48,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:48,514 INFO L93 Difference]: Finished difference Result 55 states and 69 transitions. [2022-04-15 09:34:48,514 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 69 transitions. [2022-04-15 09:34:48,515 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:48,515 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:48,516 INFO L74 IsIncluded]: Start isIncluded. First operand has 55 states, 30 states have (on average 1.2) internal successors, (36), 32 states have internal predecessors, (36), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Second operand 55 states. [2022-04-15 09:34:48,516 INFO L87 Difference]: Start difference. First operand has 55 states, 30 states have (on average 1.2) internal successors, (36), 32 states have internal predecessors, (36), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Second operand 55 states. [2022-04-15 09:34:48,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:48,519 INFO L93 Difference]: Finished difference Result 55 states and 69 transitions. [2022-04-15 09:34:48,519 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 69 transitions. [2022-04-15 09:34:48,520 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:48,520 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:48,520 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:34:48,520 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:34:48,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.2) internal successors, (36), 32 states have internal predecessors, (36), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-15 09:34:48,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 69 transitions. [2022-04-15 09:34:48,523 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 69 transitions. Word has length 38 [2022-04-15 09:34:48,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:34:48,524 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 69 transitions. [2022-04-15 09:34:48,524 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-15 09:34:48,524 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 55 states and 69 transitions. [2022-04-15 09:34:48,617 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-15 09:34:48,617 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 69 transitions. [2022-04-15 09:34:48,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-15 09:34:48,618 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:34:48,618 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 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-15 09:34:48,636 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-15 09:34:48,819 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:34:48,819 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:34:48,820 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:34:48,820 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 1 times [2022-04-15 09:34:48,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:48,820 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [792282993] [2022-04-15 09:34:48,821 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:34:48,821 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 2 times [2022-04-15 09:34:48,821 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:34:48,821 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1575356418] [2022-04-15 09:34:48,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:34:48,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:34:48,849 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:34:48,849 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1847165602] [2022-04-15 09:34:48,849 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:34:48,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:34:48,850 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:34:48,861 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-15 09:34:48,862 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-15 09:34:48,910 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 09:34:48,910 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:34:48,912 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-15 09:34:48,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:48,931 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:34:50,764 INFO L272 TraceCheckUtils]: 0: Hoare triple {1385#true} call ULTIMATE.init(); {1385#true} is VALID [2022-04-15 09:34:50,765 INFO L290 TraceCheckUtils]: 1: Hoare triple {1385#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(9, 2);call #Ultimate.allocInit(12, 3); {1385#true} is VALID [2022-04-15 09:34:50,765 INFO L290 TraceCheckUtils]: 2: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:50,765 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1385#true} {1385#true} #101#return; {1385#true} is VALID [2022-04-15 09:34:50,765 INFO L272 TraceCheckUtils]: 4: Hoare triple {1385#true} call #t~ret6 := main(); {1385#true} is VALID [2022-04-15 09:34:50,765 INFO L290 TraceCheckUtils]: 5: Hoare triple {1385#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {1385#true} is VALID [2022-04-15 09:34:50,765 INFO L272 TraceCheckUtils]: 6: Hoare triple {1385#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:50,766 INFO L290 TraceCheckUtils]: 7: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:50,766 INFO L290 TraceCheckUtils]: 8: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:50,766 INFO L290 TraceCheckUtils]: 9: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:50,766 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1385#true} {1385#true} #81#return; {1385#true} is VALID [2022-04-15 09:34:50,766 INFO L290 TraceCheckUtils]: 11: Hoare triple {1385#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {1385#true} is VALID [2022-04-15 09:34:50,766 INFO L272 TraceCheckUtils]: 12: Hoare triple {1385#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:50,775 INFO L290 TraceCheckUtils]: 13: Hoare triple {1385#true} ~cond := #in~cond; {1429#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-15 09:34:50,776 INFO L290 TraceCheckUtils]: 14: Hoare triple {1429#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {1433#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 09:34:50,777 INFO L290 TraceCheckUtils]: 15: Hoare triple {1433#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1433#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 09:34:50,778 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1433#(not (= |assume_abort_if_not_#in~cond| 0))} {1385#true} #83#return; {1440#(<= (mod main_~B~0 4294967296) 5)} is VALID [2022-04-15 09:34:50,778 INFO L272 TraceCheckUtils]: 17: Hoare triple {1440#(<= (mod main_~B~0 4294967296) 5)} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:50,779 INFO L290 TraceCheckUtils]: 18: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:50,779 INFO L290 TraceCheckUtils]: 19: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:50,779 INFO L290 TraceCheckUtils]: 20: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:50,779 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1385#true} {1440#(<= (mod main_~B~0 4294967296) 5)} #85#return; {1440#(<= (mod main_~B~0 4294967296) 5)} is VALID [2022-04-15 09:34:50,780 INFO L290 TraceCheckUtils]: 22: Hoare triple {1440#(<= (mod main_~B~0 4294967296) 5)} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 09:34:50,781 INFO L290 TraceCheckUtils]: 23: Hoare triple {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} assume !false; {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 09:34:50,781 INFO L272 TraceCheckUtils]: 24: Hoare triple {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:50,781 INFO L290 TraceCheckUtils]: 25: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:50,781 INFO L290 TraceCheckUtils]: 26: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:50,781 INFO L290 TraceCheckUtils]: 27: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:50,782 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1385#true} {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} #87#return; {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 09:34:50,782 INFO L272 TraceCheckUtils]: 29: Hoare triple {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:50,782 INFO L290 TraceCheckUtils]: 30: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:50,782 INFO L290 TraceCheckUtils]: 31: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:50,783 INFO L290 TraceCheckUtils]: 32: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:50,783 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {1385#true} {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} #89#return; {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 09:34:50,783 INFO L272 TraceCheckUtils]: 34: Hoare triple {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:50,784 INFO L290 TraceCheckUtils]: 35: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:50,784 INFO L290 TraceCheckUtils]: 36: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:50,784 INFO L290 TraceCheckUtils]: 37: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:50,785 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {1385#true} {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} #91#return; {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 09:34:50,785 INFO L290 TraceCheckUtils]: 39: Hoare triple {1459#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (= main_~q~0 0) (= main_~B~0 main_~d~0))} assume !(~r~0 % 4294967296 >= ~d~0 % 4294967296); {1511#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (not (<= (mod main_~B~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0))} is VALID [2022-04-15 09:34:50,786 INFO L290 TraceCheckUtils]: 40: Hoare triple {1511#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (not (<= (mod main_~B~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0))} assume !false; {1511#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (not (<= (mod main_~B~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0))} is VALID [2022-04-15 09:34:50,787 INFO L272 TraceCheckUtils]: 41: Hoare triple {1511#(and (= main_~A~0 main_~r~0) (<= (mod main_~B~0 4294967296) 5) (not (<= (mod main_~B~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0))} call __VERIFIER_assert((if ~A~0 % 4294967296 == (~q~0 * ~B~0 + ~r~0) % 4294967296 then 1 else 0)); {1518#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:34:50,787 INFO L290 TraceCheckUtils]: 42: Hoare triple {1518#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1522#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:34:50,788 INFO L290 TraceCheckUtils]: 43: Hoare triple {1522#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1386#false} is VALID [2022-04-15 09:34:50,788 INFO L290 TraceCheckUtils]: 44: Hoare triple {1386#false} assume !false; {1386#false} is VALID [2022-04-15 09:34:50,789 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-04-15 09:34:50,789 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 09:34:51,408 INFO L290 TraceCheckUtils]: 44: Hoare triple {1386#false} assume !false; {1386#false} is VALID [2022-04-15 09:34:51,408 INFO L290 TraceCheckUtils]: 43: Hoare triple {1522#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1386#false} is VALID [2022-04-15 09:34:51,409 INFO L290 TraceCheckUtils]: 42: Hoare triple {1518#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1522#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:34:51,410 INFO L272 TraceCheckUtils]: 41: Hoare triple {1538#(= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296))} call __VERIFIER_assert((if ~A~0 % 4294967296 == (~q~0 * ~B~0 + ~r~0) % 4294967296 then 1 else 0)); {1518#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:34:51,410 INFO L290 TraceCheckUtils]: 40: Hoare triple {1538#(= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296))} assume !false; {1538#(= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296))} is VALID [2022-04-15 09:34:51,424 INFO L290 TraceCheckUtils]: 39: Hoare triple {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} assume !(~r~0 % 4294967296 >= ~d~0 % 4294967296); {1538#(= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296))} is VALID [2022-04-15 09:34:51,425 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {1385#true} {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} #91#return; {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:34:51,425 INFO L290 TraceCheckUtils]: 37: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,425 INFO L290 TraceCheckUtils]: 36: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:51,425 INFO L290 TraceCheckUtils]: 35: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:51,426 INFO L272 TraceCheckUtils]: 34: Hoare triple {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:51,427 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {1385#true} {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} #89#return; {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:34:51,427 INFO L290 TraceCheckUtils]: 32: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,427 INFO L290 TraceCheckUtils]: 31: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:51,427 INFO L290 TraceCheckUtils]: 30: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:51,433 INFO L272 TraceCheckUtils]: 29: Hoare triple {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:51,435 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1385#true} {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} #87#return; {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:34:51,435 INFO L290 TraceCheckUtils]: 27: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,436 INFO L290 TraceCheckUtils]: 26: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:51,439 INFO L290 TraceCheckUtils]: 25: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:51,440 INFO L272 TraceCheckUtils]: 24: Hoare triple {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:51,441 INFO L290 TraceCheckUtils]: 23: Hoare triple {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} assume !false; {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:34:51,442 INFO L290 TraceCheckUtils]: 22: Hoare triple {1385#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1545#(or (= (mod (+ (* main_~B~0 main_~q~0) main_~r~0) 4294967296) (mod main_~A~0 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:34:51,442 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1385#true} {1385#true} #85#return; {1385#true} is VALID [2022-04-15 09:34:51,442 INFO L290 TraceCheckUtils]: 20: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,442 INFO L290 TraceCheckUtils]: 19: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:51,442 INFO L290 TraceCheckUtils]: 18: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:51,442 INFO L272 TraceCheckUtils]: 17: Hoare triple {1385#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:51,442 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1385#true} {1385#true} #83#return; {1385#true} is VALID [2022-04-15 09:34:51,442 INFO L290 TraceCheckUtils]: 15: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L290 TraceCheckUtils]: 14: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L290 TraceCheckUtils]: 13: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L272 TraceCheckUtils]: 12: Hoare triple {1385#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L290 TraceCheckUtils]: 11: Hoare triple {1385#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1385#true} {1385#true} #81#return; {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L290 TraceCheckUtils]: 9: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L290 TraceCheckUtils]: 8: Hoare triple {1385#true} assume !(0 == ~cond); {1385#true} is VALID [2022-04-15 09:34:51,443 INFO L290 TraceCheckUtils]: 7: Hoare triple {1385#true} ~cond := #in~cond; {1385#true} is VALID [2022-04-15 09:34:51,444 INFO L272 TraceCheckUtils]: 6: Hoare triple {1385#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {1385#true} is VALID [2022-04-15 09:34:51,444 INFO L290 TraceCheckUtils]: 5: Hoare triple {1385#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {1385#true} is VALID [2022-04-15 09:34:51,444 INFO L272 TraceCheckUtils]: 4: Hoare triple {1385#true} call #t~ret6 := main(); {1385#true} is VALID [2022-04-15 09:34:51,444 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1385#true} {1385#true} #101#return; {1385#true} is VALID [2022-04-15 09:34:51,444 INFO L290 TraceCheckUtils]: 2: Hoare triple {1385#true} assume true; {1385#true} is VALID [2022-04-15 09:34:51,445 INFO L290 TraceCheckUtils]: 1: Hoare triple {1385#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(9, 2);call #Ultimate.allocInit(12, 3); {1385#true} is VALID [2022-04-15 09:34:51,445 INFO L272 TraceCheckUtils]: 0: Hoare triple {1385#true} call ULTIMATE.init(); {1385#true} is VALID [2022-04-15 09:34:51,445 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-15 09:34:51,445 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:34:51,445 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1575356418] [2022-04-15 09:34:51,445 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:34:51,445 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1847165602] [2022-04-15 09:34:51,446 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1847165602] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-15 09:34:51,446 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-15 09:34:51,446 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-04-15 09:34:51,446 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:34:51,446 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [792282993] [2022-04-15 09:34:51,446 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [792282993] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:51,446 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:51,446 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 09:34:51,446 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [276767888] [2022-04-15 09:34:51,447 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:34:51,448 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-04-15 09:34:51,448 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:34:51,448 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-15 09:34:51,481 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 33 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:51,482 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 09:34:51,482 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:51,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 09:34:51,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-15 09:34:51,482 INFO L87 Difference]: Start difference. First operand 55 states and 69 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-15 09:34:52,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:52,101 INFO L93 Difference]: Finished difference Result 68 states and 86 transitions. [2022-04-15 09:34:52,101 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 09:34:52,101 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-04-15 09:34:52,101 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:34:52,102 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-15 09:34:52,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 60 transitions. [2022-04-15 09:34:52,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-15 09:34:52,105 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 60 transitions. [2022-04-15 09:34:52,105 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 60 transitions. [2022-04-15 09:34:52,177 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 60 edges. 60 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:52,179 INFO L225 Difference]: With dead ends: 68 [2022-04-15 09:34:52,179 INFO L226 Difference]: Without dead ends: 66 [2022-04-15 09:34:52,180 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-15 09:34:52,180 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 12 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 09:34:52,181 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 151 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 09:34:52,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-15 09:34:52,204 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-04-15 09:34:52,204 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:34:52,205 INFO L82 GeneralOperation]: Start isEquivalent. First operand 66 states. Second operand has 64 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 38 states have internal predecessors, (44), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 09:34:52,206 INFO L74 IsIncluded]: Start isIncluded. First operand 66 states. Second operand has 64 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 38 states have internal predecessors, (44), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 09:34:52,208 INFO L87 Difference]: Start difference. First operand 66 states. Second operand has 64 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 38 states have internal predecessors, (44), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 09:34:52,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:52,214 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-04-15 09:34:52,214 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 84 transitions. [2022-04-15 09:34:52,217 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:52,217 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:52,219 INFO L74 IsIncluded]: Start isIncluded. First operand has 64 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 38 states have internal predecessors, (44), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 66 states. [2022-04-15 09:34:52,220 INFO L87 Difference]: Start difference. First operand has 64 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 38 states have internal predecessors, (44), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 66 states. [2022-04-15 09:34:52,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:34:52,226 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-04-15 09:34:52,226 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 84 transitions. [2022-04-15 09:34:52,228 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:34:52,228 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:34:52,228 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:34:52,228 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:34:52,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 38 states have internal predecessors, (44), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 09:34:52,235 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 81 transitions. [2022-04-15 09:34:52,236 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 81 transitions. Word has length 45 [2022-04-15 09:34:52,237 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:34:52,238 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 81 transitions. [2022-04-15 09:34:52,238 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-15 09:34:52,238 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 64 states and 81 transitions. [2022-04-15 09:34:52,356 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 81 edges. 81 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:52,356 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 81 transitions. [2022-04-15 09:34:52,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-15 09:34:52,357 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:34:52,358 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:34:52,385 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-15 09:34:52,558 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:34:52,558 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:34:52,559 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:34:52,559 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 1 times [2022-04-15 09:34:52,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:52,559 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [399721348] [2022-04-15 09:34:52,559 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:34:52,560 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 2 times [2022-04-15 09:34:52,560 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:34:52,560 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [789751433] [2022-04-15 09:34:52,560 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:34:52,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:34:52,576 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:34:52,576 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [650677783] [2022-04-15 09:34:52,576 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:34:52,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:34:52,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:34:52,587 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-15 09:34:52,600 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-15 09:34:52,709 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 09:34:52,710 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:34:52,711 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-15 09:34:52,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:34:52,727 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:34:53,015 INFO L272 TraceCheckUtils]: 0: Hoare triple {2063#true} call ULTIMATE.init(); {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L290 TraceCheckUtils]: 1: Hoare triple {2063#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(9, 2);call #Ultimate.allocInit(12, 3); {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L290 TraceCheckUtils]: 2: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2063#true} {2063#true} #101#return; {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L272 TraceCheckUtils]: 4: Hoare triple {2063#true} call #t~ret6 := main(); {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L290 TraceCheckUtils]: 5: Hoare triple {2063#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L272 TraceCheckUtils]: 6: Hoare triple {2063#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L290 TraceCheckUtils]: 7: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,015 INFO L290 TraceCheckUtils]: 8: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 9: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2063#true} {2063#true} #81#return; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 11: Hoare triple {2063#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L272 TraceCheckUtils]: 12: Hoare triple {2063#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 13: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 14: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 15: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2063#true} {2063#true} #83#return; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L272 TraceCheckUtils]: 17: Hoare triple {2063#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 18: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 19: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L290 TraceCheckUtils]: 20: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,016 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2063#true} {2063#true} #85#return; {2063#true} is VALID [2022-04-15 09:34:53,017 INFO L290 TraceCheckUtils]: 22: Hoare triple {2063#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:53,017 INFO L290 TraceCheckUtils]: 23: Hoare triple {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !false; {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:53,017 INFO L272 TraceCheckUtils]: 24: Hoare triple {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,017 INFO L290 TraceCheckUtils]: 25: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,017 INFO L290 TraceCheckUtils]: 26: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,018 INFO L290 TraceCheckUtils]: 27: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,020 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2063#true} {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} #87#return; {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:53,020 INFO L272 TraceCheckUtils]: 29: Hoare triple {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,020 INFO L290 TraceCheckUtils]: 30: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,020 INFO L290 TraceCheckUtils]: 31: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,020 INFO L290 TraceCheckUtils]: 32: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,021 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2063#true} {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} #89#return; {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:53,021 INFO L272 TraceCheckUtils]: 34: Hoare triple {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,022 INFO L290 TraceCheckUtils]: 35: Hoare triple {2063#true} ~cond := #in~cond; {2174#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:34:53,022 INFO L290 TraceCheckUtils]: 36: Hoare triple {2174#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:34:53,023 INFO L290 TraceCheckUtils]: 37: Hoare triple {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:34:53,023 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} #91#return; {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 09:34:53,024 INFO L290 TraceCheckUtils]: 39: Hoare triple {2134#(and (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !!(~r~0 % 4294967296 >= ~d~0 % 4294967296);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} is VALID [2022-04-15 09:34:53,025 INFO L290 TraceCheckUtils]: 40: Hoare triple {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} assume !false; {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} is VALID [2022-04-15 09:34:53,025 INFO L272 TraceCheckUtils]: 41: Hoare triple {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,025 INFO L290 TraceCheckUtils]: 42: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,025 INFO L290 TraceCheckUtils]: 43: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,025 INFO L290 TraceCheckUtils]: 44: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,026 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2063#true} {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} #87#return; {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} is VALID [2022-04-15 09:34:53,026 INFO L272 TraceCheckUtils]: 46: Hoare triple {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:53,026 INFO L290 TraceCheckUtils]: 47: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:53,026 INFO L290 TraceCheckUtils]: 48: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:53,026 INFO L290 TraceCheckUtils]: 49: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:53,027 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2063#true} {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} #89#return; {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} is VALID [2022-04-15 09:34:53,029 INFO L272 TraceCheckUtils]: 51: Hoare triple {2188#(and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2225#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:34:53,030 INFO L290 TraceCheckUtils]: 52: Hoare triple {2225#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2229#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:34:53,031 INFO L290 TraceCheckUtils]: 53: Hoare triple {2229#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2064#false} is VALID [2022-04-15 09:34:53,031 INFO L290 TraceCheckUtils]: 54: Hoare triple {2064#false} assume !false; {2064#false} is VALID [2022-04-15 09:34:53,031 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 15 proven. 11 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-15 09:34:53,031 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 09:34:54,053 INFO L290 TraceCheckUtils]: 54: Hoare triple {2064#false} assume !false; {2064#false} is VALID [2022-04-15 09:34:54,055 INFO L290 TraceCheckUtils]: 53: Hoare triple {2229#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2064#false} is VALID [2022-04-15 09:34:54,056 INFO L290 TraceCheckUtils]: 52: Hoare triple {2225#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2229#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:34:54,057 INFO L272 TraceCheckUtils]: 51: Hoare triple {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2225#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:34:54,057 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2063#true} {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} #89#return; {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} is VALID [2022-04-15 09:34:54,057 INFO L290 TraceCheckUtils]: 49: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:54,057 INFO L290 TraceCheckUtils]: 48: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:54,057 INFO L290 TraceCheckUtils]: 47: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:54,058 INFO L272 TraceCheckUtils]: 46: Hoare triple {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:54,058 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2063#true} {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} #87#return; {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} is VALID [2022-04-15 09:34:54,058 INFO L290 TraceCheckUtils]: 44: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:54,058 INFO L290 TraceCheckUtils]: 43: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:54,058 INFO L290 TraceCheckUtils]: 42: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:54,058 INFO L272 TraceCheckUtils]: 41: Hoare triple {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:54,059 INFO L290 TraceCheckUtils]: 40: Hoare triple {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} assume !false; {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} is VALID [2022-04-15 09:34:56,064 WARN L290 TraceCheckUtils]: 39: Hoare triple {2282#(= (mod (* main_~d~0 2) 4294967296) (mod (* (* main_~p~0 2) main_~B~0) 4294967296))} assume !!(~r~0 % 4294967296 >= ~d~0 % 4294967296);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {2245#(= (mod main_~d~0 4294967296) (mod (* main_~B~0 main_~p~0) 4294967296))} is UNKNOWN [2022-04-15 09:34:56,093 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} {2063#true} #91#return; {2282#(= (mod (* main_~d~0 2) 4294967296) (mod (* (* main_~p~0 2) main_~B~0) 4294967296))} is VALID [2022-04-15 09:34:56,094 INFO L290 TraceCheckUtils]: 37: Hoare triple {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:34:56,094 INFO L290 TraceCheckUtils]: 36: Hoare triple {2295#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {2178#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:34:56,094 INFO L290 TraceCheckUtils]: 35: Hoare triple {2063#true} ~cond := #in~cond; {2295#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 09:34:56,095 INFO L272 TraceCheckUtils]: 34: Hoare triple {2063#true} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2063#true} {2063#true} #89#return; {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L290 TraceCheckUtils]: 32: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L290 TraceCheckUtils]: 31: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L290 TraceCheckUtils]: 30: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L272 TraceCheckUtils]: 29: Hoare triple {2063#true} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2063#true} {2063#true} #87#return; {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L290 TraceCheckUtils]: 27: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L290 TraceCheckUtils]: 26: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:56,095 INFO L290 TraceCheckUtils]: 25: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L272 TraceCheckUtils]: 24: Hoare triple {2063#true} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L290 TraceCheckUtils]: 23: Hoare triple {2063#true} assume !false; {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L290 TraceCheckUtils]: 22: Hoare triple {2063#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2063#true} {2063#true} #85#return; {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L290 TraceCheckUtils]: 20: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L290 TraceCheckUtils]: 19: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L290 TraceCheckUtils]: 18: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:56,096 INFO L272 TraceCheckUtils]: 17: Hoare triple {2063#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2063#true} {2063#true} #83#return; {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L290 TraceCheckUtils]: 15: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L290 TraceCheckUtils]: 14: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L290 TraceCheckUtils]: 13: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L272 TraceCheckUtils]: 12: Hoare triple {2063#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L290 TraceCheckUtils]: 11: Hoare triple {2063#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2063#true} {2063#true} #81#return; {2063#true} is VALID [2022-04-15 09:34:56,097 INFO L290 TraceCheckUtils]: 9: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L290 TraceCheckUtils]: 8: Hoare triple {2063#true} assume !(0 == ~cond); {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L290 TraceCheckUtils]: 7: Hoare triple {2063#true} ~cond := #in~cond; {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L272 TraceCheckUtils]: 6: Hoare triple {2063#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L290 TraceCheckUtils]: 5: Hoare triple {2063#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L272 TraceCheckUtils]: 4: Hoare triple {2063#true} call #t~ret6 := main(); {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2063#true} {2063#true} #101#return; {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L290 TraceCheckUtils]: 2: Hoare triple {2063#true} assume true; {2063#true} is VALID [2022-04-15 09:34:56,098 INFO L290 TraceCheckUtils]: 1: Hoare triple {2063#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(9, 2);call #Ultimate.allocInit(12, 3); {2063#true} is VALID [2022-04-15 09:34:56,099 INFO L272 TraceCheckUtils]: 0: Hoare triple {2063#true} call ULTIMATE.init(); {2063#true} is VALID [2022-04-15 09:34:56,099 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 19 proven. 7 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-15 09:34:56,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:34:56,099 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [789751433] [2022-04-15 09:34:56,099 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:34:56,099 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [650677783] [2022-04-15 09:34:56,099 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [650677783] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-15 09:34:56,100 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-15 09:34:56,100 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-04-15 09:34:56,100 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:34:56,100 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [399721348] [2022-04-15 09:34:56,100 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [399721348] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:34:56,100 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:34:56,100 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-15 09:34:56,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2005377825] [2022-04-15 09:34:56,100 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:34:56,101 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 55 [2022-04-15 09:34:56,101 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:34:56,101 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:34:56,597 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 40 edges. 40 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:34:56,598 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-15 09:34:56,598 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:34:56,598 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-15 09:34:56,598 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2022-04-15 09:34:56,599 INFO L87 Difference]: Start difference. First operand 64 states and 81 transitions. Second operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:00,241 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-15 09:35:03,193 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.83s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 09:35:05,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:35:05,843 INFO L93 Difference]: Finished difference Result 85 states and 109 transitions. [2022-04-15 09:35:05,844 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 09:35:05,844 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 55 [2022-04-15 09:35:05,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:35:05,844 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:05,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 88 transitions. [2022-04-15 09:35:05,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:05,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 88 transitions. [2022-04-15 09:35:05,849 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 88 transitions. [2022-04-15 09:35:06,686 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 88 edges. 88 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:35:06,689 INFO L225 Difference]: With dead ends: 85 [2022-04-15 09:35:06,689 INFO L226 Difference]: Without dead ends: 77 [2022-04-15 09:35:06,689 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 99 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2022-04-15 09:35:06,690 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 14 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 222 mSolverCounterSat, 5 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 222 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.0s IncrementalHoareTripleChecker+Time [2022-04-15 09:35:06,690 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 186 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 222 Invalid, 1 Unknown, 0 Unchecked, 8.0s Time] [2022-04-15 09:35:06,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2022-04-15 09:35:06,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2022-04-15 09:35:06,713 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:35:06,715 INFO L82 GeneralOperation]: Start isEquivalent. First operand 77 states. Second operand has 77 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:06,717 INFO L74 IsIncluded]: Start isIncluded. First operand 77 states. Second operand has 77 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:06,718 INFO L87 Difference]: Start difference. First operand 77 states. Second operand has 77 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:06,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:35:06,724 INFO L93 Difference]: Finished difference Result 77 states and 99 transitions. [2022-04-15 09:35:06,724 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 99 transitions. [2022-04-15 09:35:06,724 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:35:06,725 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:35:06,725 INFO L74 IsIncluded]: Start isIncluded. First operand has 77 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand 77 states. [2022-04-15 09:35:06,725 INFO L87 Difference]: Start difference. First operand has 77 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand 77 states. [2022-04-15 09:35:06,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:35:06,731 INFO L93 Difference]: Finished difference Result 77 states and 99 transitions. [2022-04-15 09:35:06,731 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 99 transitions. [2022-04-15 09:35:06,732 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:35:06,732 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:35:06,732 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:35:06,732 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:35:06,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:06,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 99 transitions. [2022-04-15 09:35:06,736 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 99 transitions. Word has length 55 [2022-04-15 09:35:06,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:35:06,736 INFO L478 AbstractCegarLoop]: Abstraction has 77 states and 99 transitions. [2022-04-15 09:35:06,736 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:06,737 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 77 states and 99 transitions. [2022-04-15 09:35:07,772 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 99 edges. 99 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:35:07,772 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 99 transitions. [2022-04-15 09:35:07,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-04-15 09:35:07,773 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:35:07,773 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 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-15 09:35:07,777 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-04-15 09:35:07,975 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:35:07,976 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:35:07,976 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:35:07,976 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 1 times [2022-04-15 09:35:07,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:35:07,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2052447726] [2022-04-15 09:35:07,976 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:35:07,977 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 2 times [2022-04-15 09:35:07,977 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:35:07,977 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2041141368] [2022-04-15 09:35:07,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:35:07,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:35:07,991 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:35:07,999 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1188412087] [2022-04-15 09:35:07,999 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:35:08,000 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:35:08,000 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:35:08,002 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-15 09:35:08,003 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-15 09:35:08,067 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 09:35:08,067 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:35:08,068 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-15 09:35:08,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:35:08,083 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:35:10,840 INFO L272 TraceCheckUtils]: 0: Hoare triple {2885#true} call ULTIMATE.init(); {2885#true} is VALID [2022-04-15 09:35:10,840 INFO L290 TraceCheckUtils]: 1: Hoare triple {2885#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(9, 2);call #Ultimate.allocInit(12, 3); {2885#true} is VALID [2022-04-15 09:35:10,840 INFO L290 TraceCheckUtils]: 2: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,840 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2885#true} {2885#true} #101#return; {2885#true} is VALID [2022-04-15 09:35:10,840 INFO L272 TraceCheckUtils]: 4: Hoare triple {2885#true} call #t~ret6 := main(); {2885#true} is VALID [2022-04-15 09:35:10,840 INFO L290 TraceCheckUtils]: 5: Hoare triple {2885#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L272 TraceCheckUtils]: 6: Hoare triple {2885#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L290 TraceCheckUtils]: 7: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L290 TraceCheckUtils]: 8: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L290 TraceCheckUtils]: 9: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2885#true} {2885#true} #81#return; {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L290 TraceCheckUtils]: 11: Hoare triple {2885#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {2885#true} is VALID [2022-04-15 09:35:10,841 INFO L272 TraceCheckUtils]: 12: Hoare triple {2885#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,842 INFO L290 TraceCheckUtils]: 13: Hoare triple {2885#true} ~cond := #in~cond; {2929#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-15 09:35:10,842 INFO L290 TraceCheckUtils]: 14: Hoare triple {2929#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {2933#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 09:35:10,843 INFO L290 TraceCheckUtils]: 15: Hoare triple {2933#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2933#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 09:35:10,843 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2933#(not (= |assume_abort_if_not_#in~cond| 0))} {2885#true} #83#return; {2940#(<= (mod main_~B~0 4294967296) 5)} is VALID [2022-04-15 09:35:10,843 INFO L272 TraceCheckUtils]: 17: Hoare triple {2940#(<= (mod main_~B~0 4294967296) 5)} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,843 INFO L290 TraceCheckUtils]: 18: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,844 INFO L290 TraceCheckUtils]: 19: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,844 INFO L290 TraceCheckUtils]: 20: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,844 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2885#true} {2940#(<= (mod main_~B~0 4294967296) 5)} #85#return; {2940#(<= (mod main_~B~0 4294967296) 5)} is VALID [2022-04-15 09:35:10,845 INFO L290 TraceCheckUtils]: 22: Hoare triple {2940#(<= (mod main_~B~0 4294967296) 5)} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,845 INFO L290 TraceCheckUtils]: 23: Hoare triple {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} assume !false; {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,845 INFO L272 TraceCheckUtils]: 24: Hoare triple {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,845 INFO L290 TraceCheckUtils]: 25: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,846 INFO L290 TraceCheckUtils]: 26: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,846 INFO L290 TraceCheckUtils]: 27: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,846 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2885#true} {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} #87#return; {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,846 INFO L272 TraceCheckUtils]: 29: Hoare triple {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,847 INFO L290 TraceCheckUtils]: 30: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,847 INFO L290 TraceCheckUtils]: 31: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,847 INFO L290 TraceCheckUtils]: 32: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,847 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2885#true} {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} #89#return; {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,848 INFO L272 TraceCheckUtils]: 34: Hoare triple {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,848 INFO L290 TraceCheckUtils]: 35: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,848 INFO L290 TraceCheckUtils]: 36: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,848 INFO L290 TraceCheckUtils]: 37: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,849 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {2885#true} {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} #91#return; {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,849 INFO L290 TraceCheckUtils]: 39: Hoare triple {2959#(and (= main_~A~0 main_~r~0) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} assume !(~r~0 % 4294967296 >= ~d~0 % 4294967296); {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,850 INFO L290 TraceCheckUtils]: 40: Hoare triple {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} assume !false; {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,850 INFO L272 TraceCheckUtils]: 41: Hoare triple {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} call __VERIFIER_assert((if ~A~0 % 4294967296 == (~q~0 * ~B~0 + ~r~0) % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,850 INFO L290 TraceCheckUtils]: 42: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,850 INFO L290 TraceCheckUtils]: 43: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,850 INFO L290 TraceCheckUtils]: 44: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,851 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2885#true} {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} #93#return; {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,851 INFO L272 TraceCheckUtils]: 46: Hoare triple {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:10,851 INFO L290 TraceCheckUtils]: 47: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:10,851 INFO L290 TraceCheckUtils]: 48: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:10,851 INFO L290 TraceCheckUtils]: 49: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:10,852 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2885#true} {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} #95#return; {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,853 INFO L290 TraceCheckUtils]: 51: Hoare triple {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} assume !(1 != ~p~0 % 4294967296); {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} is VALID [2022-04-15 09:35:10,853 INFO L272 TraceCheckUtils]: 52: Hoare triple {3011#(and (= main_~A~0 main_~r~0) (not (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296))) (= main_~q~0 0) (<= (mod main_~d~0 4294967296) 5))} call __VERIFIER_assert((if ~A~0 % 4294967296 == (~d~0 * ~q~0 + ~r~0) % 4294967296 then 1 else 0)); {3051#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:35:10,854 INFO L290 TraceCheckUtils]: 53: Hoare triple {3051#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {3055#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:35:10,854 INFO L290 TraceCheckUtils]: 54: Hoare triple {3055#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2886#false} is VALID [2022-04-15 09:35:10,854 INFO L290 TraceCheckUtils]: 55: Hoare triple {2886#false} assume !false; {2886#false} is VALID [2022-04-15 09:35:10,855 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 13 proven. 3 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-04-15 09:35:10,855 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 09:35:12,203 INFO L290 TraceCheckUtils]: 55: Hoare triple {2886#false} assume !false; {2886#false} is VALID [2022-04-15 09:35:12,204 INFO L290 TraceCheckUtils]: 54: Hoare triple {3055#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2886#false} is VALID [2022-04-15 09:35:12,205 INFO L290 TraceCheckUtils]: 53: Hoare triple {3051#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {3055#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:35:12,206 INFO L272 TraceCheckUtils]: 52: Hoare triple {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} call __VERIFIER_assert((if ~A~0 % 4294967296 == (~d~0 * ~q~0 + ~r~0) % 4294967296 then 1 else 0)); {3051#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:35:12,206 INFO L290 TraceCheckUtils]: 51: Hoare triple {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} assume !(1 != ~p~0 % 4294967296); {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} is VALID [2022-04-15 09:35:12,207 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2885#true} {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} #95#return; {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} is VALID [2022-04-15 09:35:12,207 INFO L290 TraceCheckUtils]: 49: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,207 INFO L290 TraceCheckUtils]: 48: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,207 INFO L290 TraceCheckUtils]: 47: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,207 INFO L272 TraceCheckUtils]: 46: Hoare triple {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,208 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2885#true} {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} #93#return; {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} is VALID [2022-04-15 09:35:12,208 INFO L290 TraceCheckUtils]: 44: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,208 INFO L290 TraceCheckUtils]: 43: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,208 INFO L290 TraceCheckUtils]: 42: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,208 INFO L272 TraceCheckUtils]: 41: Hoare triple {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} call __VERIFIER_assert((if ~A~0 % 4294967296 == (~q~0 * ~B~0 + ~r~0) % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,208 INFO L290 TraceCheckUtils]: 40: Hoare triple {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} assume !false; {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} is VALID [2022-04-15 09:35:12,209 INFO L290 TraceCheckUtils]: 39: Hoare triple {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} assume !(~r~0 % 4294967296 >= ~d~0 % 4294967296); {3071#(= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296))} is VALID [2022-04-15 09:35:12,209 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {2885#true} {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} #91#return; {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:35:12,209 INFO L290 TraceCheckUtils]: 37: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,209 INFO L290 TraceCheckUtils]: 36: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,209 INFO L290 TraceCheckUtils]: 35: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,209 INFO L272 TraceCheckUtils]: 34: Hoare triple {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} call __VERIFIER_assert((if ~d~0 % 4294967296 == ~B~0 * ~p~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,210 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2885#true} {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} #89#return; {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:35:12,210 INFO L290 TraceCheckUtils]: 32: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,210 INFO L290 TraceCheckUtils]: 31: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,210 INFO L290 TraceCheckUtils]: 30: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,210 INFO L272 TraceCheckUtils]: 29: Hoare triple {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} call __VERIFIER_assert((if ~r~0 % 4294967296 == ~A~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,211 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2885#true} {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} #87#return; {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:35:12,211 INFO L290 TraceCheckUtils]: 27: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,211 INFO L290 TraceCheckUtils]: 26: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,211 INFO L290 TraceCheckUtils]: 25: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,211 INFO L272 TraceCheckUtils]: 24: Hoare triple {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} call __VERIFIER_assert((if 0 == ~q~0 % 4294967296 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,213 INFO L290 TraceCheckUtils]: 23: Hoare triple {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} assume !false; {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:35:12,213 INFO L290 TraceCheckUtils]: 22: Hoare triple {2885#true} ~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {3111#(or (= (mod main_~A~0 4294967296) (mod (+ (* main_~d~0 main_~q~0) main_~r~0) 4294967296)) (<= (mod main_~d~0 4294967296) (mod main_~r~0 4294967296)))} is VALID [2022-04-15 09:35:12,213 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2885#true} {2885#true} #85#return; {2885#true} is VALID [2022-04-15 09:35:12,213 INFO L290 TraceCheckUtils]: 20: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,213 INFO L290 TraceCheckUtils]: 19: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,213 INFO L290 TraceCheckUtils]: 18: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L272 TraceCheckUtils]: 17: Hoare triple {2885#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2885#true} {2885#true} #83#return; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 15: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 14: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 13: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L272 TraceCheckUtils]: 12: Hoare triple {2885#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 0 && ~B~0 % 4294967296 <= 5 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 11: Hoare triple {2885#true} ~B~0 := #t~nondet5;havoc #t~nondet5; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2885#true} {2885#true} #81#return; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 9: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 8: Hoare triple {2885#true} assume !(0 == ~cond); {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 7: Hoare triple {2885#true} ~cond := #in~cond; {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L272 TraceCheckUtils]: 6: Hoare triple {2885#true} call assume_abort_if_not((if ~A~0 % 4294967296 >= 0 && ~A~0 % 4294967296 <= 5 then 1 else 0)); {2885#true} is VALID [2022-04-15 09:35:12,214 INFO L290 TraceCheckUtils]: 5: Hoare triple {2885#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;~A~0 := #t~nondet4;havoc #t~nondet4; {2885#true} is VALID [2022-04-15 09:35:12,215 INFO L272 TraceCheckUtils]: 4: Hoare triple {2885#true} call #t~ret6 := main(); {2885#true} is VALID [2022-04-15 09:35:12,215 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2885#true} {2885#true} #101#return; {2885#true} is VALID [2022-04-15 09:35:12,215 INFO L290 TraceCheckUtils]: 2: Hoare triple {2885#true} assume true; {2885#true} is VALID [2022-04-15 09:35:12,215 INFO L290 TraceCheckUtils]: 1: Hoare triple {2885#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(9, 2);call #Ultimate.allocInit(12, 3); {2885#true} is VALID [2022-04-15 09:35:12,215 INFO L272 TraceCheckUtils]: 0: Hoare triple {2885#true} call ULTIMATE.init(); {2885#true} is VALID [2022-04-15 09:35:12,215 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-04-15 09:35:12,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:35:12,215 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2041141368] [2022-04-15 09:35:12,216 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:35:12,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1188412087] [2022-04-15 09:35:12,216 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1188412087] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-15 09:35:12,216 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-15 09:35:12,216 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-04-15 09:35:12,216 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:35:12,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2052447726] [2022-04-15 09:35:12,216 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2052447726] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:35:12,216 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:35:12,216 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 09:35:12,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [31532366] [2022-04-15 09:35:12,217 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:35:12,217 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 56 [2022-04-15 09:35:12,217 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:35:12,218 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:12,259 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 38 edges. 38 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:35:12,259 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 09:35:12,259 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:35:12,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 09:35:12,260 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-15 09:35:12,260 INFO L87 Difference]: Start difference. First operand 77 states and 99 transitions. Second operand has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:17,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:35:17,780 INFO L93 Difference]: Finished difference Result 83 states and 104 transitions. [2022-04-15 09:35:17,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 09:35:17,781 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 56 [2022-04-15 09:35:17,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:35:17,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:17,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-15 09:35:17,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:17,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-15 09:35:17,785 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 65 transitions. [2022-04-15 09:35:17,862 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 65 edges. 65 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:35:17,864 INFO L225 Difference]: With dead ends: 83 [2022-04-15 09:35:17,865 INFO L226 Difference]: Without dead ends: 76 [2022-04-15 09:35:17,865 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 101 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2022-04-15 09:35:17,866 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 9 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-04-15 09:35:17,866 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 148 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-04-15 09:35:17,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-04-15 09:35:17,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 75. [2022-04-15 09:35:17,892 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:35:17,892 INFO L82 GeneralOperation]: Start isEquivalent. First operand 76 states. Second operand has 75 states, 42 states have (on average 1.1904761904761905) internal successors, (50), 44 states have internal predecessors, (50), 24 states have call successors, (24), 9 states have call predecessors, (24), 8 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:17,892 INFO L74 IsIncluded]: Start isIncluded. First operand 76 states. Second operand has 75 states, 42 states have (on average 1.1904761904761905) internal successors, (50), 44 states have internal predecessors, (50), 24 states have call successors, (24), 9 states have call predecessors, (24), 8 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:17,894 INFO L87 Difference]: Start difference. First operand 76 states. Second operand has 75 states, 42 states have (on average 1.1904761904761905) internal successors, (50), 44 states have internal predecessors, (50), 24 states have call successors, (24), 9 states have call predecessors, (24), 8 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:17,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:35:17,899 INFO L93 Difference]: Finished difference Result 76 states and 97 transitions. [2022-04-15 09:35:17,899 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 97 transitions. [2022-04-15 09:35:17,900 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:35:17,900 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:35:17,901 INFO L74 IsIncluded]: Start isIncluded. First operand has 75 states, 42 states have (on average 1.1904761904761905) internal successors, (50), 44 states have internal predecessors, (50), 24 states have call successors, (24), 9 states have call predecessors, (24), 8 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) Second operand 76 states. [2022-04-15 09:35:17,901 INFO L87 Difference]: Start difference. First operand has 75 states, 42 states have (on average 1.1904761904761905) internal successors, (50), 44 states have internal predecessors, (50), 24 states have call successors, (24), 9 states have call predecessors, (24), 8 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) Second operand 76 states. [2022-04-15 09:35:17,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:35:17,905 INFO L93 Difference]: Finished difference Result 76 states and 97 transitions. [2022-04-15 09:35:17,905 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 97 transitions. [2022-04-15 09:35:17,906 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:35:17,906 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:35:17,906 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:35:17,906 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:35:17,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 42 states have (on average 1.1904761904761905) internal successors, (50), 44 states have internal predecessors, (50), 24 states have call successors, (24), 9 states have call predecessors, (24), 8 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-15 09:35:17,910 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 96 transitions. [2022-04-15 09:35:17,910 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 96 transitions. Word has length 56 [2022-04-15 09:35:17,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:35:17,910 INFO L478 AbstractCegarLoop]: Abstraction has 75 states and 96 transitions. [2022-04-15 09:35:17,911 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-15 09:35:17,911 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 75 states and 96 transitions. [2022-04-15 09:35:18,580 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 96 edges. 96 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:35:18,581 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 96 transitions. [2022-04-15 09:35:18,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-15 09:35:18,581 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:35:18,582 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 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-15 09:35:18,600 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-15 09:35:18,787 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:35:18,787 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:35:18,788 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:35:18,788 INFO L85 PathProgramCache]: Analyzing trace with hash 1586192473, now seen corresponding path program 1 times [2022-04-15 09:35:18,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:35:18,788 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1937344696] [2022-04-15 09:35:18,788 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:35:18,788 INFO L85 PathProgramCache]: Analyzing trace with hash 1586192473, now seen corresponding path program 2 times [2022-04-15 09:35:18,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:35:18,789 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1810505636] [2022-04-15 09:35:18,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:35:18,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:35:18,803 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:35:18,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1344957230] [2022-04-15 09:35:18,804 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:35:18,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:35:18,804 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:35:18,805 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-15 09:35:18,815 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process