/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/hard2_unwindbound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 15:51:25,127 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 15:51:25,131 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 15:51:25,167 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 15:51:25,167 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 15:51:25,168 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 15:51:25,170 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 15:51:25,172 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 15:51:25,174 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 15:51:25,177 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 15:51:25,178 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 15:51:25,179 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 15:51:25,179 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 15:51:25,181 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 15:51:25,182 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 15:51:25,187 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 15:51:25,188 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 15:51:25,188 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 15:51:25,190 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 15:51:25,194 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 15:51:25,196 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 15:51:25,197 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 15:51:25,197 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 15:51:25,198 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 15:51:25,199 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 15:51:25,203 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 15:51:25,204 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 15:51:25,204 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 15:51:25,204 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 15:51:25,205 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 15:51:25,206 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 15:51:25,206 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 15:51:25,207 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 15:51:25,208 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 15:51:25,208 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 15:51:25,209 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 15:51:25,209 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 15:51:25,209 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 15:51:25,209 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 15:51:25,209 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 15:51:25,210 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 15:51:25,211 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 15:51:25,212 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-15 15:51:25,220 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 15:51:25,220 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 15:51:25,222 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 15:51:25,222 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 15:51:25,222 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 15:51:25,222 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 15:51:25,222 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 15:51:25,222 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 15:51:25,223 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 15:51:25,223 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 15:51:25,223 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 15:51:25,223 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 15:51:25,224 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-15 15:51:25,224 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-15 15:51:25,410 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 15:51:25,432 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 15:51:25,433 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 15:51:25,434 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 15:51:25,435 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 15:51:25,436 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound50.c [2022-04-15 15:51:25,509 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a80a57a23/a673d7abef954998b71526fed6a02d9b/FLAG44d8757e9 [2022-04-15 15:51:25,842 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 15:51:25,842 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound50.c [2022-04-15 15:51:25,846 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a80a57a23/a673d7abef954998b71526fed6a02d9b/FLAG44d8757e9 [2022-04-15 15:51:25,853 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a80a57a23/a673d7abef954998b71526fed6a02d9b [2022-04-15 15:51:25,855 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 15:51:25,855 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 15:51:25,858 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 15:51:25,858 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 15:51:25,861 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 15:51:25,861 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 03:51:25" (1/1) ... [2022-04-15 15:51:25,862 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5c0592dc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:25, skipping insertion in model container [2022-04-15 15:51:25,862 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 03:51:25" (1/1) ... [2022-04-15 15:51:25,866 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 15:51:25,876 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 15:51:25,994 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/hard2_unwindbound50.c[526,539] [2022-04-15 15:51:26,004 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 15:51:26,009 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 15:51:26,016 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/hard2_unwindbound50.c[526,539] [2022-04-15 15:51:26,021 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 15:51:26,030 INFO L208 MainTranslator]: Completed translation [2022-04-15 15:51:26,030 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26 WrapperNode [2022-04-15 15:51:26,030 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 15:51:26,031 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 15:51:26,031 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 15:51:26,031 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 15:51:26,038 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,038 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,042 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,042 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,046 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,049 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,049 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,050 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 15:51:26,051 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 15:51:26,051 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 15:51:26,051 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 15:51:26,051 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (1/1) ... [2022-04-15 15:51:26,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 15:51:26,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:51:26,080 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-15 15:51:26,081 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-15 15:51:26,103 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 15:51:26,103 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 15:51:26,103 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 15:51:26,103 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 15:51:26,103 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 15:51:26,103 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 15:51:26,103 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 15:51:26,103 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 15:51:26,103 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 15:51:26,103 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 15:51:26,104 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 15:51:26,143 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 15:51:26,144 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 15:51:26,297 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 15:51:26,302 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 15:51:26,302 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-15 15:51:26,303 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 03:51:26 BoogieIcfgContainer [2022-04-15 15:51:26,303 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 15:51:26,304 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 15:51:26,304 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 15:51:26,317 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 15:51:26,317 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 03:51:25" (1/3) ... [2022-04-15 15:51:26,318 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2aae84a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 03:51:26, skipping insertion in model container [2022-04-15 15:51:26,318 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:51:26" (2/3) ... [2022-04-15 15:51:26,318 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2aae84a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 03:51:26, skipping insertion in model container [2022-04-15 15:51:26,318 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 03:51:26" (3/3) ... [2022-04-15 15:51:26,319 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound50.c [2022-04-15 15:51:26,322 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 15:51:26,322 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 15:51:26,347 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 15:51:26,352 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-15 15:51:26,352 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 15:51:26,364 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-15 15:51:26,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-15 15:51:26,369 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:26,369 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:26,370 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:26,373 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:26,373 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 1 times [2022-04-15 15:51:26,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:26,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [540836955] [2022-04-15 15:51:26,393 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:26,393 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 2 times [2022-04-15 15:51:26,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:26,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326267981] [2022-04-15 15:51:26,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:26,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:26,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:26,551 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:51:26,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:26,573 INFO L290 TraceCheckUtils]: 0: Hoare triple {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-15 15:51:26,574 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 15:51:26,574 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #92#return; {34#true} is VALID [2022-04-15 15:51:26,577 INFO L272 TraceCheckUtils]: 0: Hoare triple {34#true} call ULTIMATE.init(); {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:51:26,577 INFO L290 TraceCheckUtils]: 1: Hoare triple {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-15 15:51:26,578 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 15:51:26,578 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #92#return; {34#true} is VALID [2022-04-15 15:51:26,578 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret7 := main(); {34#true} is VALID [2022-04-15 15:51:26,578 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {34#true} is VALID [2022-04-15 15:51:26,579 INFO L290 TraceCheckUtils]: 6: Hoare triple {34#true} assume !true; {35#false} is VALID [2022-04-15 15:51:26,579 INFO L290 TraceCheckUtils]: 7: Hoare triple {35#false} assume !true; {35#false} is VALID [2022-04-15 15:51:26,579 INFO L272 TraceCheckUtils]: 8: Hoare triple {35#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {35#false} is VALID [2022-04-15 15:51:26,579 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-15 15:51:26,580 INFO L290 TraceCheckUtils]: 10: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-15 15:51:26,580 INFO L290 TraceCheckUtils]: 11: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-15 15:51:26,581 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:51:26,581 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:26,581 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326267981] [2022-04-15 15:51:26,582 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [326267981] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:26,582 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:26,583 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 15:51:26,585 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:26,585 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [540836955] [2022-04-15 15:51:26,585 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [540836955] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:26,585 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:26,585 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 15:51:26,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1160714384] [2022-04-15 15:51:26,586 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:26,591 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-15 15:51:26,592 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:26,594 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:26,616 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 12 edges. 12 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:26,616 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 15:51:26,616 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:26,637 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 15:51:26,638 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 15:51:26,641 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 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 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:26,778 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:26,779 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-04-15 15:51:26,779 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 15:51:26,779 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-15 15:51:26,779 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:26,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:26,787 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 91 transitions. [2022-04-15 15:51:26,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:26,791 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 91 transitions. [2022-04-15 15:51:26,792 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 91 transitions. [2022-04-15 15:51:26,880 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 91 edges. 91 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:26,890 INFO L225 Difference]: With dead ends: 57 [2022-04-15 15:51:26,890 INFO L226 Difference]: Without dead ends: 27 [2022-04-15 15:51:26,894 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 15:51:26,897 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:26,898 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:51:26,910 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-15 15:51:26,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-15 15:51:26,935 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:26,936 INFO L82 GeneralOperation]: Start isEquivalent. First operand 27 states. Second operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:26,937 INFO L74 IsIncluded]: Start isIncluded. First operand 27 states. Second operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:26,937 INFO L87 Difference]: Start difference. First operand 27 states. Second operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:26,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:26,942 INFO L93 Difference]: Finished difference Result 27 states and 37 transitions. [2022-04-15 15:51:26,942 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2022-04-15 15:51:26,943 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:26,943 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:26,943 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 27 states. [2022-04-15 15:51:26,944 INFO L87 Difference]: Start difference. First operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 27 states. [2022-04-15 15:51:26,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:26,946 INFO L93 Difference]: Finished difference Result 27 states and 37 transitions. [2022-04-15 15:51:26,946 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2022-04-15 15:51:26,946 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:26,947 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:26,947 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:26,947 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:26,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:26,949 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-04-15 15:51:26,950 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-04-15 15:51:26,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:26,950 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-04-15 15:51:26,950 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:26,950 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 36 transitions. [2022-04-15 15:51:26,983 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 36 edges. 36 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:26,984 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-04-15 15:51:26,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-15 15:51:26,986 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:26,990 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:26,990 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 15:51:26,991 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:26,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:26,992 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 1 times [2022-04-15 15:51:26,992 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:26,993 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [180200181] [2022-04-15 15:51:26,995 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:26,995 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 2 times [2022-04-15 15:51:26,995 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:26,995 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [319978464] [2022-04-15 15:51:26,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:26,996 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:27,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,062 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:51:27,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,069 INFO L290 TraceCheckUtils]: 0: Hoare triple {270#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {262#true} is VALID [2022-04-15 15:51:27,070 INFO L290 TraceCheckUtils]: 1: Hoare triple {262#true} assume true; {262#true} is VALID [2022-04-15 15:51:27,070 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {262#true} {262#true} #92#return; {262#true} is VALID [2022-04-15 15:51:27,070 INFO L272 TraceCheckUtils]: 0: Hoare triple {262#true} call ULTIMATE.init(); {270#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:51:27,070 INFO L290 TraceCheckUtils]: 1: Hoare triple {270#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {262#true} is VALID [2022-04-15 15:51:27,071 INFO L290 TraceCheckUtils]: 2: Hoare triple {262#true} assume true; {262#true} is VALID [2022-04-15 15:51:27,071 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {262#true} {262#true} #92#return; {262#true} is VALID [2022-04-15 15:51:27,071 INFO L272 TraceCheckUtils]: 4: Hoare triple {262#true} call #t~ret7 := main(); {262#true} is VALID [2022-04-15 15:51:27,071 INFO L290 TraceCheckUtils]: 5: Hoare triple {262#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {267#(= main_~q~0 0)} is VALID [2022-04-15 15:51:27,072 INFO L290 TraceCheckUtils]: 6: Hoare triple {267#(= main_~q~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {267#(= main_~q~0 0)} is VALID [2022-04-15 15:51:27,072 INFO L290 TraceCheckUtils]: 7: Hoare triple {267#(= main_~q~0 0)} assume !!(#t~post5 < 50);havoc #t~post5; {267#(= main_~q~0 0)} is VALID [2022-04-15 15:51:27,073 INFO L272 TraceCheckUtils]: 8: Hoare triple {267#(= main_~q~0 0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {268#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:51:27,073 INFO L290 TraceCheckUtils]: 9: Hoare triple {268#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {269#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 15:51:27,073 INFO L290 TraceCheckUtils]: 10: Hoare triple {269#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {263#false} is VALID [2022-04-15 15:51:27,074 INFO L290 TraceCheckUtils]: 11: Hoare triple {263#false} assume !false; {263#false} is VALID [2022-04-15 15:51:27,074 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:51:27,074 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:27,074 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [319978464] [2022-04-15 15:51:27,074 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [319978464] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:27,074 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:27,074 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:51:27,075 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:27,075 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [180200181] [2022-04-15 15:51:27,075 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [180200181] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:27,075 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:27,075 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:51:27,075 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [49357145] [2022-04-15 15:51:27,075 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:27,076 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-15 15:51:27,076 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:27,076 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,085 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 12 edges. 12 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:27,085 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 15:51:27,085 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:27,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 15:51:27,086 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 15:51:27,086 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,358 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:27,358 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-04-15 15:51:27,359 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 15:51:27,359 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-15 15:51:27,359 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:27,359 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-15 15:51:27,361 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-15 15:51:27,363 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 56 transitions. [2022-04-15 15:51:27,402 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:27,404 INFO L225 Difference]: With dead ends: 41 [2022-04-15 15:51:27,404 INFO L226 Difference]: Without dead ends: 39 [2022-04-15 15:51:27,404 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-15 15:51:27,405 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:27,405 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 85 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 15:51:27,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-15 15:51:27,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-04-15 15:51:27,410 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:27,411 INFO L82 GeneralOperation]: Start isEquivalent. First operand 39 states. Second operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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 15:51:27,411 INFO L74 IsIncluded]: Start isIncluded. First operand 39 states. Second operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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 15:51:27,411 INFO L87 Difference]: Start difference. First operand 39 states. Second operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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 15:51:27,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:27,413 INFO L93 Difference]: Finished difference Result 39 states and 54 transitions. [2022-04-15 15:51:27,413 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 54 transitions. [2022-04-15 15:51:27,414 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:27,414 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:27,414 INFO L74 IsIncluded]: Start isIncluded. First operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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 39 states. [2022-04-15 15:51:27,414 INFO L87 Difference]: Start difference. First operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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 39 states. [2022-04-15 15:51:27,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:27,416 INFO L93 Difference]: Finished difference Result 39 states and 54 transitions. [2022-04-15 15:51:27,417 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 54 transitions. [2022-04-15 15:51:27,417 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:27,417 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:27,417 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:27,417 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:27,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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 15:51:27,419 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-15 15:51:27,419 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-04-15 15:51:27,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:27,420 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-15 15:51:27,420 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,420 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 30 states and 39 transitions. [2022-04-15 15:51:27,451 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 39 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:27,452 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-15 15:51:27,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-04-15 15:51:27,455 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:27,455 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:27,455 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 15:51:27,455 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:27,457 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:27,457 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 1 times [2022-04-15 15:51:27,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:27,460 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [879355664] [2022-04-15 15:51:27,462 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:27,462 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 2 times [2022-04-15 15:51:27,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:27,462 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1443325009] [2022-04-15 15:51:27,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:27,462 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:27,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,524 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:51:27,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,538 INFO L290 TraceCheckUtils]: 0: Hoare triple {508#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,539 INFO L290 TraceCheckUtils]: 1: Hoare triple {506#(<= ~counter~0 0)} assume true; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,539 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {506#(<= ~counter~0 0)} {501#true} #92#return; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,540 INFO L272 TraceCheckUtils]: 0: Hoare triple {501#true} call ULTIMATE.init(); {508#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:51:27,541 INFO L290 TraceCheckUtils]: 1: Hoare triple {508#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,541 INFO L290 TraceCheckUtils]: 2: Hoare triple {506#(<= ~counter~0 0)} assume true; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,542 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {506#(<= ~counter~0 0)} {501#true} #92#return; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,542 INFO L272 TraceCheckUtils]: 4: Hoare triple {506#(<= ~counter~0 0)} call #t~ret7 := main(); {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,543 INFO L290 TraceCheckUtils]: 5: Hoare triple {506#(<= ~counter~0 0)} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {506#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:27,546 INFO L290 TraceCheckUtils]: 6: Hoare triple {506#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {507#(<= |main_#t~post5| 0)} is VALID [2022-04-15 15:51:27,546 INFO L290 TraceCheckUtils]: 7: Hoare triple {507#(<= |main_#t~post5| 0)} assume !(#t~post5 < 50);havoc #t~post5; {502#false} is VALID [2022-04-15 15:51:27,547 INFO L290 TraceCheckUtils]: 8: Hoare triple {502#false} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {502#false} is VALID [2022-04-15 15:51:27,547 INFO L290 TraceCheckUtils]: 9: Hoare triple {502#false} assume !(#t~post6 < 50);havoc #t~post6; {502#false} is VALID [2022-04-15 15:51:27,547 INFO L272 TraceCheckUtils]: 10: Hoare triple {502#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {502#false} is VALID [2022-04-15 15:51:27,547 INFO L290 TraceCheckUtils]: 11: Hoare triple {502#false} ~cond := #in~cond; {502#false} is VALID [2022-04-15 15:51:27,547 INFO L290 TraceCheckUtils]: 12: Hoare triple {502#false} assume 0 == ~cond; {502#false} is VALID [2022-04-15 15:51:27,547 INFO L290 TraceCheckUtils]: 13: Hoare triple {502#false} assume !false; {502#false} is VALID [2022-04-15 15:51:27,548 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:51:27,548 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:27,548 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1443325009] [2022-04-15 15:51:27,548 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1443325009] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:27,548 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:27,548 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 15:51:27,548 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:27,548 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [879355664] [2022-04-15 15:51:27,548 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [879355664] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:27,548 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:27,549 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 15:51:27,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1800517953] [2022-04-15 15:51:27,549 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:27,549 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-15 15:51:27,549 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:27,549 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,558 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 14 edges. 14 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:27,558 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:51:27,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:27,559 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:51:27,559 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:51:27,559 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:27,684 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-04-15 15:51:27,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-15 15:51:27,684 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-15 15:51:27,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:27,684 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 58 transitions. [2022-04-15 15:51:27,686 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 58 transitions. [2022-04-15 15:51:27,687 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 58 transitions. [2022-04-15 15:51:27,722 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 58 edges. 58 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:27,724 INFO L225 Difference]: With dead ends: 46 [2022-04-15 15:51:27,724 INFO L226 Difference]: Without dead ends: 32 [2022-04-15 15:51:27,724 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 15:51:27,725 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:27,725 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:51:27,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-15 15:51:27,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-15 15:51:27,733 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:27,733 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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 15:51:27,733 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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 15:51:27,734 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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 15:51:27,735 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:27,735 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-15 15:51:27,735 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-15 15:51:27,735 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:27,735 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:27,736 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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 32 states. [2022-04-15 15:51:27,736 INFO L87 Difference]: Start difference. First operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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 32 states. [2022-04-15 15:51:27,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:27,737 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-15 15:51:27,737 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-15 15:51:27,738 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:27,738 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:27,738 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:27,738 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:27,738 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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 15:51:27,739 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-15 15:51:27,739 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-04-15 15:51:27,739 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:27,739 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-15 15:51:27,739 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 15:51:27,739 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 41 transitions. [2022-04-15 15:51:27,768 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 41 edges. 41 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:27,768 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-15 15:51:27,768 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-15 15:51:27,768 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:27,768 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:27,768 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-15 15:51:27,768 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:27,769 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:27,769 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 1 times [2022-04-15 15:51:27,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:27,769 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1069236383] [2022-04-15 15:51:27,769 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:27,769 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 2 times [2022-04-15 15:51:27,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:27,770 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [481290958] [2022-04-15 15:51:27,770 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:27,770 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:27,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,823 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:51:27,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,829 INFO L290 TraceCheckUtils]: 0: Hoare triple {745#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {733#true} is VALID [2022-04-15 15:51:27,830 INFO L290 TraceCheckUtils]: 1: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-15 15:51:27,830 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {733#true} {733#true} #92#return; {733#true} is VALID [2022-04-15 15:51:27,830 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-04-15 15:51:27,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:27,833 INFO L290 TraceCheckUtils]: 0: Hoare triple {733#true} ~cond := #in~cond; {733#true} is VALID [2022-04-15 15:51:27,834 INFO L290 TraceCheckUtils]: 1: Hoare triple {733#true} assume !(0 == ~cond); {733#true} is VALID [2022-04-15 15:51:27,834 INFO L290 TraceCheckUtils]: 2: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-15 15:51:27,834 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {733#true} {738#(= main_~A~0 main_~r~0)} #78#return; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 15:51:27,835 INFO L272 TraceCheckUtils]: 0: Hoare triple {733#true} call ULTIMATE.init(); {745#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:51:27,835 INFO L290 TraceCheckUtils]: 1: Hoare triple {745#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {733#true} is VALID [2022-04-15 15:51:27,835 INFO L290 TraceCheckUtils]: 2: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-15 15:51:27,835 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {733#true} {733#true} #92#return; {733#true} is VALID [2022-04-15 15:51:27,835 INFO L272 TraceCheckUtils]: 4: Hoare triple {733#true} call #t~ret7 := main(); {733#true} is VALID [2022-04-15 15:51:27,836 INFO L290 TraceCheckUtils]: 5: Hoare triple {733#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 15:51:27,836 INFO L290 TraceCheckUtils]: 6: Hoare triple {738#(= main_~A~0 main_~r~0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 15:51:27,836 INFO L290 TraceCheckUtils]: 7: Hoare triple {738#(= main_~A~0 main_~r~0)} assume !!(#t~post5 < 50);havoc #t~post5; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 15:51:27,836 INFO L272 TraceCheckUtils]: 8: Hoare triple {738#(= main_~A~0 main_~r~0)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {733#true} is VALID [2022-04-15 15:51:27,836 INFO L290 TraceCheckUtils]: 9: Hoare triple {733#true} ~cond := #in~cond; {733#true} is VALID [2022-04-15 15:51:27,837 INFO L290 TraceCheckUtils]: 10: Hoare triple {733#true} assume !(0 == ~cond); {733#true} is VALID [2022-04-15 15:51:27,837 INFO L290 TraceCheckUtils]: 11: Hoare triple {733#true} assume true; {733#true} is VALID [2022-04-15 15:51:27,837 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {733#true} {738#(= main_~A~0 main_~r~0)} #78#return; {738#(= main_~A~0 main_~r~0)} is VALID [2022-04-15 15:51:27,838 INFO L272 TraceCheckUtils]: 13: Hoare triple {738#(= main_~A~0 main_~r~0)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {743#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:51:27,838 INFO L290 TraceCheckUtils]: 14: Hoare triple {743#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {744#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 15:51:27,838 INFO L290 TraceCheckUtils]: 15: Hoare triple {744#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {734#false} is VALID [2022-04-15 15:51:27,838 INFO L290 TraceCheckUtils]: 16: Hoare triple {734#false} assume !false; {734#false} is VALID [2022-04-15 15:51:27,839 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:51:27,839 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:27,839 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [481290958] [2022-04-15 15:51:27,839 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [481290958] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:27,839 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:27,839 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:51:27,839 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:27,839 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1069236383] [2022-04-15 15:51:27,839 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1069236383] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:27,839 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:27,840 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 15:51:27,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2063851085] [2022-04-15 15:51:27,840 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:27,840 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), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-15 15:51:27,840 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:27,840 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:51:27,850 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 15:51:27,850 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 15:51:27,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:27,850 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 15:51:27,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 15:51:27,851 INFO L87 Difference]: Start difference. First operand 32 states and 41 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:51:28,098 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:28,098 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-15 15:51:28,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 15:51:28,098 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), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-15 15:51:28,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:28,099 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:51:28,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-15 15:51:28,100 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:51:28,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 56 transitions. [2022-04-15 15:51:28,101 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 56 transitions. [2022-04-15 15:51:28,142 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:28,143 INFO L225 Difference]: With dead ends: 46 [2022-04-15 15:51:28,144 INFO L226 Difference]: Without dead ends: 44 [2022-04-15 15:51:28,144 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-15 15:51:28,145 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:28,145 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 78 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 15:51:28,145 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-15 15:51:28,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-04-15 15:51:28,155 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:28,156 INFO L82 GeneralOperation]: Start isEquivalent. First operand 44 states. Second operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:28,156 INFO L74 IsIncluded]: Start isIncluded. First operand 44 states. Second operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:28,157 INFO L87 Difference]: Start difference. First operand 44 states. Second operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:28,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:28,162 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-15 15:51:28,162 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2022-04-15 15:51:28,164 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:28,164 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:28,165 INFO L74 IsIncluded]: Start isIncluded. First operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 44 states. [2022-04-15 15:51:28,165 INFO L87 Difference]: Start difference. First operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 44 states. [2022-04-15 15:51:28,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:28,167 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-15 15:51:28,167 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 58 transitions. [2022-04-15 15:51:28,168 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:28,168 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:28,168 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:28,168 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:28,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 15:51:28,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-04-15 15:51:28,172 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-04-15 15:51:28,172 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:28,172 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-04-15 15:51:28,172 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-15 15:51:28,172 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 36 states and 44 transitions. [2022-04-15 15:51:28,200 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:28,201 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-04-15 15:51:28,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-15 15:51:28,201 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:28,201 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:28,201 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-15 15:51:28,201 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:28,202 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:28,202 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 1 times [2022-04-15 15:51:28,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:28,202 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [682834810] [2022-04-15 15:51:28,203 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:28,203 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 2 times [2022-04-15 15:51:28,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:28,217 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [954773487] [2022-04-15 15:51:28,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:28,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:28,230 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:51:28,230 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1480362142] [2022-04-15 15:51:28,230 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:51:28,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:28,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:51:28,247 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:51:28,252 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-15 15:51:28,286 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:51:28,286 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:51:28,294 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 15:51:28,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:28,307 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:51:28,502 INFO L272 TraceCheckUtils]: 0: Hoare triple {1008#true} call ULTIMATE.init(); {1008#true} is VALID [2022-04-15 15:51:28,503 INFO L290 TraceCheckUtils]: 1: Hoare triple {1008#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(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1008#true} is VALID [2022-04-15 15:51:28,503 INFO L290 TraceCheckUtils]: 2: Hoare triple {1008#true} assume true; {1008#true} is VALID [2022-04-15 15:51:28,503 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1008#true} {1008#true} #92#return; {1008#true} is VALID [2022-04-15 15:51:28,503 INFO L272 TraceCheckUtils]: 4: Hoare triple {1008#true} call #t~ret7 := main(); {1008#true} is VALID [2022-04-15 15:51:28,503 INFO L290 TraceCheckUtils]: 5: Hoare triple {1008#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 15:51:28,504 INFO L290 TraceCheckUtils]: 6: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 15:51:28,504 INFO L290 TraceCheckUtils]: 7: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} assume !!(#t~post5 < 50);havoc #t~post5; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 15:51:28,505 INFO L272 TraceCheckUtils]: 8: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1008#true} is VALID [2022-04-15 15:51:28,505 INFO L290 TraceCheckUtils]: 9: Hoare triple {1008#true} ~cond := #in~cond; {1008#true} is VALID [2022-04-15 15:51:28,505 INFO L290 TraceCheckUtils]: 10: Hoare triple {1008#true} assume !(0 == ~cond); {1008#true} is VALID [2022-04-15 15:51:28,505 INFO L290 TraceCheckUtils]: 11: Hoare triple {1008#true} assume true; {1008#true} is VALID [2022-04-15 15:51:28,505 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1008#true} {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #78#return; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 15:51:28,506 INFO L272 TraceCheckUtils]: 13: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {1008#true} is VALID [2022-04-15 15:51:28,506 INFO L290 TraceCheckUtils]: 14: Hoare triple {1008#true} ~cond := #in~cond; {1008#true} is VALID [2022-04-15 15:51:28,506 INFO L290 TraceCheckUtils]: 15: Hoare triple {1008#true} assume !(0 == ~cond); {1008#true} is VALID [2022-04-15 15:51:28,506 INFO L290 TraceCheckUtils]: 16: Hoare triple {1008#true} assume true; {1008#true} is VALID [2022-04-15 15:51:28,506 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1008#true} {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} #80#return; {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} is VALID [2022-04-15 15:51:28,515 INFO L272 TraceCheckUtils]: 18: Hoare triple {1028#(and (= main_~B~0 1) (= main_~B~0 main_~d~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {1068#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:51:28,516 INFO L290 TraceCheckUtils]: 19: Hoare triple {1068#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1072#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:51:28,516 INFO L290 TraceCheckUtils]: 20: Hoare triple {1072#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1009#false} is VALID [2022-04-15 15:51:28,516 INFO L290 TraceCheckUtils]: 21: Hoare triple {1009#false} assume !false; {1009#false} is VALID [2022-04-15 15:51:28,516 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-15 15:51:28,517 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:51:28,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:28,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [954773487] [2022-04-15 15:51:28,517 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:51:28,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1480362142] [2022-04-15 15:51:28,517 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1480362142] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:28,517 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:28,517 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:28,518 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:28,518 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [682834810] [2022-04-15 15:51:28,518 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [682834810] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:28,518 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:28,518 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:28,518 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [529791002] [2022-04-15 15:51:28,518 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:28,519 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,519 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:28,519 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,537 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 19 edges. 19 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:28,537 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:51:28,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:28,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:51:28,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:51:28,538 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:28,673 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-15 15:51:28,673 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:51:28,673 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:28,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 81 transitions. [2022-04-15 15:51:28,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 81 transitions. [2022-04-15 15:51:28,678 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 81 transitions. [2022-04-15 15:51:28,731 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 81 edges. 81 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:28,733 INFO L225 Difference]: With dead ends: 65 [2022-04-15 15:51:28,733 INFO L226 Difference]: Without dead ends: 50 [2022-04-15 15:51:28,733 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 15:51:28,735 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:28,735 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:51:28,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-15 15:51:28,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-15 15:51:28,762 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:28,763 INFO L82 GeneralOperation]: Start isEquivalent. First operand 50 states. Second operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:28,765 INFO L74 IsIncluded]: Start isIncluded. First operand 50 states. Second operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:28,765 INFO L87 Difference]: Start difference. First operand 50 states. Second operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:28,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:28,767 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-04-15 15:51:28,767 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-15 15:51:28,768 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:28,768 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:28,768 INFO L74 IsIncluded]: Start isIncluded. First operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 50 states. [2022-04-15 15:51:28,768 INFO L87 Difference]: Start difference. First operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 50 states. [2022-04-15 15:51:28,770 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:28,770 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-04-15 15:51:28,770 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-15 15:51:28,771 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:28,771 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:28,771 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:28,771 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:28,771 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:28,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-04-15 15:51:28,773 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-04-15 15:51:28,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:28,773 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-04-15 15:51:28,773 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 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 15:51:28,773 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 50 states and 64 transitions. [2022-04-15 15:51:28,817 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:28,818 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-15 15:51:28,818 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-15 15:51:28,818 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:28,818 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:28,835 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 15:51:29,034 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:29,034 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:29,034 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:29,035 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 1 times [2022-04-15 15:51:29,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:29,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1646849822] [2022-04-15 15:51:29,035 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:29,035 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 2 times [2022-04-15 15:51:29,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:29,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [568072958] [2022-04-15 15:51:29,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:29,036 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:29,044 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:51:29,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [931340929] [2022-04-15 15:51:29,044 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:51:29,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:29,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:51:29,045 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:51:29,046 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-15 15:51:29,078 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:51:29,078 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:51:29,079 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 15:51:29,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:29,086 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:51:29,226 INFO L272 TraceCheckUtils]: 0: Hoare triple {1410#true} call ULTIMATE.init(); {1410#true} is VALID [2022-04-15 15:51:29,226 INFO L290 TraceCheckUtils]: 1: Hoare triple {1410#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(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1418#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:29,227 INFO L290 TraceCheckUtils]: 2: Hoare triple {1418#(<= ~counter~0 0)} assume true; {1418#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:29,227 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1418#(<= ~counter~0 0)} {1410#true} #92#return; {1418#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:29,227 INFO L272 TraceCheckUtils]: 4: Hoare triple {1418#(<= ~counter~0 0)} call #t~ret7 := main(); {1418#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:29,228 INFO L290 TraceCheckUtils]: 5: Hoare triple {1418#(<= ~counter~0 0)} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1418#(<= ~counter~0 0)} is VALID [2022-04-15 15:51:29,228 INFO L290 TraceCheckUtils]: 6: Hoare triple {1418#(<= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,229 INFO L290 TraceCheckUtils]: 7: Hoare triple {1434#(<= ~counter~0 1)} assume !!(#t~post5 < 50);havoc #t~post5; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,231 INFO L272 TraceCheckUtils]: 8: Hoare triple {1434#(<= ~counter~0 1)} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,232 INFO L290 TraceCheckUtils]: 9: Hoare triple {1434#(<= ~counter~0 1)} ~cond := #in~cond; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,232 INFO L290 TraceCheckUtils]: 10: Hoare triple {1434#(<= ~counter~0 1)} assume !(0 == ~cond); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,232 INFO L290 TraceCheckUtils]: 11: Hoare triple {1434#(<= ~counter~0 1)} assume true; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,233 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1434#(<= ~counter~0 1)} {1434#(<= ~counter~0 1)} #78#return; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,233 INFO L272 TraceCheckUtils]: 13: Hoare triple {1434#(<= ~counter~0 1)} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,233 INFO L290 TraceCheckUtils]: 14: Hoare triple {1434#(<= ~counter~0 1)} ~cond := #in~cond; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,234 INFO L290 TraceCheckUtils]: 15: Hoare triple {1434#(<= ~counter~0 1)} assume !(0 == ~cond); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,234 INFO L290 TraceCheckUtils]: 16: Hoare triple {1434#(<= ~counter~0 1)} assume true; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,235 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1434#(<= ~counter~0 1)} {1434#(<= ~counter~0 1)} #80#return; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,236 INFO L272 TraceCheckUtils]: 18: Hoare triple {1434#(<= ~counter~0 1)} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,236 INFO L290 TraceCheckUtils]: 19: Hoare triple {1434#(<= ~counter~0 1)} ~cond := #in~cond; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,237 INFO L290 TraceCheckUtils]: 20: Hoare triple {1434#(<= ~counter~0 1)} assume !(0 == ~cond); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,238 INFO L290 TraceCheckUtils]: 21: Hoare triple {1434#(<= ~counter~0 1)} assume true; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,239 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1434#(<= ~counter~0 1)} {1434#(<= ~counter~0 1)} #82#return; {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,248 INFO L290 TraceCheckUtils]: 23: Hoare triple {1434#(<= ~counter~0 1)} assume !(~r~0 >= ~d~0); {1434#(<= ~counter~0 1)} is VALID [2022-04-15 15:51:29,249 INFO L290 TraceCheckUtils]: 24: Hoare triple {1434#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1489#(<= |main_#t~post6| 1)} is VALID [2022-04-15 15:51:29,252 INFO L290 TraceCheckUtils]: 25: Hoare triple {1489#(<= |main_#t~post6| 1)} assume !(#t~post6 < 50);havoc #t~post6; {1411#false} is VALID [2022-04-15 15:51:29,252 INFO L272 TraceCheckUtils]: 26: Hoare triple {1411#false} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {1411#false} is VALID [2022-04-15 15:51:29,252 INFO L290 TraceCheckUtils]: 27: Hoare triple {1411#false} ~cond := #in~cond; {1411#false} is VALID [2022-04-15 15:51:29,252 INFO L290 TraceCheckUtils]: 28: Hoare triple {1411#false} assume 0 == ~cond; {1411#false} is VALID [2022-04-15 15:51:29,252 INFO L290 TraceCheckUtils]: 29: Hoare triple {1411#false} assume !false; {1411#false} is VALID [2022-04-15 15:51:29,252 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 15:51:29,252 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:51:29,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:29,253 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [568072958] [2022-04-15 15:51:29,253 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:51:29,253 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [931340929] [2022-04-15 15:51:29,253 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [931340929] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:29,253 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:29,253 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:29,253 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:29,253 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1646849822] [2022-04-15 15:51:29,253 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1646849822] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:29,253 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:29,253 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:29,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2108298679] [2022-04-15 15:51:29,253 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:29,254 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), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-15 15:51:29,254 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:29,254 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), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:51:29,272 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 15:51:29,273 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:51:29,273 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:29,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:51:29,274 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:51:29,274 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:51:29,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:29,362 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-04-15 15:51:29,362 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:51:29,362 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), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-15 15:51:29,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:29,364 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), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:51:29,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 59 transitions. [2022-04-15 15:51:29,367 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), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:51:29,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 59 transitions. [2022-04-15 15:51:29,368 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 59 transitions. [2022-04-15 15:51:29,400 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 59 edges. 59 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:29,402 INFO L225 Difference]: With dead ends: 70 [2022-04-15 15:51:29,402 INFO L226 Difference]: Without dead ends: 63 [2022-04-15 15:51:29,403 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:51:29,404 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:29,404 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 105 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:51:29,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-15 15:51:29,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-04-15 15:51:29,431 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:29,432 INFO L82 GeneralOperation]: Start isEquivalent. First operand 63 states. Second operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:29,432 INFO L74 IsIncluded]: Start isIncluded. First operand 63 states. Second operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:29,432 INFO L87 Difference]: Start difference. First operand 63 states. Second operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:29,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:29,434 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2022-04-15 15:51:29,434 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2022-04-15 15:51:29,435 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:29,435 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:29,436 INFO L74 IsIncluded]: Start isIncluded. First operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 63 states. [2022-04-15 15:51:29,436 INFO L87 Difference]: Start difference. First operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 63 states. [2022-04-15 15:51:29,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:29,438 INFO L93 Difference]: Finished difference Result 63 states and 73 transitions. [2022-04-15 15:51:29,438 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2022-04-15 15:51:29,438 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:29,438 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:29,438 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:29,438 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:29,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-15 15:51:29,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-04-15 15:51:29,441 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-04-15 15:51:29,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:29,441 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-04-15 15:51:29,441 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), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 15:51:29,441 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 62 states and 72 transitions. [2022-04-15 15:51:29,493 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 72 edges. 72 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:29,493 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-04-15 15:51:29,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-15 15:51:29,493 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:29,493 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:29,512 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 15:51:29,697 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,SelfDestructingSolverStorable5 [2022-04-15 15:51:29,697 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:29,698 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:29,698 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 1 times [2022-04-15 15:51:29,698 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:29,698 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [299191908] [2022-04-15 15:51:29,699 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:51:29,699 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 2 times [2022-04-15 15:51:29,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:29,699 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1911922057] [2022-04-15 15:51:29,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:29,699 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:29,708 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:51:29,708 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1709940938] [2022-04-15 15:51:29,708 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:51:29,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:29,709 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:51:29,724 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:51:29,725 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-15 15:51:29,756 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:51:29,757 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:51:29,757 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 15:51:29,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:29,770 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:51:29,891 INFO L272 TraceCheckUtils]: 0: Hoare triple {1894#true} call ULTIMATE.init(); {1894#true} is VALID [2022-04-15 15:51:29,891 INFO L290 TraceCheckUtils]: 1: Hoare triple {1894#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(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1894#true} is VALID [2022-04-15 15:51:29,891 INFO L290 TraceCheckUtils]: 2: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-15 15:51:29,891 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1894#true} {1894#true} #92#return; {1894#true} is VALID [2022-04-15 15:51:29,891 INFO L272 TraceCheckUtils]: 4: Hoare triple {1894#true} call #t~ret7 := main(); {1894#true} is VALID [2022-04-15 15:51:29,892 INFO L290 TraceCheckUtils]: 5: Hoare triple {1894#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,892 INFO L290 TraceCheckUtils]: 6: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,893 INFO L290 TraceCheckUtils]: 7: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} assume !!(#t~post5 < 50);havoc #t~post5; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,893 INFO L272 TraceCheckUtils]: 8: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if 0 == ~q~0 then 1 else 0)); {1894#true} is VALID [2022-04-15 15:51:29,893 INFO L290 TraceCheckUtils]: 9: Hoare triple {1894#true} ~cond := #in~cond; {1894#true} is VALID [2022-04-15 15:51:29,893 INFO L290 TraceCheckUtils]: 10: Hoare triple {1894#true} assume !(0 == ~cond); {1894#true} is VALID [2022-04-15 15:51:29,893 INFO L290 TraceCheckUtils]: 11: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-15 15:51:29,893 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1894#true} {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #78#return; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,893 INFO L272 TraceCheckUtils]: 13: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~r~0 == ~A~0 then 1 else 0)); {1894#true} is VALID [2022-04-15 15:51:29,894 INFO L290 TraceCheckUtils]: 14: Hoare triple {1894#true} ~cond := #in~cond; {1894#true} is VALID [2022-04-15 15:51:29,894 INFO L290 TraceCheckUtils]: 15: Hoare triple {1894#true} assume !(0 == ~cond); {1894#true} is VALID [2022-04-15 15:51:29,894 INFO L290 TraceCheckUtils]: 16: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-15 15:51:29,894 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1894#true} {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #80#return; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,894 INFO L272 TraceCheckUtils]: 18: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~d~0 == ~B~0 * ~p~0 then 1 else 0)); {1894#true} is VALID [2022-04-15 15:51:29,894 INFO L290 TraceCheckUtils]: 19: Hoare triple {1894#true} ~cond := #in~cond; {1894#true} is VALID [2022-04-15 15:51:29,894 INFO L290 TraceCheckUtils]: 20: Hoare triple {1894#true} assume !(0 == ~cond); {1894#true} is VALID [2022-04-15 15:51:29,895 INFO L290 TraceCheckUtils]: 21: Hoare triple {1894#true} assume true; {1894#true} is VALID [2022-04-15 15:51:29,895 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1894#true} {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #82#return; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,895 INFO L290 TraceCheckUtils]: 23: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} assume !(~r~0 >= ~d~0); {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,896 INFO L290 TraceCheckUtils]: 24: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,896 INFO L290 TraceCheckUtils]: 25: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} assume !!(#t~post6 < 50);havoc #t~post6; {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 15:51:29,897 INFO L272 TraceCheckUtils]: 26: Hoare triple {1914#(and (= main_~A~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~A~0 == ~q~0 * ~B~0 + ~r~0 then 1 else 0)); {1978#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:51:29,897 INFO L290 TraceCheckUtils]: 27: Hoare triple {1978#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1982#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:51:29,897 INFO L290 TraceCheckUtils]: 28: Hoare triple {1982#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1895#false} is VALID [2022-04-15 15:51:29,897 INFO L290 TraceCheckUtils]: 29: Hoare triple {1895#false} assume !false; {1895#false} is VALID [2022-04-15 15:51:29,898 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 15:51:29,898 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:51:29,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:29,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1911922057] [2022-04-15 15:51:29,898 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:51:29,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1709940938] [2022-04-15 15:51:29,898 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1709940938] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:29,898 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:29,898 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:29,898 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:29,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [299191908] [2022-04-15 15:51:29,899 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [299191908] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:29,899 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:29,899 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:29,899 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1774846817] [2022-04-15 15:51:29,899 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:29,899 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 30 [2022-04-15 15:51:29,899 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:29,899 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 15:51:29,913 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 15:51:29,913 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:51:29,913 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:29,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:51:29,914 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:51:29,914 INFO L87 Difference]: Start difference. First operand 62 states and 72 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 15:51:30,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:30,093 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-04-15 15:51:30,093 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:51:30,093 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 30 [2022-04-15 15:51:30,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:51:30,093 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 15:51:30,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 55 transitions. [2022-04-15 15:51:30,094 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 15:51:30,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 55 transitions. [2022-04-15 15:51:30,095 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 55 transitions. [2022-04-15 15:51:30,124 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 55 edges. 55 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:30,125 INFO L225 Difference]: With dead ends: 76 [2022-04-15 15:51:30,125 INFO L226 Difference]: Without dead ends: 64 [2022-04-15 15:51:30,126 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 15:51:30,126 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:51:30,126 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 95 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:51:30,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-15 15:51:30,171 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-04-15 15:51:30,171 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:51:30,171 INFO L82 GeneralOperation]: Start isEquivalent. First operand 64 states. Second operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:51:30,172 INFO L74 IsIncluded]: Start isIncluded. First operand 64 states. Second operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:51:30,172 INFO L87 Difference]: Start difference. First operand 64 states. Second operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:51:30,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:30,173 INFO L93 Difference]: Finished difference Result 64 states and 77 transitions. [2022-04-15 15:51:30,173 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-04-15 15:51:30,174 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:30,174 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:30,174 INFO L74 IsIncluded]: Start isIncluded. First operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 64 states. [2022-04-15 15:51:30,174 INFO L87 Difference]: Start difference. First operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 64 states. [2022-04-15 15:51:30,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:51:30,176 INFO L93 Difference]: Finished difference Result 64 states and 77 transitions. [2022-04-15 15:51:30,176 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-04-15 15:51:30,176 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:51:30,176 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:51:30,176 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:51:30,176 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:51:30,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 15:51:30,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-04-15 15:51:30,178 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-04-15 15:51:30,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:51:30,178 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-04-15 15:51:30,178 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 15:51:30,178 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 63 states and 76 transitions. [2022-04-15 15:51:30,237 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 76 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:51:30,237 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-04-15 15:51:30,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-15 15:51:30,238 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:51:30,238 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:51:30,253 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-15 15:51:30,445 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:30,446 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:51:30,446 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:51:30,446 INFO L85 PathProgramCache]: Analyzing trace with hash -1255015940, now seen corresponding path program 1 times [2022-04-15 15:51:30,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:51:30,446 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1666246811] [2022-04-15 15:51:34,730 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-15 15:51:34,731 INFO L85 PathProgramCache]: Analyzing trace with hash -861149586, now seen corresponding path program 1 times [2022-04-15 15:51:34,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:51:34,731 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [363033745] [2022-04-15 15:51:34,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:34,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:51:34,738 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:51:34,738 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1734922898] [2022-04-15 15:51:34,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:51:34,738 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:34,738 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:51:34,739 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 15:51:34,745 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-15 15:51:34,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:34,776 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 8 conjunts are in the unsatisfiable core [2022-04-15 15:51:34,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:51:34,784 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:51:34,860 INFO L272 TraceCheckUtils]: 0: Hoare triple {2396#true} call ULTIMATE.init(); {2396#true} is VALID [2022-04-15 15:51:34,861 INFO L290 TraceCheckUtils]: 1: Hoare triple {2396#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(8, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2396#true} is VALID [2022-04-15 15:51:34,861 INFO L290 TraceCheckUtils]: 2: Hoare triple {2396#true} assume true; {2396#true} is VALID [2022-04-15 15:51:34,861 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2396#true} {2396#true} #92#return; {2396#true} is VALID [2022-04-15 15:51:34,861 INFO L272 TraceCheckUtils]: 4: Hoare triple {2396#true} call #t~ret7 := main(); {2396#true} is VALID [2022-04-15 15:51:34,861 INFO L290 TraceCheckUtils]: 5: Hoare triple {2396#true} havoc ~A~0;havoc ~B~0;havoc ~r~0;havoc ~d~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4;~B~0 := 1;~r~0 := ~A~0;~d~0 := ~B~0;~p~0 := 1;~q~0 := 0; {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,863 INFO L290 TraceCheckUtils]: 6: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} [96] L34-3-->L34-1_primed: Formula: (let ((.cse1 (= v_main_~d~0_In_1 v_main_~d~0_Out_2))) (or (let ((.cse0 (* v_main_~B~0_In_1 (div (* (- 1) v_main_~p~0_Out_2) (- 2))))) (and (= (* .cse0 2) v_main_~d~0_Out_2) (= 0 (mod v_main_~p~0_Out_2 2)) .cse1 (= v_main_~d~0_Out_2 0) (= v_main_~r~0_In_1 0) (= v_main_~r~0_In_1 v_main_~A~0_In_1) (<= .cse0 v_main_~r~0_In_1) (= v_main_~p~0_Out_2 0) (= v_main_~q~0_In_1 0) (= v_main_~p~0_Out_2 v_main_~p~0_In_1) (= v_main_~A~0_In_1 0) (= v_main_~B~0_In_1 0) (< v_~counter~0_Out_2 51))) (and (= v_main_~A~0_In_1 v_main_~A~0_In_1) .cse1 (= v_main_~B~0_In_1 v_main_~B~0_In_1) (= v_main_~r~0_In_1 v_main_~r~0_In_1) (= v_main_~q~0_In_1 v_main_~q~0_In_1) (= v_main_~p~0_In_1 v_main_~p~0_Out_2)))) InVars {main_~q~0=v_main_~q~0_In_1, main_~d~0=v_main_~d~0_In_1, main_~B~0=v_main_~B~0_In_1, main_~A~0=v_main_~A~0_In_1, main_~p~0=v_main_~p~0_In_1, main_~r~0=v_main_~r~0_In_1} OutVars{main_~q~0=v_main_~q~0_In_1, ~counter~0=v_~counter~0_Out_2, main_#t~post5=|v_main_#t~post5_Out_2|, main_~d~0=v_main_~d~0_Out_2, main_~B~0=v_main_~B~0_In_1, main_~A~0=v_main_~A~0_In_1, main_~p~0=v_main_~p~0_Out_2, main_~r~0=v_main_~r~0_In_1} AuxVars[] AssignedVars[~counter~0, main_#t~post5, main_~d~0, main_~p~0] {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,863 INFO L290 TraceCheckUtils]: 7: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} [95] L34-1_primed-->L34-1: Formula: (and (= |v_main_#t~post5_1| v_~counter~0_4) (= v_~counter~0_3 (+ |v_main_#t~post5_1| 1))) InVars {~counter~0=v_~counter~0_4} OutVars{~counter~0=v_~counter~0_3, main_#t~post5=|v_main_#t~post5_1|} AuxVars[] AssignedVars[~counter~0, main_#t~post5] {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,864 INFO L290 TraceCheckUtils]: 8: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} assume !(#t~post5 < 50);havoc #t~post5; {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,864 INFO L290 TraceCheckUtils]: 9: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,864 INFO L290 TraceCheckUtils]: 10: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} assume !(#t~post6 < 50);havoc #t~post6; {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,865 INFO L272 TraceCheckUtils]: 11: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} call __VERIFIER_assert((if ~A~0 == ~d~0 * ~q~0 + ~r~0 then 1 else 0)); {2396#true} is VALID [2022-04-15 15:51:34,865 INFO L290 TraceCheckUtils]: 12: Hoare triple {2396#true} ~cond := #in~cond; {2396#true} is VALID [2022-04-15 15:51:34,865 INFO L290 TraceCheckUtils]: 13: Hoare triple {2396#true} assume !(0 == ~cond); {2396#true} is VALID [2022-04-15 15:51:34,865 INFO L290 TraceCheckUtils]: 14: Hoare triple {2396#true} assume true; {2396#true} is VALID [2022-04-15 15:51:34,865 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {2396#true} {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} #88#return; {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} is VALID [2022-04-15 15:51:34,866 INFO L272 TraceCheckUtils]: 16: Hoare triple {2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0))} call __VERIFIER_assert((if ~B~0 == ~d~0 then 1 else 0)); {2450#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:51:34,866 INFO L290 TraceCheckUtils]: 17: Hoare triple {2450#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2454#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:51:34,866 INFO L290 TraceCheckUtils]: 18: Hoare triple {2454#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2397#false} is VALID [2022-04-15 15:51:34,867 INFO L290 TraceCheckUtils]: 19: Hoare triple {2397#false} assume !false; {2397#false} is VALID [2022-04-15 15:51:34,867 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 15:51:34,867 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:51:34,867 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:51:34,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [363033745] [2022-04-15 15:51:34,867 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:51:34,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1734922898] [2022-04-15 15:51:34,867 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1734922898] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:34,867 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:34,867 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:51:39,187 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:51:39,187 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1666246811] [2022-04-15 15:51:39,187 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1666246811] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:51:39,187 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:51:39,187 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-04-15 15:51:39,187 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515821500] [2022-04-15 15:51:39,188 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:51:39,188 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 9 states have internal predecessors, (19), 5 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 37 [2022-04-15 15:51:39,188 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:51:39,188 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 14 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 9 states have internal predecessors, (19), 5 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-15 15:51:39,443 WARN L143 InductivityCheck]: Transition 2466#(and (<= (* (div (* (- 1) main_~p~0) (- 2)) main_~B~0) main_~r~0) (= main_~d~0 (* (* main_~B~0 (div (- main_~p~0) (- 2))) 2)) (< ~counter~0 51) (= (mod main_~p~0 2) 0)) ( _ , #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; , 2416#(and (= main_~B~0 1) (= main_~B~0 main_~d~0)) ) not inductive [2022-04-15 15:51:39,466 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-15 15:51:39,643 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:51:39,644 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 15:51:39,647 INFO L158 Benchmark]: Toolchain (without parser) took 13791.53ms. Allocated memory was 185.6MB in the beginning and 227.5MB in the end (delta: 41.9MB). Free memory was 134.1MB in the beginning and 79.8MB in the end (delta: 54.3MB). Peak memory consumption was 97.5MB. Max. memory is 8.0GB. [2022-04-15 15:51:39,647 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 185.6MB. Free memory was 150.7MB in the beginning and 150.5MB in the end (delta: 131.1kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 15:51:39,648 INFO L158 Benchmark]: CACSL2BoogieTranslator took 172.41ms. Allocated memory is still 185.6MB. Free memory was 134.0MB in the beginning and 160.7MB in the end (delta: -26.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-15 15:51:39,648 INFO L158 Benchmark]: Boogie Preprocessor took 19.46ms. Allocated memory is still 185.6MB. Free memory was 160.7MB in the beginning and 159.3MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-15 15:51:39,648 INFO L158 Benchmark]: RCFGBuilder took 252.13ms. Allocated memory is still 185.6MB. Free memory was 159.0MB in the beginning and 147.4MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-15 15:51:39,648 INFO L158 Benchmark]: TraceAbstraction took 13342.39ms. Allocated memory was 185.6MB in the beginning and 227.5MB in the end (delta: 41.9MB). Free memory was 147.1MB in the beginning and 79.8MB in the end (delta: 67.2MB). Peak memory consumption was 110.4MB. Max. memory is 8.0GB. [2022-04-15 15:51:39,649 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.15ms. Allocated memory is still 185.6MB. Free memory was 150.7MB in the beginning and 150.5MB in the end (delta: 131.1kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 172.41ms. Allocated memory is still 185.6MB. Free memory was 134.0MB in the beginning and 160.7MB in the end (delta: -26.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 19.46ms. Allocated memory is still 185.6MB. Free memory was 160.7MB in the beginning and 159.3MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 252.13ms. Allocated memory is still 185.6MB. Free memory was 159.0MB in the beginning and 147.4MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 13342.39ms. Allocated memory was 185.6MB in the beginning and 227.5MB in the end (delta: 41.9MB). Free memory was 147.1MB in the beginning and 79.8MB in the end (delta: 67.2MB). Peak memory consumption was 110.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 15:51:39,665 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...