/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 15:35:16,078 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 15:35:16,103 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 15:35:16,131 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 15:35:16,131 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 15:35:16,132 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 15:35:16,133 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 15:35:16,134 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 15:35:16,135 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 15:35:16,136 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 15:35:16,136 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 15:35:16,137 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 15:35:16,137 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 15:35:16,138 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 15:35:16,139 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 15:35:16,139 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 15:35:16,140 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 15:35:16,141 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 15:35:16,142 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 15:35:16,148 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 15:35:16,149 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 15:35:16,156 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 15:35:16,156 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 15:35:16,157 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 15:35:16,157 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 15:35:16,159 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 15:35:16,159 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 15:35:16,160 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 15:35:16,160 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 15:35:16,160 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 15:35:16,161 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 15:35:16,161 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 15:35:16,162 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 15:35:16,162 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 15:35:16,162 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 15:35:16,163 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 15:35:16,163 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 15:35:16,164 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 15:35:16,164 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 15:35:16,164 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 15:35:16,165 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 15:35:16,167 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 15:35:16,167 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-15 15:35:16,173 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 15:35:16,173 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 15:35:16,174 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 15:35:16,174 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 15:35:16,175 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 15:35:16,175 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 15:35:16,175 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 15:35:16,175 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 15:35:16,175 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 15:35:16,175 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 15:35:16,175 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 15:35:16,175 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 15:35:16,176 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 15:35:16,176 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 15:35:16,176 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-15 15:35:16,176 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 15:35:16,373 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 15:35:16,394 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 15:35:16,395 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 15:35:16,396 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 15:35:16,397 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 15:35:16,397 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound5.c [2022-04-15 15:35:16,452 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/90b75ba07/33153aaf4ed04d82be166455f6a4c2b2/FLAG79d115b52 [2022-04-15 15:35:16,764 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 15:35:16,764 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound5.c [2022-04-15 15:35:16,770 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/90b75ba07/33153aaf4ed04d82be166455f6a4c2b2/FLAG79d115b52 [2022-04-15 15:35:17,191 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/90b75ba07/33153aaf4ed04d82be166455f6a4c2b2 [2022-04-15 15:35:17,193 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 15:35:17,195 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 15:35:17,196 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 15:35:17,196 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 15:35:17,199 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 15:35:17,199 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,200 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@345b0af9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17, skipping insertion in model container [2022-04-15 15:35:17,200 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,204 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 15:35:17,216 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 15:35:17,327 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-ll_unwindbound5.c[538,551] [2022-04-15 15:35:17,341 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 15:35:17,346 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 15:35:17,355 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-ll_unwindbound5.c[538,551] [2022-04-15 15:35:17,360 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 15:35:17,368 INFO L208 MainTranslator]: Completed translation [2022-04-15 15:35:17,368 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17 WrapperNode [2022-04-15 15:35:17,368 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 15:35:17,369 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 15:35:17,369 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 15:35:17,369 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 15:35:17,377 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,377 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,381 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,381 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,385 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,388 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,388 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,389 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 15:35:17,390 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 15:35:17,390 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 15:35:17,390 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 15:35:17,395 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (1/1) ... [2022-04-15 15:35:17,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 15:35:17,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:17,417 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 15:35:17,431 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 15:35:17,440 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 15:35:17,441 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 15:35:17,441 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 15:35:17,441 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 15:35:17,441 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 15:35:17,441 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 15:35:17,441 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 15:35:17,441 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 15:35:17,441 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 15:35:17,441 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 15:35:17,441 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 15:35:17,442 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 15:35:17,489 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 15:35:17,490 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 15:35:17,691 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 15:35:17,695 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 15:35:17,695 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-15 15:35:17,696 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 03:35:17 BoogieIcfgContainer [2022-04-15 15:35:17,697 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 15:35:17,698 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 15:35:17,698 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 15:35:17,700 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 15:35:17,700 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 03:35:17" (1/3) ... [2022-04-15 15:35:17,701 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@79f3ee4f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 03:35:17, skipping insertion in model container [2022-04-15 15:35:17,701 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:35:17" (2/3) ... [2022-04-15 15:35:17,701 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@79f3ee4f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 03:35:17, skipping insertion in model container [2022-04-15 15:35:17,701 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 03:35:17" (3/3) ... [2022-04-15 15:35:17,702 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound5.c [2022-04-15 15:35:17,705 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 15:35:17,705 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 15:35:17,746 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 15:35:17,755 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 15:35:17,755 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 15:35:17,780 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 15:35:17,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-15 15:35:17,785 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:17,786 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:17,786 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:17,789 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:17,790 INFO L85 PathProgramCache]: Analyzing trace with hash 1191571617, now seen corresponding path program 1 times [2022-04-15 15:35:17,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:17,796 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1667763943] [2022-04-15 15:35:17,805 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:17,805 INFO L85 PathProgramCache]: Analyzing trace with hash 1191571617, now seen corresponding path program 2 times [2022-04-15 15:35:17,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:17,807 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2007894115] [2022-04-15 15:35:17,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:17,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:17,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:17,918 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:35:17,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:17,934 INFO L290 TraceCheckUtils]: 0: Hoare triple {49#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {40#true} is VALID [2022-04-15 15:35:17,934 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume true; {40#true} is VALID [2022-04-15 15:35:17,934 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {40#true} {40#true} #96#return; {40#true} is VALID [2022-04-15 15:35:17,935 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 15:35:17,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:17,941 INFO L290 TraceCheckUtils]: 0: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:35:17,941 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:35:17,941 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:35:17,942 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#false} {40#true} #80#return; {41#false} is VALID [2022-04-15 15:35:17,942 INFO L272 TraceCheckUtils]: 0: Hoare triple {40#true} call ULTIMATE.init(); {49#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:35:17,943 INFO L290 TraceCheckUtils]: 1: Hoare triple {49#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {40#true} is VALID [2022-04-15 15:35:17,943 INFO L290 TraceCheckUtils]: 2: Hoare triple {40#true} assume true; {40#true} is VALID [2022-04-15 15:35:17,943 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {40#true} {40#true} #96#return; {40#true} is VALID [2022-04-15 15:35:17,943 INFO L272 TraceCheckUtils]: 4: Hoare triple {40#true} call #t~ret8 := main(); {40#true} is VALID [2022-04-15 15:35:17,943 INFO L290 TraceCheckUtils]: 5: Hoare triple {40#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;~B~0 := #t~nondet5;havoc #t~nondet5; {40#true} is VALID [2022-04-15 15:35:17,943 INFO L272 TraceCheckUtils]: 6: Hoare triple {40#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {40#true} is VALID [2022-04-15 15:35:17,944 INFO L290 TraceCheckUtils]: 7: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:35:17,944 INFO L290 TraceCheckUtils]: 8: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:35:17,944 INFO L290 TraceCheckUtils]: 9: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:35:17,944 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {41#false} {40#true} #80#return; {41#false} is VALID [2022-04-15 15:35:17,944 INFO L290 TraceCheckUtils]: 11: Hoare triple {41#false} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {41#false} is VALID [2022-04-15 15:35:17,945 INFO L290 TraceCheckUtils]: 12: Hoare triple {41#false} assume !true; {41#false} is VALID [2022-04-15 15:35:17,945 INFO L290 TraceCheckUtils]: 13: Hoare triple {41#false} assume !true; {41#false} is VALID [2022-04-15 15:35:17,945 INFO L272 TraceCheckUtils]: 14: Hoare triple {41#false} call __VERIFIER_assert((if ~A~0 % 4294967296 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {41#false} is VALID [2022-04-15 15:35:17,945 INFO L290 TraceCheckUtils]: 15: Hoare triple {41#false} ~cond := #in~cond; {41#false} is VALID [2022-04-15 15:35:17,945 INFO L290 TraceCheckUtils]: 16: Hoare triple {41#false} assume 0 == ~cond; {41#false} is VALID [2022-04-15 15:35:17,945 INFO L290 TraceCheckUtils]: 17: Hoare triple {41#false} assume !false; {41#false} is VALID [2022-04-15 15:35:17,946 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:35:17,946 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:17,946 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2007894115] [2022-04-15 15:35:17,947 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2007894115] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:17,947 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:17,947 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 15:35:17,948 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:17,949 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1667763943] [2022-04-15 15:35:17,949 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1667763943] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:17,949 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:17,949 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 15:35:17,949 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781596281] [2022-04-15 15:35:17,949 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:17,953 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-15 15:35:17,953 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:17,955 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:17,974 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:17,975 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 15:35:17,975 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:17,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 15:35:17,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 15:35:17,990 INFO L87 Difference]: Start difference. First operand has 37 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:18,180 INFO L93 Difference]: Finished difference Result 66 states and 101 transitions. [2022-04-15 15:35:18,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 15:35:18,181 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-15 15:35:18,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:18,182 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 101 transitions. [2022-04-15 15:35:18,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 101 transitions. [2022-04-15 15:35:18,205 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 101 transitions. [2022-04-15 15:35:18,333 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 101 edges. 101 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:18,340 INFO L225 Difference]: With dead ends: 66 [2022-04-15 15:35:18,340 INFO L226 Difference]: Without dead ends: 33 [2022-04-15 15:35:18,343 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 15:35:18,347 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:18,348 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 49 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:35:18,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-15 15:35:18,377 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2022-04-15 15:35:18,377 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:18,378 INFO L82 GeneralOperation]: Start isEquivalent. First operand 33 states. Second operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,378 INFO L74 IsIncluded]: Start isIncluded. First operand 33 states. Second operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,379 INFO L87 Difference]: Start difference. First operand 33 states. Second operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:18,383 INFO L93 Difference]: Finished difference Result 33 states and 43 transitions. [2022-04-15 15:35:18,383 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-15 15:35:18,383 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:18,384 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:18,384 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 33 states. [2022-04-15 15:35:18,385 INFO L87 Difference]: Start difference. First operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 33 states. [2022-04-15 15:35:18,387 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:18,387 INFO L93 Difference]: Finished difference Result 33 states and 43 transitions. [2022-04-15 15:35:18,387 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-15 15:35:18,388 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:18,388 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:18,388 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:18,388 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:18,389 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2022-04-15 15:35:18,392 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 18 [2022-04-15 15:35:18,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:18,392 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2022-04-15 15:35:18,392 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,392 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 42 transitions. [2022-04-15 15:35:18,426 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 42 edges. 42 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:18,426 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-15 15:35:18,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-15 15:35:18,427 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:18,427 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:18,427 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 15:35:18,427 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:18,428 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:18,428 INFO L85 PathProgramCache]: Analyzing trace with hash 336486197, now seen corresponding path program 1 times [2022-04-15 15:35:18,428 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:18,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2003582082] [2022-04-15 15:35:18,435 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:18,435 INFO L85 PathProgramCache]: Analyzing trace with hash 336486197, now seen corresponding path program 2 times [2022-04-15 15:35:18,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:18,436 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [679785738] [2022-04-15 15:35:18,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:18,436 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:18,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:18,538 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:35:18,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:18,544 INFO L290 TraceCheckUtils]: 0: Hoare triple {326#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {314#true} is VALID [2022-04-15 15:35:18,544 INFO L290 TraceCheckUtils]: 1: Hoare triple {314#true} assume true; {314#true} is VALID [2022-04-15 15:35:18,545 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {314#true} {314#true} #96#return; {314#true} is VALID [2022-04-15 15:35:18,545 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 15:35:18,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:18,563 INFO L290 TraceCheckUtils]: 0: Hoare triple {314#true} ~cond := #in~cond; {314#true} is VALID [2022-04-15 15:35:18,564 INFO L290 TraceCheckUtils]: 1: Hoare triple {314#true} assume !(0 == ~cond); {314#true} is VALID [2022-04-15 15:35:18,564 INFO L290 TraceCheckUtils]: 2: Hoare triple {314#true} assume true; {314#true} is VALID [2022-04-15 15:35:18,564 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {314#true} {314#true} #80#return; {314#true} is VALID [2022-04-15 15:35:18,565 INFO L272 TraceCheckUtils]: 0: Hoare triple {314#true} call ULTIMATE.init(); {326#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:35:18,565 INFO L290 TraceCheckUtils]: 1: Hoare triple {326#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {314#true} is VALID [2022-04-15 15:35:18,565 INFO L290 TraceCheckUtils]: 2: Hoare triple {314#true} assume true; {314#true} is VALID [2022-04-15 15:35:18,565 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {314#true} {314#true} #96#return; {314#true} is VALID [2022-04-15 15:35:18,565 INFO L272 TraceCheckUtils]: 4: Hoare triple {314#true} call #t~ret8 := main(); {314#true} is VALID [2022-04-15 15:35:18,566 INFO L290 TraceCheckUtils]: 5: Hoare triple {314#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;~B~0 := #t~nondet5;havoc #t~nondet5; {314#true} is VALID [2022-04-15 15:35:18,566 INFO L272 TraceCheckUtils]: 6: Hoare triple {314#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {314#true} is VALID [2022-04-15 15:35:18,566 INFO L290 TraceCheckUtils]: 7: Hoare triple {314#true} ~cond := #in~cond; {314#true} is VALID [2022-04-15 15:35:18,566 INFO L290 TraceCheckUtils]: 8: Hoare triple {314#true} assume !(0 == ~cond); {314#true} is VALID [2022-04-15 15:35:18,566 INFO L290 TraceCheckUtils]: 9: Hoare triple {314#true} assume true; {314#true} is VALID [2022-04-15 15:35:18,566 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {314#true} {314#true} #80#return; {314#true} is VALID [2022-04-15 15:35:18,567 INFO L290 TraceCheckUtils]: 11: Hoare triple {314#true} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {323#(= main_~q~0 0)} is VALID [2022-04-15 15:35:18,568 INFO L290 TraceCheckUtils]: 12: Hoare triple {323#(= main_~q~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {323#(= main_~q~0 0)} is VALID [2022-04-15 15:35:18,568 INFO L290 TraceCheckUtils]: 13: Hoare triple {323#(= main_~q~0 0)} assume !!(#t~post6 < 5);havoc #t~post6; {323#(= main_~q~0 0)} is VALID [2022-04-15 15:35:18,569 INFO L272 TraceCheckUtils]: 14: Hoare triple {323#(= main_~q~0 0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {324#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:35:18,570 INFO L290 TraceCheckUtils]: 15: Hoare triple {324#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {325#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 15:35:18,570 INFO L290 TraceCheckUtils]: 16: Hoare triple {325#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {315#false} is VALID [2022-04-15 15:35:18,570 INFO L290 TraceCheckUtils]: 17: Hoare triple {315#false} assume !false; {315#false} is VALID [2022-04-15 15:35:18,571 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:35:18,571 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:18,571 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [679785738] [2022-04-15 15:35:18,571 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [679785738] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:18,571 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:18,571 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:35:18,572 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:18,572 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2003582082] [2022-04-15 15:35:18,572 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2003582082] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:18,572 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:18,572 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:35:18,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1309875560] [2022-04-15 15:35:18,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:18,573 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-15 15:35:18,573 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:18,573 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,585 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:18,585 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 15:35:18,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:18,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 15:35:18,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 15:35:18,586 INFO L87 Difference]: Start difference. First operand 32 states and 42 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:18,892 INFO L93 Difference]: Finished difference Result 47 states and 62 transitions. [2022-04-15 15:35:18,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 15:35:18,892 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-15 15:35:18,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:18,892 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 62 transitions. [2022-04-15 15:35:18,894 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 62 transitions. [2022-04-15 15:35:18,895 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 62 transitions. [2022-04-15 15:35:18,952 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 62 edges. 62 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:18,955 INFO L225 Difference]: With dead ends: 47 [2022-04-15 15:35:18,955 INFO L226 Difference]: Without dead ends: 45 [2022-04-15 15:35:18,956 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 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 15:35:18,958 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 28 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:18,958 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 90 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 15:35:18,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-15 15:35:18,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 36. [2022-04-15 15:35:18,971 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:18,971 INFO L82 GeneralOperation]: Start isEquivalent. First operand 45 states. Second operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,972 INFO L74 IsIncluded]: Start isIncluded. First operand 45 states. Second operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,972 INFO L87 Difference]: Start difference. First operand 45 states. Second operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:18,974 INFO L93 Difference]: Finished difference Result 45 states and 60 transitions. [2022-04-15 15:35:18,974 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 60 transitions. [2022-04-15 15:35:18,974 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:18,975 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:18,975 INFO L74 IsIncluded]: Start isIncluded. First operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 45 states. [2022-04-15 15:35:18,975 INFO L87 Difference]: Start difference. First operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 45 states. [2022-04-15 15:35:18,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:18,977 INFO L93 Difference]: Finished difference Result 45 states and 60 transitions. [2022-04-15 15:35:18,977 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 60 transitions. [2022-04-15 15:35:18,978 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:18,978 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:18,978 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:18,978 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:18,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:18,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 45 transitions. [2022-04-15 15:35:18,979 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 45 transitions. Word has length 18 [2022-04-15 15:35:18,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:18,980 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 45 transitions. [2022-04-15 15:35:18,980 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, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 15:35:18,980 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 36 states and 45 transitions. [2022-04-15 15:35:19,013 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 45 edges. 45 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:19,013 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-04-15 15:35:19,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-15 15:35:19,014 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:19,014 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:19,014 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 15:35:19,014 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:19,014 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:19,015 INFO L85 PathProgramCache]: Analyzing trace with hash -1819267188, now seen corresponding path program 1 times [2022-04-15 15:35:19,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:19,015 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1719778647] [2022-04-15 15:35:19,015 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:19,015 INFO L85 PathProgramCache]: Analyzing trace with hash -1819267188, now seen corresponding path program 2 times [2022-04-15 15:35:19,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:19,015 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1178135743] [2022-04-15 15:35:19,016 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:19,016 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:19,028 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:35:19,028 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [625766784] [2022-04-15 15:35:19,028 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:35:19,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:19,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:19,031 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 15:35:19,034 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 15:35:19,067 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-15 15:35:19,067 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:35:19,068 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-15 15:35:19,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:19,099 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:35:19,270 INFO L272 TraceCheckUtils]: 0: Hoare triple {593#true} call ULTIMATE.init(); {593#true} is VALID [2022-04-15 15:35:19,271 INFO L290 TraceCheckUtils]: 1: Hoare triple {593#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,271 INFO L290 TraceCheckUtils]: 2: Hoare triple {601#(<= ~counter~0 0)} assume true; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,272 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {601#(<= ~counter~0 0)} {593#true} #96#return; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,272 INFO L272 TraceCheckUtils]: 4: Hoare triple {601#(<= ~counter~0 0)} call #t~ret8 := main(); {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,272 INFO L290 TraceCheckUtils]: 5: Hoare triple {601#(<= ~counter~0 0)} 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;~B~0 := #t~nondet5;havoc #t~nondet5; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,273 INFO L272 TraceCheckUtils]: 6: Hoare triple {601#(<= ~counter~0 0)} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,273 INFO L290 TraceCheckUtils]: 7: Hoare triple {601#(<= ~counter~0 0)} ~cond := #in~cond; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,273 INFO L290 TraceCheckUtils]: 8: Hoare triple {601#(<= ~counter~0 0)} assume !(0 == ~cond); {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,274 INFO L290 TraceCheckUtils]: 9: Hoare triple {601#(<= ~counter~0 0)} assume true; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,274 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {601#(<= ~counter~0 0)} {601#(<= ~counter~0 0)} #80#return; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,274 INFO L290 TraceCheckUtils]: 11: Hoare triple {601#(<= ~counter~0 0)} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {601#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:19,275 INFO L290 TraceCheckUtils]: 12: Hoare triple {601#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {635#(<= |main_#t~post6| 0)} is VALID [2022-04-15 15:35:19,275 INFO L290 TraceCheckUtils]: 13: Hoare triple {635#(<= |main_#t~post6| 0)} assume !(#t~post6 < 5);havoc #t~post6; {594#false} is VALID [2022-04-15 15:35:19,275 INFO L290 TraceCheckUtils]: 14: Hoare triple {594#false} #t~post7 := ~counter~0;~counter~0 := 1 + #t~post7; {594#false} is VALID [2022-04-15 15:35:19,275 INFO L290 TraceCheckUtils]: 15: Hoare triple {594#false} assume !(#t~post7 < 5);havoc #t~post7; {594#false} is VALID [2022-04-15 15:35:19,276 INFO L272 TraceCheckUtils]: 16: Hoare triple {594#false} call __VERIFIER_assert((if ~A~0 % 4294967296 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {594#false} is VALID [2022-04-15 15:35:19,276 INFO L290 TraceCheckUtils]: 17: Hoare triple {594#false} ~cond := #in~cond; {594#false} is VALID [2022-04-15 15:35:19,276 INFO L290 TraceCheckUtils]: 18: Hoare triple {594#false} assume 0 == ~cond; {594#false} is VALID [2022-04-15 15:35:19,276 INFO L290 TraceCheckUtils]: 19: Hoare triple {594#false} assume !false; {594#false} is VALID [2022-04-15 15:35:19,276 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:35:19,276 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:35:19,276 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:19,276 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1178135743] [2022-04-15 15:35:19,277 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:35:19,277 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [625766784] [2022-04-15 15:35:19,277 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [625766784] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:19,277 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:19,277 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 15:35:19,277 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:19,277 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1719778647] [2022-04-15 15:35:19,278 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1719778647] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:19,278 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:19,278 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 15:35:19,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1678135633] [2022-04-15 15:35:19,278 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:19,278 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-15 15:35:19,278 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:19,278 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:35:19,289 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:19,289 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-15 15:35:19,289 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:19,289 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-15 15:35:19,290 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-15 15:35:19,290 INFO L87 Difference]: Start difference. First operand 36 states and 45 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:35:19,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:19,369 INFO L93 Difference]: Finished difference Result 52 states and 67 transitions. [2022-04-15 15:35:19,369 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-15 15:35:19,369 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-15 15:35:19,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:19,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:35:19,370 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 64 transitions. [2022-04-15 15:35:19,370 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:35:19,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 64 transitions. [2022-04-15 15:35:19,372 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 64 transitions. [2022-04-15 15:35:19,417 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:19,418 INFO L225 Difference]: With dead ends: 52 [2022-04-15 15:35:19,418 INFO L226 Difference]: Without dead ends: 38 [2022-04-15 15:35:19,419 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-15 15:35:19,420 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:19,420 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 107 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:35:19,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-04-15 15:35:19,443 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-04-15 15:35:19,443 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:19,446 INFO L82 GeneralOperation]: Start isEquivalent. First operand 38 states. Second operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:19,447 INFO L74 IsIncluded]: Start isIncluded. First operand 38 states. Second operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:19,447 INFO L87 Difference]: Start difference. First operand 38 states. Second operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:19,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:19,449 INFO L93 Difference]: Finished difference Result 38 states and 47 transitions. [2022-04-15 15:35:19,449 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2022-04-15 15:35:19,450 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:19,450 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:19,451 INFO L74 IsIncluded]: Start isIncluded. First operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 38 states. [2022-04-15 15:35:19,451 INFO L87 Difference]: Start difference. First operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 38 states. [2022-04-15 15:35:19,454 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:19,454 INFO L93 Difference]: Finished difference Result 38 states and 47 transitions. [2022-04-15 15:35:19,454 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2022-04-15 15:35:19,457 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:19,457 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:19,457 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:19,457 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:19,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:19,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2022-04-15 15:35:19,459 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 20 [2022-04-15 15:35:19,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:19,459 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2022-04-15 15:35:19,459 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:35:19,459 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 38 states and 47 transitions. [2022-04-15 15:35:19,492 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 47 edges. 47 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:19,492 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2022-04-15 15:35:19,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-15 15:35:19,493 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:19,493 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:19,511 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-15 15:35:19,707 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:19,707 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:19,708 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:19,708 INFO L85 PathProgramCache]: Analyzing trace with hash -784889968, now seen corresponding path program 1 times [2022-04-15 15:35:19,708 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:19,708 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [630797623] [2022-04-15 15:35:19,712 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:19,712 INFO L85 PathProgramCache]: Analyzing trace with hash -784889968, now seen corresponding path program 2 times [2022-04-15 15:35:19,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:19,712 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1274986269] [2022-04-15 15:35:19,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:19,712 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:19,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:19,762 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:35:19,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:19,769 INFO L290 TraceCheckUtils]: 0: Hoare triple {928#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {912#true} is VALID [2022-04-15 15:35:19,770 INFO L290 TraceCheckUtils]: 1: Hoare triple {912#true} assume true; {912#true} is VALID [2022-04-15 15:35:19,770 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {912#true} {912#true} #96#return; {912#true} is VALID [2022-04-15 15:35:19,770 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 15:35:19,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:19,774 INFO L290 TraceCheckUtils]: 0: Hoare triple {912#true} ~cond := #in~cond; {912#true} is VALID [2022-04-15 15:35:19,774 INFO L290 TraceCheckUtils]: 1: Hoare triple {912#true} assume !(0 == ~cond); {912#true} is VALID [2022-04-15 15:35:19,774 INFO L290 TraceCheckUtils]: 2: Hoare triple {912#true} assume true; {912#true} is VALID [2022-04-15 15:35:19,774 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {912#true} {912#true} #80#return; {912#true} is VALID [2022-04-15 15:35:19,774 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-04-15 15:35:19,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:19,780 INFO L290 TraceCheckUtils]: 0: Hoare triple {912#true} ~cond := #in~cond; {912#true} is VALID [2022-04-15 15:35:19,780 INFO L290 TraceCheckUtils]: 1: Hoare triple {912#true} assume !(0 == ~cond); {912#true} is VALID [2022-04-15 15:35:19,780 INFO L290 TraceCheckUtils]: 2: Hoare triple {912#true} assume true; {912#true} is VALID [2022-04-15 15:35:19,781 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {912#true} {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} #82#return; {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} is VALID [2022-04-15 15:35:19,782 INFO L272 TraceCheckUtils]: 0: Hoare triple {912#true} call ULTIMATE.init(); {928#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:35:19,782 INFO L290 TraceCheckUtils]: 1: Hoare triple {928#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {912#true} is VALID [2022-04-15 15:35:19,782 INFO L290 TraceCheckUtils]: 2: Hoare triple {912#true} assume true; {912#true} is VALID [2022-04-15 15:35:19,782 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {912#true} {912#true} #96#return; {912#true} is VALID [2022-04-15 15:35:19,782 INFO L272 TraceCheckUtils]: 4: Hoare triple {912#true} call #t~ret8 := main(); {912#true} is VALID [2022-04-15 15:35:19,782 INFO L290 TraceCheckUtils]: 5: Hoare triple {912#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;~B~0 := #t~nondet5;havoc #t~nondet5; {912#true} is VALID [2022-04-15 15:35:19,782 INFO L272 TraceCheckUtils]: 6: Hoare triple {912#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {912#true} is VALID [2022-04-15 15:35:19,782 INFO L290 TraceCheckUtils]: 7: Hoare triple {912#true} ~cond := #in~cond; {912#true} is VALID [2022-04-15 15:35:19,783 INFO L290 TraceCheckUtils]: 8: Hoare triple {912#true} assume !(0 == ~cond); {912#true} is VALID [2022-04-15 15:35:19,783 INFO L290 TraceCheckUtils]: 9: Hoare triple {912#true} assume true; {912#true} is VALID [2022-04-15 15:35:19,783 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {912#true} {912#true} #80#return; {912#true} is VALID [2022-04-15 15:35:19,786 INFO L290 TraceCheckUtils]: 11: Hoare triple {912#true} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} is VALID [2022-04-15 15:35:19,786 INFO L290 TraceCheckUtils]: 12: Hoare triple {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} is VALID [2022-04-15 15:35:19,787 INFO L290 TraceCheckUtils]: 13: Hoare triple {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} assume !!(#t~post6 < 5);havoc #t~post6; {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} is VALID [2022-04-15 15:35:19,787 INFO L272 TraceCheckUtils]: 14: Hoare triple {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {912#true} is VALID [2022-04-15 15:35:19,787 INFO L290 TraceCheckUtils]: 15: Hoare triple {912#true} ~cond := #in~cond; {912#true} is VALID [2022-04-15 15:35:19,787 INFO L290 TraceCheckUtils]: 16: Hoare triple {912#true} assume !(0 == ~cond); {912#true} is VALID [2022-04-15 15:35:19,787 INFO L290 TraceCheckUtils]: 17: Hoare triple {912#true} assume true; {912#true} is VALID [2022-04-15 15:35:19,788 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {912#true} {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} #82#return; {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} is VALID [2022-04-15 15:35:19,789 INFO L272 TraceCheckUtils]: 19: Hoare triple {921#(= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296)))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {926#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:35:19,789 INFO L290 TraceCheckUtils]: 20: Hoare triple {926#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {927#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 15:35:19,791 INFO L290 TraceCheckUtils]: 21: Hoare triple {927#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {913#false} is VALID [2022-04-15 15:35:19,791 INFO L290 TraceCheckUtils]: 22: Hoare triple {913#false} assume !false; {913#false} is VALID [2022-04-15 15:35:19,791 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:35:19,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:19,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1274986269] [2022-04-15 15:35:19,792 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1274986269] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:19,792 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:19,792 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:35:19,792 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:19,792 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [630797623] [2022-04-15 15:35:19,792 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [630797623] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:19,792 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:19,792 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:35:19,792 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1299843225] [2022-04-15 15:35:19,793 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:19,793 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-15 15:35:19,793 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:19,793 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 15:35:19,808 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:19,808 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 15:35:19,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:19,809 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 15:35:19,809 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 15:35:19,810 INFO L87 Difference]: Start difference. First operand 38 states and 47 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 15:35:20,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:20,171 INFO L93 Difference]: Finished difference Result 52 states and 66 transitions. [2022-04-15 15:35:20,171 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 15:35:20,172 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-15 15:35:20,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:20,172 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 15:35:20,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 62 transitions. [2022-04-15 15:35:20,174 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 15:35:20,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 62 transitions. [2022-04-15 15:35:20,175 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 62 transitions. [2022-04-15 15:35:20,237 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 62 edges. 62 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:20,242 INFO L225 Difference]: With dead ends: 52 [2022-04-15 15:35:20,242 INFO L226 Difference]: Without dead ends: 50 [2022-04-15 15:35:20,243 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 7 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 15:35:20,246 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 23 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 126 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:20,246 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 83 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 15:35:20,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-15 15:35:20,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 42. [2022-04-15 15:35:20,263 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:20,264 INFO L82 GeneralOperation]: Start isEquivalent. First operand 50 states. Second operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:20,264 INFO L74 IsIncluded]: Start isIncluded. First operand 50 states. Second operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:20,264 INFO L87 Difference]: Start difference. First operand 50 states. Second operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:20,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:20,266 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-04-15 15:35:20,266 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-15 15:35:20,266 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:20,266 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:20,267 INFO L74 IsIncluded]: Start isIncluded. First operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 50 states. [2022-04-15 15:35:20,267 INFO L87 Difference]: Start difference. First operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 50 states. [2022-04-15 15:35:20,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:20,269 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-04-15 15:35:20,269 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-15 15:35:20,269 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:20,269 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:20,269 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:20,269 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:20,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:35:20,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 50 transitions. [2022-04-15 15:35:20,271 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 50 transitions. Word has length 23 [2022-04-15 15:35:20,271 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:20,271 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 50 transitions. [2022-04-15 15:35:20,271 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, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 15:35:20,272 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 42 states and 50 transitions. [2022-04-15 15:35:20,315 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:20,315 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 50 transitions. [2022-04-15 15:35:20,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-15 15:35:20,315 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:20,315 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:20,316 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-15 15:35:20,316 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:20,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:20,316 INFO L85 PathProgramCache]: Analyzing trace with hash -1024624683, now seen corresponding path program 1 times [2022-04-15 15:35:20,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:20,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1781396898] [2022-04-15 15:35:20,316 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:20,317 INFO L85 PathProgramCache]: Analyzing trace with hash -1024624683, now seen corresponding path program 2 times [2022-04-15 15:35:20,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:20,317 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1731433521] [2022-04-15 15:35:20,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:20,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:20,333 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:35:20,333 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2062477424] [2022-04-15 15:35:20,333 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:35:20,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:20,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:20,342 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 15:35:20,343 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 15:35:20,386 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:35:20,386 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:35:20,387 INFO L263 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 15:35:20,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:20,394 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:35:20,517 INFO L272 TraceCheckUtils]: 0: Hoare triple {1227#true} call ULTIMATE.init(); {1227#true} is VALID [2022-04-15 15:35:20,517 INFO L290 TraceCheckUtils]: 1: Hoare triple {1227#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1227#true} is VALID [2022-04-15 15:35:20,517 INFO L290 TraceCheckUtils]: 2: Hoare triple {1227#true} assume true; {1227#true} is VALID [2022-04-15 15:35:20,517 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1227#true} {1227#true} #96#return; {1227#true} is VALID [2022-04-15 15:35:20,517 INFO L272 TraceCheckUtils]: 4: Hoare triple {1227#true} call #t~ret8 := main(); {1227#true} is VALID [2022-04-15 15:35:20,517 INFO L290 TraceCheckUtils]: 5: Hoare triple {1227#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;~B~0 := #t~nondet5;havoc #t~nondet5; {1227#true} is VALID [2022-04-15 15:35:20,517 INFO L272 TraceCheckUtils]: 6: Hoare triple {1227#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {1227#true} is VALID [2022-04-15 15:35:20,518 INFO L290 TraceCheckUtils]: 7: Hoare triple {1227#true} ~cond := #in~cond; {1227#true} is VALID [2022-04-15 15:35:20,518 INFO L290 TraceCheckUtils]: 8: Hoare triple {1227#true} assume !(0 == ~cond); {1227#true} is VALID [2022-04-15 15:35:20,518 INFO L290 TraceCheckUtils]: 9: Hoare triple {1227#true} assume true; {1227#true} is VALID [2022-04-15 15:35:20,518 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1227#true} {1227#true} #80#return; {1227#true} is VALID [2022-04-15 15:35:20,518 INFO L290 TraceCheckUtils]: 11: Hoare triple {1227#true} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:35:20,519 INFO L290 TraceCheckUtils]: 12: Hoare triple {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:35:20,519 INFO L290 TraceCheckUtils]: 13: Hoare triple {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} assume !!(#t~post6 < 5);havoc #t~post6; {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:35:20,519 INFO L272 TraceCheckUtils]: 14: Hoare triple {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1227#true} is VALID [2022-04-15 15:35:20,519 INFO L290 TraceCheckUtils]: 15: Hoare triple {1227#true} ~cond := #in~cond; {1227#true} is VALID [2022-04-15 15:35:20,519 INFO L290 TraceCheckUtils]: 16: Hoare triple {1227#true} assume !(0 == ~cond); {1227#true} is VALID [2022-04-15 15:35:20,520 INFO L290 TraceCheckUtils]: 17: Hoare triple {1227#true} assume true; {1227#true} is VALID [2022-04-15 15:35:20,520 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1227#true} {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #82#return; {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:35:20,520 INFO L272 TraceCheckUtils]: 19: Hoare triple {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {1227#true} is VALID [2022-04-15 15:35:20,520 INFO L290 TraceCheckUtils]: 20: Hoare triple {1227#true} ~cond := #in~cond; {1227#true} is VALID [2022-04-15 15:35:20,520 INFO L290 TraceCheckUtils]: 21: Hoare triple {1227#true} assume !(0 == ~cond); {1227#true} is VALID [2022-04-15 15:35:20,520 INFO L290 TraceCheckUtils]: 22: Hoare triple {1227#true} assume true; {1227#true} is VALID [2022-04-15 15:35:20,521 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {1227#true} {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #84#return; {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:35:20,521 INFO L272 TraceCheckUtils]: 24: Hoare triple {1265#(and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {1305#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:35:20,522 INFO L290 TraceCheckUtils]: 25: Hoare triple {1305#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1309#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:35:20,522 INFO L290 TraceCheckUtils]: 26: Hoare triple {1309#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1228#false} is VALID [2022-04-15 15:35:20,522 INFO L290 TraceCheckUtils]: 27: Hoare triple {1228#false} assume !false; {1228#false} is VALID [2022-04-15 15:35:20,522 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-15 15:35:20,522 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:35:20,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:20,523 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1731433521] [2022-04-15 15:35:20,523 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:35:20,523 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2062477424] [2022-04-15 15:35:20,523 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2062477424] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:20,523 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:20,523 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:20,523 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:20,523 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1781396898] [2022-04-15 15:35:20,523 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1781396898] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:20,523 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:20,523 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:20,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1064268182] [2022-04-15 15:35:20,523 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:20,524 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-15 15:35:20,524 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:20,524 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:35:20,539 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:20,539 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:35:20,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:20,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:35:20,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:35:20,540 INFO L87 Difference]: Start difference. First operand 42 states and 50 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:35:20,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:20,721 INFO L93 Difference]: Finished difference Result 71 states and 93 transitions. [2022-04-15 15:35:20,721 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:35:20,721 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-15 15:35:20,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:20,723 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:35:20,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 87 transitions. [2022-04-15 15:35:20,726 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:35:20,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 87 transitions. [2022-04-15 15:35:20,728 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 87 transitions. [2022-04-15 15:35:20,795 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 87 edges. 87 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:20,797 INFO L225 Difference]: With dead ends: 71 [2022-04-15 15:35:20,798 INFO L226 Difference]: Without dead ends: 56 [2022-04-15 15:35:20,798 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 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 15:35:20,801 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 10 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:20,801 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 143 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:35:20,802 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-04-15 15:35:20,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2022-04-15 15:35:20,827 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:20,827 INFO L82 GeneralOperation]: Start isEquivalent. First operand 56 states. Second operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:20,827 INFO L74 IsIncluded]: Start isIncluded. First operand 56 states. Second operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:20,828 INFO L87 Difference]: Start difference. First operand 56 states. Second operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:20,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:20,833 INFO L93 Difference]: Finished difference Result 56 states and 70 transitions. [2022-04-15 15:35:20,833 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2022-04-15 15:35:20,834 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:20,834 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:20,834 INFO L74 IsIncluded]: Start isIncluded. First operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand 56 states. [2022-04-15 15:35:20,834 INFO L87 Difference]: Start difference. First operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand 56 states. [2022-04-15 15:35:20,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:20,836 INFO L93 Difference]: Finished difference Result 56 states and 70 transitions. [2022-04-15 15:35:20,836 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2022-04-15 15:35:20,836 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:20,836 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:20,836 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:20,836 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:20,837 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:20,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 70 transitions. [2022-04-15 15:35:20,838 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 70 transitions. Word has length 28 [2022-04-15 15:35:20,838 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:20,838 INFO L478 AbstractCegarLoop]: Abstraction has 56 states and 70 transitions. [2022-04-15 15:35:20,839 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:35:20,839 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 56 states and 70 transitions. [2022-04-15 15:35:20,895 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 70 edges. 70 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:20,895 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2022-04-15 15:35:20,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-15 15:35:20,895 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:20,896 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:20,911 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-15 15:35:21,111 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 15:35:21,112 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:21,112 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:21,112 INFO L85 PathProgramCache]: Analyzing trace with hash 1301357193, now seen corresponding path program 1 times [2022-04-15 15:35:21,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:21,112 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [347451586] [2022-04-15 15:35:21,112 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:21,113 INFO L85 PathProgramCache]: Analyzing trace with hash 1301357193, now seen corresponding path program 2 times [2022-04-15 15:35:21,113 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:21,113 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [49079309] [2022-04-15 15:35:21,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:21,113 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:21,132 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:35:21,132 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [297550192] [2022-04-15 15:35:21,132 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:35:21,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:21,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:21,142 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 15:35:21,142 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 15:35:21,185 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:35:21,185 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:35:21,186 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 15:35:21,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:21,196 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:35:21,339 INFO L272 TraceCheckUtils]: 0: Hoare triple {1683#true} call ULTIMATE.init(); {1683#true} is VALID [2022-04-15 15:35:21,340 INFO L290 TraceCheckUtils]: 1: Hoare triple {1683#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,340 INFO L290 TraceCheckUtils]: 2: Hoare triple {1691#(<= ~counter~0 0)} assume true; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,341 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1691#(<= ~counter~0 0)} {1683#true} #96#return; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,341 INFO L272 TraceCheckUtils]: 4: Hoare triple {1691#(<= ~counter~0 0)} call #t~ret8 := main(); {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,341 INFO L290 TraceCheckUtils]: 5: Hoare triple {1691#(<= ~counter~0 0)} 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;~B~0 := #t~nondet5;havoc #t~nondet5; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,342 INFO L272 TraceCheckUtils]: 6: Hoare triple {1691#(<= ~counter~0 0)} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,342 INFO L290 TraceCheckUtils]: 7: Hoare triple {1691#(<= ~counter~0 0)} ~cond := #in~cond; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,342 INFO L290 TraceCheckUtils]: 8: Hoare triple {1691#(<= ~counter~0 0)} assume !(0 == ~cond); {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,342 INFO L290 TraceCheckUtils]: 9: Hoare triple {1691#(<= ~counter~0 0)} assume true; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,343 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1691#(<= ~counter~0 0)} {1691#(<= ~counter~0 0)} #80#return; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,343 INFO L290 TraceCheckUtils]: 11: Hoare triple {1691#(<= ~counter~0 0)} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {1691#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:21,343 INFO L290 TraceCheckUtils]: 12: Hoare triple {1691#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,344 INFO L290 TraceCheckUtils]: 13: Hoare triple {1725#(<= ~counter~0 1)} assume !!(#t~post6 < 5);havoc #t~post6; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,344 INFO L272 TraceCheckUtils]: 14: Hoare triple {1725#(<= ~counter~0 1)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,344 INFO L290 TraceCheckUtils]: 15: Hoare triple {1725#(<= ~counter~0 1)} ~cond := #in~cond; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,345 INFO L290 TraceCheckUtils]: 16: Hoare triple {1725#(<= ~counter~0 1)} assume !(0 == ~cond); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,345 INFO L290 TraceCheckUtils]: 17: Hoare triple {1725#(<= ~counter~0 1)} assume true; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,345 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1725#(<= ~counter~0 1)} {1725#(<= ~counter~0 1)} #82#return; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,346 INFO L272 TraceCheckUtils]: 19: Hoare triple {1725#(<= ~counter~0 1)} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,346 INFO L290 TraceCheckUtils]: 20: Hoare triple {1725#(<= ~counter~0 1)} ~cond := #in~cond; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,346 INFO L290 TraceCheckUtils]: 21: Hoare triple {1725#(<= ~counter~0 1)} assume !(0 == ~cond); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,347 INFO L290 TraceCheckUtils]: 22: Hoare triple {1725#(<= ~counter~0 1)} assume true; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,347 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {1725#(<= ~counter~0 1)} {1725#(<= ~counter~0 1)} #84#return; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,347 INFO L272 TraceCheckUtils]: 24: Hoare triple {1725#(<= ~counter~0 1)} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,348 INFO L290 TraceCheckUtils]: 25: Hoare triple {1725#(<= ~counter~0 1)} ~cond := #in~cond; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,348 INFO L290 TraceCheckUtils]: 26: Hoare triple {1725#(<= ~counter~0 1)} assume !(0 == ~cond); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,348 INFO L290 TraceCheckUtils]: 27: Hoare triple {1725#(<= ~counter~0 1)} assume true; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,349 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1725#(<= ~counter~0 1)} {1725#(<= ~counter~0 1)} #86#return; {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,349 INFO L290 TraceCheckUtils]: 29: Hoare triple {1725#(<= ~counter~0 1)} assume !(~r~0 >= ~d~0); {1725#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:21,349 INFO L290 TraceCheckUtils]: 30: Hoare triple {1725#(<= ~counter~0 1)} #t~post7 := ~counter~0;~counter~0 := 1 + #t~post7; {1780#(<= |main_#t~post7| 1)} is VALID [2022-04-15 15:35:21,350 INFO L290 TraceCheckUtils]: 31: Hoare triple {1780#(<= |main_#t~post7| 1)} assume !(#t~post7 < 5);havoc #t~post7; {1684#false} is VALID [2022-04-15 15:35:21,350 INFO L272 TraceCheckUtils]: 32: Hoare triple {1684#false} call __VERIFIER_assert((if ~A~0 % 4294967296 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {1684#false} is VALID [2022-04-15 15:35:21,350 INFO L290 TraceCheckUtils]: 33: Hoare triple {1684#false} ~cond := #in~cond; {1684#false} is VALID [2022-04-15 15:35:21,350 INFO L290 TraceCheckUtils]: 34: Hoare triple {1684#false} assume 0 == ~cond; {1684#false} is VALID [2022-04-15 15:35:21,350 INFO L290 TraceCheckUtils]: 35: Hoare triple {1684#false} assume !false; {1684#false} is VALID [2022-04-15 15:35:21,350 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 15:35:21,350 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:35:21,350 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:21,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [49079309] [2022-04-15 15:35:21,351 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:35:21,351 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [297550192] [2022-04-15 15:35:21,351 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [297550192] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:21,351 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:21,351 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:21,351 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:21,351 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [347451586] [2022-04-15 15:35:21,351 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [347451586] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:21,351 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:21,351 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:21,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1464743275] [2022-04-15 15:35:21,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:21,352 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 36 [2022-04-15 15:35:21,352 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:21,352 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-15 15:35:21,373 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:21,373 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:35:21,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:21,374 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:35:21,374 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:35:21,374 INFO L87 Difference]: Start difference. First operand 56 states and 70 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-15 15:35:21,508 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:21,509 INFO L93 Difference]: Finished difference Result 76 states and 86 transitions. [2022-04-15 15:35:21,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:35:21,509 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 36 [2022-04-15 15:35:21,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:21,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-15 15:35:21,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-15 15:35:21,510 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-15 15:35:21,511 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-15 15:35:21,511 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 65 transitions. [2022-04-15 15:35:21,554 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 15:35:21,555 INFO L225 Difference]: With dead ends: 76 [2022-04-15 15:35:21,555 INFO L226 Difference]: Without dead ends: 69 [2022-04-15 15:35:21,555 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:35:21,556 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 7 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:21,556 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 117 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:35:21,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-04-15 15:35:21,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 68. [2022-04-15 15:35:21,595 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:21,596 INFO L82 GeneralOperation]: Start isEquivalent. First operand 69 states. Second operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:21,596 INFO L74 IsIncluded]: Start isIncluded. First operand 69 states. Second operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:21,596 INFO L87 Difference]: Start difference. First operand 69 states. Second operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:21,598 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:21,598 INFO L93 Difference]: Finished difference Result 69 states and 79 transitions. [2022-04-15 15:35:21,598 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 79 transitions. [2022-04-15 15:35:21,598 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:21,598 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:21,599 INFO L74 IsIncluded]: Start isIncluded. First operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand 69 states. [2022-04-15 15:35:21,599 INFO L87 Difference]: Start difference. First operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand 69 states. [2022-04-15 15:35:21,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:21,600 INFO L93 Difference]: Finished difference Result 69 states and 79 transitions. [2022-04-15 15:35:21,600 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 79 transitions. [2022-04-15 15:35:21,601 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:21,601 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:21,601 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:21,601 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:21,601 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:35:21,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 78 transitions. [2022-04-15 15:35:21,603 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 78 transitions. Word has length 36 [2022-04-15 15:35:21,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:21,603 INFO L478 AbstractCegarLoop]: Abstraction has 68 states and 78 transitions. [2022-04-15 15:35:21,603 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-15 15:35:21,603 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 68 states and 78 transitions. [2022-04-15 15:35:21,675 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 78 edges. 78 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:21,676 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 78 transitions. [2022-04-15 15:35:21,676 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-15 15:35:21,676 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:21,676 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:21,697 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-15 15:35:21,892 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 15:35:21,893 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:21,893 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:21,893 INFO L85 PathProgramCache]: Analyzing trace with hash 1303085071, now seen corresponding path program 1 times [2022-04-15 15:35:21,893 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:21,893 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1477433183] [2022-04-15 15:35:21,893 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:35:21,894 INFO L85 PathProgramCache]: Analyzing trace with hash 1303085071, now seen corresponding path program 2 times [2022-04-15 15:35:21,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:21,894 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [23005308] [2022-04-15 15:35:21,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:21,894 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:21,906 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:35:21,906 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1433023264] [2022-04-15 15:35:21,906 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:35:21,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:21,906 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:21,907 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 15:35:21,908 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 15:35:21,942 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:35:21,943 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:35:21,943 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 15:35:21,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:21,952 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:35:22,088 INFO L272 TraceCheckUtils]: 0: Hoare triple {2221#true} call ULTIMATE.init(); {2221#true} is VALID [2022-04-15 15:35:22,088 INFO L290 TraceCheckUtils]: 1: Hoare triple {2221#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L290 TraceCheckUtils]: 2: Hoare triple {2221#true} assume true; {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2221#true} {2221#true} #96#return; {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L272 TraceCheckUtils]: 4: Hoare triple {2221#true} call #t~ret8 := main(); {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L290 TraceCheckUtils]: 5: Hoare triple {2221#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;~B~0 := #t~nondet5;havoc #t~nondet5; {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L272 TraceCheckUtils]: 6: Hoare triple {2221#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L290 TraceCheckUtils]: 7: Hoare triple {2221#true} ~cond := #in~cond; {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L290 TraceCheckUtils]: 8: Hoare triple {2221#true} assume !(0 == ~cond); {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L290 TraceCheckUtils]: 9: Hoare triple {2221#true} assume true; {2221#true} is VALID [2022-04-15 15:35:22,089 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2221#true} {2221#true} #80#return; {2221#true} is VALID [2022-04-15 15:35:22,094 INFO L290 TraceCheckUtils]: 11: Hoare triple {2221#true} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,095 INFO L290 TraceCheckUtils]: 12: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,103 INFO L290 TraceCheckUtils]: 13: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} assume !!(#t~post6 < 5);havoc #t~post6; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,103 INFO L272 TraceCheckUtils]: 14: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {2221#true} is VALID [2022-04-15 15:35:22,103 INFO L290 TraceCheckUtils]: 15: Hoare triple {2221#true} ~cond := #in~cond; {2221#true} is VALID [2022-04-15 15:35:22,103 INFO L290 TraceCheckUtils]: 16: Hoare triple {2221#true} assume !(0 == ~cond); {2221#true} is VALID [2022-04-15 15:35:22,104 INFO L290 TraceCheckUtils]: 17: Hoare triple {2221#true} assume true; {2221#true} is VALID [2022-04-15 15:35:22,106 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {2221#true} {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} #82#return; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,106 INFO L272 TraceCheckUtils]: 19: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {2221#true} is VALID [2022-04-15 15:35:22,106 INFO L290 TraceCheckUtils]: 20: Hoare triple {2221#true} ~cond := #in~cond; {2221#true} is VALID [2022-04-15 15:35:22,106 INFO L290 TraceCheckUtils]: 21: Hoare triple {2221#true} assume !(0 == ~cond); {2221#true} is VALID [2022-04-15 15:35:22,106 INFO L290 TraceCheckUtils]: 22: Hoare triple {2221#true} assume true; {2221#true} is VALID [2022-04-15 15:35:22,111 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {2221#true} {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} #84#return; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,111 INFO L272 TraceCheckUtils]: 24: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {2221#true} is VALID [2022-04-15 15:35:22,111 INFO L290 TraceCheckUtils]: 25: Hoare triple {2221#true} ~cond := #in~cond; {2221#true} is VALID [2022-04-15 15:35:22,111 INFO L290 TraceCheckUtils]: 26: Hoare triple {2221#true} assume !(0 == ~cond); {2221#true} is VALID [2022-04-15 15:35:22,112 INFO L290 TraceCheckUtils]: 27: Hoare triple {2221#true} assume true; {2221#true} is VALID [2022-04-15 15:35:22,112 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2221#true} {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} #86#return; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,112 INFO L290 TraceCheckUtils]: 29: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} assume !(~r~0 >= ~d~0); {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,116 INFO L290 TraceCheckUtils]: 30: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} #t~post7 := ~counter~0;~counter~0 := 1 + #t~post7; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,116 INFO L290 TraceCheckUtils]: 31: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} assume !!(#t~post7 < 5);havoc #t~post7; {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:35:22,117 INFO L272 TraceCheckUtils]: 32: Hoare triple {2259#(and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~A~0 % 4294967296 == ~q~0 * (~B~0 % 4294967296) + ~r~0 then 1 else 0)); {2323#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:35:22,117 INFO L290 TraceCheckUtils]: 33: Hoare triple {2323#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2327#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:35:22,117 INFO L290 TraceCheckUtils]: 34: Hoare triple {2327#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2222#false} is VALID [2022-04-15 15:35:22,117 INFO L290 TraceCheckUtils]: 35: Hoare triple {2222#false} assume !false; {2222#false} is VALID [2022-04-15 15:35:22,118 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 15:35:22,118 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:35:22,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:22,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [23005308] [2022-04-15 15:35:22,118 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:35:22,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1433023264] [2022-04-15 15:35:22,118 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1433023264] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:22,118 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:22,118 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:22,118 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:22,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1477433183] [2022-04-15 15:35:22,119 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1477433183] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:22,119 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:22,119 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:22,119 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1637185794] [2022-04-15 15:35:22,119 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:22,119 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 36 [2022-04-15 15:35:22,119 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:22,119 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 15:35:22,149 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:22,149 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:35:22,149 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:22,149 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:35:22,149 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:35:22,149 INFO L87 Difference]: Start difference. First operand 68 states and 78 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 15:35:22,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:22,339 INFO L93 Difference]: Finished difference Result 82 states and 97 transitions. [2022-04-15 15:35:22,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:35:22,340 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 36 [2022-04-15 15:35:22,341 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:22,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 15:35:22,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 61 transitions. [2022-04-15 15:35:22,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 15:35:22,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 61 transitions. [2022-04-15 15:35:22,345 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 61 transitions. [2022-04-15 15:35:22,393 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 61 edges. 61 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:22,394 INFO L225 Difference]: With dead ends: 82 [2022-04-15 15:35:22,394 INFO L226 Difference]: Without dead ends: 70 [2022-04-15 15:35:22,395 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 32 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 15:35:22,395 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 11 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:22,395 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 118 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:35:22,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-04-15 15:35:22,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 69. [2022-04-15 15:35:22,438 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:22,439 INFO L82 GeneralOperation]: Start isEquivalent. First operand 70 states. Second operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:22,439 INFO L74 IsIncluded]: Start isIncluded. First operand 70 states. Second operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:22,439 INFO L87 Difference]: Start difference. First operand 70 states. Second operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:22,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:22,441 INFO L93 Difference]: Finished difference Result 70 states and 83 transitions. [2022-04-15 15:35:22,441 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 83 transitions. [2022-04-15 15:35:22,441 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:22,441 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:22,441 INFO L74 IsIncluded]: Start isIncluded. First operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) Second operand 70 states. [2022-04-15 15:35:22,442 INFO L87 Difference]: Start difference. First operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) Second operand 70 states. [2022-04-15 15:35:22,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:22,443 INFO L93 Difference]: Finished difference Result 70 states and 83 transitions. [2022-04-15 15:35:22,443 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 83 transitions. [2022-04-15 15:35:22,444 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:22,444 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:22,444 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:22,444 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:22,444 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:22,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 82 transitions. [2022-04-15 15:35:22,446 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 82 transitions. Word has length 36 [2022-04-15 15:35:22,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:22,446 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 82 transitions. [2022-04-15 15:35:22,446 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 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 15:35:22,446 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 69 states and 82 transitions. [2022-04-15 15:35:22,520 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 82 edges. 82 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:22,520 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 82 transitions. [2022-04-15 15:35:22,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-15 15:35:22,520 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:22,520 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:22,549 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 15:35:22,721 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 15:35:22,721 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:22,721 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:22,721 INFO L85 PathProgramCache]: Analyzing trace with hash 817878903, now seen corresponding path program 1 times [2022-04-15 15:35:22,721 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:22,721 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1178012973] [2022-04-15 15:35:29,671 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-15 15:35:29,672 INFO L85 PathProgramCache]: Analyzing trace with hash 119537629, now seen corresponding path program 1 times [2022-04-15 15:35:29,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:29,672 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1863661254] [2022-04-15 15:35:29,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:29,673 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:29,693 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:35:29,694 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1417998357] [2022-04-15 15:35:29,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:29,694 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:29,694 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:29,701 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 15:35:29,701 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-15 15:35:29,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-15 15:35:29,730 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-15 15:35:29,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-15 15:35:29,760 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-15 15:35:29,761 INFO L85 PathProgramCache]: Analyzing trace with hash 817878903, now seen corresponding path program 2 times [2022-04-15 15:35:29,761 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:35:29,761 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1935348610] [2022-04-15 15:35:29,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:35:29,761 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:35:29,776 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:35:29,777 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1372083961] [2022-04-15 15:35:29,777 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:35:29,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:29,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:35:29,792 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:35:29,793 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-15 15:35:29,869 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:35:29,869 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:35:29,870 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 15:35:29,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:35:29,878 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:35:30,044 INFO L272 TraceCheckUtils]: 0: Hoare triple {2777#true} call ULTIMATE.init(); {2777#true} is VALID [2022-04-15 15:35:30,045 INFO L290 TraceCheckUtils]: 1: Hoare triple {2777#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,045 INFO L290 TraceCheckUtils]: 2: Hoare triple {2785#(<= ~counter~0 0)} assume true; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,045 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2785#(<= ~counter~0 0)} {2777#true} #96#return; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,045 INFO L272 TraceCheckUtils]: 4: Hoare triple {2785#(<= ~counter~0 0)} call #t~ret8 := main(); {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,046 INFO L290 TraceCheckUtils]: 5: Hoare triple {2785#(<= ~counter~0 0)} 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;~B~0 := #t~nondet5;havoc #t~nondet5; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,046 INFO L272 TraceCheckUtils]: 6: Hoare triple {2785#(<= ~counter~0 0)} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,046 INFO L290 TraceCheckUtils]: 7: Hoare triple {2785#(<= ~counter~0 0)} ~cond := #in~cond; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,047 INFO L290 TraceCheckUtils]: 8: Hoare triple {2785#(<= ~counter~0 0)} assume !(0 == ~cond); {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,047 INFO L290 TraceCheckUtils]: 9: Hoare triple {2785#(<= ~counter~0 0)} assume true; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,047 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2785#(<= ~counter~0 0)} {2785#(<= ~counter~0 0)} #80#return; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,048 INFO L290 TraceCheckUtils]: 11: Hoare triple {2785#(<= ~counter~0 0)} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {2785#(<= ~counter~0 0)} is VALID [2022-04-15 15:35:30,048 INFO L290 TraceCheckUtils]: 12: Hoare triple {2785#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,048 INFO L290 TraceCheckUtils]: 13: Hoare triple {2819#(<= ~counter~0 1)} assume !!(#t~post6 < 5);havoc #t~post6; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,049 INFO L272 TraceCheckUtils]: 14: Hoare triple {2819#(<= ~counter~0 1)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,049 INFO L290 TraceCheckUtils]: 15: Hoare triple {2819#(<= ~counter~0 1)} ~cond := #in~cond; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,049 INFO L290 TraceCheckUtils]: 16: Hoare triple {2819#(<= ~counter~0 1)} assume !(0 == ~cond); {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,050 INFO L290 TraceCheckUtils]: 17: Hoare triple {2819#(<= ~counter~0 1)} assume true; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,050 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {2819#(<= ~counter~0 1)} {2819#(<= ~counter~0 1)} #82#return; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,051 INFO L272 TraceCheckUtils]: 19: Hoare triple {2819#(<= ~counter~0 1)} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,051 INFO L290 TraceCheckUtils]: 20: Hoare triple {2819#(<= ~counter~0 1)} ~cond := #in~cond; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,051 INFO L290 TraceCheckUtils]: 21: Hoare triple {2819#(<= ~counter~0 1)} assume !(0 == ~cond); {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,051 INFO L290 TraceCheckUtils]: 22: Hoare triple {2819#(<= ~counter~0 1)} assume true; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,052 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {2819#(<= ~counter~0 1)} {2819#(<= ~counter~0 1)} #84#return; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,052 INFO L272 TraceCheckUtils]: 24: Hoare triple {2819#(<= ~counter~0 1)} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,053 INFO L290 TraceCheckUtils]: 25: Hoare triple {2819#(<= ~counter~0 1)} ~cond := #in~cond; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,053 INFO L290 TraceCheckUtils]: 26: Hoare triple {2819#(<= ~counter~0 1)} assume !(0 == ~cond); {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,053 INFO L290 TraceCheckUtils]: 27: Hoare triple {2819#(<= ~counter~0 1)} assume true; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,054 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2819#(<= ~counter~0 1)} {2819#(<= ~counter~0 1)} #86#return; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,054 INFO L290 TraceCheckUtils]: 29: Hoare triple {2819#(<= ~counter~0 1)} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {2819#(<= ~counter~0 1)} is VALID [2022-04-15 15:35:30,055 INFO L290 TraceCheckUtils]: 30: Hoare triple {2819#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2874#(<= |main_#t~post6| 1)} is VALID [2022-04-15 15:35:30,055 INFO L290 TraceCheckUtils]: 31: Hoare triple {2874#(<= |main_#t~post6| 1)} assume !(#t~post6 < 5);havoc #t~post6; {2778#false} is VALID [2022-04-15 15:35:30,055 INFO L290 TraceCheckUtils]: 32: Hoare triple {2778#false} #t~post7 := ~counter~0;~counter~0 := 1 + #t~post7; {2778#false} is VALID [2022-04-15 15:35:30,055 INFO L290 TraceCheckUtils]: 33: Hoare triple {2778#false} assume !(#t~post7 < 5);havoc #t~post7; {2778#false} is VALID [2022-04-15 15:35:30,055 INFO L272 TraceCheckUtils]: 34: Hoare triple {2778#false} call __VERIFIER_assert((if ~A~0 % 4294967296 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {2778#false} is VALID [2022-04-15 15:35:30,055 INFO L290 TraceCheckUtils]: 35: Hoare triple {2778#false} ~cond := #in~cond; {2778#false} is VALID [2022-04-15 15:35:30,055 INFO L290 TraceCheckUtils]: 36: Hoare triple {2778#false} assume !(0 == ~cond); {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L290 TraceCheckUtils]: 37: Hoare triple {2778#false} assume true; {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {2778#false} {2778#false} #92#return; {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L272 TraceCheckUtils]: 39: Hoare triple {2778#false} call __VERIFIER_assert((if ~B~0 % 4294967296 == ~d~0 then 1 else 0)); {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L290 TraceCheckUtils]: 40: Hoare triple {2778#false} ~cond := #in~cond; {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L290 TraceCheckUtils]: 41: Hoare triple {2778#false} assume 0 == ~cond; {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L290 TraceCheckUtils]: 42: Hoare triple {2778#false} assume !false; {2778#false} is VALID [2022-04-15 15:35:30,056 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-04-15 15:35:30,056 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 15:35:30,259 INFO L290 TraceCheckUtils]: 42: Hoare triple {2778#false} assume !false; {2778#false} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 41: Hoare triple {2778#false} assume 0 == ~cond; {2778#false} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 40: Hoare triple {2778#false} ~cond := #in~cond; {2778#false} is VALID [2022-04-15 15:35:30,260 INFO L272 TraceCheckUtils]: 39: Hoare triple {2778#false} call __VERIFIER_assert((if ~B~0 % 4294967296 == ~d~0 then 1 else 0)); {2778#false} is VALID [2022-04-15 15:35:30,260 INFO L284 TraceCheckUtils]: 38: Hoare quadruple {2777#true} {2778#false} #92#return; {2778#false} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 37: Hoare triple {2777#true} assume true; {2777#true} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 36: Hoare triple {2777#true} assume !(0 == ~cond); {2777#true} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 35: Hoare triple {2777#true} ~cond := #in~cond; {2777#true} is VALID [2022-04-15 15:35:30,260 INFO L272 TraceCheckUtils]: 34: Hoare triple {2778#false} call __VERIFIER_assert((if ~A~0 % 4294967296 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {2777#true} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 33: Hoare triple {2778#false} assume !(#t~post7 < 5);havoc #t~post7; {2778#false} is VALID [2022-04-15 15:35:30,260 INFO L290 TraceCheckUtils]: 32: Hoare triple {2778#false} #t~post7 := ~counter~0;~counter~0 := 1 + #t~post7; {2778#false} is VALID [2022-04-15 15:35:30,262 INFO L290 TraceCheckUtils]: 31: Hoare triple {2944#(< |main_#t~post6| 5)} assume !(#t~post6 < 5);havoc #t~post6; {2778#false} is VALID [2022-04-15 15:35:30,262 INFO L290 TraceCheckUtils]: 30: Hoare triple {2948#(< ~counter~0 5)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2944#(< |main_#t~post6| 5)} is VALID [2022-04-15 15:35:30,263 INFO L290 TraceCheckUtils]: 29: Hoare triple {2948#(< ~counter~0 5)} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {2948#(< ~counter~0 5)} is VALID [2022-04-15 15:35:30,263 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2777#true} {2948#(< ~counter~0 5)} #86#return; {2948#(< ~counter~0 5)} is VALID [2022-04-15 15:35:30,263 INFO L290 TraceCheckUtils]: 27: Hoare triple {2777#true} assume true; {2777#true} is VALID [2022-04-15 15:35:30,263 INFO L290 TraceCheckUtils]: 26: Hoare triple {2777#true} assume !(0 == ~cond); {2777#true} is VALID [2022-04-15 15:35:30,263 INFO L290 TraceCheckUtils]: 25: Hoare triple {2777#true} ~cond := #in~cond; {2777#true} is VALID [2022-04-15 15:35:30,264 INFO L272 TraceCheckUtils]: 24: Hoare triple {2948#(< ~counter~0 5)} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {2777#true} is VALID [2022-04-15 15:35:30,264 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {2777#true} {2948#(< ~counter~0 5)} #84#return; {2948#(< ~counter~0 5)} is VALID [2022-04-15 15:35:30,264 INFO L290 TraceCheckUtils]: 22: Hoare triple {2777#true} assume true; {2777#true} is VALID [2022-04-15 15:35:30,264 INFO L290 TraceCheckUtils]: 21: Hoare triple {2777#true} assume !(0 == ~cond); {2777#true} is VALID [2022-04-15 15:35:30,264 INFO L290 TraceCheckUtils]: 20: Hoare triple {2777#true} ~cond := #in~cond; {2777#true} is VALID [2022-04-15 15:35:30,264 INFO L272 TraceCheckUtils]: 19: Hoare triple {2948#(< ~counter~0 5)} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {2777#true} is VALID [2022-04-15 15:35:30,265 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {2777#true} {2948#(< ~counter~0 5)} #82#return; {2948#(< ~counter~0 5)} is VALID [2022-04-15 15:35:30,265 INFO L290 TraceCheckUtils]: 17: Hoare triple {2777#true} assume true; {2777#true} is VALID [2022-04-15 15:35:30,265 INFO L290 TraceCheckUtils]: 16: Hoare triple {2777#true} assume !(0 == ~cond); {2777#true} is VALID [2022-04-15 15:35:30,265 INFO L290 TraceCheckUtils]: 15: Hoare triple {2777#true} ~cond := #in~cond; {2777#true} is VALID [2022-04-15 15:35:30,265 INFO L272 TraceCheckUtils]: 14: Hoare triple {2948#(< ~counter~0 5)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {2777#true} is VALID [2022-04-15 15:35:30,265 INFO L290 TraceCheckUtils]: 13: Hoare triple {2948#(< ~counter~0 5)} assume !!(#t~post6 < 5);havoc #t~post6; {2948#(< ~counter~0 5)} is VALID [2022-04-15 15:35:30,266 INFO L290 TraceCheckUtils]: 12: Hoare triple {3003#(< ~counter~0 4)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2948#(< ~counter~0 5)} is VALID [2022-04-15 15:35:30,266 INFO L290 TraceCheckUtils]: 11: Hoare triple {3003#(< ~counter~0 4)} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,267 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2777#true} {3003#(< ~counter~0 4)} #80#return; {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,267 INFO L290 TraceCheckUtils]: 9: Hoare triple {2777#true} assume true; {2777#true} is VALID [2022-04-15 15:35:30,267 INFO L290 TraceCheckUtils]: 8: Hoare triple {2777#true} assume !(0 == ~cond); {2777#true} is VALID [2022-04-15 15:35:30,267 INFO L290 TraceCheckUtils]: 7: Hoare triple {2777#true} ~cond := #in~cond; {2777#true} is VALID [2022-04-15 15:35:30,267 INFO L272 TraceCheckUtils]: 6: Hoare triple {3003#(< ~counter~0 4)} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {2777#true} is VALID [2022-04-15 15:35:30,267 INFO L290 TraceCheckUtils]: 5: Hoare triple {3003#(< ~counter~0 4)} 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;~B~0 := #t~nondet5;havoc #t~nondet5; {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,267 INFO L272 TraceCheckUtils]: 4: Hoare triple {3003#(< ~counter~0 4)} call #t~ret8 := main(); {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,268 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3003#(< ~counter~0 4)} {2777#true} #96#return; {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,268 INFO L290 TraceCheckUtils]: 2: Hoare triple {3003#(< ~counter~0 4)} assume true; {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,269 INFO L290 TraceCheckUtils]: 1: Hoare triple {2777#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3003#(< ~counter~0 4)} is VALID [2022-04-15 15:35:30,269 INFO L272 TraceCheckUtils]: 0: Hoare triple {2777#true} call ULTIMATE.init(); {2777#true} is VALID [2022-04-15 15:35:30,269 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-15 15:35:30,269 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:35:30,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1935348610] [2022-04-15 15:35:30,269 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:35:30,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1372083961] [2022-04-15 15:35:30,269 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1372083961] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-15 15:35:30,269 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-15 15:35:30,269 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-15 15:35:30,270 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:35:30,270 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1178012973] [2022-04-15 15:35:30,270 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1178012973] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:35:30,270 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:35:30,270 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:35:30,270 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931598098] [2022-04-15 15:35:30,270 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:35:30,270 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) Word has length 43 [2022-04-15 15:35:30,270 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:35:30,270 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-15 15:35:30,298 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 36 edges. 36 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:30,298 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:35:30,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:30,298 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:35:30,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-15 15:35:30,299 INFO L87 Difference]: Start difference. First operand 69 states and 82 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-15 15:35:30,454 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:30,454 INFO L93 Difference]: Finished difference Result 96 states and 120 transitions. [2022-04-15 15:35:30,454 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-15 15:35:30,454 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) Word has length 43 [2022-04-15 15:35:30,454 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:35:30,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-15 15:35:30,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 76 transitions. [2022-04-15 15:35:30,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-15 15:35:30,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 76 transitions. [2022-04-15 15:35:30,457 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 76 transitions. [2022-04-15 15:35:30,513 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 76 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:30,514 INFO L225 Difference]: With dead ends: 96 [2022-04-15 15:35:30,514 INFO L226 Difference]: Without dead ends: 71 [2022-04-15 15:35:30,514 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-15 15:35:30,515 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 6 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:35:30,515 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 117 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:35:30,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2022-04-15 15:35:30,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2022-04-15 15:35:30,564 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:35:30,564 INFO L82 GeneralOperation]: Start isEquivalent. First operand 71 states. Second operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:30,569 INFO L74 IsIncluded]: Start isIncluded. First operand 71 states. Second operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:30,571 INFO L87 Difference]: Start difference. First operand 71 states. Second operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:30,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:30,574 INFO L93 Difference]: Finished difference Result 71 states and 84 transitions. [2022-04-15 15:35:30,574 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 84 transitions. [2022-04-15 15:35:30,574 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:30,574 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:30,575 INFO L74 IsIncluded]: Start isIncluded. First operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) Second operand 71 states. [2022-04-15 15:35:30,575 INFO L87 Difference]: Start difference. First operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) Second operand 71 states. [2022-04-15 15:35:30,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:35:30,576 INFO L93 Difference]: Finished difference Result 71 states and 84 transitions. [2022-04-15 15:35:30,576 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 84 transitions. [2022-04-15 15:35:30,577 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:35:30,577 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:35:30,577 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:35:30,577 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:35:30,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 15:35:30,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 84 transitions. [2022-04-15 15:35:30,579 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 84 transitions. Word has length 43 [2022-04-15 15:35:30,579 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:35:30,579 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 84 transitions. [2022-04-15 15:35:30,580 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-15 15:35:30,580 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 71 states and 84 transitions. [2022-04-15 15:35:30,655 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 84 edges. 84 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:35:30,655 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 84 transitions. [2022-04-15 15:35:30,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-04-15 15:35:30,657 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:35:30,657 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:35:30,676 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-15 15:35:30,892 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-15 15:35:31,082 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:35:31,083 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:35:31,083 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:35:31,083 INFO L85 PathProgramCache]: Analyzing trace with hash 1861890039, now seen corresponding path program 1 times [2022-04-15 15:35:31,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:35:31,083 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1890671426] [2022-04-15 15:36:39,833 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-15 15:36:39,834 INFO L85 PathProgramCache]: Analyzing trace with hash -210838127, now seen corresponding path program 1 times [2022-04-15 15:36:39,834 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:36:39,835 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [958116414] [2022-04-15 15:36:39,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:36:39,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:36:39,841 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:36:39,841 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [28139018] [2022-04-15 15:36:39,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:36:39,841 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:36:39,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:36:39,842 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:36:39,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-15 15:36:39,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-15 15:36:39,894 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-15 15:36:39,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-15 15:36:39,913 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-15 15:36:39,915 INFO L85 PathProgramCache]: Analyzing trace with hash 1861890039, now seen corresponding path program 2 times [2022-04-15 15:36:39,915 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:36:39,915 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1841091439] [2022-04-15 15:36:39,915 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:36:39,915 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:36:39,933 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:36:39,933 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [708188340] [2022-04-15 15:36:39,933 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:36:39,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:36:39,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:36:39,936 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:36:39,936 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-15 15:36:39,978 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:36:39,978 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:36:39,979 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 16 conjunts are in the unsatisfiable core [2022-04-15 15:36:39,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:36:39,992 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:36:40,661 INFO L272 TraceCheckUtils]: 0: Hoare triple {3520#true} call ULTIMATE.init(); {3520#true} is VALID [2022-04-15 15:36:40,661 INFO L290 TraceCheckUtils]: 1: Hoare triple {3520#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3520#true} is VALID [2022-04-15 15:36:40,661 INFO L290 TraceCheckUtils]: 2: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,662 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3520#true} {3520#true} #96#return; {3520#true} is VALID [2022-04-15 15:36:40,662 INFO L272 TraceCheckUtils]: 4: Hoare triple {3520#true} call #t~ret8 := main(); {3520#true} is VALID [2022-04-15 15:36:40,662 INFO L290 TraceCheckUtils]: 5: Hoare triple {3520#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;~B~0 := #t~nondet5;havoc #t~nondet5; {3520#true} is VALID [2022-04-15 15:36:40,662 INFO L272 TraceCheckUtils]: 6: Hoare triple {3520#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,662 INFO L290 TraceCheckUtils]: 7: Hoare triple {3520#true} ~cond := #in~cond; {3546#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-15 15:36:40,662 INFO L290 TraceCheckUtils]: 8: Hoare triple {3546#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {3550#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 15:36:40,663 INFO L290 TraceCheckUtils]: 9: Hoare triple {3550#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {3550#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 15:36:40,663 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {3550#(not (= |assume_abort_if_not_#in~cond| 0))} {3520#true} #80#return; {3557#(<= 1 (mod main_~B~0 4294967296))} is VALID [2022-04-15 15:36:40,664 INFO L290 TraceCheckUtils]: 11: Hoare triple {3557#(<= 1 (mod main_~B~0 4294967296))} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:36:40,664 INFO L290 TraceCheckUtils]: 12: Hoare triple {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:36:40,664 INFO L290 TraceCheckUtils]: 13: Hoare triple {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} assume !!(#t~post6 < 5);havoc #t~post6; {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:36:40,664 INFO L272 TraceCheckUtils]: 14: Hoare triple {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,665 INFO L290 TraceCheckUtils]: 15: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,665 INFO L290 TraceCheckUtils]: 16: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,665 INFO L290 TraceCheckUtils]: 17: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,666 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {3520#true} {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #82#return; {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:36:40,666 INFO L272 TraceCheckUtils]: 19: Hoare triple {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L290 TraceCheckUtils]: 20: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L290 TraceCheckUtils]: 21: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L290 TraceCheckUtils]: 22: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {3520#true} {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #84#return; {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:36:40,667 INFO L272 TraceCheckUtils]: 24: Hoare triple {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L290 TraceCheckUtils]: 25: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L290 TraceCheckUtils]: 26: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,667 INFO L290 TraceCheckUtils]: 27: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,668 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {3520#true} {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} #86#return; {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} is VALID [2022-04-15 15:36:40,668 INFO L290 TraceCheckUtils]: 29: Hoare triple {3561#(and (= main_~d~0 (mod main_~B~0 4294967296)) (<= 1 (mod main_~B~0 4294967296)) (= main_~p~0 1))} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,669 INFO L290 TraceCheckUtils]: 30: Hoare triple {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,669 INFO L290 TraceCheckUtils]: 31: Hoare triple {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} assume !!(#t~post6 < 5);havoc #t~post6; {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,669 INFO L272 TraceCheckUtils]: 32: Hoare triple {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,669 INFO L290 TraceCheckUtils]: 33: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,670 INFO L290 TraceCheckUtils]: 34: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,670 INFO L290 TraceCheckUtils]: 35: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,670 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {3520#true} {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} #82#return; {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,670 INFO L272 TraceCheckUtils]: 37: Hoare triple {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,670 INFO L290 TraceCheckUtils]: 38: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,670 INFO L290 TraceCheckUtils]: 39: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,670 INFO L290 TraceCheckUtils]: 40: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,678 INFO L284 TraceCheckUtils]: 41: Hoare quadruple {3520#true} {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} #84#return; {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,678 INFO L272 TraceCheckUtils]: 42: Hoare triple {3616#(and (= main_~d~0 (* 2 (mod main_~B~0 4294967296))) (= main_~p~0 2) (<= 1 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {3656#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:36:40,679 INFO L290 TraceCheckUtils]: 43: Hoare triple {3656#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {3660#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:36:40,679 INFO L290 TraceCheckUtils]: 44: Hoare triple {3660#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {3521#false} is VALID [2022-04-15 15:36:40,679 INFO L290 TraceCheckUtils]: 45: Hoare triple {3521#false} assume !false; {3521#false} is VALID [2022-04-15 15:36:40,679 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-15 15:36:40,679 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 15:36:40,951 INFO L290 TraceCheckUtils]: 45: Hoare triple {3521#false} assume !false; {3521#false} is VALID [2022-04-15 15:36:40,952 INFO L290 TraceCheckUtils]: 44: Hoare triple {3660#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {3521#false} is VALID [2022-04-15 15:36:40,952 INFO L290 TraceCheckUtils]: 43: Hoare triple {3656#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {3660#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:36:40,953 INFO L272 TraceCheckUtils]: 42: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {3656#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:36:40,953 INFO L284 TraceCheckUtils]: 41: Hoare quadruple {3520#true} {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #84#return; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,953 INFO L290 TraceCheckUtils]: 40: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,953 INFO L290 TraceCheckUtils]: 39: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,953 INFO L290 TraceCheckUtils]: 38: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,953 INFO L272 TraceCheckUtils]: 37: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,954 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {3520#true} {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #82#return; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,954 INFO L290 TraceCheckUtils]: 35: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,954 INFO L290 TraceCheckUtils]: 34: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,954 INFO L290 TraceCheckUtils]: 33: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,954 INFO L272 TraceCheckUtils]: 32: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,954 INFO L290 TraceCheckUtils]: 31: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} assume !!(#t~post6 < 5);havoc #t~post6; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,955 INFO L290 TraceCheckUtils]: 30: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,957 INFO L290 TraceCheckUtils]: 29: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} assume !!(~r~0 >= ~d~0);~d~0 := 2 * ~d~0;~p~0 := 2 * ~p~0; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,957 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {3520#true} {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #86#return; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,957 INFO L290 TraceCheckUtils]: 27: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,957 INFO L290 TraceCheckUtils]: 26: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,957 INFO L290 TraceCheckUtils]: 25: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,957 INFO L272 TraceCheckUtils]: 24: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if ~d~0 == ~B~0 % 4294967296 * ~p~0 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,958 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {3520#true} {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #84#return; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,958 INFO L290 TraceCheckUtils]: 22: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,958 INFO L290 TraceCheckUtils]: 21: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,958 INFO L290 TraceCheckUtils]: 20: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,958 INFO L272 TraceCheckUtils]: 19: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if ~r~0 == ~A~0 % 4294967296 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,959 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {3520#true} {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #82#return; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,959 INFO L290 TraceCheckUtils]: 17: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,959 INFO L290 TraceCheckUtils]: 16: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,959 INFO L290 TraceCheckUtils]: 15: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,959 INFO L272 TraceCheckUtils]: 14: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,959 INFO L290 TraceCheckUtils]: 13: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} assume !!(#t~post6 < 5);havoc #t~post6; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,960 INFO L290 TraceCheckUtils]: 12: Hoare triple {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,960 INFO L290 TraceCheckUtils]: 11: Hoare triple {3520#true} ~r~0 := ~A~0 % 4294967296;~d~0 := ~B~0 % 4294967296;~p~0 := 1;~q~0 := 0; {3676#(= main_~d~0 (* main_~p~0 (mod main_~B~0 4294967296)))} is VALID [2022-04-15 15:36:40,960 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {3520#true} {3520#true} #80#return; {3520#true} is VALID [2022-04-15 15:36:40,960 INFO L290 TraceCheckUtils]: 9: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,960 INFO L290 TraceCheckUtils]: 8: Hoare triple {3520#true} assume !(0 == ~cond); {3520#true} is VALID [2022-04-15 15:36:40,960 INFO L290 TraceCheckUtils]: 7: Hoare triple {3520#true} ~cond := #in~cond; {3520#true} is VALID [2022-04-15 15:36:40,960 INFO L272 TraceCheckUtils]: 6: Hoare triple {3520#true} call assume_abort_if_not((if ~B~0 % 4294967296 >= 1 then 1 else 0)); {3520#true} is VALID [2022-04-15 15:36:40,960 INFO L290 TraceCheckUtils]: 5: Hoare triple {3520#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;~B~0 := #t~nondet5;havoc #t~nondet5; {3520#true} is VALID [2022-04-15 15:36:40,961 INFO L272 TraceCheckUtils]: 4: Hoare triple {3520#true} call #t~ret8 := main(); {3520#true} is VALID [2022-04-15 15:36:40,961 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3520#true} {3520#true} #96#return; {3520#true} is VALID [2022-04-15 15:36:40,961 INFO L290 TraceCheckUtils]: 2: Hoare triple {3520#true} assume true; {3520#true} is VALID [2022-04-15 15:36:40,961 INFO L290 TraceCheckUtils]: 1: Hoare triple {3520#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3520#true} is VALID [2022-04-15 15:36:40,961 INFO L272 TraceCheckUtils]: 0: Hoare triple {3520#true} call ULTIMATE.init(); {3520#true} is VALID [2022-04-15 15:36:40,961 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-15 15:36:40,961 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:36:40,961 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1841091439] [2022-04-15 15:36:40,961 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:36:40,961 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [708188340] [2022-04-15 15:36:40,961 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [708188340] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-15 15:36:40,961 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-15 15:36:40,961 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-15 15:36:40,962 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:36:40,962 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1890671426] [2022-04-15 15:36:40,962 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1890671426] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:36:40,962 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:36:40,962 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:36:40,962 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1242873799] [2022-04-15 15:36:40,962 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:36:40,967 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 46 [2022-04-15 15:36:40,967 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:36:40,967 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 15:36:40,991 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 28 edges. 28 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:36:40,991 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:36:40,991 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:36:40,991 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:36:40,992 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-15 15:36:40,992 INFO L87 Difference]: Start difference. First operand 71 states and 84 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 15:36:43,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:36:43,349 INFO L93 Difference]: Finished difference Result 84 states and 101 transitions. [2022-04-15 15:36:43,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:36:43,350 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 46 [2022-04-15 15:36:43,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:36:43,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 15:36:43,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 59 transitions. [2022-04-15 15:36:43,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 15:36:43,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 59 transitions. [2022-04-15 15:36:43,356 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 59 transitions. [2022-04-15 15:36:43,417 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 59 edges. 59 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:36:43,420 INFO L225 Difference]: With dead ends: 84 [2022-04-15 15:36:43,420 INFO L226 Difference]: Without dead ends: 82 [2022-04-15 15:36:43,420 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-15 15:36:43,422 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 11 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 15:36:43,422 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 125 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 15:36:43,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-04-15 15:36:43,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 79. [2022-04-15 15:36:43,469 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:36:43,469 INFO L82 GeneralOperation]: Start isEquivalent. First operand 82 states. Second operand has 79 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 18 states have call successors, (18), 11 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 15:36:43,469 INFO L74 IsIncluded]: Start isIncluded. First operand 82 states. Second operand has 79 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 18 states have call successors, (18), 11 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 15:36:43,469 INFO L87 Difference]: Start difference. First operand 82 states. Second operand has 79 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 18 states have call successors, (18), 11 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 15:36:43,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:36:43,472 INFO L93 Difference]: Finished difference Result 82 states and 99 transitions. [2022-04-15 15:36:43,472 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 99 transitions. [2022-04-15 15:36:43,473 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:36:43,473 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:36:43,473 INFO L74 IsIncluded]: Start isIncluded. First operand has 79 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 18 states have call successors, (18), 11 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) Second operand 82 states. [2022-04-15 15:36:43,473 INFO L87 Difference]: Start difference. First operand has 79 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 18 states have call successors, (18), 11 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) Second operand 82 states. [2022-04-15 15:36:43,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:36:43,475 INFO L93 Difference]: Finished difference Result 82 states and 99 transitions. [2022-04-15 15:36:43,475 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 99 transitions. [2022-04-15 15:36:43,475 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:36:43,475 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:36:43,475 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:36:43,475 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:36:43,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 18 states have call successors, (18), 11 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 15:36:43,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 94 transitions. [2022-04-15 15:36:43,478 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 94 transitions. Word has length 46 [2022-04-15 15:36:43,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:36:43,478 INFO L478 AbstractCegarLoop]: Abstraction has 79 states and 94 transitions. [2022-04-15 15:36:43,478 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 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 15:36:43,478 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 79 states and 94 transitions. [2022-04-15 15:36:43,573 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 94 edges. 94 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:36:43,573 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 94 transitions. [2022-04-15 15:36:43,574 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-04-15 15:36:43,574 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:36:43,574 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:36:43,595 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-04-15 15:36:43,790 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-15 15:36:43,974 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10,SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:36:43,975 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:36:43,975 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:36:43,975 INFO L85 PathProgramCache]: Analyzing trace with hash 967982746, now seen corresponding path program 1 times [2022-04-15 15:36:43,975 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:36:43,975 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [994245423]