/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/sqrt1-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 17:35:26,036 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 17:35:26,037 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 17:35:26,074 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 17:35:26,074 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 17:35:26,076 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 17:35:26,077 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 17:35:26,079 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 17:35:26,081 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 17:35:26,084 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 17:35:26,085 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 17:35:26,086 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 17:35:26,086 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 17:35:26,088 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 17:35:26,088 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 17:35:26,090 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 17:35:26,091 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 17:35:26,091 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 17:35:26,093 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 17:35:26,097 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 17:35:26,098 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 17:35:26,100 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 17:35:26,100 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 17:35:26,101 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 17:35:26,102 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 17:35:26,106 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 17:35:26,106 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 17:35:26,107 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 17:35:26,107 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 17:35:26,107 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 17:35:26,108 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 17:35:26,109 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 17:35:26,110 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 17:35:26,110 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 17:35:26,111 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 17:35:26,111 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 17:35:26,111 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 17:35:26,112 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 17:35:26,112 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 17:35:26,112 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 17:35:26,112 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 17:35:26,114 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 17:35:26,114 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-15 17:35:26,122 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 17:35:26,122 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 17:35:26,123 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 17:35:26,123 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 17:35:26,124 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 17:35:26,124 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 17:35:26,124 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 17:35:26,124 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 17:35:26,124 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 17:35:26,124 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 17:35:26,125 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 17:35:26,125 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 17:35:26,125 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-15 17:35:26,126 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-15 17:35:26,325 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 17:35:26,342 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 17:35:26,345 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 17:35:26,345 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 17:35:26,346 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 17:35:26,346 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/sqrt1-ll_valuebound20.c [2022-04-15 17:35:26,391 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/898a9c325/949c7adb55c9475e8ad5b8768a040b9f/FLAGb629bc52c [2022-04-15 17:35:26,713 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 17:35:26,714 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/sqrt1-ll_valuebound20.c [2022-04-15 17:35:26,719 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/898a9c325/949c7adb55c9475e8ad5b8768a040b9f/FLAGb629bc52c [2022-04-15 17:35:27,128 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/898a9c325/949c7adb55c9475e8ad5b8768a040b9f [2022-04-15 17:35:27,130 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 17:35:27,131 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 17:35:27,133 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 17:35:27,133 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 17:35:27,136 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 17:35:27,137 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,138 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@9b13866 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27, skipping insertion in model container [2022-04-15 17:35:27,138 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,142 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 17:35:27,152 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 17:35:27,271 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/sqrt1-ll_valuebound20.c[520,533] [2022-04-15 17:35:27,293 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 17:35:27,299 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 17:35:27,316 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/sqrt1-ll_valuebound20.c[520,533] [2022-04-15 17:35:27,326 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 17:35:27,335 INFO L208 MainTranslator]: Completed translation [2022-04-15 17:35:27,336 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27 WrapperNode [2022-04-15 17:35:27,336 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 17:35:27,337 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 17:35:27,337 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 17:35:27,338 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 17:35:27,346 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,346 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,351 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,351 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,363 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,366 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,366 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,369 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 17:35:27,369 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 17:35:27,369 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 17:35:27,369 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 17:35:27,370 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (1/1) ... [2022-04-15 17:35:27,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 17:35:27,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 17:35:27,413 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-15 17:35:27,416 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-15 17:35:27,447 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 17:35:27,447 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 17:35:27,447 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 17:35:27,447 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 17:35:27,447 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 17:35:27,447 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 17:35:27,447 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 17:35:27,447 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 17:35:27,447 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 17:35:27,448 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 17:35:27,490 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 17:35:27,491 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 17:35:27,630 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 17:35:27,634 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 17:35:27,635 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-15 17:35:27,636 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 05:35:27 BoogieIcfgContainer [2022-04-15 17:35:27,636 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 17:35:27,637 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 17:35:27,637 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 17:35:27,653 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 17:35:27,654 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 05:35:27" (1/3) ... [2022-04-15 17:35:27,654 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31d04355 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 05:35:27, skipping insertion in model container [2022-04-15 17:35:27,654 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 05:35:27" (2/3) ... [2022-04-15 17:35:27,654 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31d04355 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 05:35:27, skipping insertion in model container [2022-04-15 17:35:27,654 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 05:35:27" (3/3) ... [2022-04-15 17:35:27,655 INFO L111 eAbstractionObserver]: Analyzing ICFG sqrt1-ll_valuebound20.c [2022-04-15 17:35:27,658 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 17:35:27,659 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 17:35:27,719 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 17:35:27,723 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-15 17:35:27,723 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 17:35:27,756 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-15 17:35:27,761 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-15 17:35:27,761 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 17:35:27,761 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 17:35:27,762 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 17:35:27,768 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 17:35:27,769 INFO L85 PathProgramCache]: Analyzing trace with hash 326851384, now seen corresponding path program 1 times [2022-04-15 17:35:27,774 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:27,774 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1077998593] [2022-04-15 17:35:27,781 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 17:35:27,781 INFO L85 PathProgramCache]: Analyzing trace with hash 326851384, now seen corresponding path program 2 times [2022-04-15 17:35:27,784 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 17:35:27,785 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [460633031] [2022-04-15 17:35:27,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 17:35:27,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 17:35:27,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:27,923 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 17:35:27,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:27,941 INFO L290 TraceCheckUtils]: 0: Hoare triple {43#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); {34#true} is VALID [2022-04-15 17:35:27,941 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 17:35:27,941 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #69#return; {34#true} is VALID [2022-04-15 17:35:27,942 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 17:35:27,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:27,951 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 17:35:27,951 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 17:35:27,952 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 17:35:27,952 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {34#true} #55#return; {35#false} is VALID [2022-04-15 17:35:27,954 INFO L272 TraceCheckUtils]: 0: Hoare triple {34#true} call ULTIMATE.init(); {43#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 17:35:27,955 INFO L290 TraceCheckUtils]: 1: Hoare triple {43#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); {34#true} is VALID [2022-04-15 17:35:27,955 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 17:35:27,955 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #69#return; {34#true} is VALID [2022-04-15 17:35:27,955 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret5 := main(); {34#true} is VALID [2022-04-15 17:35:27,956 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4; {34#true} is VALID [2022-04-15 17:35:27,956 INFO L272 TraceCheckUtils]: 6: Hoare triple {34#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 <= 20 then 1 else 0)); {34#true} is VALID [2022-04-15 17:35:27,956 INFO L290 TraceCheckUtils]: 7: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 17:35:27,956 INFO L290 TraceCheckUtils]: 8: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 17:35:27,957 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 17:35:27,957 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {35#false} {34#true} #55#return; {35#false} is VALID [2022-04-15 17:35:27,958 INFO L290 TraceCheckUtils]: 11: Hoare triple {35#false} ~a~0 := 0;~s~0 := 1;~t~0 := 1; {35#false} is VALID [2022-04-15 17:35:27,958 INFO L290 TraceCheckUtils]: 12: Hoare triple {35#false} assume false; {35#false} is VALID [2022-04-15 17:35:27,958 INFO L272 TraceCheckUtils]: 13: Hoare triple {35#false} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {35#false} is VALID [2022-04-15 17:35:27,958 INFO L290 TraceCheckUtils]: 14: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-15 17:35:27,959 INFO L290 TraceCheckUtils]: 15: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-15 17:35:27,960 INFO L290 TraceCheckUtils]: 16: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-15 17:35:27,960 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 17:35:27,961 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 17:35:27,961 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [460633031] [2022-04-15 17:35:27,962 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [460633031] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:27,962 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:27,962 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 17:35:27,966 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 17:35:27,966 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1077998593] [2022-04-15 17:35:27,966 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1077998593] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:27,967 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:27,967 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 17:35:27,967 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2110799669] [2022-04-15 17:35:27,968 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 17:35:27,971 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 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 17 [2022-04-15 17:35:27,972 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 17:35:27,974 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,001 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:28,001 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 17:35:28,001 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:28,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 17:35:28,021 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 17:35:28,023 INFO L87 Difference]: Start difference. First operand has 31 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:28,163 INFO L93 Difference]: Finished difference Result 53 states and 76 transitions. [2022-04-15 17:35:28,169 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 17:35:28,169 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 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 17 [2022-04-15 17:35:28,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 17:35:28,171 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 76 transitions. [2022-04-15 17:35:28,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 76 transitions. [2022-04-15 17:35:28,183 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 76 transitions. [2022-04-15 17:35:28,252 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 76 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:28,258 INFO L225 Difference]: With dead ends: 53 [2022-04-15 17:35:28,258 INFO L226 Difference]: Without dead ends: 26 [2022-04-15 17:35:28,260 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 17:35:28,262 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 15 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 17:35:28,263 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 32 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 17:35:28,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-15 17:35:28,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-15 17:35:28,284 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 17:35:28,284 INFO L82 GeneralOperation]: Start isEquivalent. First operand 26 states. Second operand has 26 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 17:35:28,285 INFO L74 IsIncluded]: Start isIncluded. First operand 26 states. Second operand has 26 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 17:35:28,285 INFO L87 Difference]: Start difference. First operand 26 states. Second operand has 26 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 17:35:28,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:28,288 INFO L93 Difference]: Finished difference Result 26 states and 31 transitions. [2022-04-15 17:35:28,288 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2022-04-15 17:35:28,289 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:28,289 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:28,290 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 26 states. [2022-04-15 17:35:28,291 INFO L87 Difference]: Start difference. First operand has 26 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 26 states. [2022-04-15 17:35:28,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:28,298 INFO L93 Difference]: Finished difference Result 26 states and 31 transitions. [2022-04-15 17:35:28,298 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2022-04-15 17:35:28,299 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:28,300 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:28,301 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 17:35:28,301 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 17:35:28,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 17:35:28,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 31 transitions. [2022-04-15 17:35:28,306 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 31 transitions. Word has length 17 [2022-04-15 17:35:28,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 17:35:28,306 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 31 transitions. [2022-04-15 17:35:28,307 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,307 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 31 transitions. [2022-04-15 17:35:28,339 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 31 edges. 31 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:28,340 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2022-04-15 17:35:28,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-15 17:35:28,340 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 17:35:28,341 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 17:35:28,341 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 17:35:28,341 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 17:35:28,342 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 17:35:28,342 INFO L85 PathProgramCache]: Analyzing trace with hash 1008578050, now seen corresponding path program 1 times [2022-04-15 17:35:28,342 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:28,342 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [653664493] [2022-04-15 17:35:28,349 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 17:35:28,349 INFO L85 PathProgramCache]: Analyzing trace with hash 1008578050, now seen corresponding path program 2 times [2022-04-15 17:35:28,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 17:35:28,350 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [594031192] [2022-04-15 17:35:28,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 17:35:28,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 17:35:28,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:28,470 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 17:35:28,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:28,490 INFO L290 TraceCheckUtils]: 0: Hoare triple {268#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); {256#true} is VALID [2022-04-15 17:35:28,491 INFO L290 TraceCheckUtils]: 1: Hoare triple {256#true} assume true; {256#true} is VALID [2022-04-15 17:35:28,491 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {256#true} {256#true} #69#return; {256#true} is VALID [2022-04-15 17:35:28,491 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 17:35:28,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:28,498 INFO L290 TraceCheckUtils]: 0: Hoare triple {256#true} ~cond := #in~cond; {256#true} is VALID [2022-04-15 17:35:28,499 INFO L290 TraceCheckUtils]: 1: Hoare triple {256#true} assume !(0 == ~cond); {256#true} is VALID [2022-04-15 17:35:28,499 INFO L290 TraceCheckUtils]: 2: Hoare triple {256#true} assume true; {256#true} is VALID [2022-04-15 17:35:28,499 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {256#true} {256#true} #55#return; {256#true} is VALID [2022-04-15 17:35:28,500 INFO L272 TraceCheckUtils]: 0: Hoare triple {256#true} call ULTIMATE.init(); {268#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 17:35:28,500 INFO L290 TraceCheckUtils]: 1: Hoare triple {268#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); {256#true} is VALID [2022-04-15 17:35:28,500 INFO L290 TraceCheckUtils]: 2: Hoare triple {256#true} assume true; {256#true} is VALID [2022-04-15 17:35:28,500 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {256#true} {256#true} #69#return; {256#true} is VALID [2022-04-15 17:35:28,501 INFO L272 TraceCheckUtils]: 4: Hoare triple {256#true} call #t~ret5 := main(); {256#true} is VALID [2022-04-15 17:35:28,501 INFO L290 TraceCheckUtils]: 5: Hoare triple {256#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4; {256#true} is VALID [2022-04-15 17:35:28,501 INFO L272 TraceCheckUtils]: 6: Hoare triple {256#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 <= 20 then 1 else 0)); {256#true} is VALID [2022-04-15 17:35:28,501 INFO L290 TraceCheckUtils]: 7: Hoare triple {256#true} ~cond := #in~cond; {256#true} is VALID [2022-04-15 17:35:28,501 INFO L290 TraceCheckUtils]: 8: Hoare triple {256#true} assume !(0 == ~cond); {256#true} is VALID [2022-04-15 17:35:28,501 INFO L290 TraceCheckUtils]: 9: Hoare triple {256#true} assume true; {256#true} is VALID [2022-04-15 17:35:28,501 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {256#true} {256#true} #55#return; {256#true} is VALID [2022-04-15 17:35:28,502 INFO L290 TraceCheckUtils]: 11: Hoare triple {256#true} ~a~0 := 0;~s~0 := 1;~t~0 := 1; {265#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} is VALID [2022-04-15 17:35:28,503 INFO L290 TraceCheckUtils]: 12: Hoare triple {265#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} assume !false; {265#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} is VALID [2022-04-15 17:35:28,504 INFO L272 TraceCheckUtils]: 13: Hoare triple {265#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {266#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 17:35:28,505 INFO L290 TraceCheckUtils]: 14: Hoare triple {266#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {267#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 17:35:28,505 INFO L290 TraceCheckUtils]: 15: Hoare triple {267#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {257#false} is VALID [2022-04-15 17:35:28,506 INFO L290 TraceCheckUtils]: 16: Hoare triple {257#false} assume !false; {257#false} is VALID [2022-04-15 17:35:28,506 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 17:35:28,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 17:35:28,509 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [594031192] [2022-04-15 17:35:28,509 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [594031192] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:28,509 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:28,509 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 17:35:28,510 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 17:35:28,510 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [653664493] [2022-04-15 17:35:28,511 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [653664493] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:28,511 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:28,511 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 17:35:28,512 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1336354578] [2022-04-15 17:35:28,512 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 17:35:28,513 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-15 17:35:28,514 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 17:35:28,514 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,526 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:28,526 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 17:35:28,527 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:28,527 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 17:35:28,528 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 17:35:28,528 INFO L87 Difference]: Start difference. First operand 26 states and 31 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:28,872 INFO L93 Difference]: Finished difference Result 40 states and 50 transitions. [2022-04-15 17:35:28,872 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-15 17:35:28,872 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-15 17:35:28,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 17:35:28,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 50 transitions. [2022-04-15 17:35:28,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 50 transitions. [2022-04-15 17:35:28,877 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 7 states and 50 transitions. [2022-04-15 17:35:28,923 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:28,925 INFO L225 Difference]: With dead ends: 40 [2022-04-15 17:35:28,925 INFO L226 Difference]: Without dead ends: 38 [2022-04-15 17:35:28,926 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-15 17:35:28,926 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 25 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 17:35:28,927 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 39 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 17:35:28,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-04-15 17:35:28,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 36. [2022-04-15 17:35:28,933 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 17:35:28,934 INFO L82 GeneralOperation]: Start isEquivalent. First operand 38 states. Second operand has 36 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 17:35:28,934 INFO L74 IsIncluded]: Start isIncluded. First operand 38 states. Second operand has 36 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 17:35:28,934 INFO L87 Difference]: Start difference. First operand 38 states. Second operand has 36 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 17:35:28,936 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:28,936 INFO L93 Difference]: Finished difference Result 38 states and 48 transitions. [2022-04-15 17:35:28,937 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 48 transitions. [2022-04-15 17:35:28,937 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:28,937 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:28,938 INFO L74 IsIncluded]: Start isIncluded. First operand has 36 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Second operand 38 states. [2022-04-15 17:35:28,938 INFO L87 Difference]: Start difference. First operand has 36 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Second operand 38 states. [2022-04-15 17:35:28,940 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:28,940 INFO L93 Difference]: Finished difference Result 38 states and 48 transitions. [2022-04-15 17:35:28,940 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 48 transitions. [2022-04-15 17:35:28,941 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:28,941 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:28,941 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 17:35:28,941 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 17:35:28,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 17:35:28,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 45 transitions. [2022-04-15 17:35:28,943 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 45 transitions. Word has length 17 [2022-04-15 17:35:28,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 17:35:28,943 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 45 transitions. [2022-04-15 17:35:28,943 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 17:35:28,944 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 36 states and 45 transitions. [2022-04-15 17:35:28,986 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 45 edges. 45 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:28,986 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-04-15 17:35:28,987 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-15 17:35:28,987 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 17:35:28,987 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] [2022-04-15 17:35:28,987 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 17:35:28,987 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 17:35:28,988 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 17:35:28,988 INFO L85 PathProgramCache]: Analyzing trace with hash -789682422, now seen corresponding path program 1 times [2022-04-15 17:35:28,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:28,988 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2127728330] [2022-04-15 17:35:28,988 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 17:35:28,989 INFO L85 PathProgramCache]: Analyzing trace with hash -789682422, now seen corresponding path program 2 times [2022-04-15 17:35:28,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 17:35:28,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1784895703] [2022-04-15 17:35:28,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 17:35:28,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 17:35:29,024 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 17:35:29,025 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [162999802] [2022-04-15 17:35:29,025 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 17:35:29,025 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 17:35:29,025 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 17:35:29,040 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 17:35:29,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-15 17:35:29,093 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 17:35:29,094 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 17:35:29,095 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 17:35:29,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:29,104 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 17:35:29,207 INFO L272 TraceCheckUtils]: 0: Hoare triple {507#true} call ULTIMATE.init(); {507#true} is VALID [2022-04-15 17:35:29,208 INFO L290 TraceCheckUtils]: 1: Hoare triple {507#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(11, 2);call #Ultimate.allocInit(12, 3); {507#true} is VALID [2022-04-15 17:35:29,208 INFO L290 TraceCheckUtils]: 2: Hoare triple {507#true} assume true; {507#true} is VALID [2022-04-15 17:35:29,208 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {507#true} {507#true} #69#return; {507#true} is VALID [2022-04-15 17:35:29,208 INFO L272 TraceCheckUtils]: 4: Hoare triple {507#true} call #t~ret5 := main(); {507#true} is VALID [2022-04-15 17:35:29,208 INFO L290 TraceCheckUtils]: 5: Hoare triple {507#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4; {507#true} is VALID [2022-04-15 17:35:29,209 INFO L272 TraceCheckUtils]: 6: Hoare triple {507#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 <= 20 then 1 else 0)); {507#true} is VALID [2022-04-15 17:35:29,209 INFO L290 TraceCheckUtils]: 7: Hoare triple {507#true} ~cond := #in~cond; {507#true} is VALID [2022-04-15 17:35:29,209 INFO L290 TraceCheckUtils]: 8: Hoare triple {507#true} assume !(0 == ~cond); {507#true} is VALID [2022-04-15 17:35:29,209 INFO L290 TraceCheckUtils]: 9: Hoare triple {507#true} assume true; {507#true} is VALID [2022-04-15 17:35:29,209 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {507#true} {507#true} #55#return; {507#true} is VALID [2022-04-15 17:35:29,212 INFO L290 TraceCheckUtils]: 11: Hoare triple {507#true} ~a~0 := 0;~s~0 := 1;~t~0 := 1; {545#(and (= main_~a~0 0) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,212 INFO L290 TraceCheckUtils]: 12: Hoare triple {545#(and (= main_~a~0 0) (= main_~s~0 1))} assume !false; {545#(and (= main_~a~0 0) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,213 INFO L272 TraceCheckUtils]: 13: Hoare triple {545#(and (= main_~a~0 0) (= main_~s~0 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {507#true} is VALID [2022-04-15 17:35:29,213 INFO L290 TraceCheckUtils]: 14: Hoare triple {507#true} ~cond := #in~cond; {507#true} is VALID [2022-04-15 17:35:29,213 INFO L290 TraceCheckUtils]: 15: Hoare triple {507#true} assume !(0 == ~cond); {507#true} is VALID [2022-04-15 17:35:29,213 INFO L290 TraceCheckUtils]: 16: Hoare triple {507#true} assume true; {507#true} is VALID [2022-04-15 17:35:29,214 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {507#true} {545#(and (= main_~a~0 0) (= main_~s~0 1))} #57#return; {545#(and (= main_~a~0 0) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,214 INFO L272 TraceCheckUtils]: 18: Hoare triple {545#(and (= main_~a~0 0) (= main_~s~0 1))} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {567#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 17:35:29,215 INFO L290 TraceCheckUtils]: 19: Hoare triple {567#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {571#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 17:35:29,215 INFO L290 TraceCheckUtils]: 20: Hoare triple {571#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {508#false} is VALID [2022-04-15 17:35:29,215 INFO L290 TraceCheckUtils]: 21: Hoare triple {508#false} assume !false; {508#false} is VALID [2022-04-15 17:35:29,215 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 17:35:29,216 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 17:35:29,216 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 17:35:29,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1784895703] [2022-04-15 17:35:29,216 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 17:35:29,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [162999802] [2022-04-15 17:35:29,216 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [162999802] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:29,216 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:29,216 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 17:35:29,217 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 17:35:29,217 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2127728330] [2022-04-15 17:35:29,217 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2127728330] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:29,217 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:29,217 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 17:35:29,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2084933977] [2022-04-15 17:35:29,217 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 17:35:29,218 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-15 17:35:29,218 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 17:35:29,218 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 17:35:29,237 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:29,237 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 17:35:29,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:29,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 17:35:29,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 17:35:29,238 INFO L87 Difference]: Start difference. First operand 36 states and 45 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 17:35:29,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:29,389 INFO L93 Difference]: Finished difference Result 44 states and 53 transitions. [2022-04-15 17:35:29,389 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 17:35:29,389 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-15 17:35:29,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 17:35:29,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 17:35:29,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 50 transitions. [2022-04-15 17:35:29,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 17:35:29,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 50 transitions. [2022-04-15 17:35:29,393 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 50 transitions. [2022-04-15 17:35:29,430 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:29,432 INFO L225 Difference]: With dead ends: 44 [2022-04-15 17:35:29,432 INFO L226 Difference]: Without dead ends: 42 [2022-04-15 17:35:29,432 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 17:35:29,433 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 17:35:29,433 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 103 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 17:35:29,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-04-15 17:35:29,443 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2022-04-15 17:35:29,443 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 17:35:29,444 INFO L82 GeneralOperation]: Start isEquivalent. First operand 42 states. Second operand has 41 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 17:35:29,444 INFO L74 IsIncluded]: Start isIncluded. First operand 42 states. Second operand has 41 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 17:35:29,444 INFO L87 Difference]: Start difference. First operand 42 states. Second operand has 41 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 17:35:29,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:29,446 INFO L93 Difference]: Finished difference Result 42 states and 51 transitions. [2022-04-15 17:35:29,447 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 51 transitions. [2022-04-15 17:35:29,447 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:29,447 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:29,448 INFO L74 IsIncluded]: Start isIncluded. First operand has 41 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) Second operand 42 states. [2022-04-15 17:35:29,448 INFO L87 Difference]: Start difference. First operand has 41 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) Second operand 42 states. [2022-04-15 17:35:29,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:29,450 INFO L93 Difference]: Finished difference Result 42 states and 51 transitions. [2022-04-15 17:35:29,450 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 51 transitions. [2022-04-15 17:35:29,451 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:29,451 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:29,451 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 17:35:29,451 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 17:35:29,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 17:35:29,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2022-04-15 17:35:29,453 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 22 [2022-04-15 17:35:29,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 17:35:29,453 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2022-04-15 17:35:29,453 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 17:35:29,453 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 41 states and 50 transitions. [2022-04-15 17:35:29,501 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:29,501 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2022-04-15 17:35:29,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-15 17:35:29,502 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 17:35:29,502 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 17:35:29,519 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-15 17:35:29,712 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 17:35:29,713 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 17:35:29,713 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 17:35:29,713 INFO L85 PathProgramCache]: Analyzing trace with hash 2087529154, now seen corresponding path program 1 times [2022-04-15 17:35:29,713 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:29,727 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2042601149] [2022-04-15 17:35:29,728 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 17:35:29,728 INFO L85 PathProgramCache]: Analyzing trace with hash 2087529154, now seen corresponding path program 2 times [2022-04-15 17:35:29,728 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 17:35:29,728 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1559337737] [2022-04-15 17:35:29,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 17:35:29,728 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 17:35:29,741 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 17:35:29,741 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1442104187] [2022-04-15 17:35:29,742 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 17:35:29,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 17:35:29,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 17:35:29,760 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 17:35:29,803 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-15 17:35:29,834 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 17:35:29,834 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 17:35:29,835 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 17:35:29,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:29,843 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 17:35:29,929 INFO L272 TraceCheckUtils]: 0: Hoare triple {833#true} call ULTIMATE.init(); {833#true} is VALID [2022-04-15 17:35:29,929 INFO L290 TraceCheckUtils]: 1: Hoare triple {833#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(11, 2);call #Ultimate.allocInit(12, 3); {833#true} is VALID [2022-04-15 17:35:29,929 INFO L290 TraceCheckUtils]: 2: Hoare triple {833#true} assume true; {833#true} is VALID [2022-04-15 17:35:29,929 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {833#true} {833#true} #69#return; {833#true} is VALID [2022-04-15 17:35:29,929 INFO L272 TraceCheckUtils]: 4: Hoare triple {833#true} call #t~ret5 := main(); {833#true} is VALID [2022-04-15 17:35:29,930 INFO L290 TraceCheckUtils]: 5: Hoare triple {833#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4; {833#true} is VALID [2022-04-15 17:35:29,930 INFO L272 TraceCheckUtils]: 6: Hoare triple {833#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 <= 20 then 1 else 0)); {833#true} is VALID [2022-04-15 17:35:29,930 INFO L290 TraceCheckUtils]: 7: Hoare triple {833#true} ~cond := #in~cond; {833#true} is VALID [2022-04-15 17:35:29,930 INFO L290 TraceCheckUtils]: 8: Hoare triple {833#true} assume !(0 == ~cond); {833#true} is VALID [2022-04-15 17:35:29,930 INFO L290 TraceCheckUtils]: 9: Hoare triple {833#true} assume true; {833#true} is VALID [2022-04-15 17:35:29,930 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {833#true} {833#true} #55#return; {833#true} is VALID [2022-04-15 17:35:29,931 INFO L290 TraceCheckUtils]: 11: Hoare triple {833#true} ~a~0 := 0;~s~0 := 1;~t~0 := 1; {871#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,931 INFO L290 TraceCheckUtils]: 12: Hoare triple {871#(and (= main_~t~0 1) (= main_~s~0 1))} assume !false; {871#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,931 INFO L272 TraceCheckUtils]: 13: Hoare triple {871#(and (= main_~t~0 1) (= main_~s~0 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {833#true} is VALID [2022-04-15 17:35:29,931 INFO L290 TraceCheckUtils]: 14: Hoare triple {833#true} ~cond := #in~cond; {833#true} is VALID [2022-04-15 17:35:29,931 INFO L290 TraceCheckUtils]: 15: Hoare triple {833#true} assume !(0 == ~cond); {833#true} is VALID [2022-04-15 17:35:29,931 INFO L290 TraceCheckUtils]: 16: Hoare triple {833#true} assume true; {833#true} is VALID [2022-04-15 17:35:29,932 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {833#true} {871#(and (= main_~t~0 1) (= main_~s~0 1))} #57#return; {871#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,932 INFO L272 TraceCheckUtils]: 18: Hoare triple {871#(and (= main_~t~0 1) (= main_~s~0 1))} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {833#true} is VALID [2022-04-15 17:35:29,932 INFO L290 TraceCheckUtils]: 19: Hoare triple {833#true} ~cond := #in~cond; {833#true} is VALID [2022-04-15 17:35:29,932 INFO L290 TraceCheckUtils]: 20: Hoare triple {833#true} assume !(0 == ~cond); {833#true} is VALID [2022-04-15 17:35:29,932 INFO L290 TraceCheckUtils]: 21: Hoare triple {833#true} assume true; {833#true} is VALID [2022-04-15 17:35:29,933 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {833#true} {871#(and (= main_~t~0 1) (= main_~s~0 1))} #59#return; {871#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-15 17:35:29,934 INFO L272 TraceCheckUtils]: 23: Hoare triple {871#(and (= main_~t~0 1) (= main_~s~0 1))} call __VERIFIER_assert((if 0 == 1 + (~t~0 * ~t~0 - 4 * ~s~0 + 2 * ~t~0) then 1 else 0)); {908#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 17:35:29,934 INFO L290 TraceCheckUtils]: 24: Hoare triple {908#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {912#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 17:35:29,934 INFO L290 TraceCheckUtils]: 25: Hoare triple {912#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {834#false} is VALID [2022-04-15 17:35:29,934 INFO L290 TraceCheckUtils]: 26: Hoare triple {834#false} assume !false; {834#false} is VALID [2022-04-15 17:35:29,935 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-15 17:35:29,935 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 17:35:29,935 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 17:35:29,935 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1559337737] [2022-04-15 17:35:29,935 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 17:35:29,935 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1442104187] [2022-04-15 17:35:29,935 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1442104187] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:29,935 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:29,935 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 17:35:29,935 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 17:35:29,935 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2042601149] [2022-04-15 17:35:29,936 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2042601149] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:29,936 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:29,936 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 17:35:29,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [104064755] [2022-04-15 17:35:29,936 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 17:35:29,936 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-04-15 17:35:29,936 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 17:35:29,936 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 17:35:29,951 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 24 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:29,952 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 17:35:29,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:29,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 17:35:29,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 17:35:29,952 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 17:35:30,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:30,064 INFO L93 Difference]: Finished difference Result 48 states and 56 transitions. [2022-04-15 17:35:30,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 17:35:30,065 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-04-15 17:35:30,065 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 17:35:30,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 17:35:30,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 50 transitions. [2022-04-15 17:35:30,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 17:35:30,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 50 transitions. [2022-04-15 17:35:30,067 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 50 transitions. [2022-04-15 17:35:30,100 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 17:35:30,102 INFO L225 Difference]: With dead ends: 48 [2022-04-15 17:35:30,102 INFO L226 Difference]: Without dead ends: 43 [2022-04-15 17:35:30,102 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 17:35:30,103 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 17:35:30,103 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 106 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 17:35:30,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-04-15 17:35:30,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2022-04-15 17:35:30,114 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 17:35:30,114 INFO L82 GeneralOperation]: Start isEquivalent. First operand 43 states. Second operand has 43 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 12 states have call successors, (12), 7 states have call predecessors, (12), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 17:35:30,115 INFO L74 IsIncluded]: Start isIncluded. First operand 43 states. Second operand has 43 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 12 states have call successors, (12), 7 states have call predecessors, (12), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 17:35:30,115 INFO L87 Difference]: Start difference. First operand 43 states. Second operand has 43 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 12 states have call successors, (12), 7 states have call predecessors, (12), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 17:35:30,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:30,119 INFO L93 Difference]: Finished difference Result 43 states and 48 transitions. [2022-04-15 17:35:30,119 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2022-04-15 17:35:30,119 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:30,119 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:30,120 INFO L74 IsIncluded]: Start isIncluded. First operand has 43 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 12 states have call successors, (12), 7 states have call predecessors, (12), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 43 states. [2022-04-15 17:35:30,120 INFO L87 Difference]: Start difference. First operand has 43 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 12 states have call successors, (12), 7 states have call predecessors, (12), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 43 states. [2022-04-15 17:35:30,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 17:35:30,121 INFO L93 Difference]: Finished difference Result 43 states and 48 transitions. [2022-04-15 17:35:30,121 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2022-04-15 17:35:30,122 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 17:35:30,122 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 17:35:30,122 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 17:35:30,122 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 17:35:30,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 12 states have call successors, (12), 7 states have call predecessors, (12), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 17:35:30,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 48 transitions. [2022-04-15 17:35:30,123 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 48 transitions. Word has length 27 [2022-04-15 17:35:30,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 17:35:30,124 INFO L478 AbstractCegarLoop]: Abstraction has 43 states and 48 transitions. [2022-04-15 17:35:30,124 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 17:35:30,124 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 43 states and 48 transitions. [2022-04-15 17:35:30,163 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-15 17:35:30,163 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2022-04-15 17:35:30,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-15 17:35:30,163 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 17:35:30,164 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 17:35:30,199 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-15 17:35:30,400 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,SelfDestructingSolverStorable3 [2022-04-15 17:35:30,401 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 17:35:30,401 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 17:35:30,401 INFO L85 PathProgramCache]: Analyzing trace with hash -2092280728, now seen corresponding path program 1 times [2022-04-15 17:35:30,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 17:35:30,401 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [695611397] [2022-04-15 17:35:30,998 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-15 17:35:30,999 INFO L85 PathProgramCache]: Analyzing trace with hash -1589942244, now seen corresponding path program 1 times [2022-04-15 17:35:31,000 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 17:35:31,000 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1938604338] [2022-04-15 17:35:31,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 17:35:31,000 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 17:35:31,011 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 17:35:31,012 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [509651732] [2022-04-15 17:35:31,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 17:35:31,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 17:35:31,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 17:35:31,028 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 17:35:31,029 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-15 17:35:31,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:31,054 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 8 conjunts are in the unsatisfiable core [2022-04-15 17:35:31,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 17:35:31,061 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 17:35:31,175 INFO L272 TraceCheckUtils]: 0: Hoare triple {1188#true} call ULTIMATE.init(); {1188#true} is VALID [2022-04-15 17:35:31,175 INFO L290 TraceCheckUtils]: 1: Hoare triple {1188#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(11, 2);call #Ultimate.allocInit(12, 3); {1188#true} is VALID [2022-04-15 17:35:31,175 INFO L290 TraceCheckUtils]: 2: Hoare triple {1188#true} assume true; {1188#true} is VALID [2022-04-15 17:35:31,175 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1188#true} {1188#true} #69#return; {1188#true} is VALID [2022-04-15 17:35:31,175 INFO L272 TraceCheckUtils]: 4: Hoare triple {1188#true} call #t~ret5 := main(); {1188#true} is VALID [2022-04-15 17:35:31,176 INFO L290 TraceCheckUtils]: 5: Hoare triple {1188#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4; {1188#true} is VALID [2022-04-15 17:35:31,176 INFO L272 TraceCheckUtils]: 6: Hoare triple {1188#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 <= 20 then 1 else 0)); {1188#true} is VALID [2022-04-15 17:35:31,176 INFO L290 TraceCheckUtils]: 7: Hoare triple {1188#true} ~cond := #in~cond; {1188#true} is VALID [2022-04-15 17:35:31,176 INFO L290 TraceCheckUtils]: 8: Hoare triple {1188#true} assume !(0 == ~cond); {1188#true} is VALID [2022-04-15 17:35:31,176 INFO L290 TraceCheckUtils]: 9: Hoare triple {1188#true} assume true; {1188#true} is VALID [2022-04-15 17:35:31,176 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1188#true} {1188#true} #55#return; {1188#true} is VALID [2022-04-15 17:35:31,177 INFO L290 TraceCheckUtils]: 11: Hoare triple {1188#true} ~a~0 := 0;~s~0 := 1;~t~0 := 1; {1226#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-15 17:35:31,178 INFO L290 TraceCheckUtils]: 12: Hoare triple {1226#(and (= main_~a~0 0) (= main_~t~0 1))} [73] L30-2-->L31_primed: Formula: (or (let ((.cse0 (* 2 v_main_~a~0_Out_2)) (.cse3 (* (- 1) v_main_~t~0_In_1)) (.cse1 (* v_main_~a~0_Out_2 v_main_~a~0_Out_2))) (and (= (mod (+ v_main_~t~0_In_1 v_main_~t~0_Out_2) 2) 0) (= (+ .cse0 1) v_main_~t~0_Out_2) (<= .cse1 v_main_~n~0_In_1) (= .cse0 0) (= (+ (- 1) (let ((.cse2 (+ (- 1) .cse0))) (* .cse2 .cse2)) (* .cse1 (- 4)) (* v_main_~a~0_Out_2 4)) 0) (= .cse0 (* 2 v_main_~a~0_In_1)) (= (+ (* (- 1) v_main_~t~0_Out_2) (* v_main_~s~0_Out_2 2)) (+ (* v_main_~s~0_In_1 2) .cse3)) (<= 0 (div (+ v_main_~t~0_Out_2 .cse3) 2)) (= v_main_~s~0_Out_2 (+ .cse1 v_main_~t~0_Out_2)))) (and (= v_main_~t~0_In_1 v_main_~t~0_Out_2) (= v_main_~a~0_In_1 v_main_~a~0_Out_2) (= v_main_~n~0_In_1 v_main_~n~0_In_1) (= v_main_~s~0_In_1 v_main_~s~0_Out_2))) InVars {main_~t~0=v_main_~t~0_In_1, main_~n~0=v_main_~n~0_In_1, main_~s~0=v_main_~s~0_In_1, main_~a~0=v_main_~a~0_In_1} OutVars{main_~t~0=v_main_~t~0_Out_2, main_~n~0=v_main_~n~0_In_1, main_~s~0=v_main_~s~0_Out_2, main_~a~0=v_main_~a~0_Out_2} AuxVars[] AssignedVars[main_~t~0, main_~s~0, main_~a~0] {1226#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-15 17:35:31,178 INFO L290 TraceCheckUtils]: 13: Hoare triple {1226#(and (= main_~a~0 0) (= main_~t~0 1))} [72] L31_primed-->L31: Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] {1226#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-15 17:35:31,179 INFO L272 TraceCheckUtils]: 14: Hoare triple {1226#(and (= main_~a~0 0) (= main_~t~0 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1236#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 17:35:31,179 INFO L290 TraceCheckUtils]: 15: Hoare triple {1236#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1240#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 17:35:31,180 INFO L290 TraceCheckUtils]: 16: Hoare triple {1240#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1189#false} is VALID [2022-04-15 17:35:31,180 INFO L290 TraceCheckUtils]: 17: Hoare triple {1189#false} assume !false; {1189#false} is VALID [2022-04-15 17:35:31,180 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 17:35:31,180 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 17:35:31,180 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 17:35:31,180 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1938604338] [2022-04-15 17:35:31,180 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 17:35:31,180 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [509651732] [2022-04-15 17:35:31,180 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [509651732] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:31,180 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:31,181 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 17:35:31,353 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 17:35:31,353 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [695611397] [2022-04-15 17:35:31,353 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [695611397] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 17:35:31,353 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 17:35:31,353 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-15 17:35:31,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1719597978] [2022-04-15 17:35:31,354 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 17:35:31,354 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 1.6363636363636365) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 34 [2022-04-15 17:35:31,354 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 17:35:31,354 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 13 states, 11 states have (on average 1.6363636363636365) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-15 17:35:31,378 WARN L143 InductivityCheck]: Transition 1251#(and (<= main_~s~0 (+ main_~n~0 main_~t~0)) (= (+ (* main_~t~0 6) (- 3) (* main_~s~0 (- 4)) (* (+ (- 2) main_~t~0) (+ (- 2) main_~t~0))) 0)) ( _ , assume !false; , 1226#(and (= main_~a~0 0) (= main_~t~0 1)) ) not inductive [2022-04-15 17:35:31,407 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-15 17:35:31,594 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-15 17:35:31,595 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: inductivity failed at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.evaluateResult(InductivityCheck.java:145) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.checkInductivity(InductivityCheck.java:103) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.(InductivityCheck.java:75) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.constructInterpolantAutomaton(BasicCegarLoop.java:682) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.constructRefinementAutomaton(AbstractCegarLoop.java:547) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:420) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:349) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:331) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:411) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:301) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:261) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:153) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2022-04-15 17:35:31,598 INFO L158 Benchmark]: Toolchain (without parser) took 4466.99ms. Allocated memory was 223.3MB in the beginning and 277.9MB in the end (delta: 54.5MB). Free memory was 173.9MB in the beginning and 230.6MB in the end (delta: -56.7MB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 17:35:31,598 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 223.3MB. Free memory was 189.9MB in the beginning and 189.8MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 17:35:31,598 INFO L158 Benchmark]: CACSL2BoogieTranslator took 202.88ms. Allocated memory is still 223.3MB. Free memory was 173.7MB in the beginning and 200.0MB in the end (delta: -26.2MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-15 17:35:31,599 INFO L158 Benchmark]: Boogie Preprocessor took 31.73ms. Allocated memory is still 223.3MB. Free memory was 199.4MB in the beginning and 198.4MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-15 17:35:31,599 INFO L158 Benchmark]: RCFGBuilder took 266.72ms. Allocated memory is still 223.3MB. Free memory was 198.4MB in the beginning and 186.9MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-15 17:35:31,599 INFO L158 Benchmark]: TraceAbstraction took 3960.31ms. Allocated memory was 223.3MB in the beginning and 277.9MB in the end (delta: 54.5MB). Free memory was 186.3MB in the beginning and 230.6MB in the end (delta: -44.3MB). Peak memory consumption was 11.4MB. Max. memory is 8.0GB. [2022-04-15 17:35:31,600 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.11ms. Allocated memory is still 223.3MB. Free memory was 189.9MB in the beginning and 189.8MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 202.88ms. Allocated memory is still 223.3MB. Free memory was 173.7MB in the beginning and 200.0MB in the end (delta: -26.2MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * Boogie Preprocessor took 31.73ms. Allocated memory is still 223.3MB. Free memory was 199.4MB in the beginning and 198.4MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 266.72ms. Allocated memory is still 223.3MB. Free memory was 198.4MB in the beginning and 186.9MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 3960.31ms. Allocated memory was 223.3MB in the beginning and 277.9MB in the end (delta: 54.5MB). Free memory was 186.3MB in the beginning and 230.6MB in the end (delta: -44.3MB). Peak memory consumption was 11.4MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: inductivity failed de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: inductivity failed: de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.evaluateResult(InductivityCheck.java:145) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2022-04-15 17:35:31,632 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...