/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-fb4f59a-m [2022-04-28 04:43:45,781 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-28 04:43:45,783 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-28 04:43:45,805 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-28 04:43:45,806 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-28 04:43:45,807 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-28 04:43:45,808 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-28 04:43:45,809 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-28 04:43:45,810 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-28 04:43:45,811 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-28 04:43:45,812 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-28 04:43:45,813 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-28 04:43:45,813 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-28 04:43:45,814 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-28 04:43:45,815 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-28 04:43:45,815 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-28 04:43:45,816 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-28 04:43:45,817 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-28 04:43:45,818 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-28 04:43:45,819 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-28 04:43:45,820 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-28 04:43:45,821 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-28 04:43:45,821 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-28 04:43:45,822 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-28 04:43:45,823 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-28 04:43:45,825 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-28 04:43:45,825 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-28 04:43:45,825 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-28 04:43:45,826 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-28 04:43:45,826 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-28 04:43:45,827 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-28 04:43:45,827 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-28 04:43:45,828 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-28 04:43:45,828 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-28 04:43:45,829 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-28 04:43:45,830 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-28 04:43:45,830 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-28 04:43:45,831 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-28 04:43:45,831 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-28 04:43:45,831 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-28 04:43:45,832 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-28 04:43:45,832 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-28 04:43:45,833 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-28 04:43:45,840 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-28 04:43:45,840 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-28 04:43:45,841 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-28 04:43:45,841 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-28 04:43:45,841 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-28 04:43:45,841 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-28 04:43:45,842 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-28 04:43:45,843 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-28 04:43:45,843 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-28 04:43:45,843 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-28 04:43:45,843 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-28 04:43:45,843 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-28 04:43:45,843 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 04:43:45,844 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-28 04:43:45,844 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-28 04:43:45,844 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-28 04:43:45,844 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-28 04:43:45,844 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-28 04:43:45,844 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-28 04:43:45,844 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-28 04:43:46,020 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-28 04:43:46,037 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-28 04:43:46,039 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-28 04:43:46,040 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-28 04:43:46,041 INFO L275 PluginConnector]: CDTParser initialized [2022-04-28 04:43:46,042 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound20.c [2022-04-28 04:43:46,094 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a76055adc/af1c288c6ea8431db7d2b72d09533ca8/FLAG80c63120c [2022-04-28 04:43:46,418 INFO L306 CDTParser]: Found 1 translation units. [2022-04-28 04:43:46,419 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound20.c [2022-04-28 04:43:46,426 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a76055adc/af1c288c6ea8431db7d2b72d09533ca8/FLAG80c63120c [2022-04-28 04:43:46,434 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a76055adc/af1c288c6ea8431db7d2b72d09533ca8 [2022-04-28 04:43:46,436 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-28 04:43:46,437 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-28 04:43:46,438 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-28 04:43:46,438 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-28 04:43:46,443 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-28 04:43:46,444 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,445 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@19f199cc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46, skipping insertion in model container [2022-04-28 04:43:46,445 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,451 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-28 04:43:46,462 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-28 04:43:46,609 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/cohencu-ll_unwindbound20.c[588,601] [2022-04-28 04:43:46,651 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 04:43:46,658 INFO L203 MainTranslator]: Completed pre-run [2022-04-28 04:43:46,676 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/cohencu-ll_unwindbound20.c[588,601] [2022-04-28 04:43:46,698 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 04:43:46,712 INFO L208 MainTranslator]: Completed translation [2022-04-28 04:43:46,713 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46 WrapperNode [2022-04-28 04:43:46,713 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-28 04:43:46,715 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-28 04:43:46,715 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-28 04:43:46,715 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-28 04:43:46,724 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,724 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,740 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,740 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,749 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,752 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,753 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,754 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-28 04:43:46,755 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-28 04:43:46,755 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-28 04:43:46,755 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-28 04:43:46,760 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (1/1) ... [2022-04-28 04:43:46,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 04:43:46,774 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 04:43:46,788 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-28 04:43:46,806 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-28 04:43:46,832 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-28 04:43:46,832 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-28 04:43:46,833 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-28 04:43:46,833 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-28 04:43:46,833 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-28 04:43:46,833 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-28 04:43:46,833 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-28 04:43:46,833 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-28 04:43:46,834 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-28 04:43:46,834 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-28 04:43:46,834 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_ushort [2022-04-28 04:43:46,835 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-28 04:43:46,835 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-28 04:43:46,835 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-28 04:43:46,836 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-28 04:43:46,836 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-28 04:43:46,836 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-28 04:43:46,836 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-28 04:43:46,836 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-28 04:43:46,836 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-28 04:43:46,881 INFO L234 CfgBuilder]: Building ICFG [2022-04-28 04:43:46,883 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-28 04:43:47,007 INFO L275 CfgBuilder]: Performing block encoding [2022-04-28 04:43:47,012 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-28 04:43:47,013 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-28 04:43:47,014 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 04:43:47 BoogieIcfgContainer [2022-04-28 04:43:47,014 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-28 04:43:47,016 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-28 04:43:47,016 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-28 04:43:47,018 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-28 04:43:47,019 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.04 04:43:46" (1/3) ... [2022-04-28 04:43:47,019 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b718dc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 04:43:47, skipping insertion in model container [2022-04-28 04:43:47,019 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 04:43:46" (2/3) ... [2022-04-28 04:43:47,020 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b718dc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 04:43:47, skipping insertion in model container [2022-04-28 04:43:47,020 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 04:43:47" (3/3) ... [2022-04-28 04:43:47,021 INFO L111 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound20.c [2022-04-28 04:43:47,032 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-28 04:43:47,032 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-28 04:43:47,065 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-28 04:43:47,070 INFO L357 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, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@2429429f, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@485723ab [2022-04-28 04:43:47,071 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-28 04:43:47,077 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-28 04:43:47,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-28 04:43:47,083 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:47,083 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:47,084 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:47,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:47,097 INFO L85 PathProgramCache]: Analyzing trace with hash 1839589780, now seen corresponding path program 1 times [2022-04-28 04:43:47,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:47,105 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [688511957] [2022-04-28 04:43:47,115 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 04:43:47,116 INFO L85 PathProgramCache]: Analyzing trace with hash 1839589780, now seen corresponding path program 2 times [2022-04-28 04:43:47,118 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:43:47,119 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [600905372] [2022-04-28 04:43:47,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:43:47,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:43:47,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:47,246 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 04:43:47,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:47,266 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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-28 04:43:47,267 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-28 04:43:47,267 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #81#return; {34#true} is VALID [2022-04-28 04:43:47,269 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-28 04:43:47,270 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(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-28 04:43:47,270 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-28 04:43:47,270 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #81#return; {34#true} is VALID [2022-04-28 04:43:47,270 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret6 := main(); {34#true} is VALID [2022-04-28 04:43:47,271 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {34#true} is VALID [2022-04-28 04:43:47,271 INFO L290 TraceCheckUtils]: 6: Hoare triple {34#true} assume !true; {35#false} is VALID [2022-04-28 04:43:47,272 INFO L272 TraceCheckUtils]: 7: Hoare triple {35#false} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {35#false} is VALID [2022-04-28 04:43:47,272 INFO L290 TraceCheckUtils]: 8: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-28 04:43:47,272 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-28 04:43:47,272 INFO L290 TraceCheckUtils]: 10: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-28 04:43:47,273 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-28 04:43:47,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:43:47,273 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [600905372] [2022-04-28 04:43:47,274 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [600905372] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:47,274 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:47,274 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 04:43:47,277 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 04:43:47,277 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [688511957] [2022-04-28 04:43:47,277 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [688511957] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:47,277 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:47,277 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 04:43:47,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [784376111] [2022-04-28 04:43:47,278 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 04:43:47,282 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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 11 [2022-04-28 04:43:47,284 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 04:43:47,286 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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-28 04:43:47,303 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 11 edges. 11 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:47,303 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-28 04:43:47,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:47,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-28 04:43:47,330 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-28 04:43:47,332 INFO L87 Difference]: Start difference. First operand has 31 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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-28 04:43:47,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:47,566 INFO L93 Difference]: Finished difference Result 57 states and 95 transitions. [2022-04-28 04:43:47,566 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-28 04:43:47,567 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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 11 [2022-04-28 04:43:47,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 04:43:47,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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-28 04:43:47,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 95 transitions. [2022-04-28 04:43:47,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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-28 04:43:47,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 95 transitions. [2022-04-28 04:43:47,586 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 95 transitions. [2022-04-28 04:43:47,726 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 95 edges. 95 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:47,734 INFO L225 Difference]: With dead ends: 57 [2022-04-28 04:43:47,734 INFO L226 Difference]: Without dead ends: 27 [2022-04-28 04:43:47,737 INFO L412 NwaCegarLoop]: 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-28 04:43:47,742 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-28 04:43:47,744 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 45 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 04:43:47,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-28 04:43:47,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-28 04:43:47,784 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 04:43:47,785 INFO L82 GeneralOperation]: Start isEquivalent. First operand 27 states. Second operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:47,786 INFO L74 IsIncluded]: Start isIncluded. First operand 27 states. Second operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:47,786 INFO L87 Difference]: Start difference. First operand 27 states. Second operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:47,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:47,791 INFO L93 Difference]: Finished difference Result 27 states and 38 transitions. [2022-04-28 04:43:47,791 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 38 transitions. [2022-04-28 04:43:47,792 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:47,792 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:47,792 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 27 states. [2022-04-28 04:43:47,793 INFO L87 Difference]: Start difference. First operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 27 states. [2022-04-28 04:43:47,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:47,797 INFO L93 Difference]: Finished difference Result 27 states and 38 transitions. [2022-04-28 04:43:47,797 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 38 transitions. [2022-04-28 04:43:47,798 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:47,798 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:47,798 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 04:43:47,798 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 04:43:47,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:47,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 37 transitions. [2022-04-28 04:43:47,803 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 37 transitions. Word has length 11 [2022-04-28 04:43:47,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 04:43:47,806 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 37 transitions. [2022-04-28 04:43:47,807 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 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-28 04:43:47,808 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 37 transitions. [2022-04-28 04:43:47,850 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 37 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:47,850 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 37 transitions. [2022-04-28 04:43:47,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-28 04:43:47,858 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:47,858 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:47,858 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-28 04:43:47,859 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:47,861 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:47,861 INFO L85 PathProgramCache]: Analyzing trace with hash 660459433, now seen corresponding path program 1 times [2022-04-28 04:43:47,861 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:47,861 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [190082365] [2022-04-28 04:43:47,865 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 04:43:47,866 INFO L85 PathProgramCache]: Analyzing trace with hash 660459433, now seen corresponding path program 2 times [2022-04-28 04:43:47,866 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:43:47,866 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1905458269] [2022-04-28 04:43:47,866 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:43:47,866 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:43:47,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:47,975 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 04:43:47,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:48,001 INFO L290 TraceCheckUtils]: 0: Hoare triple {269#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,002 INFO L290 TraceCheckUtils]: 1: Hoare triple {267#(= ~counter~0 0)} assume true; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,002 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {267#(= ~counter~0 0)} {262#true} #81#return; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,003 INFO L272 TraceCheckUtils]: 0: Hoare triple {262#true} call ULTIMATE.init(); {269#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 04:43:48,004 INFO L290 TraceCheckUtils]: 1: Hoare triple {269#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,004 INFO L290 TraceCheckUtils]: 2: Hoare triple {267#(= ~counter~0 0)} assume true; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,005 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {267#(= ~counter~0 0)} {262#true} #81#return; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,005 INFO L272 TraceCheckUtils]: 4: Hoare triple {267#(= ~counter~0 0)} call #t~ret6 := main(); {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,005 INFO L290 TraceCheckUtils]: 5: Hoare triple {267#(= ~counter~0 0)} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {267#(= ~counter~0 0)} is VALID [2022-04-28 04:43:48,006 INFO L290 TraceCheckUtils]: 6: Hoare triple {267#(= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {268#(= |main_#t~post5| 0)} is VALID [2022-04-28 04:43:48,007 INFO L290 TraceCheckUtils]: 7: Hoare triple {268#(= |main_#t~post5| 0)} assume !(#t~post5 < 20);havoc #t~post5; {263#false} is VALID [2022-04-28 04:43:48,007 INFO L272 TraceCheckUtils]: 8: Hoare triple {263#false} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {263#false} is VALID [2022-04-28 04:43:48,007 INFO L290 TraceCheckUtils]: 9: Hoare triple {263#false} ~cond := #in~cond; {263#false} is VALID [2022-04-28 04:43:48,007 INFO L290 TraceCheckUtils]: 10: Hoare triple {263#false} assume 0 == ~cond; {263#false} is VALID [2022-04-28 04:43:48,007 INFO L290 TraceCheckUtils]: 11: Hoare triple {263#false} assume !false; {263#false} is VALID [2022-04-28 04:43:48,008 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-28 04:43:48,008 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:43:48,008 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1905458269] [2022-04-28 04:43:48,008 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1905458269] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:48,008 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:48,008 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-28 04:43:48,009 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 04:43:48,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [190082365] [2022-04-28 04:43:48,009 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [190082365] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:48,009 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:48,009 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-28 04:43:48,009 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1760325921] [2022-04-28 04:43:48,009 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 04:43:48,010 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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 12 [2022-04-28 04:43:48,010 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 04:43:48,011 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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-28 04:43:48,034 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-28 04:43:48,034 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 04:43:48,034 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:48,035 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 04:43:48,035 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 04:43:48,035 INFO L87 Difference]: Start difference. First operand 26 states and 37 transitions. Second operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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-28 04:43:51,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:51,288 INFO L93 Difference]: Finished difference Result 40 states and 56 transitions. [2022-04-28 04:43:51,288 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-28 04:43:51,288 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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 12 [2022-04-28 04:43:51,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 04:43:51,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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-28 04:43:51,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 56 transitions. [2022-04-28 04:43:51,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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-28 04:43:51,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 56 transitions. [2022-04-28 04:43:51,294 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 56 transitions. [2022-04-28 04:43:51,366 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-28 04:43:51,368 INFO L225 Difference]: With dead ends: 40 [2022-04-28 04:43:51,368 INFO L226 Difference]: Without dead ends: 28 [2022-04-28 04:43:51,369 INFO L412 NwaCegarLoop]: 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-28 04:43:51,370 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 6 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-28 04:43:51,370 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 69 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 04:43:51,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-28 04:43:51,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2022-04-28 04:43:51,375 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 04:43:51,376 INFO L82 GeneralOperation]: Start isEquivalent. First operand 28 states. Second operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:51,376 INFO L74 IsIncluded]: Start isIncluded. First operand 28 states. Second operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:51,376 INFO L87 Difference]: Start difference. First operand 28 states. Second operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:51,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:51,379 INFO L93 Difference]: Finished difference Result 28 states and 39 transitions. [2022-04-28 04:43:51,379 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2022-04-28 04:43:51,380 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:51,380 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:51,380 INFO L74 IsIncluded]: Start isIncluded. First operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 28 states. [2022-04-28 04:43:51,381 INFO L87 Difference]: Start difference. First operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 28 states. [2022-04-28 04:43:51,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:51,383 INFO L93 Difference]: Finished difference Result 28 states and 39 transitions. [2022-04-28 04:43:51,383 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2022-04-28 04:43:51,384 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:51,384 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:51,384 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 04:43:51,385 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 04:43:51,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:51,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 39 transitions. [2022-04-28 04:43:51,387 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 39 transitions. Word has length 12 [2022-04-28 04:43:51,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 04:43:51,388 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 39 transitions. [2022-04-28 04:43:51,388 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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-28 04:43:51,388 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 28 states and 39 transitions. [2022-04-28 04:43:51,429 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-28 04:43:51,430 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2022-04-28 04:43:51,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-28 04:43:51,430 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:51,430 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:51,430 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-28 04:43:51,430 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:51,431 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:51,431 INFO L85 PathProgramCache]: Analyzing trace with hash 662008565, now seen corresponding path program 1 times [2022-04-28 04:43:51,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:51,431 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1296007860] [2022-04-28 04:43:51,432 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 04:43:51,432 INFO L85 PathProgramCache]: Analyzing trace with hash 662008565, now seen corresponding path program 2 times [2022-04-28 04:43:51,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:43:51,432 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [766680682] [2022-04-28 04:43:51,432 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:43:51,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:43:51,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:51,521 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 04:43:51,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:51,529 INFO L290 TraceCheckUtils]: 0: Hoare triple {474#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {466#true} is VALID [2022-04-28 04:43:51,530 INFO L290 TraceCheckUtils]: 1: Hoare triple {466#true} assume true; {466#true} is VALID [2022-04-28 04:43:51,530 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {466#true} {466#true} #81#return; {466#true} is VALID [2022-04-28 04:43:51,531 INFO L272 TraceCheckUtils]: 0: Hoare triple {466#true} call ULTIMATE.init(); {474#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 04:43:51,531 INFO L290 TraceCheckUtils]: 1: Hoare triple {474#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {466#true} is VALID [2022-04-28 04:43:51,531 INFO L290 TraceCheckUtils]: 2: Hoare triple {466#true} assume true; {466#true} is VALID [2022-04-28 04:43:51,532 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {466#true} {466#true} #81#return; {466#true} is VALID [2022-04-28 04:43:51,532 INFO L272 TraceCheckUtils]: 4: Hoare triple {466#true} call #t~ret6 := main(); {466#true} is VALID [2022-04-28 04:43:51,532 INFO L290 TraceCheckUtils]: 5: Hoare triple {466#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} is VALID [2022-04-28 04:43:51,533 INFO L290 TraceCheckUtils]: 6: Hoare triple {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} is VALID [2022-04-28 04:43:51,534 INFO L290 TraceCheckUtils]: 7: Hoare triple {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} assume !!(#t~post5 < 20);havoc #t~post5; {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} is VALID [2022-04-28 04:43:51,535 INFO L272 TraceCheckUtils]: 8: Hoare triple {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {472#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-28 04:43:51,535 INFO L290 TraceCheckUtils]: 9: Hoare triple {472#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {473#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-28 04:43:51,536 INFO L290 TraceCheckUtils]: 10: Hoare triple {473#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {467#false} is VALID [2022-04-28 04:43:51,536 INFO L290 TraceCheckUtils]: 11: Hoare triple {467#false} assume !false; {467#false} is VALID [2022-04-28 04:43:51,536 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-28 04:43:51,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:43:51,536 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [766680682] [2022-04-28 04:43:51,537 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [766680682] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:51,537 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:51,537 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-28 04:43:51,537 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 04:43:51,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1296007860] [2022-04-28 04:43:51,537 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1296007860] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:51,538 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:51,538 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-28 04:43:51,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [223289908] [2022-04-28 04:43:51,538 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 04:43:51,538 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-28 04:43:51,538 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 04:43:51,539 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-28 04:43:51,564 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-28 04:43:51,564 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-28 04:43:51,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:51,565 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-28 04:43:51,565 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-28 04:43:51,565 INFO L87 Difference]: Start difference. First operand 28 states and 39 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-28 04:43:51,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:51,970 INFO L93 Difference]: Finished difference Result 34 states and 44 transitions. [2022-04-28 04:43:51,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-28 04:43:51,970 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-28 04:43:51,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 04:43:51,971 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-28 04:43:51,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 43 transitions. [2022-04-28 04:43:51,973 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-28 04:43:51,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 43 transitions. [2022-04-28 04:43:51,986 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 43 transitions. [2022-04-28 04:43:52,033 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 43 edges. 43 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:52,034 INFO L225 Difference]: With dead ends: 34 [2022-04-28 04:43:52,034 INFO L226 Difference]: Without dead ends: 32 [2022-04-28 04:43:52,035 INFO L412 NwaCegarLoop]: 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-28 04:43:52,036 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 17 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-28 04:43:52,036 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 51 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 04:43:52,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-28 04:43:52,044 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-28 04:43:52,044 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 04:43:52,044 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:52,045 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:52,045 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:52,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:52,048 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-28 04:43:52,048 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-28 04:43:52,048 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:52,048 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:52,049 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 32 states. [2022-04-28 04:43:52,049 INFO L87 Difference]: Start difference. First operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 32 states. [2022-04-28 04:43:52,051 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:52,051 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-28 04:43:52,052 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-28 04:43:52,052 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:52,052 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:52,052 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 04:43:52,053 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 04:43:52,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 04:43:52,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2022-04-28 04:43:52,055 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 12 [2022-04-28 04:43:52,055 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 04:43:52,055 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2022-04-28 04:43:52,056 INFO L496 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-28 04:43:52,056 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 42 transitions. [2022-04-28 04:43:52,103 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 42 edges. 42 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:52,103 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-28 04:43:52,104 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-28 04:43:52,104 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:52,104 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:52,104 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-28 04:43:52,104 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:52,105 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:52,105 INFO L85 PathProgramCache]: Analyzing trace with hash 2023221563, now seen corresponding path program 1 times [2022-04-28 04:43:52,105 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:52,105 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [877932276] [2022-04-28 04:43:52,106 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 04:43:52,106 INFO L85 PathProgramCache]: Analyzing trace with hash 2023221563, now seen corresponding path program 2 times [2022-04-28 04:43:52,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:43:52,107 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [779227574] [2022-04-28 04:43:52,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:43:52,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:43:52,121 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 04:43:52,122 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1685341069] [2022-04-28 04:43:52,122 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 04:43:52,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:43:52,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 04:43:52,135 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-28 04:43:52,155 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-28 04:43:52,191 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 04:43:52,191 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 04:43:52,193 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-28 04:43:52,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:52,209 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 04:43:52,327 INFO L272 TraceCheckUtils]: 0: Hoare triple {681#true} call ULTIMATE.init(); {681#true} is VALID [2022-04-28 04:43:52,327 INFO L290 TraceCheckUtils]: 1: Hoare triple {681#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {681#true} is VALID [2022-04-28 04:43:52,327 INFO L290 TraceCheckUtils]: 2: Hoare triple {681#true} assume true; {681#true} is VALID [2022-04-28 04:43:52,327 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {681#true} {681#true} #81#return; {681#true} is VALID [2022-04-28 04:43:52,330 INFO L272 TraceCheckUtils]: 4: Hoare triple {681#true} call #t~ret6 := main(); {681#true} is VALID [2022-04-28 04:43:52,331 INFO L290 TraceCheckUtils]: 5: Hoare triple {681#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-28 04:43:52,332 INFO L290 TraceCheckUtils]: 6: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-28 04:43:52,333 INFO L290 TraceCheckUtils]: 7: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} assume !!(#t~post5 < 20);havoc #t~post5; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-28 04:43:52,334 INFO L272 TraceCheckUtils]: 8: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {681#true} is VALID [2022-04-28 04:43:52,335 INFO L290 TraceCheckUtils]: 9: Hoare triple {681#true} ~cond := #in~cond; {681#true} is VALID [2022-04-28 04:43:52,335 INFO L290 TraceCheckUtils]: 10: Hoare triple {681#true} assume !(0 == ~cond); {681#true} is VALID [2022-04-28 04:43:52,338 INFO L290 TraceCheckUtils]: 11: Hoare triple {681#true} assume true; {681#true} is VALID [2022-04-28 04:43:52,339 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {681#true} {701#(and (= main_~n~0 0) (= main_~y~0 1))} #59#return; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-28 04:43:52,340 INFO L272 TraceCheckUtils]: 13: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} call __VERIFIER_assert((if ~y~0 == 1 + (3 * ~n~0 * ~n~0 + 3 * ~n~0) then 1 else 0)); {726#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 04:43:52,340 INFO L290 TraceCheckUtils]: 14: Hoare triple {726#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {730#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 04:43:52,341 INFO L290 TraceCheckUtils]: 15: Hoare triple {730#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {682#false} is VALID [2022-04-28 04:43:52,341 INFO L290 TraceCheckUtils]: 16: Hoare triple {682#false} assume !false; {682#false} is VALID [2022-04-28 04:43:52,342 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-28 04:43:52,342 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 04:43:52,343 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:43:52,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [779227574] [2022-04-28 04:43:52,343 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 04:43:52,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1685341069] [2022-04-28 04:43:52,344 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1685341069] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:52,344 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:52,345 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 04:43:52,348 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 04:43:52,349 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [877932276] [2022-04-28 04:43:52,351 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [877932276] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:52,351 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:52,351 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 04:43:52,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981603071] [2022-04-28 04:43:52,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 04:43:52,352 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, (4), 2 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-28 04:43:52,352 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 04:43:52,353 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, (4), 2 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-28 04:43:52,366 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-28 04:43:52,367 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 04:43:52,367 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:52,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 04:43:52,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 04:43:52,368 INFO L87 Difference]: Start difference. First operand 32 states and 42 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, (4), 2 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-28 04:43:55,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:55,001 INFO L93 Difference]: Finished difference Result 50 states and 70 transitions. [2022-04-28 04:43:55,001 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 04:43:55,001 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, (4), 2 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-28 04:43:55,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 04:43:55,001 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, (4), 2 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-28 04:43:55,004 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 04:43:55,005 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, (4), 2 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-28 04:43:55,007 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 04:43:55,007 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-28 04:43:55,079 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:55,081 INFO L225 Difference]: With dead ends: 50 [2022-04-28 04:43:55,081 INFO L226 Difference]: Without dead ends: 48 [2022-04-28 04:43:55,082 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 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-28 04:43:55,087 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-28 04:43:55,089 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 141 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 04:43:55,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-28 04:43:55,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 38. [2022-04-28 04:43:55,110 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 04:43:55,111 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-28 04:43:55,112 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-28 04:43:55,113 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-28 04:43:55,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:55,123 INFO L93 Difference]: Finished difference Result 48 states and 68 transitions. [2022-04-28 04:43:55,123 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 68 transitions. [2022-04-28 04:43:55,128 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:55,128 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:55,128 INFO L74 IsIncluded]: Start isIncluded. First operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 48 states. [2022-04-28 04:43:55,128 INFO L87 Difference]: Start difference. First operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 48 states. [2022-04-28 04:43:55,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:55,131 INFO L93 Difference]: Finished difference Result 48 states and 68 transitions. [2022-04-28 04:43:55,131 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 68 transitions. [2022-04-28 04:43:55,132 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:55,132 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:55,132 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 04:43:55,132 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 04:43:55,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-28 04:43:55,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 49 transitions. [2022-04-28 04:43:55,135 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 49 transitions. Word has length 17 [2022-04-28 04:43:55,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 04:43:55,135 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 49 transitions. [2022-04-28 04:43:55,135 INFO L496 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, (4), 2 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-28 04:43:55,135 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 38 states and 49 transitions. [2022-04-28 04:43:55,199 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 49 edges. 49 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:55,200 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 49 transitions. [2022-04-28 04:43:55,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-28 04:43:55,200 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:55,200 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:55,226 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-28 04:43:55,419 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:43:55,420 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:55,420 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:55,420 INFO L85 PathProgramCache]: Analyzing trace with hash 1612678773, now seen corresponding path program 1 times [2022-04-28 04:43:55,420 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:55,420 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1124809378] [2022-04-28 04:43:55,421 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 04:43:55,421 INFO L85 PathProgramCache]: Analyzing trace with hash 1612678773, now seen corresponding path program 2 times [2022-04-28 04:43:55,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:43:55,421 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [88701131] [2022-04-28 04:43:55,421 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:43:55,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:43:55,438 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 04:43:55,438 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1371336986] [2022-04-28 04:43:55,438 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 04:43:55,438 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:43:55,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 04:43:55,440 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-28 04:43:55,440 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-28 04:43:55,473 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 04:43:55,473 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 04:43:55,474 INFO L263 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-28 04:43:55,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:55,500 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 04:43:55,614 INFO L272 TraceCheckUtils]: 0: Hoare triple {1010#true} call ULTIMATE.init(); {1010#true} is VALID [2022-04-28 04:43:55,614 INFO L290 TraceCheckUtils]: 1: Hoare triple {1010#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1010#true} is VALID [2022-04-28 04:43:55,615 INFO L290 TraceCheckUtils]: 2: Hoare triple {1010#true} assume true; {1010#true} is VALID [2022-04-28 04:43:55,615 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1010#true} {1010#true} #81#return; {1010#true} is VALID [2022-04-28 04:43:55,615 INFO L272 TraceCheckUtils]: 4: Hoare triple {1010#true} call #t~ret6 := main(); {1010#true} is VALID [2022-04-28 04:43:55,616 INFO L290 TraceCheckUtils]: 5: Hoare triple {1010#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-28 04:43:55,616 INFO L290 TraceCheckUtils]: 6: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-28 04:43:55,617 INFO L290 TraceCheckUtils]: 7: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} assume !!(#t~post5 < 20);havoc #t~post5; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-28 04:43:55,617 INFO L272 TraceCheckUtils]: 8: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {1010#true} is VALID [2022-04-28 04:43:55,617 INFO L290 TraceCheckUtils]: 9: Hoare triple {1010#true} ~cond := #in~cond; {1010#true} is VALID [2022-04-28 04:43:55,617 INFO L290 TraceCheckUtils]: 10: Hoare triple {1010#true} assume !(0 == ~cond); {1010#true} is VALID [2022-04-28 04:43:55,618 INFO L290 TraceCheckUtils]: 11: Hoare triple {1010#true} assume true; {1010#true} is VALID [2022-04-28 04:43:55,618 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1010#true} {1030#(and (= main_~x~0 0) (= main_~n~0 0))} #59#return; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-28 04:43:55,618 INFO L272 TraceCheckUtils]: 13: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} call __VERIFIER_assert((if ~y~0 == 1 + (3 * ~n~0 * ~n~0 + 3 * ~n~0) then 1 else 0)); {1010#true} is VALID [2022-04-28 04:43:55,618 INFO L290 TraceCheckUtils]: 14: Hoare triple {1010#true} ~cond := #in~cond; {1010#true} is VALID [2022-04-28 04:43:55,619 INFO L290 TraceCheckUtils]: 15: Hoare triple {1010#true} assume !(0 == ~cond); {1010#true} is VALID [2022-04-28 04:43:55,619 INFO L290 TraceCheckUtils]: 16: Hoare triple {1010#true} assume true; {1010#true} is VALID [2022-04-28 04:43:55,619 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1010#true} {1030#(and (= main_~x~0 0) (= main_~n~0 0))} #61#return; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-28 04:43:55,620 INFO L272 TraceCheckUtils]: 18: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} call __VERIFIER_assert((if ~x~0 == ~n~0 * ~n~0 * ~n~0 then 1 else 0)); {1070#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 04:43:55,620 INFO L290 TraceCheckUtils]: 19: Hoare triple {1070#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1074#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 04:43:55,621 INFO L290 TraceCheckUtils]: 20: Hoare triple {1074#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1011#false} is VALID [2022-04-28 04:43:55,621 INFO L290 TraceCheckUtils]: 21: Hoare triple {1011#false} assume !false; {1011#false} is VALID [2022-04-28 04:43:55,622 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-28 04:43:55,622 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 04:43:55,622 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:43:55,622 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [88701131] [2022-04-28 04:43:55,622 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 04:43:55,622 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1371336986] [2022-04-28 04:43:55,622 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1371336986] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:55,622 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:55,623 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 04:43:55,623 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 04:43:55,623 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1124809378] [2022-04-28 04:43:55,623 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1124809378] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:55,623 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:55,623 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 04:43:55,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [76660071] [2022-04-28 04:43:55,623 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 04:43:55,624 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-28 04:43:55,624 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 04:43:55,624 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-28 04:43:55,640 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-28 04:43:55,640 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 04:43:55,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:55,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 04:43:55,640 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 04:43:55,641 INFO L87 Difference]: Start difference. First operand 38 states and 49 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-28 04:43:55,889 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:55,889 INFO L93 Difference]: Finished difference Result 54 states and 73 transitions. [2022-04-28 04:43:55,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 04:43:55,889 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-28 04:43:55,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 04:43:55,890 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-28 04:43:55,892 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 04:43:55,892 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-28 04:43:55,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 04:43:55,894 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-28 04:43:55,960 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:55,961 INFO L225 Difference]: With dead ends: 54 [2022-04-28 04:43:55,961 INFO L226 Difference]: Without dead ends: 52 [2022-04-28 04:43:55,962 INFO L412 NwaCegarLoop]: 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-28 04:43:55,962 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-28 04:43:55,963 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 134 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-28 04:43:55,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-28 04:43:55,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 48. [2022-04-28 04:43:55,979 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 04:43:55,981 INFO L82 GeneralOperation]: Start isEquivalent. First operand 52 states. Second operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-28 04:43:55,982 INFO L74 IsIncluded]: Start isIncluded. First operand 52 states. Second operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-28 04:43:55,984 INFO L87 Difference]: Start difference. First operand 52 states. Second operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-28 04:43:55,988 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:55,988 INFO L93 Difference]: Finished difference Result 52 states and 71 transitions. [2022-04-28 04:43:55,988 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 71 transitions. [2022-04-28 04:43:55,988 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:55,988 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:55,989 INFO L74 IsIncluded]: Start isIncluded. First operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) Second operand 52 states. [2022-04-28 04:43:55,989 INFO L87 Difference]: Start difference. First operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) Second operand 52 states. [2022-04-28 04:43:55,992 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:55,992 INFO L93 Difference]: Finished difference Result 52 states and 71 transitions. [2022-04-28 04:43:55,992 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 71 transitions. [2022-04-28 04:43:55,993 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:55,993 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:55,993 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 04:43:55,993 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 04:43:55,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-28 04:43:55,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 64 transitions. [2022-04-28 04:43:55,997 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 64 transitions. Word has length 22 [2022-04-28 04:43:55,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 04:43:55,999 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 64 transitions. [2022-04-28 04:43:55,999 INFO L496 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-28 04:43:55,999 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 48 states and 64 transitions. [2022-04-28 04:43:56,075 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-28 04:43:56,075 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 64 transitions. [2022-04-28 04:43:56,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-28 04:43:56,076 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:56,076 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:56,101 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-28 04:43:56,296 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:43:56,297 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:56,297 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:56,297 INFO L85 PathProgramCache]: Analyzing trace with hash 1625830715, now seen corresponding path program 1 times [2022-04-28 04:43:56,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:56,297 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [394059644] [2022-04-28 04:43:56,298 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 04:43:56,298 INFO L85 PathProgramCache]: Analyzing trace with hash 1625830715, now seen corresponding path program 2 times [2022-04-28 04:43:56,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:43:56,298 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [626266297] [2022-04-28 04:43:56,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:43:56,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:43:56,311 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 04:43:56,311 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [119017509] [2022-04-28 04:43:56,311 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 04:43:56,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:43:56,312 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 04:43:56,313 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-28 04:43:56,343 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-28 04:43:56,357 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 04:43:56,357 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 04:43:56,358 INFO L263 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-28 04:43:56,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:43:56,367 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 04:43:56,506 INFO L272 TraceCheckUtils]: 0: Hoare triple {1390#true} call ULTIMATE.init(); {1390#true} is VALID [2022-04-28 04:43:56,506 INFO L290 TraceCheckUtils]: 1: Hoare triple {1390#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1390#true} is VALID [2022-04-28 04:43:56,507 INFO L290 TraceCheckUtils]: 2: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-28 04:43:56,507 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1390#true} {1390#true} #81#return; {1390#true} is VALID [2022-04-28 04:43:56,507 INFO L272 TraceCheckUtils]: 4: Hoare triple {1390#true} call #t~ret6 := main(); {1390#true} is VALID [2022-04-28 04:43:56,508 INFO L290 TraceCheckUtils]: 5: Hoare triple {1390#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-28 04:43:56,508 INFO L290 TraceCheckUtils]: 6: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-28 04:43:56,509 INFO L290 TraceCheckUtils]: 7: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} assume !!(#t~post5 < 20);havoc #t~post5; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-28 04:43:56,510 INFO L272 TraceCheckUtils]: 8: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {1390#true} is VALID [2022-04-28 04:43:56,510 INFO L290 TraceCheckUtils]: 9: Hoare triple {1390#true} ~cond := #in~cond; {1390#true} is VALID [2022-04-28 04:43:56,510 INFO L290 TraceCheckUtils]: 10: Hoare triple {1390#true} assume !(0 == ~cond); {1390#true} is VALID [2022-04-28 04:43:56,510 INFO L290 TraceCheckUtils]: 11: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-28 04:43:56,511 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1390#true} {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #59#return; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-28 04:43:56,511 INFO L272 TraceCheckUtils]: 13: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if ~y~0 == 1 + (3 * ~n~0 * ~n~0 + 3 * ~n~0) then 1 else 0)); {1390#true} is VALID [2022-04-28 04:43:56,511 INFO L290 TraceCheckUtils]: 14: Hoare triple {1390#true} ~cond := #in~cond; {1390#true} is VALID [2022-04-28 04:43:56,511 INFO L290 TraceCheckUtils]: 15: Hoare triple {1390#true} assume !(0 == ~cond); {1390#true} is VALID [2022-04-28 04:43:56,512 INFO L290 TraceCheckUtils]: 16: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-28 04:43:56,512 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1390#true} {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #61#return; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-28 04:43:56,514 INFO L272 TraceCheckUtils]: 18: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if ~x~0 == ~n~0 * ~n~0 * ~n~0 then 1 else 0)); {1390#true} is VALID [2022-04-28 04:43:56,514 INFO L290 TraceCheckUtils]: 19: Hoare triple {1390#true} ~cond := #in~cond; {1390#true} is VALID [2022-04-28 04:43:56,514 INFO L290 TraceCheckUtils]: 20: Hoare triple {1390#true} assume !(0 == ~cond); {1390#true} is VALID [2022-04-28 04:43:56,515 INFO L290 TraceCheckUtils]: 21: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-28 04:43:56,515 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1390#true} {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #63#return; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-28 04:43:56,516 INFO L272 TraceCheckUtils]: 23: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if 0 == ~y~0 * ~z~0 - 18 * ~x~0 - 12 * ~y~0 + 2 * ~z~0 - 6 then 1 else 0)); {1465#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 04:43:56,517 INFO L290 TraceCheckUtils]: 24: Hoare triple {1465#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1469#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 04:43:56,517 INFO L290 TraceCheckUtils]: 25: Hoare triple {1469#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1391#false} is VALID [2022-04-28 04:43:56,517 INFO L290 TraceCheckUtils]: 26: Hoare triple {1391#false} assume !false; {1391#false} is VALID [2022-04-28 04:43:56,518 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-28 04:43:56,518 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 04:43:56,518 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:43:56,518 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [626266297] [2022-04-28 04:43:56,518 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 04:43:56,518 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119017509] [2022-04-28 04:43:56,518 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [119017509] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:56,518 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:56,518 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 04:43:56,519 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 04:43:56,519 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [394059644] [2022-04-28 04:43:56,519 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [394059644] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 04:43:56,519 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 04:43:56,519 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 04:43:56,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [933257564] [2022-04-28 04:43:56,519 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 04:43:56,520 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-04-28 04:43:56,520 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 04:43:56,520 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, (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-28 04:43:56,539 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:56,539 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 04:43:56,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:56,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 04:43:56,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 04:43:56,540 INFO L87 Difference]: Start difference. First operand 48 states and 64 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, (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-28 04:43:56,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:56,858 INFO L93 Difference]: Finished difference Result 62 states and 79 transitions. [2022-04-28 04:43:56,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 04:43:56,858 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-04-28 04:43:56,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 04:43:56,858 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, (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-28 04:43:56,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 04:43:56,860 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, (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-28 04:43:56,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 04:43:56,861 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-28 04:43:56,929 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:56,930 INFO L225 Difference]: With dead ends: 62 [2022-04-28 04:43:56,931 INFO L226 Difference]: Without dead ends: 50 [2022-04-28 04:43:56,931 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-28 04:43:56,932 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 6 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-28 04:43:56,932 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 130 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 04:43:56,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-28 04:43:56,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-28 04:43:56,956 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 04:43:56,956 INFO L82 GeneralOperation]: Start isEquivalent. First operand 50 states. Second operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-28 04:43:56,957 INFO L74 IsIncluded]: Start isIncluded. First operand 50 states. Second operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-28 04:43:56,958 INFO L87 Difference]: Start difference. First operand 50 states. Second operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-28 04:43:56,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:56,961 INFO L93 Difference]: Finished difference Result 50 states and 62 transitions. [2022-04-28 04:43:56,961 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2022-04-28 04:43:56,961 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:56,962 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:56,962 INFO L74 IsIncluded]: Start isIncluded. First operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 50 states. [2022-04-28 04:43:56,963 INFO L87 Difference]: Start difference. First operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 50 states. [2022-04-28 04:43:56,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 04:43:56,965 INFO L93 Difference]: Finished difference Result 50 states and 62 transitions. [2022-04-28 04:43:56,965 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2022-04-28 04:43:56,966 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 04:43:56,966 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 04:43:56,966 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 04:43:56,966 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 04:43:56,966 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-28 04:43:56,968 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 62 transitions. [2022-04-28 04:43:56,969 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 62 transitions. Word has length 27 [2022-04-28 04:43:56,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 04:43:56,969 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 62 transitions. [2022-04-28 04:43:56,969 INFO L496 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, (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-28 04:43:56,969 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 50 states and 62 transitions. [2022-04-28 04:43:57,043 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 62 edges. 62 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 04:43:57,043 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2022-04-28 04:43:57,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-28 04:43:57,044 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 04:43:57,044 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 04:43:57,070 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-28 04:43:57,259 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:43:57,259 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 04:43:57,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 04:43:57,260 INFO L85 PathProgramCache]: Analyzing trace with hash 1440923632, now seen corresponding path program 1 times [2022-04-28 04:43:57,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 04:43:57,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [60304325] [2022-04-28 04:46:17,684 WARN L232 SmtUtils]: Spent 2.32m on a formula simplification. DAG size of input: 209 DAG size of output: 204 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-04-28 04:46:17,723 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 5 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {1={1=2, 4=1}}, 0 SequentialAcceleration, 1 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-28 04:46:17,730 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-28 04:46:17,737 INFO L85 PathProgramCache]: Analyzing trace with hash 1083327145, now seen corresponding path program 1 times [2022-04-28 04:46:17,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 04:46:17,738 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520594544] [2022-04-28 04:46:17,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:46:17,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 04:46:17,753 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 04:46:17,753 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1308171039] [2022-04-28 04:46:17,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 04:46:17,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:46:17,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 04:46:17,759 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-28 04:46:17,769 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-28 04:46:17,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:46:17,825 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 6 conjunts are in the unsatisfiable core [2022-04-28 04:46:18,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 04:46:18,096 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 04:48:33,310 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 04:48:33,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [520594544] [2022-04-28 04:48:33,311 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 04:48:33,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1308171039] [2022-04-28 04:48:33,311 WARN L319 FreeRefinementEngine]: Global settings require throwing the following exception [2022-04-28 04:48:33,334 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-28 04:48:33,519 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 04:48:33,520 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: Illegal for the call above at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtilsForLocalEliminatees.findSomePushableLocalEliminateeSet(QuantifierPushUtilsForLocalEliminatees.java:177) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtilsForLocalEliminatees.pushLocalEliminateesOverCorrespondingFiniteJunction(QuantifierPushUtilsForLocalEliminatees.java:74) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtils.preprocessDualFiniteJunction(QuantifierPushUtils.java:174) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:330) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:175) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine$ApplicationTermTask.doStep(TermContextTransformationEngine.java:169) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:77) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:61) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:264) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtilsForLocalEliminatees.pushLocalEliminateeSetToDualJunct(QuantifierPushUtilsForLocalEliminatees.java:129) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtilsForLocalEliminatees.pushLocalEliminateesOverCorrespondingFiniteJunction(QuantifierPushUtilsForLocalEliminatees.java:83) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtils.preprocessDualFiniteJunction(QuantifierPushUtils.java:174) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:330) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:175) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:65) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:61) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:264) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:250) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.PartialQuantifierElimination.eliminateLight(PartialQuantifierElimination.java:111) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.PartialQuantifierElimination.eliminateCompat(PartialQuantifierElimination.java:129) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp$LiveVariablesPostprocessorForward.postprocess(TraceCheckSpWp.java:539) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.applyPostprocessors(IterativePredicateTransformer.java:420) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeStrongestPostconditionSequence(IterativePredicateTransformer.java:199) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolantsUsingUnsatCore(TraceCheckSpWp.java:299) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolants(TraceCheckSpWp.java:185) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.(TraceCheckSpWp.java:163) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:108) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:121) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.lib.acceleratedinterpolation.AcceleratedInterpolationCore.runStrategy(AcceleratedInterpolationCore.java:300) at de.uni_freiburg.informatik.ultimate.lib.acceleratedinterpolation.AcceleratedInterpolationCore.acceleratedInterpolationCoreIsCorrect(AcceleratedInterpolationCore.java:289) at de.uni_freiburg.informatik.ultimate.lib.acceleratedinterpolation.AcceleratedInterpolation.(AcceleratedInterpolation.java:195) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleAcceleratedInterpolation.construct(IpTcStrategyModuleAcceleratedInterpolation.java:80) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:121) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:248) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:409) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:300) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:260) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:173) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:152) 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-28 04:48:33,523 INFO L158 Benchmark]: Toolchain (without parser) took 287086.19ms. Allocated memory was 184.5MB in the beginning and 305.1MB in the end (delta: 120.6MB). Free memory was 133.2MB in the beginning and 154.5MB in the end (delta: -21.4MB). Peak memory consumption was 150.7MB. Max. memory is 8.0GB. [2022-04-28 04:48:33,523 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 184.5MB. Free memory is still 149.4MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-28 04:48:33,524 INFO L158 Benchmark]: CACSL2BoogieTranslator took 275.93ms. Allocated memory was 184.5MB in the beginning and 253.8MB in the end (delta: 69.2MB). Free memory was 132.9MB in the beginning and 228.5MB in the end (delta: -95.6MB). Peak memory consumption was 12.3MB. Max. memory is 8.0GB. [2022-04-28 04:48:33,524 INFO L158 Benchmark]: Boogie Preprocessor took 39.24ms. Allocated memory is still 253.8MB. Free memory was 228.5MB in the beginning and 227.1MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-28 04:48:33,524 INFO L158 Benchmark]: RCFGBuilder took 259.64ms. Allocated memory is still 253.8MB. Free memory was 227.1MB in the beginning and 214.9MB in the end (delta: 12.3MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-28 04:48:33,524 INFO L158 Benchmark]: TraceAbstraction took 286506.69ms. Allocated memory was 253.8MB in the beginning and 305.1MB in the end (delta: 51.4MB). Free memory was 214.2MB in the beginning and 154.5MB in the end (delta: 59.7MB). Peak memory consumption was 162.2MB. Max. memory is 8.0GB. [2022-04-28 04:48:33,526 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.11ms. Allocated memory is still 184.5MB. Free memory is still 149.4MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 275.93ms. Allocated memory was 184.5MB in the beginning and 253.8MB in the end (delta: 69.2MB). Free memory was 132.9MB in the beginning and 228.5MB in the end (delta: -95.6MB). Peak memory consumption was 12.3MB. Max. memory is 8.0GB. * Boogie Preprocessor took 39.24ms. Allocated memory is still 253.8MB. Free memory was 228.5MB in the beginning and 227.1MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 259.64ms. Allocated memory is still 253.8MB. Free memory was 227.1MB in the beginning and 214.9MB in the end (delta: 12.3MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 286506.69ms. Allocated memory was 253.8MB in the beginning and 305.1MB in the end (delta: 51.4MB). Free memory was 214.2MB in the beginning and 154.5MB in the end (delta: 59.7MB). Peak memory consumption was 162.2MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: Illegal for the call above de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: Illegal for the call above: de.uni_freiburg.informatik.ultimate.lib.smtlibutils.QuantifierPushUtilsForLocalEliminatees.findSomePushableLocalEliminateeSet(QuantifierPushUtilsForLocalEliminatees.java:177) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2022-04-28 04:48:33,746 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forcibly destroying the process [2022-04-28 04:48:33,776 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 137 Received shutdown request...