/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 11:26:59,772 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 11:26:59,774 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 11:26:59,791 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 11:26:59,791 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 11:26:59,792 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 11:26:59,792 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 11:26:59,793 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 11:26:59,794 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 11:26:59,795 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 11:26:59,795 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 11:26:59,796 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 11:26:59,796 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 11:26:59,796 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 11:26:59,797 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 11:26:59,798 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 11:26:59,798 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 11:26:59,799 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 11:26:59,800 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 11:26:59,801 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 11:26:59,801 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 11:26:59,802 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 11:26:59,803 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 11:26:59,803 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 11:26:59,804 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 11:26:59,806 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 11:26:59,806 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 11:26:59,806 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 11:26:59,807 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 11:26:59,807 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 11:26:59,807 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 11:26:59,808 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 11:26:59,808 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 11:26:59,808 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 11:26:59,809 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 11:26:59,809 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 11:26:59,810 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 11:26:59,810 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 11:26:59,810 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 11:26:59,810 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 11:26:59,811 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 11:26:59,812 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 11:26:59,812 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-08 11:26:59,818 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 11:26:59,818 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 11:26:59,818 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 11:26:59,818 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 11:26:59,819 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 11:26:59,819 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 11:26:59,820 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 11:26:59,820 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 11:26:59,821 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 11:26:59,821 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-08 11:26:59,821 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-08 11:27:00,004 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 11:27:00,029 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 11:27:00,031 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 11:27:00,031 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 11:27:00,039 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 11:27:00,040 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c [2022-04-08 11:27:00,091 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/592bb16f9/3436184f72114a279fe509ea5abb04d1/FLAG5f7954372 [2022-04-08 11:27:00,396 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 11:27:00,396 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c [2022-04-08 11:27:00,401 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/592bb16f9/3436184f72114a279fe509ea5abb04d1/FLAG5f7954372 [2022-04-08 11:27:00,838 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/592bb16f9/3436184f72114a279fe509ea5abb04d1 [2022-04-08 11:27:00,840 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 11:27:00,840 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 11:27:00,842 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 11:27:00,842 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 11:27:00,844 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 11:27:00,845 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 11:27:00" (1/1) ... [2022-04-08 11:27:00,845 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6792683a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:00, skipping insertion in model container [2022-04-08 11:27:00,845 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 11:27:00" (1/1) ... [2022-04-08 11:27:00,849 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 11:27:00,858 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 11:27:00,999 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c[525,538] [2022-04-08 11:27:01,020 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 11:27:01,026 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 11:27:01,033 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c[525,538] [2022-04-08 11:27:01,045 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 11:27:01,052 INFO L208 MainTranslator]: Completed translation [2022-04-08 11:27:01,053 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01 WrapperNode [2022-04-08 11:27:01,053 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 11:27:01,053 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 11:27:01,054 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 11:27:01,054 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 11:27:01,061 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,061 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,065 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,065 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,069 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,072 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,072 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,074 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 11:27:01,074 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 11:27:01,074 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 11:27:01,074 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 11:27:01,075 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (1/1) ... [2022-04-08 11:27:01,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 11:27:01,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:27:01,097 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-08 11:27:01,110 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-08 11:27:01,118 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 11:27:01,131 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 11:27:01,131 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 11:27:01,132 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 11:27:01,132 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 11:27:01,132 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 11:27:01,132 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 11:27:01,132 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 11:27:01,132 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 11:27:01,132 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 11:27:01,132 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-08 11:27:01,132 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 11:27:01,133 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 11:27:01,174 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 11:27:01,175 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 11:27:01,403 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 11:27:01,408 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 11:27:01,408 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-08 11:27:01,409 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 11:27:01 BoogieIcfgContainer [2022-04-08 11:27:01,409 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 11:27:01,424 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 11:27:01,424 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 11:27:01,427 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 11:27:01,427 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 11:27:00" (1/3) ... [2022-04-08 11:27:01,427 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f9152e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 11:27:01, skipping insertion in model container [2022-04-08 11:27:01,427 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 11:27:01" (2/3) ... [2022-04-08 11:27:01,428 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f9152e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 11:27:01, skipping insertion in model container [2022-04-08 11:27:01,428 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 11:27:01" (3/3) ... [2022-04-08 11:27:01,429 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_unwindbound10.c [2022-04-08 11:27:01,449 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 11:27:01,449 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 11:27:01,475 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 11:27:01,483 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-08 11:27:01,483 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 11:27:01,502 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 11:27:01,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-08 11:27:01,508 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:01,509 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:01,509 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:01,515 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:01,515 INFO L85 PathProgramCache]: Analyzing trace with hash -2024343623, now seen corresponding path program 1 times [2022-04-08 11:27:01,523 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:01,523 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [917513203] [2022-04-08 11:27:01,531 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:27:01,531 INFO L85 PathProgramCache]: Analyzing trace with hash -2024343623, now seen corresponding path program 2 times [2022-04-08 11:27:01,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:01,533 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1336912784] [2022-04-08 11:27:01,534 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:01,535 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:01,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:01,671 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:27:01,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:01,690 INFO L290 TraceCheckUtils]: 0: Hoare triple {51#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {42#true} is VALID [2022-04-08 11:27:01,691 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume true; {42#true} is VALID [2022-04-08 11:27:01,691 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {42#true} {42#true} #102#return; {42#true} is VALID [2022-04-08 11:27:01,692 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:27:01,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:01,702 INFO L290 TraceCheckUtils]: 0: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-08 11:27:01,703 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-08 11:27:01,703 INFO L290 TraceCheckUtils]: 2: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-08 11:27:01,703 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {43#false} {42#true} #82#return; {43#false} is VALID [2022-04-08 11:27:01,705 INFO L272 TraceCheckUtils]: 0: Hoare triple {42#true} call ULTIMATE.init(); {51#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:27:01,705 INFO L290 TraceCheckUtils]: 1: Hoare triple {51#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {42#true} is VALID [2022-04-08 11:27:01,705 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#true} assume true; {42#true} is VALID [2022-04-08 11:27:01,705 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#true} {42#true} #102#return; {42#true} is VALID [2022-04-08 11:27:01,705 INFO L272 TraceCheckUtils]: 4: Hoare triple {42#true} call #t~ret7 := main(); {42#true} is VALID [2022-04-08 11:27:01,706 INFO L290 TraceCheckUtils]: 5: Hoare triple {42#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {42#true} is VALID [2022-04-08 11:27:01,706 INFO L272 TraceCheckUtils]: 6: Hoare triple {42#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {42#true} is VALID [2022-04-08 11:27:01,706 INFO L290 TraceCheckUtils]: 7: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-08 11:27:01,706 INFO L290 TraceCheckUtils]: 8: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-08 11:27:01,707 INFO L290 TraceCheckUtils]: 9: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-08 11:27:01,707 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {43#false} {42#true} #82#return; {43#false} is VALID [2022-04-08 11:27:01,707 INFO L290 TraceCheckUtils]: 11: Hoare triple {43#false} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {43#false} is VALID [2022-04-08 11:27:01,707 INFO L290 TraceCheckUtils]: 12: Hoare triple {43#false} assume !true; {43#false} is VALID [2022-04-08 11:27:01,707 INFO L290 TraceCheckUtils]: 13: Hoare triple {43#false} assume !true; {43#false} is VALID [2022-04-08 11:27:01,708 INFO L272 TraceCheckUtils]: 14: Hoare triple {43#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {43#false} is VALID [2022-04-08 11:27:01,708 INFO L290 TraceCheckUtils]: 15: Hoare triple {43#false} ~cond := #in~cond; {43#false} is VALID [2022-04-08 11:27:01,708 INFO L290 TraceCheckUtils]: 16: Hoare triple {43#false} assume 0 == ~cond; {43#false} is VALID [2022-04-08 11:27:01,708 INFO L290 TraceCheckUtils]: 17: Hoare triple {43#false} assume !false; {43#false} is VALID [2022-04-08 11:27:01,708 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:27:01,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:01,709 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1336912784] [2022-04-08 11:27:01,710 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1336912784] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:01,710 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:01,710 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 11:27:01,712 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:01,712 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [917513203] [2022-04-08 11:27:01,712 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [917513203] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:01,712 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:01,712 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 11:27:01,712 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065894209] [2022-04-08 11:27:01,713 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:01,716 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-08 11:27:01,717 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:01,719 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:01,736 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:01,736 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 11:27:01,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:01,754 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 11:27:01,754 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 11:27:01,757 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:03,862 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:27:06,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:06,842 INFO L93 Difference]: Finished difference Result 70 states and 111 transitions. [2022-04-08 11:27:06,842 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 11:27:06,843 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-08 11:27:06,843 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:27:06,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:06,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 111 transitions. [2022-04-08 11:27:06,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:06,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 111 transitions. [2022-04-08 11:27:06,856 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 111 transitions. [2022-04-08 11:27:06,966 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 111 edges. 111 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:06,978 INFO L225 Difference]: With dead ends: 70 [2022-04-08 11:27:06,978 INFO L226 Difference]: Without dead ends: 35 [2022-04-08 11:27:06,980 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 11:27:06,985 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 11 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2022-04-08 11:27:06,986 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 53 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 25 Invalid, 1 Unknown, 0 Unchecked, 2.5s Time] [2022-04-08 11:27:06,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-08 11:27:07,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2022-04-08 11:27:07,019 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:27:07,020 INFO L82 GeneralOperation]: Start isEquivalent. First operand 35 states. Second operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:07,020 INFO L74 IsIncluded]: Start isIncluded. First operand 35 states. Second operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:07,021 INFO L87 Difference]: Start difference. First operand 35 states. Second operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:07,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:07,033 INFO L93 Difference]: Finished difference Result 35 states and 47 transitions. [2022-04-08 11:27:07,033 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 47 transitions. [2022-04-08 11:27:07,034 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:07,034 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:07,034 INFO L74 IsIncluded]: Start isIncluded. First operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 35 states. [2022-04-08 11:27:07,035 INFO L87 Difference]: Start difference. First operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 35 states. [2022-04-08 11:27:07,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:07,037 INFO L93 Difference]: Finished difference Result 35 states and 47 transitions. [2022-04-08 11:27:07,037 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 47 transitions. [2022-04-08 11:27:07,038 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:07,038 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:07,038 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:27:07,038 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:27:07,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:07,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 46 transitions. [2022-04-08 11:27:07,041 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 46 transitions. Word has length 18 [2022-04-08 11:27:07,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:27:07,041 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 46 transitions. [2022-04-08 11:27:07,042 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:07,042 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 34 states and 46 transitions. [2022-04-08 11:27:07,105 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 46 edges. 46 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:07,105 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 46 transitions. [2022-04-08 11:27:07,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-08 11:27:07,107 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:07,107 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:07,107 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 11:27:07,107 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:07,108 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:07,108 INFO L85 PathProgramCache]: Analyzing trace with hash -96361696, now seen corresponding path program 1 times [2022-04-08 11:27:07,109 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:07,109 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1774072605] [2022-04-08 11:27:07,117 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:27:07,117 INFO L85 PathProgramCache]: Analyzing trace with hash -96361696, now seen corresponding path program 2 times [2022-04-08 11:27:07,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:07,119 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [485549520] [2022-04-08 11:27:07,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:07,119 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:07,135 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:27:07,136 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [686054084] [2022-04-08 11:27:07,136 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:27:07,136 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:07,136 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:27:07,156 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:27:07,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-08 11:27:07,217 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:27:07,217 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:27:07,219 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-08 11:27:07,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:07,232 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:27:07,357 INFO L272 TraceCheckUtils]: 0: Hoare triple {332#true} call ULTIMATE.init(); {332#true} is VALID [2022-04-08 11:27:07,358 INFO L290 TraceCheckUtils]: 1: Hoare triple {332#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,359 INFO L290 TraceCheckUtils]: 2: Hoare triple {340#(<= ~counter~0 0)} assume true; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,359 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {340#(<= ~counter~0 0)} {332#true} #102#return; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,360 INFO L272 TraceCheckUtils]: 4: Hoare triple {340#(<= ~counter~0 0)} call #t~ret7 := main(); {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,360 INFO L290 TraceCheckUtils]: 5: Hoare triple {340#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,360 INFO L272 TraceCheckUtils]: 6: Hoare triple {340#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,361 INFO L290 TraceCheckUtils]: 7: Hoare triple {340#(<= ~counter~0 0)} ~cond := #in~cond; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,361 INFO L290 TraceCheckUtils]: 8: Hoare triple {340#(<= ~counter~0 0)} assume !(0 == ~cond); {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,362 INFO L290 TraceCheckUtils]: 9: Hoare triple {340#(<= ~counter~0 0)} assume true; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,362 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {340#(<= ~counter~0 0)} {340#(<= ~counter~0 0)} #82#return; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,363 INFO L290 TraceCheckUtils]: 11: Hoare triple {340#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {340#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:07,363 INFO L290 TraceCheckUtils]: 12: Hoare triple {340#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {374#(<= |main_#t~post5| 0)} is VALID [2022-04-08 11:27:07,364 INFO L290 TraceCheckUtils]: 13: Hoare triple {374#(<= |main_#t~post5| 0)} assume !(#t~post5 < 10);havoc #t~post5; {333#false} is VALID [2022-04-08 11:27:07,364 INFO L290 TraceCheckUtils]: 14: Hoare triple {333#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {333#false} is VALID [2022-04-08 11:27:07,364 INFO L290 TraceCheckUtils]: 15: Hoare triple {333#false} assume !(#t~post6 < 10);havoc #t~post6; {333#false} is VALID [2022-04-08 11:27:07,364 INFO L272 TraceCheckUtils]: 16: Hoare triple {333#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {333#false} is VALID [2022-04-08 11:27:07,365 INFO L290 TraceCheckUtils]: 17: Hoare triple {333#false} ~cond := #in~cond; {333#false} is VALID [2022-04-08 11:27:07,365 INFO L290 TraceCheckUtils]: 18: Hoare triple {333#false} assume 0 == ~cond; {333#false} is VALID [2022-04-08 11:27:07,365 INFO L290 TraceCheckUtils]: 19: Hoare triple {333#false} assume !false; {333#false} is VALID [2022-04-08 11:27:07,365 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:27:07,366 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:27:07,366 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:07,366 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [485549520] [2022-04-08 11:27:07,366 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:27:07,366 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [686054084] [2022-04-08 11:27:07,367 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [686054084] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:07,367 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:07,367 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 11:27:07,368 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:07,368 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1774072605] [2022-04-08 11:27:07,368 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1774072605] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:07,368 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:07,368 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 11:27:07,368 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1203449433] [2022-04-08 11:27:07,368 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:07,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-08 11:27:07,369 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:07,370 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:07,385 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:07,385 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-08 11:27:07,385 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:07,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-08 11:27:07,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 11:27:07,386 INFO L87 Difference]: Start difference. First operand 34 states and 46 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:10,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:10,579 INFO L93 Difference]: Finished difference Result 55 states and 78 transitions. [2022-04-08 11:27:10,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-08 11:27:10,579 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-08 11:27:10,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:27:10,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:10,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 78 transitions. [2022-04-08 11:27:10,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:10,584 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 78 transitions. [2022-04-08 11:27:10,584 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 78 transitions. [2022-04-08 11:27:10,664 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 78 edges. 78 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:10,665 INFO L225 Difference]: With dead ends: 55 [2022-04-08 11:27:10,665 INFO L226 Difference]: Without dead ends: 36 [2022-04-08 11:27:10,666 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 11:27:10,666 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 11:27:10,667 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 119 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 11:27:10,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-08 11:27:10,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-04-08 11:27:10,683 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:27:10,684 INFO L82 GeneralOperation]: Start isEquivalent. First operand 36 states. Second operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:10,685 INFO L74 IsIncluded]: Start isIncluded. First operand 36 states. Second operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:10,685 INFO L87 Difference]: Start difference. First operand 36 states. Second operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:10,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:10,688 INFO L93 Difference]: Finished difference Result 36 states and 48 transitions. [2022-04-08 11:27:10,688 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 11:27:10,689 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:10,689 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:10,689 INFO L74 IsIncluded]: Start isIncluded. First operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 36 states. [2022-04-08 11:27:10,690 INFO L87 Difference]: Start difference. First operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 36 states. [2022-04-08 11:27:10,691 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:10,691 INFO L93 Difference]: Finished difference Result 36 states and 48 transitions. [2022-04-08 11:27:10,691 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 11:27:10,692 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:10,692 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:10,692 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:27:10,692 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:27:10,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:10,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 48 transitions. [2022-04-08 11:27:10,694 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 48 transitions. Word has length 20 [2022-04-08 11:27:10,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:27:10,694 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 48 transitions. [2022-04-08 11:27:10,694 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:10,694 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 36 states and 48 transitions. [2022-04-08 11:27:10,741 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 48 edges. 48 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:10,742 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 11:27:10,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-08 11:27:10,742 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:10,742 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:10,761 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-08 11:27:10,947 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:10,948 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:10,948 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:10,948 INFO L85 PathProgramCache]: Analyzing trace with hash 962099791, now seen corresponding path program 1 times [2022-04-08 11:27:10,948 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:10,948 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1815428227] [2022-04-08 11:27:10,949 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:27:10,949 INFO L85 PathProgramCache]: Analyzing trace with hash 962099791, now seen corresponding path program 2 times [2022-04-08 11:27:10,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:10,949 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [785172718] [2022-04-08 11:27:10,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:10,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:10,962 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:27:10,962 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [463187248] [2022-04-08 11:27:10,962 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:27:10,962 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:10,962 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:27:10,979 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:27:10,980 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-08 11:27:11,014 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:27:11,014 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:27:11,015 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 11:27:11,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:11,033 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:27:11,166 INFO L272 TraceCheckUtils]: 0: Hoare triple {649#true} call ULTIMATE.init(); {649#true} is VALID [2022-04-08 11:27:11,167 INFO L290 TraceCheckUtils]: 1: Hoare triple {649#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,167 INFO L290 TraceCheckUtils]: 2: Hoare triple {657#(<= ~counter~0 0)} assume true; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,170 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {657#(<= ~counter~0 0)} {649#true} #102#return; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,171 INFO L272 TraceCheckUtils]: 4: Hoare triple {657#(<= ~counter~0 0)} call #t~ret7 := main(); {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,174 INFO L290 TraceCheckUtils]: 5: Hoare triple {657#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,174 INFO L272 TraceCheckUtils]: 6: Hoare triple {657#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,174 INFO L290 TraceCheckUtils]: 7: Hoare triple {657#(<= ~counter~0 0)} ~cond := #in~cond; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,175 INFO L290 TraceCheckUtils]: 8: Hoare triple {657#(<= ~counter~0 0)} assume !(0 == ~cond); {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,175 INFO L290 TraceCheckUtils]: 9: Hoare triple {657#(<= ~counter~0 0)} assume true; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,176 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {657#(<= ~counter~0 0)} {657#(<= ~counter~0 0)} #82#return; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,176 INFO L290 TraceCheckUtils]: 11: Hoare triple {657#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {657#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:11,176 INFO L290 TraceCheckUtils]: 12: Hoare triple {657#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {691#(<= ~counter~0 1)} is VALID [2022-04-08 11:27:11,177 INFO L290 TraceCheckUtils]: 13: Hoare triple {691#(<= ~counter~0 1)} assume !!(#t~post5 < 10);havoc #t~post5; {691#(<= ~counter~0 1)} is VALID [2022-04-08 11:27:11,177 INFO L290 TraceCheckUtils]: 14: Hoare triple {691#(<= ~counter~0 1)} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {691#(<= ~counter~0 1)} is VALID [2022-04-08 11:27:11,178 INFO L290 TraceCheckUtils]: 15: Hoare triple {691#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {701#(<= |main_#t~post6| 1)} is VALID [2022-04-08 11:27:11,178 INFO L290 TraceCheckUtils]: 16: Hoare triple {701#(<= |main_#t~post6| 1)} assume !(#t~post6 < 10);havoc #t~post6; {650#false} is VALID [2022-04-08 11:27:11,178 INFO L272 TraceCheckUtils]: 17: Hoare triple {650#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {650#false} is VALID [2022-04-08 11:27:11,178 INFO L290 TraceCheckUtils]: 18: Hoare triple {650#false} ~cond := #in~cond; {650#false} is VALID [2022-04-08 11:27:11,178 INFO L290 TraceCheckUtils]: 19: Hoare triple {650#false} assume 0 == ~cond; {650#false} is VALID [2022-04-08 11:27:11,178 INFO L290 TraceCheckUtils]: 20: Hoare triple {650#false} assume !false; {650#false} is VALID [2022-04-08 11:27:11,179 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:27:11,179 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:27:11,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:11,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [785172718] [2022-04-08 11:27:11,179 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:27:11,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [463187248] [2022-04-08 11:27:11,179 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [463187248] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:11,179 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:11,179 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:27:11,180 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:11,180 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1815428227] [2022-04-08 11:27:11,180 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1815428227] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:11,180 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:11,180 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:27:11,180 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781941069] [2022-04-08 11:27:11,180 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:11,180 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-04-08 11:27:11,181 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:11,181 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:11,199 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:11,199 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 11:27:11,199 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:11,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 11:27:11,199 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-08 11:27:11,199 INFO L87 Difference]: Start difference. First operand 36 states and 48 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:19,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:19,391 INFO L93 Difference]: Finished difference Result 49 states and 64 transitions. [2022-04-08 11:27:19,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 11:27:19,391 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-04-08 11:27:19,392 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:27:19,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:19,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-08 11:27:19,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:19,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-08 11:27:19,395 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 64 transitions. [2022-04-08 11:27:19,443 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:19,444 INFO L225 Difference]: With dead ends: 49 [2022-04-08 11:27:19,444 INFO L226 Difference]: Without dead ends: 40 [2022-04-08 11:27:19,444 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-08 11:27:19,445 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 11:27:19,445 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 149 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 11:27:19,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-08 11:27:19,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2022-04-08 11:27:19,458 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:27:19,458 INFO L82 GeneralOperation]: Start isEquivalent. First operand 40 states. Second operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:19,459 INFO L74 IsIncluded]: Start isIncluded. First operand 40 states. Second operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:19,459 INFO L87 Difference]: Start difference. First operand 40 states. Second operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:19,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:19,461 INFO L93 Difference]: Finished difference Result 40 states and 53 transitions. [2022-04-08 11:27:19,461 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 53 transitions. [2022-04-08 11:27:19,461 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:19,461 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:19,462 INFO L74 IsIncluded]: Start isIncluded. First operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 40 states. [2022-04-08 11:27:19,462 INFO L87 Difference]: Start difference. First operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 40 states. [2022-04-08 11:27:19,464 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:19,464 INFO L93 Difference]: Finished difference Result 40 states and 53 transitions. [2022-04-08 11:27:19,464 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 53 transitions. [2022-04-08 11:27:19,464 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:19,464 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:19,464 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:27:19,465 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:27:19,465 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 11:27:19,466 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2022-04-08 11:27:19,466 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 21 [2022-04-08 11:27:19,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:27:19,466 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2022-04-08 11:27:19,467 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 11:27:19,467 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 39 states and 52 transitions. [2022-04-08 11:27:19,514 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 52 edges. 52 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:19,515 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2022-04-08 11:27:19,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-08 11:27:19,515 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:19,515 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:19,531 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-08 11:27:19,731 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-08 11:27:19,732 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:19,732 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:19,732 INFO L85 PathProgramCache]: Analyzing trace with hash 963589341, now seen corresponding path program 1 times [2022-04-08 11:27:19,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:19,732 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2094150425] [2022-04-08 11:27:19,733 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 11:27:19,733 INFO L85 PathProgramCache]: Analyzing trace with hash 963589341, now seen corresponding path program 2 times [2022-04-08 11:27:19,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:19,733 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1240222467] [2022-04-08 11:27:19,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:19,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:19,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:19,943 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:27:19,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:19,949 INFO L290 TraceCheckUtils]: 0: Hoare triple {985#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {972#true} is VALID [2022-04-08 11:27:19,949 INFO L290 TraceCheckUtils]: 1: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:27:19,949 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {972#true} {972#true} #102#return; {972#true} is VALID [2022-04-08 11:27:19,949 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:27:19,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:19,953 INFO L290 TraceCheckUtils]: 0: Hoare triple {972#true} ~cond := #in~cond; {972#true} is VALID [2022-04-08 11:27:19,953 INFO L290 TraceCheckUtils]: 1: Hoare triple {972#true} assume !(0 == ~cond); {972#true} is VALID [2022-04-08 11:27:19,967 INFO L290 TraceCheckUtils]: 2: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:27:19,967 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {972#true} {972#true} #82#return; {972#true} is VALID [2022-04-08 11:27:19,968 INFO L272 TraceCheckUtils]: 0: Hoare triple {972#true} call ULTIMATE.init(); {985#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:27:19,969 INFO L290 TraceCheckUtils]: 1: Hoare triple {985#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {972#true} is VALID [2022-04-08 11:27:19,969 INFO L290 TraceCheckUtils]: 2: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:27:19,969 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {972#true} {972#true} #102#return; {972#true} is VALID [2022-04-08 11:27:19,969 INFO L272 TraceCheckUtils]: 4: Hoare triple {972#true} call #t~ret7 := main(); {972#true} is VALID [2022-04-08 11:27:19,969 INFO L290 TraceCheckUtils]: 5: Hoare triple {972#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {972#true} is VALID [2022-04-08 11:27:19,969 INFO L272 TraceCheckUtils]: 6: Hoare triple {972#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {972#true} is VALID [2022-04-08 11:27:19,970 INFO L290 TraceCheckUtils]: 7: Hoare triple {972#true} ~cond := #in~cond; {972#true} is VALID [2022-04-08 11:27:19,970 INFO L290 TraceCheckUtils]: 8: Hoare triple {972#true} assume !(0 == ~cond); {972#true} is VALID [2022-04-08 11:27:19,970 INFO L290 TraceCheckUtils]: 9: Hoare triple {972#true} assume true; {972#true} is VALID [2022-04-08 11:27:19,970 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {972#true} {972#true} #82#return; {972#true} is VALID [2022-04-08 11:27:19,971 INFO L290 TraceCheckUtils]: 11: Hoare triple {972#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-08 11:27:19,971 INFO L290 TraceCheckUtils]: 12: Hoare triple {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-08 11:27:19,971 INFO L290 TraceCheckUtils]: 13: Hoare triple {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !!(#t~post5 < 10);havoc #t~post5; {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-08 11:27:19,972 INFO L290 TraceCheckUtils]: 14: Hoare triple {981#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-08 11:27:19,973 INFO L290 TraceCheckUtils]: 15: Hoare triple {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-08 11:27:19,973 INFO L290 TraceCheckUtils]: 16: Hoare triple {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} assume !!(#t~post6 < 10);havoc #t~post6; {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-08 11:27:19,974 INFO L272 TraceCheckUtils]: 17: Hoare triple {982#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {983#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 11:27:19,975 INFO L290 TraceCheckUtils]: 18: Hoare triple {983#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {984#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 11:27:19,975 INFO L290 TraceCheckUtils]: 19: Hoare triple {984#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {973#false} is VALID [2022-04-08 11:27:19,975 INFO L290 TraceCheckUtils]: 20: Hoare triple {973#false} assume !false; {973#false} is VALID [2022-04-08 11:27:19,976 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:27:19,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:19,976 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1240222467] [2022-04-08 11:27:19,976 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1240222467] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:19,976 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:19,976 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-08 11:27:19,977 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:19,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2094150425] [2022-04-08 11:27:19,977 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2094150425] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:19,977 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:19,977 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-08 11:27:19,977 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [486591897] [2022-04-08 11:27:19,977 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:19,977 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2022-04-08 11:27:19,978 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:19,978 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:19,991 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:19,991 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-08 11:27:19,992 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:19,992 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-08 11:27:19,992 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-08 11:27:19,992 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:28,926 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:27:31,325 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:27:39,230 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:27:41,499 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:27:43,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:43,724 INFO L93 Difference]: Finished difference Result 72 states and 104 transitions. [2022-04-08 11:27:43,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-08 11:27:43,724 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2022-04-08 11:27:43,724 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:27:43,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:43,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 104 transitions. [2022-04-08 11:27:43,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:43,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 104 transitions. [2022-04-08 11:27:43,728 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 104 transitions. [2022-04-08 11:27:43,960 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 104 edges. 104 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:43,961 INFO L225 Difference]: With dead ends: 72 [2022-04-08 11:27:43,961 INFO L226 Difference]: Without dead ends: 51 [2022-04-08 11:27:43,962 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-08 11:27:43,963 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 24 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 37 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.8s IncrementalHoareTripleChecker+Time [2022-04-08 11:27:43,963 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 107 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 205 Invalid, 4 Unknown, 0 Unchecked, 13.8s Time] [2022-04-08 11:27:43,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-08 11:27:43,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-04-08 11:27:43,989 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:27:43,989 INFO L82 GeneralOperation]: Start isEquivalent. First operand 51 states. Second operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:27:43,990 INFO L74 IsIncluded]: Start isIncluded. First operand 51 states. Second operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:27:43,991 INFO L87 Difference]: Start difference. First operand 51 states. Second operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:27:43,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:43,997 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-04-08 11:27:43,997 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-08 11:27:44,000 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:44,000 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:44,000 INFO L74 IsIncluded]: Start isIncluded. First operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 51 states. [2022-04-08 11:27:44,000 INFO L87 Difference]: Start difference. First operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 51 states. [2022-04-08 11:27:44,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:44,005 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-04-08 11:27:44,005 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-08 11:27:44,006 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:44,006 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:44,006 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:27:44,006 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:27:44,006 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-08 11:27:44,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 69 transitions. [2022-04-08 11:27:44,008 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 69 transitions. Word has length 21 [2022-04-08 11:27:44,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:27:44,008 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 69 transitions. [2022-04-08 11:27:44,008 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:44,008 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 51 states and 69 transitions. [2022-04-08 11:27:44,236 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:44,236 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-08 11:27:44,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-08 11:27:44,237 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:44,237 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:44,237 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-08 11:27:44,237 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:44,237 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:44,237 INFO L85 PathProgramCache]: Analyzing trace with hash -1701877900, now seen corresponding path program 1 times [2022-04-08 11:27:44,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:44,237 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [216980975] [2022-04-08 11:27:44,254 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:27:44,255 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:27:44,255 INFO L85 PathProgramCache]: Analyzing trace with hash -1701877900, now seen corresponding path program 2 times [2022-04-08 11:27:44,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:44,255 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2100507997] [2022-04-08 11:27:44,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:44,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:44,265 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:27:44,265 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [725768207] [2022-04-08 11:27:44,265 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:27:44,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:44,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:27:44,276 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:27:44,277 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-08 11:27:44,313 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:27:44,314 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:27:44,314 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 11:27:44,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:44,322 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:27:44,411 INFO L272 TraceCheckUtils]: 0: Hoare triple {1346#true} call ULTIMATE.init(); {1346#true} is VALID [2022-04-08 11:27:44,411 INFO L290 TraceCheckUtils]: 1: Hoare triple {1346#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1346#true} is VALID [2022-04-08 11:27:44,411 INFO L290 TraceCheckUtils]: 2: Hoare triple {1346#true} assume true; {1346#true} is VALID [2022-04-08 11:27:44,411 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1346#true} {1346#true} #102#return; {1346#true} is VALID [2022-04-08 11:27:44,411 INFO L272 TraceCheckUtils]: 4: Hoare triple {1346#true} call #t~ret7 := main(); {1346#true} is VALID [2022-04-08 11:27:44,412 INFO L290 TraceCheckUtils]: 5: Hoare triple {1346#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1346#true} is VALID [2022-04-08 11:27:44,412 INFO L272 TraceCheckUtils]: 6: Hoare triple {1346#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1346#true} is VALID [2022-04-08 11:27:44,412 INFO L290 TraceCheckUtils]: 7: Hoare triple {1346#true} ~cond := #in~cond; {1346#true} is VALID [2022-04-08 11:27:44,412 INFO L290 TraceCheckUtils]: 8: Hoare triple {1346#true} assume !(0 == ~cond); {1346#true} is VALID [2022-04-08 11:27:44,412 INFO L290 TraceCheckUtils]: 9: Hoare triple {1346#true} assume true; {1346#true} is VALID [2022-04-08 11:27:44,412 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1346#true} {1346#true} #82#return; {1346#true} is VALID [2022-04-08 11:27:44,413 INFO L290 TraceCheckUtils]: 11: Hoare triple {1346#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,413 INFO L290 TraceCheckUtils]: 12: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,413 INFO L290 TraceCheckUtils]: 13: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(#t~post5 < 10);havoc #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,414 INFO L290 TraceCheckUtils]: 14: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,414 INFO L290 TraceCheckUtils]: 15: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,415 INFO L290 TraceCheckUtils]: 16: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(#t~post5 < 10);havoc #t~post5; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,415 INFO L290 TraceCheckUtils]: 17: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,415 INFO L290 TraceCheckUtils]: 18: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(#t~post6 < 10);havoc #t~post6; {1384#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-08 11:27:44,416 INFO L272 TraceCheckUtils]: 19: Hoare triple {1384#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {1409#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 11:27:44,417 INFO L290 TraceCheckUtils]: 20: Hoare triple {1409#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1413#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 11:27:44,417 INFO L290 TraceCheckUtils]: 21: Hoare triple {1413#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1347#false} is VALID [2022-04-08 11:27:44,417 INFO L290 TraceCheckUtils]: 22: Hoare triple {1347#false} assume !false; {1347#false} is VALID [2022-04-08 11:27:44,417 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-08 11:27:44,417 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:27:44,418 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:44,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2100507997] [2022-04-08 11:27:44,418 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:27:44,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [725768207] [2022-04-08 11:27:44,418 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [725768207] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:44,418 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:44,418 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:27:44,418 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:44,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [216980975] [2022-04-08 11:27:44,418 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [216980975] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:44,418 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:44,418 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:27:44,419 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [583916006] [2022-04-08 11:27:44,419 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:44,419 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:27:44,419 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:44,419 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:44,434 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:44,434 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 11:27:44,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:44,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 11:27:44,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 11:27:44,434 INFO L87 Difference]: Start difference. First operand 51 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:50,028 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:27:52,293 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:27:52,766 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:52,767 INFO L93 Difference]: Finished difference Result 73 states and 99 transitions. [2022-04-08 11:27:52,767 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 11:27:52,767 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:27:52,767 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:27:52,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:52,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 73 transitions. [2022-04-08 11:27:52,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:52,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 73 transitions. [2022-04-08 11:27:52,770 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 73 transitions. [2022-04-08 11:27:52,837 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 73 edges. 73 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:52,839 INFO L225 Difference]: With dead ends: 73 [2022-04-08 11:27:52,839 INFO L226 Difference]: Without dead ends: 52 [2022-04-08 11:27:52,839 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 11:27:52,840 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 8 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2022-04-08 11:27:52,840 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 157 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 2 Unknown, 0 Unchecked, 4.6s Time] [2022-04-08 11:27:52,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-08 11:27:52,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-04-08 11:27:52,853 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:27:52,854 INFO L82 GeneralOperation]: Start isEquivalent. First operand 52 states. Second operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:27:52,854 INFO L74 IsIncluded]: Start isIncluded. First operand 52 states. Second operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:27:52,854 INFO L87 Difference]: Start difference. First operand 52 states. Second operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:27:52,856 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:52,856 INFO L93 Difference]: Finished difference Result 52 states and 72 transitions. [2022-04-08 11:27:52,856 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-08 11:27:52,856 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:52,857 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:52,857 INFO L74 IsIncluded]: Start isIncluded. First operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 52 states. [2022-04-08 11:27:52,857 INFO L87 Difference]: Start difference. First operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 52 states. [2022-04-08 11:27:52,859 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:52,859 INFO L93 Difference]: Finished difference Result 52 states and 72 transitions. [2022-04-08 11:27:52,859 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-08 11:27:52,859 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:52,859 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:52,859 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:27:52,859 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:27:52,860 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 29 states have internal predecessors, (35), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-08 11:27:52,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 72 transitions. [2022-04-08 11:27:52,861 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 72 transitions. Word has length 23 [2022-04-08 11:27:52,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:27:52,861 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 72 transitions. [2022-04-08 11:27:52,862 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:52,862 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 52 states and 72 transitions. [2022-04-08 11:27:52,939 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 72 edges. 72 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:52,940 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-08 11:27:52,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-08 11:27:52,940 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:52,940 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:52,956 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-08 11:27:53,140 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:53,141 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:53,141 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:53,141 INFO L85 PathProgramCache]: Analyzing trace with hash -1700388350, now seen corresponding path program 1 times [2022-04-08 11:27:53,141 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:53,142 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [267568054] [2022-04-08 11:27:53,154 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:27:53,155 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:27:53,155 INFO L85 PathProgramCache]: Analyzing trace with hash -1700388350, now seen corresponding path program 2 times [2022-04-08 11:27:53,155 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:53,155 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [392986931] [2022-04-08 11:27:53,155 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:53,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:53,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:53,200 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:27:53,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:53,207 INFO L290 TraceCheckUtils]: 0: Hoare triple {1787#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,208 INFO L290 TraceCheckUtils]: 1: Hoare triple {1780#(<= ~counter~0 0)} assume true; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,208 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {1780#(<= ~counter~0 0)} {1775#true} #102#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,208 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:27:53,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:53,212 INFO L290 TraceCheckUtils]: 0: Hoare triple {1775#true} ~cond := #in~cond; {1775#true} is VALID [2022-04-08 11:27:53,212 INFO L290 TraceCheckUtils]: 1: Hoare triple {1775#true} assume !(0 == ~cond); {1775#true} is VALID [2022-04-08 11:27:53,212 INFO L290 TraceCheckUtils]: 2: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:27:53,213 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1775#true} {1780#(<= ~counter~0 0)} #82#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,213 INFO L272 TraceCheckUtils]: 0: Hoare triple {1775#true} call ULTIMATE.init(); {1787#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:27:53,214 INFO L290 TraceCheckUtils]: 1: Hoare triple {1787#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,214 INFO L290 TraceCheckUtils]: 2: Hoare triple {1780#(<= ~counter~0 0)} assume true; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,215 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1780#(<= ~counter~0 0)} {1775#true} #102#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,215 INFO L272 TraceCheckUtils]: 4: Hoare triple {1780#(<= ~counter~0 0)} call #t~ret7 := main(); {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,218 INFO L290 TraceCheckUtils]: 5: Hoare triple {1780#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,218 INFO L272 TraceCheckUtils]: 6: Hoare triple {1780#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1775#true} is VALID [2022-04-08 11:27:53,218 INFO L290 TraceCheckUtils]: 7: Hoare triple {1775#true} ~cond := #in~cond; {1775#true} is VALID [2022-04-08 11:27:53,218 INFO L290 TraceCheckUtils]: 8: Hoare triple {1775#true} assume !(0 == ~cond); {1775#true} is VALID [2022-04-08 11:27:53,218 INFO L290 TraceCheckUtils]: 9: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:27:53,219 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1775#true} {1780#(<= ~counter~0 0)} #82#return; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,219 INFO L290 TraceCheckUtils]: 11: Hoare triple {1780#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1780#(<= ~counter~0 0)} is VALID [2022-04-08 11:27:53,219 INFO L290 TraceCheckUtils]: 12: Hoare triple {1780#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1785#(<= ~counter~0 1)} is VALID [2022-04-08 11:27:53,220 INFO L290 TraceCheckUtils]: 13: Hoare triple {1785#(<= ~counter~0 1)} assume !!(#t~post5 < 10);havoc #t~post5; {1785#(<= ~counter~0 1)} is VALID [2022-04-08 11:27:53,220 INFO L290 TraceCheckUtils]: 14: Hoare triple {1785#(<= ~counter~0 1)} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1785#(<= ~counter~0 1)} is VALID [2022-04-08 11:27:53,220 INFO L290 TraceCheckUtils]: 15: Hoare triple {1785#(<= ~counter~0 1)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1786#(<= |main_#t~post5| 1)} is VALID [2022-04-08 11:27:53,221 INFO L290 TraceCheckUtils]: 16: Hoare triple {1786#(<= |main_#t~post5| 1)} assume !(#t~post5 < 10);havoc #t~post5; {1776#false} is VALID [2022-04-08 11:27:53,221 INFO L290 TraceCheckUtils]: 17: Hoare triple {1776#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1776#false} is VALID [2022-04-08 11:27:53,221 INFO L290 TraceCheckUtils]: 18: Hoare triple {1776#false} assume !!(#t~post6 < 10);havoc #t~post6; {1776#false} is VALID [2022-04-08 11:27:53,221 INFO L272 TraceCheckUtils]: 19: Hoare triple {1776#false} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1776#false} is VALID [2022-04-08 11:27:53,252 INFO L290 TraceCheckUtils]: 20: Hoare triple {1776#false} ~cond := #in~cond; {1776#false} is VALID [2022-04-08 11:27:53,252 INFO L290 TraceCheckUtils]: 21: Hoare triple {1776#false} assume 0 == ~cond; {1776#false} is VALID [2022-04-08 11:27:53,252 INFO L290 TraceCheckUtils]: 22: Hoare triple {1776#false} assume !false; {1776#false} is VALID [2022-04-08 11:27:53,252 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:27:53,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:53,252 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [392986931] [2022-04-08 11:27:53,252 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [392986931] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-08 11:27:53,253 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1129850325] [2022-04-08 11:27:53,253 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:27:53,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:53,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:27:53,254 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:27:53,255 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-08 11:27:53,293 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:27:53,294 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:27:53,294 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-08 11:27:53,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:53,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:27:53,381 INFO L272 TraceCheckUtils]: 0: Hoare triple {1775#true} call ULTIMATE.init(); {1775#true} is VALID [2022-04-08 11:27:53,381 INFO L290 TraceCheckUtils]: 1: Hoare triple {1775#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1775#true} is VALID [2022-04-08 11:27:53,381 INFO L290 TraceCheckUtils]: 2: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:27:53,381 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1775#true} {1775#true} #102#return; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L272 TraceCheckUtils]: 4: Hoare triple {1775#true} call #t~ret7 := main(); {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 5: Hoare triple {1775#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L272 TraceCheckUtils]: 6: Hoare triple {1775#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 7: Hoare triple {1775#true} ~cond := #in~cond; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 8: Hoare triple {1775#true} assume !(0 == ~cond); {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 9: Hoare triple {1775#true} assume true; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1775#true} {1775#true} #82#return; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 11: Hoare triple {1775#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 12: Hoare triple {1775#true} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1775#true} is VALID [2022-04-08 11:27:53,382 INFO L290 TraceCheckUtils]: 13: Hoare triple {1775#true} assume !!(#t~post5 < 10);havoc #t~post5; {1775#true} is VALID [2022-04-08 11:27:53,383 INFO L290 TraceCheckUtils]: 14: Hoare triple {1775#true} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1775#true} is VALID [2022-04-08 11:27:53,383 INFO L290 TraceCheckUtils]: 15: Hoare triple {1775#true} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1836#(<= (+ |main_#t~post5| 1) ~counter~0)} is VALID [2022-04-08 11:27:53,383 INFO L290 TraceCheckUtils]: 16: Hoare triple {1836#(<= (+ |main_#t~post5| 1) ~counter~0)} assume !(#t~post5 < 10);havoc #t~post5; {1840#(<= 11 ~counter~0)} is VALID [2022-04-08 11:27:53,384 INFO L290 TraceCheckUtils]: 17: Hoare triple {1840#(<= 11 ~counter~0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1844#(<= 11 |main_#t~post6|)} is VALID [2022-04-08 11:27:53,384 INFO L290 TraceCheckUtils]: 18: Hoare triple {1844#(<= 11 |main_#t~post6|)} assume !!(#t~post6 < 10);havoc #t~post6; {1776#false} is VALID [2022-04-08 11:27:53,384 INFO L272 TraceCheckUtils]: 19: Hoare triple {1776#false} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1776#false} is VALID [2022-04-08 11:27:53,384 INFO L290 TraceCheckUtils]: 20: Hoare triple {1776#false} ~cond := #in~cond; {1776#false} is VALID [2022-04-08 11:27:53,385 INFO L290 TraceCheckUtils]: 21: Hoare triple {1776#false} assume 0 == ~cond; {1776#false} is VALID [2022-04-08 11:27:53,385 INFO L290 TraceCheckUtils]: 22: Hoare triple {1776#false} assume !false; {1776#false} is VALID [2022-04-08 11:27:53,385 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-08 11:27:53,385 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:27:53,385 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1129850325] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:53,385 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-08 11:27:53,385 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2022-04-08 11:27:53,385 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:53,385 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [267568054] [2022-04-08 11:27:53,385 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [267568054] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:53,385 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:53,386 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 11:27:53,386 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2089278047] [2022-04-08 11:27:53,386 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:53,386 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:27:53,386 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:53,386 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:53,402 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:53,402 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 11:27:53,402 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:53,402 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 11:27:53,402 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2022-04-08 11:27:53,402 INFO L87 Difference]: Start difference. First operand 52 states and 72 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:54,981 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.48s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-08 11:27:58,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:58,071 INFO L93 Difference]: Finished difference Result 98 states and 135 transitions. [2022-04-08 11:27:58,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 11:27:58,071 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2022-04-08 11:27:58,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:27:58,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:58,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 86 transitions. [2022-04-08 11:27:58,073 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:58,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 86 transitions. [2022-04-08 11:27:58,074 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 86 transitions. [2022-04-08 11:27:58,135 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 86 edges. 86 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:58,136 INFO L225 Difference]: With dead ends: 98 [2022-04-08 11:27:58,136 INFO L226 Difference]: Without dead ends: 64 [2022-04-08 11:27:58,136 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-08 11:27:58,137 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 8 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2022-04-08 11:27:58,137 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 170 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2022-04-08 11:27:58,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-08 11:27:58,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 62. [2022-04-08 11:27:58,161 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:27:58,162 INFO L82 GeneralOperation]: Start isEquivalent. First operand 64 states. Second operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:27:58,162 INFO L74 IsIncluded]: Start isIncluded. First operand 64 states. Second operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:27:58,162 INFO L87 Difference]: Start difference. First operand 64 states. Second operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:27:58,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:58,164 INFO L93 Difference]: Finished difference Result 64 states and 83 transitions. [2022-04-08 11:27:58,164 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 83 transitions. [2022-04-08 11:27:58,164 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:58,164 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:58,165 INFO L74 IsIncluded]: Start isIncluded. First operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Second operand 64 states. [2022-04-08 11:27:58,165 INFO L87 Difference]: Start difference. First operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Second operand 64 states. [2022-04-08 11:27:58,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:27:58,167 INFO L93 Difference]: Finished difference Result 64 states and 83 transitions. [2022-04-08 11:27:58,167 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 83 transitions. [2022-04-08 11:27:58,167 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:27:58,167 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:27:58,167 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:27:58,167 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:27:58,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 36 states have internal predecessors, (42), 22 states have call successors, (22), 7 states have call predecessors, (22), 5 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-08 11:27:58,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 82 transitions. [2022-04-08 11:27:58,169 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 82 transitions. Word has length 23 [2022-04-08 11:27:58,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:27:58,169 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 82 transitions. [2022-04-08 11:27:58,169 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:58,169 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 62 states and 82 transitions. [2022-04-08 11:27:58,243 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 82 edges. 82 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:58,243 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 82 transitions. [2022-04-08 11:27:58,243 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-08 11:27:58,243 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:27:58,243 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:27:58,259 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-08 11:27:58,444 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:58,444 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:27:58,444 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:27:58,444 INFO L85 PathProgramCache]: Analyzing trace with hash -1562772727, now seen corresponding path program 1 times [2022-04-08 11:27:58,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:58,444 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1036959820] [2022-04-08 11:27:58,450 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:27:58,450 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:27:58,450 INFO L85 PathProgramCache]: Analyzing trace with hash -1562772727, now seen corresponding path program 2 times [2022-04-08 11:27:58,450 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:27:58,450 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [525281453] [2022-04-08 11:27:58,450 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:27:58,451 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:27:58,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:58,626 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 11:27:58,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:58,635 INFO L290 TraceCheckUtils]: 0: Hoare triple {2323#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2309#true} is VALID [2022-04-08 11:27:58,636 INFO L290 TraceCheckUtils]: 1: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:27:58,636 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {2309#true} {2309#true} #102#return; {2309#true} is VALID [2022-04-08 11:27:58,636 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 11:27:58,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:58,648 INFO L290 TraceCheckUtils]: 0: Hoare triple {2309#true} ~cond := #in~cond; {2309#true} is VALID [2022-04-08 11:27:58,648 INFO L290 TraceCheckUtils]: 1: Hoare triple {2309#true} assume !(0 == ~cond); {2309#true} is VALID [2022-04-08 11:27:58,648 INFO L290 TraceCheckUtils]: 2: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:27:58,649 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2309#true} {2309#true} #82#return; {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L272 TraceCheckUtils]: 0: Hoare triple {2309#true} call ULTIMATE.init(); {2323#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 11:27:58,650 INFO L290 TraceCheckUtils]: 1: Hoare triple {2323#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L290 TraceCheckUtils]: 2: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2309#true} {2309#true} #102#return; {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L272 TraceCheckUtils]: 4: Hoare triple {2309#true} call #t~ret7 := main(); {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L290 TraceCheckUtils]: 5: Hoare triple {2309#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L272 TraceCheckUtils]: 6: Hoare triple {2309#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L290 TraceCheckUtils]: 7: Hoare triple {2309#true} ~cond := #in~cond; {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L290 TraceCheckUtils]: 8: Hoare triple {2309#true} assume !(0 == ~cond); {2309#true} is VALID [2022-04-08 11:27:58,650 INFO L290 TraceCheckUtils]: 9: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:27:58,651 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2309#true} {2309#true} #82#return; {2309#true} is VALID [2022-04-08 11:27:58,654 INFO L290 TraceCheckUtils]: 11: Hoare triple {2309#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} is VALID [2022-04-08 11:27:58,655 INFO L290 TraceCheckUtils]: 12: Hoare triple {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} is VALID [2022-04-08 11:27:58,655 INFO L290 TraceCheckUtils]: 13: Hoare triple {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} assume !!(#t~post5 < 10);havoc #t~post5; {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} is VALID [2022-04-08 11:27:58,656 INFO L290 TraceCheckUtils]: 14: Hoare triple {2318#(and (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0) (= (+ main_~n~0 (* (- 1) main_~r~0)) 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:58,656 INFO L290 TraceCheckUtils]: 15: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:58,656 INFO L290 TraceCheckUtils]: 16: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(#t~post5 < 10);havoc #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:58,657 INFO L290 TraceCheckUtils]: 17: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:27:58,657 INFO L290 TraceCheckUtils]: 18: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:27:58,658 INFO L290 TraceCheckUtils]: 19: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} assume !!(#t~post6 < 10);havoc #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:27:58,659 INFO L272 TraceCheckUtils]: 20: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2321#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 11:27:58,659 INFO L290 TraceCheckUtils]: 21: Hoare triple {2321#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {2322#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 11:27:58,659 INFO L290 TraceCheckUtils]: 22: Hoare triple {2322#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {2310#false} is VALID [2022-04-08 11:27:58,659 INFO L290 TraceCheckUtils]: 23: Hoare triple {2310#false} assume !false; {2310#false} is VALID [2022-04-08 11:27:58,660 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 11:27:58,660 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:27:58,660 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [525281453] [2022-04-08 11:27:58,660 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [525281453] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-08 11:27:58,660 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [735718720] [2022-04-08 11:27:58,660 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:27:58,660 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:27:58,660 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:27:58,661 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:27:58,667 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-08 11:27:58,691 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 11:27:58,691 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:27:58,691 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 8 conjunts are in the unsatisfiable core [2022-04-08 11:27:58,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:27:58,701 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:27:59,306 INFO L272 TraceCheckUtils]: 0: Hoare triple {2309#true} call ULTIMATE.init(); {2309#true} is VALID [2022-04-08 11:27:59,306 INFO L290 TraceCheckUtils]: 1: Hoare triple {2309#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L290 TraceCheckUtils]: 2: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2309#true} {2309#true} #102#return; {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L272 TraceCheckUtils]: 4: Hoare triple {2309#true} call #t~ret7 := main(); {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L290 TraceCheckUtils]: 5: Hoare triple {2309#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L272 TraceCheckUtils]: 6: Hoare triple {2309#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L290 TraceCheckUtils]: 7: Hoare triple {2309#true} ~cond := #in~cond; {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L290 TraceCheckUtils]: 8: Hoare triple {2309#true} assume !(0 == ~cond); {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L290 TraceCheckUtils]: 9: Hoare triple {2309#true} assume true; {2309#true} is VALID [2022-04-08 11:27:59,307 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2309#true} {2309#true} #82#return; {2309#true} is VALID [2022-04-08 11:27:59,308 INFO L290 TraceCheckUtils]: 11: Hoare triple {2309#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:59,308 INFO L290 TraceCheckUtils]: 12: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:59,308 INFO L290 TraceCheckUtils]: 13: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(#t~post5 < 10);havoc #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:59,309 INFO L290 TraceCheckUtils]: 14: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:59,309 INFO L290 TraceCheckUtils]: 15: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:59,310 INFO L290 TraceCheckUtils]: 16: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(#t~post5 < 10);havoc #t~post5; {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-08 11:27:59,310 INFO L290 TraceCheckUtils]: 17: Hoare triple {2319#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:27:59,311 INFO L290 TraceCheckUtils]: 18: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:27:59,311 INFO L290 TraceCheckUtils]: 19: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} assume !!(#t~post6 < 10);havoc #t~post6; {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-08 11:27:59,312 INFO L272 TraceCheckUtils]: 20: Hoare triple {2320#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2387#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 11:27:59,312 INFO L290 TraceCheckUtils]: 21: Hoare triple {2387#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2391#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 11:27:59,313 INFO L290 TraceCheckUtils]: 22: Hoare triple {2391#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2310#false} is VALID [2022-04-08 11:27:59,313 INFO L290 TraceCheckUtils]: 23: Hoare triple {2310#false} assume !false; {2310#false} is VALID [2022-04-08 11:27:59,313 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-08 11:27:59,313 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 11:27:59,313 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [735718720] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:59,313 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-08 11:27:59,313 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 10 [2022-04-08 11:27:59,314 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:27:59,314 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1036959820] [2022-04-08 11:27:59,314 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1036959820] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:27:59,314 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:27:59,314 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 11:27:59,314 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [699484230] [2022-04-08 11:27:59,314 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:27:59,314 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-04-08 11:27:59,314 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:27:59,314 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:27:59,329 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:27:59,329 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-08 11:27:59,329 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:27:59,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-08 11:27:59,329 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-08 11:27:59,329 INFO L87 Difference]: Start difference. First operand 62 states and 82 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:08,409 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-08 11:28:10,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:10,141 INFO L93 Difference]: Finished difference Result 85 states and 114 transitions. [2022-04-08 11:28:10,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-08 11:28:10,142 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-04-08 11:28:10,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:28:10,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:10,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 95 transitions. [2022-04-08 11:28:10,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:10,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 95 transitions. [2022-04-08 11:28:10,145 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 95 transitions. [2022-04-08 11:28:10,384 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 95 edges. 95 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:10,385 INFO L225 Difference]: With dead ends: 85 [2022-04-08 11:28:10,385 INFO L226 Difference]: Without dead ends: 69 [2022-04-08 11:28:10,386 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-08 11:28:10,386 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 16 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 123 mSolverCounterSat, 26 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 150 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 123 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2022-04-08 11:28:10,386 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 182 Invalid, 150 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 123 Invalid, 1 Unknown, 0 Unchecked, 4.2s Time] [2022-04-08 11:28:10,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-04-08 11:28:10,414 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2022-04-08 11:28:10,414 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:28:10,414 INFO L82 GeneralOperation]: Start isEquivalent. First operand 69 states. Second operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:28:10,414 INFO L74 IsIncluded]: Start isIncluded. First operand 69 states. Second operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:28:10,414 INFO L87 Difference]: Start difference. First operand 69 states. Second operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:28:10,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:10,416 INFO L93 Difference]: Finished difference Result 69 states and 92 transitions. [2022-04-08 11:28:10,416 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 92 transitions. [2022-04-08 11:28:10,417 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:10,417 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:10,417 INFO L74 IsIncluded]: Start isIncluded. First operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand 69 states. [2022-04-08 11:28:10,417 INFO L87 Difference]: Start difference. First operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand 69 states. [2022-04-08 11:28:10,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:10,419 INFO L93 Difference]: Finished difference Result 69 states and 92 transitions. [2022-04-08 11:28:10,419 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 92 transitions. [2022-04-08 11:28:10,419 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:10,419 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:10,419 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:28:10,419 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:28:10,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 39 states have internal predecessors, (45), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-08 11:28:10,421 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 92 transitions. [2022-04-08 11:28:10,421 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 92 transitions. Word has length 24 [2022-04-08 11:28:10,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:28:10,422 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 92 transitions. [2022-04-08 11:28:10,422 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 11:28:10,422 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 69 states and 92 transitions. [2022-04-08 11:28:10,719 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 92 edges. 92 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:10,719 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 92 transitions. [2022-04-08 11:28:10,720 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-08 11:28:10,720 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:28:10,720 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:28:10,735 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-08 11:28:10,920 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:10,920 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:28:10,921 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:28:10,921 INFO L85 PathProgramCache]: Analyzing trace with hash 107903087, now seen corresponding path program 1 times [2022-04-08 11:28:10,921 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:10,921 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1339792807] [2022-04-08 11:28:10,948 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:28:10,948 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:28:10,949 INFO L85 PathProgramCache]: Analyzing trace with hash 107903087, now seen corresponding path program 2 times [2022-04-08 11:28:10,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:28:10,949 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1006648504] [2022-04-08 11:28:10,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:28:10,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:28:10,972 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:28:10,973 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [853680364] [2022-04-08 11:28:10,973 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:28:10,973 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:10,973 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:28:10,983 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:28:10,984 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-08 11:28:11,054 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 11:28:11,054 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 11:28:11,055 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-08 11:28:11,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 11:28:11,068 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 11:28:11,346 INFO L272 TraceCheckUtils]: 0: Hoare triple {2847#true} call ULTIMATE.init(); {2847#true} is VALID [2022-04-08 11:28:11,347 INFO L290 TraceCheckUtils]: 1: Hoare triple {2847#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,347 INFO L290 TraceCheckUtils]: 2: Hoare triple {2855#(<= ~counter~0 0)} assume true; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,347 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2855#(<= ~counter~0 0)} {2847#true} #102#return; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,348 INFO L272 TraceCheckUtils]: 4: Hoare triple {2855#(<= ~counter~0 0)} call #t~ret7 := main(); {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,348 INFO L290 TraceCheckUtils]: 5: Hoare triple {2855#(<= ~counter~0 0)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,349 INFO L272 TraceCheckUtils]: 6: Hoare triple {2855#(<= ~counter~0 0)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,349 INFO L290 TraceCheckUtils]: 7: Hoare triple {2855#(<= ~counter~0 0)} ~cond := #in~cond; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,349 INFO L290 TraceCheckUtils]: 8: Hoare triple {2855#(<= ~counter~0 0)} assume !(0 == ~cond); {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,349 INFO L290 TraceCheckUtils]: 9: Hoare triple {2855#(<= ~counter~0 0)} assume true; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,350 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2855#(<= ~counter~0 0)} {2855#(<= ~counter~0 0)} #82#return; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,350 INFO L290 TraceCheckUtils]: 11: Hoare triple {2855#(<= ~counter~0 0)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {2855#(<= ~counter~0 0)} is VALID [2022-04-08 11:28:11,351 INFO L290 TraceCheckUtils]: 12: Hoare triple {2855#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2889#(<= ~counter~0 1)} is VALID [2022-04-08 11:28:11,351 INFO L290 TraceCheckUtils]: 13: Hoare triple {2889#(<= ~counter~0 1)} assume !!(#t~post5 < 10);havoc #t~post5; {2889#(<= ~counter~0 1)} is VALID [2022-04-08 11:28:11,351 INFO L290 TraceCheckUtils]: 14: Hoare triple {2889#(<= ~counter~0 1)} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {2889#(<= ~counter~0 1)} is VALID [2022-04-08 11:28:11,352 INFO L290 TraceCheckUtils]: 15: Hoare triple {2889#(<= ~counter~0 1)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {2899#(<= ~counter~0 2)} is VALID [2022-04-08 11:28:11,352 INFO L290 TraceCheckUtils]: 16: Hoare triple {2899#(<= ~counter~0 2)} assume !!(#t~post5 < 10);havoc #t~post5; {2899#(<= ~counter~0 2)} is VALID [2022-04-08 11:28:11,352 INFO L290 TraceCheckUtils]: 17: Hoare triple {2899#(<= ~counter~0 2)} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {2899#(<= ~counter~0 2)} is VALID [2022-04-08 11:28:11,353 INFO L290 TraceCheckUtils]: 18: Hoare triple {2899#(<= ~counter~0 2)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,353 INFO L290 TraceCheckUtils]: 19: Hoare triple {2909#(<= ~counter~0 3)} assume !!(#t~post6 < 10);havoc #t~post6; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,354 INFO L272 TraceCheckUtils]: 20: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,354 INFO L290 TraceCheckUtils]: 21: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,354 INFO L290 TraceCheckUtils]: 22: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,355 INFO L290 TraceCheckUtils]: 23: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,355 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #84#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,356 INFO L272 TraceCheckUtils]: 25: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,358 INFO L290 TraceCheckUtils]: 26: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,374 INFO L290 TraceCheckUtils]: 27: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,375 INFO L290 TraceCheckUtils]: 28: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,376 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #86#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,377 INFO L272 TraceCheckUtils]: 30: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,377 INFO L290 TraceCheckUtils]: 31: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,377 INFO L290 TraceCheckUtils]: 32: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,378 INFO L290 TraceCheckUtils]: 33: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,378 INFO L284 TraceCheckUtils]: 34: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #88#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,379 INFO L272 TraceCheckUtils]: 35: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~n~0 - 4 * ~h~0 * ~n~0 * ~p~0 + 4 * (~n~0 * ~n~0) * ~q~0 - ~n~0 * ~q~0 * ~q~0 - ~h~0 * ~h~0 * ~r~0 + 4 * ~h~0 * ~p~0 * ~r~0 - 8 * ~n~0 * ~q~0 * ~r~0 + ~q~0 * ~q~0 * ~r~0 + 4 * ~q~0 * ~r~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,379 INFO L290 TraceCheckUtils]: 36: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,379 INFO L290 TraceCheckUtils]: 37: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,380 INFO L290 TraceCheckUtils]: 38: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,380 INFO L284 TraceCheckUtils]: 39: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #90#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,381 INFO L272 TraceCheckUtils]: 40: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~p~0 - 4 * ~h~0 * ~n~0 * ~q~0 + 4 * ~n~0 * ~p~0 * ~q~0 - ~p~0 * ~q~0 * ~q~0 + 4 * ~h~0 * ~q~0 * ~r~0 - 4 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,381 INFO L290 TraceCheckUtils]: 41: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,381 INFO L290 TraceCheckUtils]: 42: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,382 INFO L290 TraceCheckUtils]: 43: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,382 INFO L284 TraceCheckUtils]: 44: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #92#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,383 INFO L272 TraceCheckUtils]: 45: Hoare triple {2909#(<= ~counter~0 3)} call __VERIFIER_assert((if 0 == (~p~0 * ~p~0 - ~n~0 * ~q~0 + ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,383 INFO L290 TraceCheckUtils]: 46: Hoare triple {2909#(<= ~counter~0 3)} ~cond := #in~cond; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,384 INFO L290 TraceCheckUtils]: 47: Hoare triple {2909#(<= ~counter~0 3)} assume !(0 == ~cond); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,384 INFO L290 TraceCheckUtils]: 48: Hoare triple {2909#(<= ~counter~0 3)} assume true; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,384 INFO L284 TraceCheckUtils]: 49: Hoare quadruple {2909#(<= ~counter~0 3)} {2909#(<= ~counter~0 3)} #94#return; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,385 INFO L290 TraceCheckUtils]: 50: Hoare triple {2909#(<= ~counter~0 3)} assume !!(1 != ~q~0 % 4294967296);~q~0 := (if ~q~0 % 4294967296 < 0 && 0 != ~q~0 % 4294967296 % 4 then 1 + ~q~0 % 4294967296 / 4 else ~q~0 % 4294967296 / 4);~h~0 := ~p~0 + ~q~0;~p~0 := (if ~p~0 % 4294967296 < 0 && 0 != ~p~0 % 4294967296 % 2 then 1 + ~p~0 % 4294967296 / 2 else ~p~0 % 4294967296 / 2); {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,385 INFO L290 TraceCheckUtils]: 51: Hoare triple {2909#(<= ~counter~0 3)} assume ~r~0 % 4294967296 >= ~h~0 % 4294967296;~p~0 := ~p~0 + ~q~0;~r~0 := ~r~0 - ~h~0; {2909#(<= ~counter~0 3)} is VALID [2022-04-08 11:28:11,385 INFO L290 TraceCheckUtils]: 52: Hoare triple {2909#(<= ~counter~0 3)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3012#(<= |main_#t~post6| 3)} is VALID [2022-04-08 11:28:11,386 INFO L290 TraceCheckUtils]: 53: Hoare triple {3012#(<= |main_#t~post6| 3)} assume !(#t~post6 < 10);havoc #t~post6; {2848#false} is VALID [2022-04-08 11:28:11,386 INFO L272 TraceCheckUtils]: 54: Hoare triple {2848#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {2848#false} is VALID [2022-04-08 11:28:11,386 INFO L290 TraceCheckUtils]: 55: Hoare triple {2848#false} ~cond := #in~cond; {2848#false} is VALID [2022-04-08 11:28:11,386 INFO L290 TraceCheckUtils]: 56: Hoare triple {2848#false} assume 0 == ~cond; {2848#false} is VALID [2022-04-08 11:28:11,386 INFO L290 TraceCheckUtils]: 57: Hoare triple {2848#false} assume !false; {2848#false} is VALID [2022-04-08 11:28:11,386 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-08 11:28:11,386 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 11:28:11,679 INFO L290 TraceCheckUtils]: 57: Hoare triple {2848#false} assume !false; {2848#false} is VALID [2022-04-08 11:28:11,679 INFO L290 TraceCheckUtils]: 56: Hoare triple {2848#false} assume 0 == ~cond; {2848#false} is VALID [2022-04-08 11:28:11,679 INFO L290 TraceCheckUtils]: 55: Hoare triple {2848#false} ~cond := #in~cond; {2848#false} is VALID [2022-04-08 11:28:11,679 INFO L272 TraceCheckUtils]: 54: Hoare triple {2848#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {2848#false} is VALID [2022-04-08 11:28:11,680 INFO L290 TraceCheckUtils]: 53: Hoare triple {3040#(< |main_#t~post6| 10)} assume !(#t~post6 < 10);havoc #t~post6; {2848#false} is VALID [2022-04-08 11:28:11,680 INFO L290 TraceCheckUtils]: 52: Hoare triple {3044#(< ~counter~0 10)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3040#(< |main_#t~post6| 10)} is VALID [2022-04-08 11:28:11,680 INFO L290 TraceCheckUtils]: 51: Hoare triple {3044#(< ~counter~0 10)} assume ~r~0 % 4294967296 >= ~h~0 % 4294967296;~p~0 := ~p~0 + ~q~0;~r~0 := ~r~0 - ~h~0; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,681 INFO L290 TraceCheckUtils]: 50: Hoare triple {3044#(< ~counter~0 10)} assume !!(1 != ~q~0 % 4294967296);~q~0 := (if ~q~0 % 4294967296 < 0 && 0 != ~q~0 % 4294967296 % 4 then 1 + ~q~0 % 4294967296 / 4 else ~q~0 % 4294967296 / 4);~h~0 := ~p~0 + ~q~0;~p~0 := (if ~p~0 % 4294967296 < 0 && 0 != ~p~0 % 4294967296 % 2 then 1 + ~p~0 % 4294967296 / 2 else ~p~0 % 4294967296 / 2); {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,681 INFO L284 TraceCheckUtils]: 49: Hoare quadruple {2847#true} {3044#(< ~counter~0 10)} #94#return; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,682 INFO L290 TraceCheckUtils]: 48: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,682 INFO L290 TraceCheckUtils]: 47: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,682 INFO L290 TraceCheckUtils]: 46: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,682 INFO L272 TraceCheckUtils]: 45: Hoare triple {3044#(< ~counter~0 10)} call __VERIFIER_assert((if 0 == (~p~0 * ~p~0 - ~n~0 * ~q~0 + ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,683 INFO L284 TraceCheckUtils]: 44: Hoare quadruple {2847#true} {3044#(< ~counter~0 10)} #92#return; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,683 INFO L290 TraceCheckUtils]: 43: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,683 INFO L290 TraceCheckUtils]: 42: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,683 INFO L290 TraceCheckUtils]: 41: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,683 INFO L272 TraceCheckUtils]: 40: Hoare triple {3044#(< ~counter~0 10)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~p~0 - 4 * ~h~0 * ~n~0 * ~q~0 + 4 * ~n~0 * ~p~0 * ~q~0 - ~p~0 * ~q~0 * ~q~0 + 4 * ~h~0 * ~q~0 * ~r~0 - 4 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,684 INFO L284 TraceCheckUtils]: 39: Hoare quadruple {2847#true} {3044#(< ~counter~0 10)} #90#return; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,684 INFO L290 TraceCheckUtils]: 38: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,684 INFO L290 TraceCheckUtils]: 37: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,684 INFO L290 TraceCheckUtils]: 36: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,684 INFO L272 TraceCheckUtils]: 35: Hoare triple {3044#(< ~counter~0 10)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~n~0 - 4 * ~h~0 * ~n~0 * ~p~0 + 4 * (~n~0 * ~n~0) * ~q~0 - ~n~0 * ~q~0 * ~q~0 - ~h~0 * ~h~0 * ~r~0 + 4 * ~h~0 * ~p~0 * ~r~0 - 8 * ~n~0 * ~q~0 * ~r~0 + ~q~0 * ~q~0 * ~r~0 + 4 * ~q~0 * ~r~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,685 INFO L284 TraceCheckUtils]: 34: Hoare quadruple {2847#true} {3044#(< ~counter~0 10)} #88#return; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,685 INFO L290 TraceCheckUtils]: 33: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,685 INFO L290 TraceCheckUtils]: 32: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,685 INFO L290 TraceCheckUtils]: 31: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,685 INFO L272 TraceCheckUtils]: 30: Hoare triple {3044#(< ~counter~0 10)} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,686 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {2847#true} {3044#(< ~counter~0 10)} #86#return; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,686 INFO L290 TraceCheckUtils]: 28: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,686 INFO L290 TraceCheckUtils]: 27: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,686 INFO L290 TraceCheckUtils]: 26: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,686 INFO L272 TraceCheckUtils]: 25: Hoare triple {3044#(< ~counter~0 10)} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,687 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {2847#true} {3044#(< ~counter~0 10)} #84#return; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,687 INFO L290 TraceCheckUtils]: 23: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,687 INFO L290 TraceCheckUtils]: 22: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,687 INFO L290 TraceCheckUtils]: 21: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,687 INFO L272 TraceCheckUtils]: 20: Hoare triple {3044#(< ~counter~0 10)} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,687 INFO L290 TraceCheckUtils]: 19: Hoare triple {3044#(< ~counter~0 10)} assume !!(#t~post6 < 10);havoc #t~post6; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,688 INFO L290 TraceCheckUtils]: 18: Hoare triple {3147#(< ~counter~0 9)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {3044#(< ~counter~0 10)} is VALID [2022-04-08 11:28:11,688 INFO L290 TraceCheckUtils]: 17: Hoare triple {3147#(< ~counter~0 9)} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {3147#(< ~counter~0 9)} is VALID [2022-04-08 11:28:11,688 INFO L290 TraceCheckUtils]: 16: Hoare triple {3147#(< ~counter~0 9)} assume !!(#t~post5 < 10);havoc #t~post5; {3147#(< ~counter~0 9)} is VALID [2022-04-08 11:28:11,689 INFO L290 TraceCheckUtils]: 15: Hoare triple {3157#(< ~counter~0 8)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3147#(< ~counter~0 9)} is VALID [2022-04-08 11:28:11,689 INFO L290 TraceCheckUtils]: 14: Hoare triple {3157#(< ~counter~0 8)} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {3157#(< ~counter~0 8)} is VALID [2022-04-08 11:28:11,690 INFO L290 TraceCheckUtils]: 13: Hoare triple {3157#(< ~counter~0 8)} assume !!(#t~post5 < 10);havoc #t~post5; {3157#(< ~counter~0 8)} is VALID [2022-04-08 11:28:11,690 INFO L290 TraceCheckUtils]: 12: Hoare triple {3167#(< ~counter~0 7)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {3157#(< ~counter~0 8)} is VALID [2022-04-08 11:28:11,690 INFO L290 TraceCheckUtils]: 11: Hoare triple {3167#(< ~counter~0 7)} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,691 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2847#true} {3167#(< ~counter~0 7)} #82#return; {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,691 INFO L290 TraceCheckUtils]: 9: Hoare triple {2847#true} assume true; {2847#true} is VALID [2022-04-08 11:28:11,691 INFO L290 TraceCheckUtils]: 8: Hoare triple {2847#true} assume !(0 == ~cond); {2847#true} is VALID [2022-04-08 11:28:11,691 INFO L290 TraceCheckUtils]: 7: Hoare triple {2847#true} ~cond := #in~cond; {2847#true} is VALID [2022-04-08 11:28:11,691 INFO L272 TraceCheckUtils]: 6: Hoare triple {3167#(< ~counter~0 7)} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {2847#true} is VALID [2022-04-08 11:28:11,691 INFO L290 TraceCheckUtils]: 5: Hoare triple {3167#(< ~counter~0 7)} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,692 INFO L272 TraceCheckUtils]: 4: Hoare triple {3167#(< ~counter~0 7)} call #t~ret7 := main(); {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,692 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {3167#(< ~counter~0 7)} {2847#true} #102#return; {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,692 INFO L290 TraceCheckUtils]: 2: Hoare triple {3167#(< ~counter~0 7)} assume true; {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,693 INFO L290 TraceCheckUtils]: 1: Hoare triple {2847#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {3167#(< ~counter~0 7)} is VALID [2022-04-08 11:28:11,693 INFO L272 TraceCheckUtils]: 0: Hoare triple {2847#true} call ULTIMATE.init(); {2847#true} is VALID [2022-04-08 11:28:11,693 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-08 11:28:11,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 11:28:11,693 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1006648504] [2022-04-08 11:28:11,693 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 11:28:11,694 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [853680364] [2022-04-08 11:28:11,694 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [853680364] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 11:28:11,694 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 11:28:11,694 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-04-08 11:28:11,694 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 11:28:11,694 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1339792807] [2022-04-08 11:28:11,694 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1339792807] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 11:28:11,694 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 11:28:11,694 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-08 11:28:11,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [422592474] [2022-04-08 11:28:11,694 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 11:28:11,695 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 58 [2022-04-08 11:28:11,695 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 11:28:11,695 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:28:11,731 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 43 edges. 43 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:11,731 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-08 11:28:11,731 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:11,731 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-08 11:28:11,731 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2022-04-08 11:28:11,731 INFO L87 Difference]: Start difference. First operand 69 states and 92 transitions. Second operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:28:19,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:19,793 INFO L93 Difference]: Finished difference Result 114 states and 146 transitions. [2022-04-08 11:28:19,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-08 11:28:19,793 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 58 [2022-04-08 11:28:19,793 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 11:28:19,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:28:19,795 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-08 11:28:19,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:28:19,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-08 11:28:19,796 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 90 transitions. [2022-04-08 11:28:19,865 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 90 edges. 90 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:19,867 INFO L225 Difference]: With dead ends: 114 [2022-04-08 11:28:19,867 INFO L226 Difference]: Without dead ends: 104 [2022-04-08 11:28:19,868 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=97, Unknown=0, NotChecked=0, Total=156 [2022-04-08 11:28:19,868 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 21 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-04-08 11:28:19,868 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 157 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-04-08 11:28:19,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-04-08 11:28:19,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 98. [2022-04-08 11:28:19,944 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 11:28:19,945 INFO L82 GeneralOperation]: Start isEquivalent. First operand 104 states. Second operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:28:19,951 INFO L74 IsIncluded]: Start isIncluded. First operand 104 states. Second operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:28:19,954 INFO L87 Difference]: Start difference. First operand 104 states. Second operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:28:19,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:19,957 INFO L93 Difference]: Finished difference Result 104 states and 133 transitions. [2022-04-08 11:28:19,957 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 133 transitions. [2022-04-08 11:28:19,957 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:19,958 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:19,958 INFO L74 IsIncluded]: Start isIncluded. First operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand 104 states. [2022-04-08 11:28:19,958 INFO L87 Difference]: Start difference. First operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand 104 states. [2022-04-08 11:28:19,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 11:28:19,961 INFO L93 Difference]: Finished difference Result 104 states and 133 transitions. [2022-04-08 11:28:19,961 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 133 transitions. [2022-04-08 11:28:19,961 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 11:28:19,961 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 11:28:19,961 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 11:28:19,961 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 11:28:19,961 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 59 states have internal predecessors, (67), 31 states have call successors, (31), 10 states have call predecessors, (31), 9 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-08 11:28:19,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 126 transitions. [2022-04-08 11:28:19,964 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 126 transitions. Word has length 58 [2022-04-08 11:28:19,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 11:28:19,964 INFO L478 AbstractCegarLoop]: Abstraction has 98 states and 126 transitions. [2022-04-08 11:28:19,964 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 4 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-08 11:28:19,964 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 98 states and 126 transitions. [2022-04-08 11:28:20,432 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 126 edges. 126 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 11:28:20,432 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 126 transitions. [2022-04-08 11:28:20,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-08 11:28:20,434 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 11:28:20,435 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 11:28:20,439 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-04-08 11:28:20,639 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:20,639 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 11:28:20,639 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 11:28:20,639 INFO L85 PathProgramCache]: Analyzing trace with hash 109392637, now seen corresponding path program 1 times [2022-04-08 11:28:20,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 11:28:20,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [746970129] [2022-04-08 11:28:20,661 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 11:28:20,661 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 11:28:20,661 INFO L85 PathProgramCache]: Analyzing trace with hash 109392637, now seen corresponding path program 2 times [2022-04-08 11:28:20,661 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 11:28:20,661 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1268430523] [2022-04-08 11:28:20,661 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 11:28:20,661 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 11:28:20,675 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 11:28:20,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2067130718] [2022-04-08 11:28:20,675 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 11:28:20,676 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 11:28:20,676 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 11:28:20,676 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 11:28:20,678 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process